Algorithms
Orange@123
EmailingCrsAss-7.pdf
Prof. Pitts CS557A: Algorithms Fall 2019
Assignment 4
Answer the questions below. You may submit scanned or photo'd copies of handwritten submissions, but use the PDF format. You may also submit your answers using Microsoft Word or other electronic word processors, but convert to
PDF format before submission.
1. Consider the red-black tree above. For each of the value below, indicate where in the tree they would be inserted.
Give you answer as: <color><node-value>:Left or <color><node-value>:Right, where <color> is the color of the node to be added, <node-value> is the value in the node under which the value is added, and Left/Right is used to
indicate whether the value is added as a left or right child, respectively. a. 50
b. 192 c. 119
2. Will any of the additions above require a color switch or a rebalance of the red-black tree? Why or why not? 3. For each of the scenarios below of a partial red-black, indicate whethere a color switch or a rebalance is required
and then perform the action. Indicate whether it is possible that a further change is required higher in the tree. a.
1/3
120
180
30 150 210
60
90
60
30
80
20 90
40
50
90
Prof. Pitts CS557A: Algorithms Fall 2019
b.
c.
d.
4. For the input 28, 34, 27, 25, 22, 9, 11, 43, 21 and the hash function h(k) = k mod 9
1. construct the closed hash table 2. determine the maximum number of key comparisons for a successful search in this table
3. determine the average number of key comparisons for a successful search in this table. 5. For the input 28, 34, 27, 25, 22, 9, 11, 43, 21 and the hash function h(k) = k mod 9
1. construct the open hash table 2. determine the maximum number of key comparisons for a successful search in this table
3. determine the average number of key comparisons for a successful search in this table. 6. For the input 32, 6, 43, 35, 18, 28, 47, 21, 40, and the hash function h(k) = k mod 9
2/3
60
80
70
40
60
80
20 70 90
40
50
65
60
80
20 70
40
50
65
Prof. Pitts CS557A: Algorithms Fall 2019
1. construct the open hash table
2. determine the maximum number of key comparisons for a successful search in this table 3. determine the average number of key comparisons for a successful search in this table
7. Solve the coin selection problem for each of the lists of coins below.
a.
0 1 2 3 4 5 6 7 8
C 1 2 4 6 2 2 1 8
F 0
b.
0 1 2 3 4 5 6 7
C 1 3 1 2 3 5 2
F 0
8. Consider the Change-making problem: Give change for an amount n using the minimum number of coins with the
values v1<v2< ... <vm, where v1= 1. Let F(n) be te minimum number of coins required for the amount n. Define
F(0) = 0. F(n) can be defined recursively as F ( n)=min j : n>d j {F (n−d j)}+ 1 for n>0 F (0 )=0
. Use this recursive definition
to write a short bottom up, dynamic programming algorithm for the change-making problem.
3/3
