Algorithms

Prof. Pitts 557A: Algorithms Fall 2019

Study Guide and Practice Problems for the Final Exam The final exam will not be comprehensive. It will cover only material after the midterm. I will not have questions on the exam that deal with text searching algorithms. The material dealing with P, NP, NP-Hard, NP-Complete, problem reductions, etc will not be covered on the exam. See the questions below for examples of questions similar to thoses that may appear on the final exam. As the the midterm exam, the final exam will be closed book and closed note, but you may bring two sheets of paper with prepared notes to use during the final exam.

1. Add this list of values to the open hash table with 17 slots: 52, 85, 3, 21, 49, 34, 15, 20, 48, 11, 89, 78, 2, 33. What is the maximum number of key comparisons for a successful search? What is the average number of key comparisons for a successful search?

1/5

For this hash table, the number of key comparisons for successful searches are:

Value # Key Comps

52 1

85 1

3 1

21 1

49 1

34 2

15 2

20 2

48 1

11 1

89 2

78 1

2 1

33 1

So, the maximum number of key comparisons for a successful search is 2 and the average is 1.3 key comparisons for a successful search.

Prof. Pitts 557A: Algorithms Fall 2019

2. Repeat the previous question using closed hashing and linear probing.

For this hash table, the number of key comparisons for successful searches are:

Value # Key Comps

52 1

85 1

3 1

21 1

49 1

34 3

15 2

20 3

48 1

11 1

89 3

78 1

2 6

33 10

So, the maximum number of key comparisons for a successful search is 10, while the average is 2.5 key comparisons per successful search.

3. How has clustering affected the performance between the open and closed hashing tables? Clustering had a significant effect on the maximum number of key comparison. in the open hash table, 33 required 10 key comparisons while only one was required in the closed hash table.

4. Add the following sequence of values (in this order) to an red/black tree showing all rotations/recolorings: 1, 2, 3, 4, 5, 10, 9, 8, 7, 6.

2/5

Prof. Pitts 557A: Algorithms Fall 2019

5. Add the above numbers to a regular binary search tree.

6. How does the height of the binary search tree in Error: Reference source not found compare with the height of the red/black tree in 4? The height of the tree in Error: Reference source not found is the worst case linear height in the number of nodes, n-1=10-1=9. The height of the red/black tree is 4 which is ⌊ log 2 10 ⌋+1 . Red/black do not always exhibit the minimum height but do keep close to it.

7. Solve the coin selection problem for the following set of coins: 5, 7, 3, 2, 1, 6, 1, 2 0 1 2 3 4 5 6 7

C 5 7 3 2 1 6 1 2

F 0 7 8 9 9 15 15 17

Looking back from F[7], since F[7] and F[6] are different, we use coins 7 and 5. Since F[5] and F[4] are different, we use coin 3. Since F[3] and F[2] are different, we use coin 1. The selection is then, coins 1, 3, 5, and 7 for value 7+2+6+2=17.

3/5

Prof. Pitts 557A: Algorithms Fall 2019

8. Solve the robot coin collector problem for the following board:

1 2 3 4

1 1 1

2 1

3 1 1 1

4 1

1 2 3 4

1 0 1 1 2

2 0 1 1 3

3 1 1 2 4

4 1 2 2 4

From the bottom right, we follow a path straight up to row 1, then to the left to column 1.

9. Consider the undirected graph below. Use Prim's algorithm to find the minimum spanning tree.

10. Repeat the previous problem using Kruskal's algorithm. Kruskal's algorithm requires us to process the edges in order of their weight smallest to largest. That is: (4, 7): 2; (5,8): 2; (2,7): 3; (3,7): 3; (4,5): 3; (2,4): 4; (1, 2): 5; (3,6): 5; (6, 8): 5; (6, 7): 6; (1, 7): 7; (4, 8): 7

4/5

Prof. Pitts 557A: Algorithms Fall 2019

An edges is only added to the spanning tree if it leaves the graph acyclic. 11. Use Dijkstra's shortest path algorithm to find the shortest paths from vertex 1 to the other vertices.

5/5