Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS2413/Fall 2024

Algorithms

Exam 2. Tuesday, Nov. 19, 2024; 12:30-1:50pm.

1. Red-Black Tree Questions

(a) (2 points) Color the nodes of the following binary search tree so that it is red-black tree, and so that the black-height of the root is as large as possible. Show the color of each node by writing R next to every red node and B next to every black node. The NIL nodes are not shown, but remember that they are there.

(b) (2 points) Repeat part (a) with the following tree

(c) Suppose we inserted the keys 1,2,3 into an initially empty red-black tree, in that order.

i. (1 point) Show the tree as it looked after inserting 1,2 (before inserting 3). On your tree, write R next to the red nodes and B next to the black nodes.

ii. (2 points) Show the tree as it looked after inserting 1,2,3? Again, write R next to the red nodes and B next to the black nodes.

2. Sorting using search trees

Recall that an in-order traversal of a Binary Search Tree with n nodes can be used to ”visit” the nodes of the tree in increasing key order, in time ω(n).

(a) (4 points) Consider the following algorithm for sorting an unsorted array A[1 ...n]: Insert the items of A, one at a time, into an initially empty BINARY SEARCH TREE (not a red-black tree). Then perform an in-order traversal of the tree to visit the nodes of the tree in increasing key order, and put the keys back into A in that order.

Which of the following is a correct asymptotic bound on the worst-case running time of this algorithm?

 ω(n)

 ω(n log n)

 ω(n2)

 ω(n2 log n)

 ω(n3)

 ω(n4)

Explain/Justify your answer. No credit without a justification.

(b) (4 points) Consider the same sorting algorithm as in the part (a), but implemented with a red-black tree rather than with a binary search tree.

Which of the following is a correct asymptotic bound on the worst-case running time of this algorithm?

 ω(n)

 ω(n log n)

 ω(n2)

 ω(n2 log n)

 ω(n3)

 ω(n4)

Explain/Justify your answer. No credit without a justification.

3. Hash Tables

(a) (2 points) True or False: In a hash table using open-addressing with linear probing, the load factor of the table can be greater than 1.

 True    False

(b) (2 points) True or False: Double-hashing is to avoid primary clustering.

 True    False

(c) (3 points) Consider a hash table of size m that resolves collisions by chaining. Suppose the hash table is initially empty, you insert m/2 distinct keys into the table, and you then perform 1 unsuccessful search.

Under the assumption of independent uniform hashing, what is the expected running time of that one unsuccessful search (not including the time for the previous insertions)? Give your answer in theta notation.

(c)                                            

(d) (1 point) Consider an empty hash table of size 300, that uses open addressing with linear probing. What is the worst-case total number of probes performed when inserting 3 distinct keys into this table, one at a time? Your answer should be an exact value. Do not use asymptotic notation.

(d)                                            

(e) (3 points) Consider an empty hash table of size m, that uses open addressing with linear probing. As a function of m, what is the worst-case total number of probes performed when inserting m/2 distinct keys into this table, one at a time? Give an exact expression (such as 3m + 4). Do not use asymptotic notation in your answer.

(e)                                            

4. (a) (2 points) Below is the table used by the dynamic programming algorithm (bottom-up implementation) to compute the length of the longest common subsequence of the sequences X =< A, A, B > and Y =< A, A, C >. One entry is missing, the entry in position [2,3]. Fill in the entry AND circle the other entries that were used by the algorithm at the time it computed the value to place in this entry.

(b) (3 points) Here is the table from part (a) again. Fill in the same entry that you did in part (a). Then, circle all entries of the table that would be computed in a top-down implementation of the dynamic program, using memoization, when used to compute the length of the longest subsequence of X =< A, A, B > and Y =< A, A, C >. (For entries in the first row and column, do not circle them unless they would actually be used in the top-down computation.)

To avoid careless errors, you may find it useful not just to circle an entry, but also to add arrows to the other entries needed to compute it (as determined by the recurrence relation). You may include these arrows in the table if you wish.

5. Consider the following problem. You are given a set of n positive integers X = {x1,...,xn}. You are also given a positive integer t. You need to determine whether or not there is a subset of X such that the sum of the elements in that subset is t.

Your task is to design a dynamic programming algorithm that solves this problem in worst-case time ω(nt), with a bottom-up implementation.

Examples: If X = {3, 7, 9, 2, 4} and t = 14, then your algorithm should output Yes, because the sum of the elements in the subset {3, 9, 2} is equal to 14. But for the same X, if t = 8, your algorithm should output No, because no subset of X satisfies the property that its elements sum to 8.

You may assume that the input set X is given as an array of n distinct integers, X[1 : n], where X[i] contains element xi.

Do not give pseudocode for your algorithm. Just answer the questions below.

Hint: Consider subproblems involving prefixes of the array X, including the empty prefix that corresponds to the empty set, and values smaller than t.

(a) (3 points) Describe the table that you would use in your dynamic program. What are the dimensions of the table? What is the meaning of a table entry?

(b) (4 points) Give the recurrence you would use to fill in your table.

(c) (2 points) Once the table is filled in, what value will you return as the final solution to the problem?

6. (a) (2 points) Describe one advantage to using a hash table instead of a red-black tree.

(b) (2 points) Describe one advantage to using a red-black tree instead of a hash table.