Homework Five

Due July 6th at 8:00:00AM

Objectives

Learn about graphs
Practice depth-first search
Practice breadth-first search
Practice state-space search
Learn about variables and how to use them in Scheme

Restrictions
You may not use side effects to solve any of the graph, tree, or state space problems.

Graph Representation
For this assignment we'll be representing graph nodes in this format:

(node-addr (node-data (edge-address ... edge-address)))

A graph will be represented as an association list of nodes. For example, the graph:


   ccb--------physics-------skiles

Can be represented with the following association list:

((101 (ccb (102)))
 (102 (physics (101 103)))
 (103 (skiles (102))))

Remember that the nodes can be in any order and with any address.
Here's another example:

   
       atlantis

Can be represented as:

((386 (atlantis ())))

Notice that when a node has no edges, the list of children is empty, while on the last homework (which was exclusively trees) there would have been two zeros.

One more example:

albany---------------atlanta
 |                     |    \
 |                     |     \
 |                     |      \
trenton------------nashville   \
                                \
                              little-rock

Representation:

((901 (albany (902 903)))
 (902 (atlanta (904 901 905)))
 (903 (trenton (901 904)))
 (904 (nashville (902 903)))
 (905 (little-rock (902))))

As you've hopefully realized already, you can (and should) reuse helper functions from the last homework. You'll probably need at least one more, so let's write that one:

Problem 1
5 points
Write a function called get-adjacencies which will take in an address and a graph and will return the addresses of the nodes adjacent to that node. Example usage:

> (get-adjacencies 902 '((901 (albany (902 903)))
  			 (902 (atlanta (904 901 905)))
		         (903 (trenton (901 904)))
		         (904 (nashville (902 903)))
		         (905 (little-rock (902)))))
(904 901 905)

Problem 2
20 points
Homework four gave you experience with binary trees (trees where each node has no more than two children). There are many other kinds of trees, however. One type of tree is an n-ary tree. An n-anry tree is a tree where each node may have any number of children. For example:


                       GT
                      /  \
    		     /    \
                    /      \
                  west    east
                 /  \        \
                /    \        \
               /      \        \
            sixth   center    area2__
                     / |        | \  \
                    /  |        |  \  \__
                   /   |        |   \    \
               north  south     |    \    \______
                                |     \          \
                              perry  hanson    matheson

Note how a node can have any number of children. We'll represent this tree like this:

head address is 1
((1 (gt (2 3)))
 (2 (west (5 8)))
 (3 (east (13)))
 (5 (sixth ()))
 (8 (center (21 34)))
 (13 (area2 (55 89 144)))
 (21 (north ()))
 (34 (south ()))
 (55 (perry ()))
 (89 (hanson ()))
 (144 (matheson ())))

Remember that those nodes can be in any order. Notice that leaf nodes have null lists where other nodes have lists of their adjacencies (since they have no children).

Write a function named nary-internals which will return a list of the internal nodes in the tree. Your function should take in a head address and the association-list representation (in that order). Remember that any node that is not a leaf node is an internal node. Remember that a leaf node is a node with no children. For example:

> (nary-internals 1 '((1 (gt (2 3)))
  		      (2 (west (5 8)))
		      (3 (east (13)))
		      (5 (sixth ()))
		      (8 (center (21 34)))
		      (13 (area2 (55 89 144)))
	   	      (21 (north ()))
		      (34 (south ()))
		      (55 (perry ()))
		      (89 (hanson ()))
		      (144 (matheson ()))))
(gt west east center area2)

For the next few examples we're going to use the following "map" of campus buildings:


                                Cherry_Emerson
                                     |
                                     |
    MRDC--------Howey_Physics-------CCB
      |           |                  |
      |           |                  |
      |         Mason--------------Pettit
      |           |                  |
    MRDC-2        |                  |
      |        Bunger_Henry--------VanLeer-----Architecture
      |          |                  /           /
      |         /                  /           /
      |        /  /-----------Hightower-------/
      |       /  /
SAC---IC----StuCen------Skiles--------Juniors-------\
                            \             |        Stadium
                             \            |          /
                              \---------Tech_Tower--/

note: not to scale

The representation for this map is a bit large, so let's define a function that takes in no parameters and returns this monster:

(define (campus-map)
  '((101 (SAC (102)))
    (102 (IC (101 103 108)))
    (103 (MRDC-2 (102 104)))
    (104 (MRDC (103 105)))
    (105 (Howey_Physics (104 106 118)))
    (106 (Mason (105 107 117)))
    (107 (Bunger_Henry (108 106 116)))
    (108 (StuCen (102 107 115 109)))
    (109 (Skiles (110 111 108)))
    (110 (Juniors (111 113 109)))
    (111 (Tech_Tower (109 110 113)))
    (113 (Stadium (110 111)))
    (114 (Architecture (115 116)))
    (115 (Hightower (108 116 114)))
    (116 (VanLeer (115 107 117 114)))
    (117 (Pettit (116 118 106)))
    (118 (CoC (105 117 119)))
    (119 (Cherry_Emerson (118)))))

Problem 3
30 points
Write a function called dfs-path that takes in three parameters: a starting address, an ending address, and the graph data structure to be searched. Your function should return a path of the buildings between (and including) the start and end addresses using a depth-first search. For example:

> (dfs-path 101 102 (campus-map))
(sac ic) ; remember that DrScheme will make everything lowercase

> (dfs-path 102 105 (campus-map))
(ic stucen hightower architecture vanleer pettit coc howey_physics)

notice that there are many differnt paths that your function can find. The only requirements are that the path exists and that it has no cycles.

Problem 4
30 points
Now write a function called bfs-path which will take in parameters and return a path like in problem three, but this time you must use a breadth-first search.

> (bfs-path 102 105 (campus-map))
(ic mrdc2 mrdc howey_physics)

> (bfs-path 119 118 (campus-map))
(cherry_emerson coc)

Problem 5
35 points
You've learned (or will soon learn) about state space searching in lecture. Use a state space search to solve this puzzle:

You've got a bunch of numbered tiles in a track, and the track is constructed in such a way that you may reverse the ordering of any four adjacent tiles. For example, let's say the track had tiles arranged like this:

+---+---+---+---+---+---+---+
| 1 | 5 | 4 | 3 | 2 | 6 | 7 |
+---+---+---+---+---+---+---+
      X   X   X   X

then you could "reverse" the ordering of the four tiles above the X's and get:

+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+

We can represent this set of tiles in a simple list:

(1 2 3 4 5 6 7)

Your job is to write a function which will take in a list representation of the tiles in their initial order and a list representation of the tiles in a final order. Your function should return a list of states, beginning with the initial state and ending with the final state, which show how to "solve" the puzzle (ie, convert it one step at a time from the initial state to the final state). Your function should be able to handle any number of tiles. Name your function tile-solver. Your answer should not have any duplicate states. Your function must work for any list of four or more tiles. If you cannot reach the goal state from the starting state then your function should return #f.

> (tile-solver '(1 5 4 3 2 6 7) '(1 2 3 4 5 6 7))
((1 5 4 3 2 6 7)
 (1 2 3 4 5 6 7)  ; this only required one "step"

> (tile-solver '(1 2 3 4 5 6 7 8) '(3 6 7 5 4 2 1 8))
((1 2 3 4 5 6 7 8)
 (1 5 4 3 2 6 7 8)
 (3 4 5 1 2 6 7 8)
 (3 4 5 7 6 2 1 8)
 (3 6 7 5 4 2 1 8)) ; this required several steps

> (tile-solver '(1 2 4 3) '(1 2 3 4))
#f ; can't get there from here

Problem 6
15 points
Rewrite the following function(s) using let and set! to avoid expensive operations. NOTE: you may not have to rewrite EVERY function, just some of them.

(define (factorial n)
  (if (= 0 n)
      1
      (* n (factorial (- n 1)))))

(define (bar y)
  (cond ((> 300 (foo y)) 'cat)
        ((> 6000 (foo y)) 'dog)
        (else 'wombat)))

(define (foo x)
  (cond ((or (< 1024 (factorial x))
              (= 5 (remainder (factorial x) 15))) (factorial (- x 1)))
        (else (quotient (factorial x) (factorial (- x (quotient x 2)))))))

Problem 7
15 points
Explain the difference between global and local variables. Which is preferable most of the time and why? Give an advantage and a disadvantage to using variables over parameters.