CSE1729-SCHEME Introduction to Programming May 4-8, 2020 Final Project
This is a final project which will provide your final exam grade for the course. You may make use of any of the material or solutions for labs and problem sets, including any examples in the course textbook or lecture notes. You may not use any outside materials or results found on the internet. Your submission must be the result of your individual effort. Please read every question carefully before answering and express your answers as completely as you can.
Question:
1
2
3
Total
Points:
20
20
10
50
Score:
Introduction
This course has been focused on building the fundamental skills needed to effectively develop solutions to difficult problems. One of the most valuable tools you will use when working on harder problems is abstraction. Being able to decompose a hard problem into smaller sub-problems, solve the smaller sub-problems and then compose the solutions to the smaller sub-problems into a complete solution is a useful skill. The overall problem given in this project is a topic you will see again in the Algorithms course here at UConn. But, you already have the fundamental skills to solve this problem. Using the tool of abstraction, you can certainly solve the harder problem just by concentrating on each of the sub-problems presented here.
Now, show off your mad skills!
1
Background
Figure 1: A sample minimum length path problem instance.
Finding a Path and the Minimum-Length Path
Given map information (places, direct connections, and distances), use search to find paths between any 2 locations. The ultimate goal is to find the minimum-length path.
Specifically, you will use different versions of search to return the path between any two pairs of locations. You can test your code on the map in Figure 1.
We will need to represent the edge information so that you can find out 1) all edges leading from a location, and 2) the distance on each of those edges. You could use a set of tuples of the form (place1, place2, distance), where these represent a link on the map such as (v, m, 4). You can represent the states in different ways, but your search code should return a list containing the path from source to destination (which is a list) and the cost of that path.
For example, on the above map, the search from E to S should return the path [E, J, M, S].
We will use three types of search: two versions that search blindly (i.e. breadth-first or depth-first) until you have found a non-cyclic path from the start to the destination and another version that uses A∗ search using path cost plus estimated distance to goal as an evaluation function. I used the following (x, y) locations for the places and used straight-line distance as an estimate of distance to goal. These are provided as starter code attached to the assignment.
N (0.2, 1)
P (1.35, 4.25) U (2.15, 0.875) E (3.42, 2.125) J (3.8, 4.575) M (6.7, 3.875) S (6.7, 1.875) V (5.6, 0.1)
2
Search Strategies
We will make use of some well known search strategies without much discussion. You will learn more about these in future classes. This will serve as a brief introduction.
Exploring a graph, such as the graph of cities in this example, can be viewed as traversing a tree structure where the cities that can be traveled to directly are children of a particular city in the tree. In fact, this is the way we will view solving this problem. Surprisingly, we can do this without building an actual tree data structure. The idea is that we will represent cities/locations as nodes in some tree structure and expand a node to get its children in the tree. The different search strategies will be determined by the order in which we choose the next node to expand/explore. Instead of building an actual tree structure (like the binary trees we used this semester) we will store nodes waiting to be expanded/explored in an ADT. The type of ADT will determine the order in which these nodes are removed which therefore determines the order in which nodes are explored in the tree. You are provided with an abstract search function which takes a container (implementation of one of these ADTs) as well as a starting and destination nodes. Just by changing the type of container, we can change the order in which nodes are explored, which changes the search strategy with the very same abstract search function.
When traversing the tree of locations, the nodes waiting to be explored are collectively referred to as the fringe. The search strategy will determine which of the nodes in the fringe will be the next to be explored. Once expanded, all adjacent nodes are added to the fringe. The search starts with the starting location/node as the only node in the fringe.
Uninformed Search
Breadth-First Search The strategy for Breadth-First Search (BFS) is to expand all neighbors of a node before any of its successors. So, we want to expand the shallowest unexpanded node in the tree. In this case, the fringe is a FIFO queue ADT where new nodes go to the end of the queue. The intuition is that we don’t want to venture too deep in the tree if a shorter path to our destination exists. So, we explore all the “closest” locations first before venturing deeper into the tree.
The following sequence shows an example of the order in which nodes are explored using BFS. The red arrow indicates the next node to be expanded. Grey nodes have been already explored. White nodes are nodes that are currently in the fringe waiting to be explored. Green nodes have not been discovered at that stage of the search.
3
So, the full order would be A, B, C, D, E, F, G using a BFS strategy.
Depth-First Search The strategy for Depth-First Search (DFS) is the opposite strategy as BFS. With DFS we expand all successors (children) of a node before any of its neighbors. So, we want to expand the deepest unexpanded node in the tree. In this case, the fringe is a LIFO stack ADT where new nodes go to the top of the stack. The intuition is that we don’t want to waste too much time exploring local nodes if the destination is deep in the tree. So, we explore all the “farthest” locations first before venturing in another direction/branch in the tree.
The following sequence shows an example of the order in which nodes are explored using DFS. The red arrow indicates the next node to be expanded. Grey nodes have been already explored. White nodes are nodes that are currently in the fringe waiting to be explored. Green nodes have not been discovered at that stage of the search.
4
5
So, the full order would be A, B, D, H, I, E, J, K, C, F, L, M, G, N, O using a DFS strategy.
Finding the Minimal Path Uninformed search strategies use no particular knowledge to guide the search. These search strategies will keep expanding nodes until the find a path from the starting location to the desired destination. There is no way to determine if the first path found is the shortest path. To find the shortest path, one would need to continue searching the entire tree to find all paths and then compare them all to find the shortest.
6
Informed Search
Informed search strategies use additional information to guide the search. One informed search strategy, A* (pronounced “A star”), uses a heuristic to determine which node to explore next. If the heuristic function has particular properties, it guarantees an optimal solution. That is, a proper heuristic finds the minimum distance path from the start to destination cities as the first solution found. The heuristic we will use takes the distance traveled so far in the search from start city, through the locations so far, to the current location. It also adds the distance “as the crow flies” from the current location to the location of the destination city (e.g. using the euclidean distance formula). You will notice that the (x, y) coordinates (think GPS coordinates) of the cities in this problem are given. This sum provides an estimate of the total distance from the starting city, to the location that has a node in the fringe, onward to the destination. A* search will choose the node in the fringe with the smallest estimated path distance from source to the destination when selecting the next node to expand. For A*, we can view the fringe as a priority queue ADT.
Tree Search
The general tree search algorithm represents the state of the search with the current node and the path of nodes visited to reach that node. The search function begins with just one node in the fringe which represents the starting state. The search function then continues removing the front node in the fringe. It then checks if this is the solution/goal node. If so, it returns this node. Otherwise, it expands the node and adds all of the resulting nodes to the fringe.
An implementation of this type of search function is supplied in the starter code on Mimir.
7
TL;DR
Your mission, should you choose to accept it, is to build the objects, including ADT objects, which support the abstract search function provided in the starter code on Mimir.
1. ADT Objects
(a) (2 points) Stack Object
In this problem you will define an object that implements the Stack abstract data type using a list to store the elements. When the object is created, it starts as an empty stack.
To implement the stack, the object will initially create an empty list, which it will store the elements of the stack. The stack contents are then maintained with the following convention: to represent the stack containing the elements e1, e2, . . . , en (where e1 is the top of the stack and en is the bottom of the stack) the list will contain the elements as shown in Figure 2, just below. Observe that the bottom element of the stack is always at the end of the list. The top
’(e1 e2 e3 …ek )
Figure 2: Layout of a stack in a list.
element of the stack can be accessed at the front of the list. To place a new element on the top of the stack, one needs only add it to the front of the list. Popping an element off the top of the stack is handled by returning the appropriate element (take particular care to ensure you are returning the proper value when using destructive assignment) and “removing” that element from the front of the list. Your object should expose methods for
empty? Returns a Boolean value (#t or #f) depending on whether the stack is empty. push Pushes a new element onto the top of the stack.
pop Pops off the top element from the stack and returns it.
top Returns the value of the top of the stack (without changing the contents of the stack).
Thus, your object should have the form:
(define (make-stack)
(let (…)
(define (empty?) …)
(define (push x) …)
(define (pop) …)
(define (top) …)
(define (dispatcher method)
;; internal stack variables
;; stack methods
(cond ((eq? method ‘top) top) ((eq? method ‘pop) pop)
((eq? method ‘push) push)
((eq? method ’empty) empty?))) dispatcher))
8
(b) (3 points) Queue Object
Given a complete, efficient implementation of the queue data structure. To be tidy, encapsulate your queue structure in an object. Your data structure should implement
empty? which determines if the queue is empty,
enqueue which adds a new element to the “end” of the queue, and
dequeue which removes (and returns) the element at the “front” of the queue.
Your queue must be efficient in the sense that enqueue and dequeue operations must take a fixed amount of time, independent of the length of the queue. (Hint: Use destructive list operations and variables to keep track of the front and the end of the queue.)
Thus, your object should have the form:
(define (make-queue)
(let ((…)) ;; internal queue variables
(define (empty?) …) ;; queue methods
(define (enqueue x) …)
(define (dequeue) …)
(define (dispatcher method)
(cond ((eq? method ’empty) empty?) ((eq? method ‘enqueue) enqueue) ((eq? method ‘dequeue) dequeue) ((eq? method ‘front) front)))
dispatcher))
9
(c) (8 points) Set Object
Recall the SET abstract data type, which must implement insert, member?, and empty?. Recall that a binary-search tree is a binary tree which satisfies an extra condition: all elements appearing in the left subtree of a given node have values less than the value of the node; likewise, all elements appearing in the right subtree of a node have values that are larger than the value of the node. (You may assume there are no duplicates.) For this problem, you will define a SCHEME object which implements the SET ADT using a binary search tree to store the set elements. Use the tree conventions we adopted in class: a node of a tree is represented as a list containing the numeric value of the node and the two subtrees.
We would like to use this set object for sets of many different types of elements, even objects! Therefore, we will need to generalize or set object to be able to store different types of objects in the binary-search tree. To support this, our insert and member? functions must be generalized to work with different data elements. Their implementations must be supplied with functions to determine if one data element is “less than” another and if one data element is “equal to” another. These functions will be passed to our object creator function make-set as the arguments indicated below.
For our purposes, we will be storing the locations adjacent to a particular city, as well as the distance between the two locations, together to form set elements. We will place locations into the set based on their location name. But, we will need to be able to retrieve the distance to that location later. Therefore, it is not enough to be able to see if a location is in the set or not. We must be able to retrieve the full element to get the distance between the two locations. To support this need, we will add a “get” method to the standard set operations for this object as shown below.
Finally, we include a “list-elements” method which provides a list of all elements in the set, sorted in the order determined by the before? function.
Write an entire SCHEME object (make-set is-equal? before?) which implements the SET ADT using binary search trees. Your object should have the form
(define (make-set is-equal? before?)
(let ((…)) ;; internal variables
(define (empty?) …) ;; ADT methods
(define (member? x) …)
(define (insert x) …)
(define (dispatcher method)
(cond ((eq? method ‘insert) insert)
((eq? method ‘member?) member?)
((eq? method ‘get) get)
((eq? method ‘list-elements) list-elements) ((eq? method ’empty) empty?)))
dispatcher))
10
(d) (7 points) Heap Object A priority queue is a modified queue, such that when one requests the next element off the front of the queue, the highest-priority element is retrieved first (e.g., the tree with the lightest weight in the case of the Huffman encoding problem).
The objective is to construct a heap object which:
1. maintains the priority queue as a heap,
2. uses a generic (first order) order relation,
3. exposes methods empty?, insert, remove, and heap-root.
Thus, the object constructor for the priority queue should take one argument (the order relation), and return a dispatcher yielding 4 methods. Your object should have the form:
(define (make-heap before?)
(let ((…)) ;; internal variables
; Tree helper functions
(define (create-heap value left right)
(list value left right))
(define (heap-root H) (car H))
(define (left T) (cadr T))
(define (right T) (caddr T))
(define (empty?) …) ;; ADT methods
; Heap management functions
(define (combine Ha Hb)
(cond ((null? Ha) Hb) …)
(define (heap-insert x)…)
(define (heap-remove) …)
(define (dispatcher method)
(cond ((eq? method ‘insert) heap-insert)
((eq? method ‘remove) heap-remove) ((eq? method ’empty) empty?)
((eq? method ‘heap-root) heap-root)))
dispatcher))
11
2. Objects
(a) (10 points) Location Object
For search, we will store our location information in an object. Our object creation function, (make-location n x y), accepts three arguments where n is a SCHEME string representing the name of the location, x and y are two numbers representing the (x, y) coordinates of the precise position of the location represented by this object.
get-name Simply returns the name of this location as provided when the object was created. get-position Returns a SCHEME pair representing the position of the location as provided
by the x and y values passed as arguments to the object creation function.
is-equal? Evaluates to #t if the location passed to is-equal is the same as this location. It suffices to compare the names of the two locations using string=? to determine if they are equal.
add-route Initially, a location object will not be connected to any other locations. We will add routes from one location to another using the add-route method. This method takes two arguments, location which is another location object, and distance which represents the travel distance between these two locations. Locations directly accessible from this location are added one at a time through this function and stored in a set object.
get-routes Returns a list of destinations adjacent to this location. That is, it evaluates to a list of all of the (location . distance) pairs stored in the set object associated with this location.
get-distance-to Given a location that is adjacent to this one, get-distance-to evalu- ates to the distance from this location to the given location.
Your object dispatcher should expose the methods shown below. Note the definition of the private methods same-location? and location