Answer all questions and for all questions, show the step using algorithm.
Q1. Running time analysis
(a) Given T(n) = 5T(n/2) + n2. Find out its asymptotic tight bound using the Master Theorem.
(b) Prove the previous asymptotic tight bound using either substitution or induction methods.
Q2. Rod-black tree.
(a) Step-by-step, build a red-black tree with the an ordered input sequence of {20, 5, 11, 10, 29, 5, 21, 4, 15}.
(b) Given the following red-black tree, step-by-step show how to delete the rod node of 21.
Q3. van Embde Boas tree
(a) What is the worst-case run time of the operations on a Van Emde Boas tree? Most time complexity analysis is concerned with the number of elements that are being looked at. How does the time-complexity of a Van Emde Boas tree differ from that norm?
(b) Describe the two functions high(x) and low(x) in the context of a Van Emde Boas tree.
(c) Modify the proto-vEB(16) structure in Figure 20.4 in CLRS textbook to represent the set {2, 3, 4, 5, 7, 13, 14, 15}.
Q4. You are asked to modify the LCS algorithm to identify the heaviest common subsequence (HCS) using a weighted scoring scheme, denoted as matrix M, as shown below.
|
|
A
|
B
|
C
|
D
|
|
A
|
1
|
0.5
|
0
|
0
|
|
B
|
0.5
|
2
|
0
|
0
|
|
C
|
0
|
0
|
1
|
0.5
|
|
D
|
0
|
0
|
0.5
|
1
|
Based on this score scheme, A-A match has a score of 1, B-B match has a score of 2, A-B match has a score of 0.5. For example, given that X = {BACBADCDD} and Y = {BC DABCBDD), the subsequences S1x = {BABA} and S1y = {BABB} has a matching scorn of 2 + 1 + 2 + 0.5 = 5.5, and the subsequence S2 = {CDCDD} has a matching score of 1 + 1 + 1 + 1 + 1 = 5. Hence, the shared sequence of S1x and S1y is heavier (with higher scores) than the perfect match subsequence of S2. (In practice, S1a and S1b are often merged as {BABA/B}. Your task is to design an algorithm to identify the heaviest common subsequence by modifying the LCS algorithm in CLRS textbook.
(a) First, illustrate the application of dynamic programming on heaviest common sub-sequence (HCS) using the example of X and Y sequences given above, by following the example of Figure 15.8 in the CLRS textbook.
(b) Design a HCS algorithm by modifying the LCS-LENGTH(X, Y) in Chapter 15 of the CLRS textbook using a weighted scoring matrix M as shown above. The rows and columns in M are symbols of {A. B, C, D}, and the elements of M are scores such that M[A, A] = 1, M[B, B] = 2, M [A, B] = 0.5, M[A, C] = 0, . .
Q5. Knap-sack problem. Illustrate the application of dynamic programming on the following Knapsack problem with the maximum weight 7 pounds. Please note that chargers and their served devices should always be taken together.
|
Item
|
Value (dollars)
|
Weight (pounds)
|
|
Cell phone
|
100
|
1
|
|
Charger for cell phone
|
30
|
1
|
|
Laptop
|
300
|
3
|
|
Charger for laptop
|
70
|
1
|
|
Tent
|
250
|
4
|
|
Medicine
|
200
|
1
|
|
Instant food
|
80
|
2
|
|
Water bottle
|
10
|
1
|
|
Umbrella
|
20
|
1
|
|
Flashlight
|
35
|
1
|
Q6. Computational geometry: A generic point representation is P = (X, Y). Given that P0 = (0, 0); P1 = (4, 3); P2 = (1, 0), P3 = (3, 4), calculate the cross product (P0P1)→x(P2P3)→. Are (P2P3)→ clockwise or counterclockwise to (P0P1)→ with respect to their cross point? Your explanation should be justified by the cross-product.