Use these problems to get an idea about the format for the actual exam and the level of difficulty of the exam questions. The actual exam may or may not have problems that look like these problems, but the amount and difficulty of the problems will be similar. Note that there are additional topics in the course material that you should study that are not included in the problems below.
1. Consider the following lists define in a functional language like Scheme:
(define alice (list 'Pittsburgh 22 'Walk)) (define bob (list 'Monroeville 35 'Bus)) (define carol (list 'Robinson 40 'Car)) (define dan (list 'Cranberry 38 'Car)) (define ethel (list 'Etna 61 'Bus)) (define fred (list 'SquirrelHill 56 'Bike))
Each list contains a person's hometown, age and means of commuting to work.
(a) Using Scheme, how would you display Ethel's means of commuting?(b) Consider the following Scheme function mysteryfunction that requires one parameter, a list named people:
(define (mysteryfunction people) (if (null? people) 0 (+ 1 (mysteryfunction (rest people))) ) )What does the function (null? people) mean?
(c) What is the output for the Scheme instruction below using the list definitions above and the function mysteryfunction from part (b)? Show your work.
(mysteryfunction (list alice bob carol dan ethel fred))(d) Is the mystery function in part (b) recursive? Why or why not?
2. The following recursive function computes the number of ways to form combinations of N things taken R at a time:
C(N,R) = 1 if R = N C(N,R) = N if R = 1 C(N,R) = C(N-1,R) + C(N-1,R-1) if 1 < R < N
(a) Draw the recursive tree that shows all the computational steps required to run this algorithm for N = 4 and R = 2.(b) Using your tree, what is the value of C(4,2)? (Verify your answer by taking the four letters A,B,C,D and writing all combinations of 2 letters from this set of four.)
(c) Would dynamic programming help reduce the number of recursive steps in this computation in general? Explain.
3. A Huffman tree is derived for an alphabet of {A,B,C,D,E} as follows:
w
/ \
x E
/ \
A y
/ \
B z
/ \
C D
Each left branch is encoded with a 0 and each right branch is encoded with a 1.
(a) Decode the following message using the Huffman tree above: 101010111100011010011010.(b) If we encoded this alphabet using a minimal fixed-length encoding scheme, how many bits would we use to encode each letter? Why?
(c) Complete the EBNF rules below for any valid message derived from the Huffman tree above.
message --> ___________________________________ (one or more letters) letter --> ___________________________________ (binary pattern for A or binary pattern for B or etc.)
4. The following matrix represents a weighted directed graph with 6 nodes labeled U, V, W, X, Y, Z.
U V W X Y Z U 0 7 4 0 0 0 V 0 0 0 6 5 0 W 0 0 0 8 3 0 X 0 0 0 0 0 2 Y 0 0 0 0 0 9 Z 0 0 0 0 0 0
(a) Draw a picture of the graph represented by the matrix above.(b) Using Dijkstra's shortest path algorithm, we wish to find the shortest path from U to each node. Compute the values for SP (Shortest Path) and Pr (Predecessor) for each node except U. (NOTE: If you know how this algorithm works, you don't have to do the entire trace. You should be able to deduce what the final results will be based on the graph.)
(c) Consider a greedy algorithm that builds a path to node Z by starting at node U and taking the lowest cost edge to another node. From that node, we take the lowest cost edge again. We repeat this until we reach node Z. Explain using this graph why this greedy approach does not yield the shortest path from U to Z.
5. The following algorithm is designed to compute x * y through repeated addition, assuming x > 0 and y > 0.
1. Set result = x
2. Set i = 1
3. While i ≠ y do the following:
(a) Add 1 to i
(b) Add x to result
4. Output result
The invariant for this loop is "result = x * i". Show that this algorithm is correct by giving logical explanations for the following steps.
(a) Show that the invariant must be true immediately before the loop begins.(b) Show that if the invariant is true at the beginning of each iteration of the loop, it must be true at the end of each iteration as well.
(c) Show that if the loop exits, the output value must be x * y.
(d) Explain briefly why the loop must exit.