2021/7/26 Submit Exam3 | Gradescope
https://www.gradescope.com/courses/270292/assignments/1389479/submissions/new 1/5
0/6 Questions Answered
TIME REMAINING
� hr �� mins
Exam3
Q1 Potential method
15 Points
a) Suppose that you use the Potential Method to analyze a particular algorithm
that performs operations, and conclude that the amortized time per
operation is Then you calculate that , and .
What upper bound do you report for the time complexity of the entire
algorithm?
Enter your answer here
b) You then notice that you made a little mistake writing things down, so in fact
, and .
Does this change anything?
Enter your answer here
c) Oops, you realize that in fact you miscalculated, so , and
.
Does this change anything?
Enter your answer here
n
log n. Φ =0 n Φ =n n log n2
Φ =0 n log n2 Φ =n n
Φ =0 n log n
Φ =n n
2021/7/26 Submit Exam3 | Gradescope
https://www.gradescope.com/courses/270292/assignments/1389479/submissions/new 2/5
Q2 Practice problem 1 (array doubling)
20 Points
a) For practice problem 1, we ended up with a potential function,
Suppose that we downsize an array of size . What is the precise potential
before and after downsizing, using this function?
Enter your answer here
b) Use a formula to calculate the precise amortized cost of downsizing, using
this function.
Enter your answer here
c) Do you notice anything slightly unusual in (b)?
Does this cause any problems? Is there anything that needs to be addressed?
Enter your answer here
Q3 LCS with 4 input strings
20 Points
Suppose that you are given 4 strings, A,B,C,D, each containing characters.
Let L be a subsequence of maximum length that is common to all 4 strings.
a) Write a recursive function that would return the length of L.
Φ =i 2i − ∣ ∣2
Size i
k
n
2021/7/26 Submit Exam3 | Gradescope
https://www.gradescope.com/courses/270292/assignments/1389479/submissions/new 3/5
Enter your answer here
b) Briefly describe what your function does, in English.
This should probably not require more than 2-3 sentences.
Enter your answer here
c) If you were to use dynamic programming to find L (or another longest
common subsequence), what table size would you use? How do you
determine this?
Enter your answer here
d) State the maximum time complexity of filling in a cell in the table.
Enter your answer here
e) State the time complexity of solving this problem with dynamic
programming.
Enter your answer here
f) State how much space would you use if you only need to find the length of L.
If you’re having trouble with this, answer (f) assuming there are only 3 strings,
and include a brief description of the logic.
Enter your answer here
Q4 Practice problem 4 (LPS)
2021/7/26 Submit Exam3 | Gradescope
https://www.gradescope.com/courses/270292/assignments/1389479/submissions/new 4/5
15 Points
Give a proof of correctness for the recurrence in practice problem 4 (shown
below).
The description style should have some similarity to the proof for LCS.
Don’t just translate math into English. You need to address the logic.
If T[i] = T [j] LPS[i,j] = 2 + LPS[i+1, j−1]
Else LPS[i,j] = max{ LPS[i+1, j] , LPS[i, j−1] }
Part of the credit will depend on the clarity of your answer. For full marks it
should be very easy to read.
Enter your answer here
Q5 Topological sort
15 Points
Suppose that we run DFS on a directed graph, for the purpose of topological
sort. We obtain a single DFS tree. In this tree, there exist two particular vertices,
and , such that neither is an ancestor (or descendant) of the other.
How do we determine that and are in correct topologically sorted order?
Part of the credit will depend on the clarity of your answer. For full marks it
should be very easy to read.
Enter your answer here
Q6 Practice problem 8 (universal sink)
15 Points
b c
b c
2021/7/26 Submit Exam3 | Gradescope
https://www.gradescope.com/courses/270292/assignments/1389479/submissions/new 5/5
What happens in practice problem 8 if the input is given as an adjacency list?
Can you get the same time complexity, or better? Or does it get worse?
Enter your answer here
Submit & View Submission
https://www.gradescope.com/courses/270292/assignments/1389479/submissions/84298638