CS570 Spring 2021: Analysis of Algorithms
Practice Exam I
Instructions:
1. This is a 2-hr and 20-mins exam. Closed book and notes
2. Any kind of cheating will lead to score 0 for the entire exam and be reported to SJACS.
3. If a description to an algorithm or a proof is required please limit your description or proof to
within 150 words, preferably not exceeding the space allotted for that question.
4. If you require an additional page for a question, you can use the extra page provided within
this booklet. However please indicate clearly that you are continuing the solution on the
additional page.
5. Do not detach any sheets from the booklet. Detached sheets will not be scanned.
6. If using a pencil to write the answers, make sure you apply enough pressure, so your answers
are readable in the scanned copy of your exam.
7. Do not write your answers in cursive scripts.
1) 20 pts
Mark the following statements as TRUE or FALSE. No need to provide any justification.
[TRUE/FALSE]
The shortest path between two points in a graph could change if the weight of each edge is increased by an identical number.
[TRUE/FALSE]
In a dynamic programming formulation, the sub-problems must be mutually independent.
[TRUE/FALSE]
Function 𝑓(𝑛) = 5𝑛24𝑛 + 6𝑛43𝑛 is 𝑂(𝑛43𝑛).
[TRUE/FALSE]
The smallest element in a binary max-heap of size n can be found with at most n/2 comparisons.
[TRUE/FALSE]
In dynamic programming, you must calculate the optimal value of a sub-problem twice, once during the bottom up pass and once during the top down pass.
[TRUE/FALSE]
Suppose we are given an array A of n distinct elements, and we want to find n/2 elements in the array whose median is also the median of A. Any algorithm that does this must take Ω(n log n) time.
[TRUE/FALSE]
In a simple, undirected, connected, weighted graph with at least three vertices and unique edge weights, the heaviest edge in the graph is in no minimum spanning tree.
[TRUE/FALSE]
In a divide & conquer algorithm, the size of each sub-problem must be at most half the size of the original problem.
[TRUE/FALSE]
Amortized cost of operations in a Fibonacci heap is at least as good as the worst case cost of those same operations in a binomial heap.
[TRUE/FALSE]
The Master theorem can always be used to find the complexity of T(n), if it can be
written as a recurrence relation T(n) = aT(𝑛 ) + f(n). 𝑏
2)
14 pts
Arrange the following functions in increasing order of growth rate with g(n) following
f(n) in your list if and only if f (n) = O(g(n)):
1𝑛
𝑛√𝑛, (log𝑛)𝑛, 𝑛(log𝑛)2, 𝑛log𝑛 , 2𝑛2, ∑(𝑖+1)2, log(𝑛!)
𝑖=1
3)
12 pts.
Suppose that we have an undirected graph G = (V, E). Prove the following statements. a) If 𝐺 = 𝐾5, then 𝐺 is not a planar graph. (3 pts)
b) If 𝐺 is a simple planar graph with 𝑉 < 12, then 𝐺 has a vertex of degree 4 or less. (9 pts)
4) 12 pts.
Jared owns all 𝑁 stores along with a straight avenue of length 𝐿 miles. He knows that for
his i-th store, which is located at 𝑥𝑖 miles from the start point of the avenue, can attract all
residents whose house is no more than 𝑟 miles from that store. That is, if one’s house 𝑖
distance from the start point of the avenue is within [𝑥 − 𝑟 , 𝑥 + 𝑟 ], then he/she will be 𝑖𝑖𝑖𝑖
attracted to Jared’s i-th store. Jared is very proud that no matter where the resident lives in this avenue, he/she will be attracted by at least one of Jared’s stores now. Unfortunately, Jared is short of cash now. He will close some of his stores, but he still wants all the residents in this avenue, no matter where they live, to be attracted by at least one of his stores.
a) Design a greedy algorithm to help Jared to find the minimum stores he can keep but his requirement is still fulfilled. (7 pts)
b) Compute the runtime complexity of your algorithm in terms of 𝑁. Explain your answer by analyzing the runtime complexity of each step in the algorithm description. (4 pts)
c) Prove the correctness (feasibility and optimality) of your greedy algorithm. (6 pts)
5) 10 pts.
For each of the following recurrences, give an expression in the Theta notation for the runtime T(n) if the recurrence can be solved with the Master Theorem. Otherwise, indicate that the Master Theorem does not apply.
1. 𝑇(𝑛) = 3𝑇 (𝑛) + 𝑛 32
2. 𝑇(𝑛) = 2𝑇 (𝑛) + 𝑛 2 log𝑛
3. 𝑇(𝑛) = 16𝑇 (𝑛) + 𝑛! 4
4. 𝑇(𝑛) = 2𝑇 (𝑛) + 𝑛0.51 4
5. 𝑇(𝑛) = 2𝑛𝑇 (𝑛) + 𝑛𝑛 2
T(n) =
T(n) =
T(n) =
T(n) =
T(n) =
6) 15 pts
T is a spanning tree on an undirected graph G = (V, E). Edge costs in G are NOT guaranteed to be unique. Prove or disprove the following: If every edge in T belongs to SOME minimum cost spanning trees in G, then T is itself a minimum cost spanning tree.
7) 17 pts
Kara is the owner of a fried chicken restaurant called Kara’s Fried Chicken. One night, she receives a request for providing lunch for a conference at USC on the next day. The coordinator of the conference has collected lots of orders, but Kara’s restaurant is too small to support all of the orders. She has to decide to forfeit some orders, but she wants to earn as much as she can. Here is the information she has now.
- There are 𝑁 orders from the conference. For the 𝑖th order, Kara knows it will take 𝑡𝑖 minutes to prepare and will need 𝑘𝑖 pounds of chicken.
- The coordinator will pay 𝑐𝑖 dollars if Kara can deliver the 𝑖th order. If Kara cannot deliver that order, she could cancel now without paying any cost.
- Kara has only 𝑇 minutes and 𝐾 pounds of chicken for the lunch of the conference in the next morning.
- 𝑇, 𝐾, 𝑁, and 𝑐𝑖, 𝑡𝑖, 𝑘𝑖 for all 𝑖 are positive integers for simplicity.
Now, Kara has to respond to the coordinator of the conference with which orders she could
deliver. Please give an algorithm using dynamic programming to help Kara.
a) Define (in plain English) subproblems to be solved. (3 pts)
b) Write the recurrence relation for subproblems. (5 pts)
c) Give the pseudocode for the DP algorithm using tabulation. (6 pts)
d) Compute the runtime of the above DP algorithm in terms of 𝑁, 𝑇, 𝐾. (3 pts)