Question 1
December 6, 2020
You are given two sorted arrays A[1..n + 1], of size n + 1, and B[1..n], of size n. Each array has distinct elements. Find an index i, 1 ≤ i ≤ n + 1, such that the element A[i] is not present in array B. Note: there may be more than one such element; you need to output just one of them: i.e., B is not necessarily a subset of A.
• (5 points) Write pseudocode for an O(log n) algorithm which solves this problem.
def find(A, leftA, rightA, B, leftB, rightB): # one element array
if (leftA == rightA): return A[ leftA ]
# two element array
else if (rightA − leftA == 1): if (B[leftB] ==A[leftA]):
return A[rightA] else :
return A[ leftA ]
else :
midA = (leftA + rightA) / 2 midBLeft = midA − leftA + leftB − 1 midBRight = midBLeft + 1
if (B[midBLeft] >= A[midA]):
return find(A, leftA , midA − 1, B, leftB , midBLeft − 1)
else if (B[midBRight] <= A[midA]):
return find(A, midA+1, rightA , B, midBRight + 1, rightB)
else :
return A[midA]
find(A, 1, n+1, B, 1, n)
• (1 point) Analyze the running time of your algorithm in terms of n.
Running time of this algorithm is the same as regular binary search which running time is O(logn). We find mid point of array A then reduce the problem to a single smaller subproblem, either to work on left subset of array A and the left subset of array B or to work on the right subset of array A and the right subset of array B. The recursion tree has no branching, it only makes one recursive call. The height of recursion tree is at most log2 n and other steps take constant time. So the runnign time is O(logn).
Question 2
You are planning a hike. You are given a list of elevations E[1..n] at n points along your route. You would like to know the greatest decrease in elevation from an earlier point to a later point along your hike, i.e., maxi
result = maximumE − E[ i ] if (E[i]>maximumE):
maximumE = E [ i ] ; return result
• (1 points) Analyze the running time of your algorithm in terms of n.
This algorithm only iterates through the whole array with two O(1) checks for each value, so the running time
is O(n). Question 3
You are given a string S[1..n] and a pattern of characters P[1..k], where k ≤ n. You need to count the number of anagrams of P in S. An anagram is a string formed by rearranging the letters of a different string, using all the original letters exactly once.
• (3 points) Write pseudocode for your algorithm. Your algorithm should run in O(n + k) expected time.
def countAnagrams(S, n, P, k): # normalize P
PCharacterMap = empty hashmap PCharacterCount = 0
for i = 1 to k:
cnt = PCharacterMap . get (P[ i ] ) ; if cnt == 0:
PCharacterCount++ PCharacterMap [P[ i ] ] = cnt + 1
ans = 0;
# first k in S
SCharacterMap = empty hashmap SCharacterMatchCount = 0
for i = 1 to k:
i f
SCharacterMap[S[ i ]] = SCharacterMap[S[ i ]] + 1
if (SCharacterMap[S[ i ]] == PCharacterMap[S[ i ]]):
SCharacterMatchCount++
else if (SCharacterMap[S[ i ]] == PCharacterMap[S[ i ]] + 1):
SCharacterMatchCount−−
( SCharacterMatchCount == PCharacterCount ) :
ans++
# Go through the rest of S for i = k+1 to n:
# Add new character
SCharacterMap[S[ i ]] = SCharacterMap[S[ i ]] + 1;
if (SCharacterMap[S[ i ]] == PCharacterMap[S[ i ]]): SCharacterMatchCount++
else if (SCharacterMap[S[ i ]] == PCharacterMap[S[ i ]] + 1): SCharacterMatchCount−−
# Remove old character
SCharacterMap[S[i−k]] = SCharacterMap[S[i−k]] − 1
if (SCharacterMap[S[i−k]] == PCharacterMap[S[i−k]]): SCharacterMatchCount++
else if (SCharacterMap[S[i−k]] == PCharacterMap[S[i−k]] − 1): SCharacterMatchCount−−
2
i f ( SCharacterMatchCount == PCharacterCount ) : ans++
# result return ans
• (2 points) Modify your algorithm to output all occurrences of P in S, i.e., every pair of indices (i, j) such that S[i..j] = P .
def countAnagrams(S, n, P, k): # normalize P
PCharacterMap = empty hashmap PCharacterCount = 0
for i = 1 to k:
cnt = PCharacterMap . get (P[ i ] ) ; if cnt == 0:
PCharacterCount++ PCharacterMap [P[ i ] ] = cnt + 1
ans = empty list # first k in S
SCharacterMap = empty hashmap SCharacterMatchCount = 0
for i = 1 to k:
i f
SCharacterMap[S[ i ]] = SCharacterMap[S[ i ]] + 1
if (SCharacterMap[S[ i ]] == PCharacterMap[S[ i ]]):
SCharacterMatchCount++
else if (SCharacterMap[S[ i ]] == PCharacterMap[S[ i ]] + 1):
SCharacterMatchCount−−
( SCharacterMatchCount == PCharacterCount ) :
ans . add (1)
# Go through the rest of S for i = k+1 to n:
# Add new character
SCharacterMap[S[ i ]] = SCharacterMap[S[ i ]] + 1;
if (SCharacterMap[S[ i ]] == PCharacterMap[S[ i ]]): SCharacterMatchCount++
else if (SCharacterMap[S[ i ]] == PCharacterMap[S[ i ]] + 1): SCharacterMatchCount−−
# Remove old character
SCharacterMap[S[i−k]] = SCharacterMap[S[i−k]] − 1
if (SCharacterMap[S[i−k]] == PCharacterMap[S[i−k]]): SCharacterMatchCount++
else if (SCharacterMap[S[i−k]] == PCharacterMap[S[i−k]] − 1): SCharacterMatchCount−−
i f ( SCharacterMatchCount == PCharacterCount ) : a n s . a d d ( i −k + 1 )
# result
for i = 1 to ans.size():
return (i, i+k−1)
• (1 point) Suppose that S contains m anagrams of P. What is the running time of the second algorithm in terms of n and m?
3
Clearly we go through P, S, ans all for once with O(1) operations, the running time is O(n + k + m), as k ≤ n, it is 2n+m which is O(n+m).
Theoretically, m ≤ n as well, so the running time is O(n).
4
Question 4
Given an array A[1..n] of real numbers and an integer M ≥ 0, you want to compute the largest sum of a contiguous subarray of A such that the sum is less than or equal to M.
• (2 points) Write pseudocode for an O(n2) algorithm which solves this problem.
def calculate(A, n, M): PrefixSum = empty l i s t
# for subarray from the first element PrefixSum . add ( 0 )
for i = 1 to n:
prefixSum.add(prefixSum[i−1] + A[i]) ans = none
for i = 1 to n:
for j = 0 to i−1:
if (prefixSum[i] − prefixSum[j] <=M
&& (ans == none || prefixSum[i] − prefixSum[j] > ans)):
ans = prefixSum[i] − prefixSum[j]
• (2 points) Say you have access to a balanced tree data structure D which has the following two functions each
running in log(|D|) time:
– Insert(D, x) – Insert x in D
– Search(D,k) – Returns an element y from D such that y is the smallest element greater than k
Write pseudocode for an O(n log(n)) algorithm for our problem using this data structure.
def calculate(A, n, M): PrefixSum = 0
PrefixTree = new D() Insert(PrefixTree , 0) ans = none
for i = 1 to n:
prefixSum += A[ i ]
sub = Search ( PrefixTree , prefixSum − M)
if (sub != none && (ans == none || ans < prefixSum − sub)): ans = prefixSum − sub
Insert(PrefixTree , prefixSum) return ans
• (2 points) Describe a faster algorithm for the above problem given the additional constraint that every number in A is nonnegative. Analyze the running time of your algorithm.
If A is nonnegative, for increasing j, the maximum valid pair(i, j), i must be non decrease. So we can just maintain a pointer to i.
def calculate(A, n, M): PrefixSum = empty l i s t
# for subarray from the first element PrefixSum . add ( 0 )
ans = none
p=0
for i = 1 to n:
newPrefix = prefixSum[i−1] +A[i];
while (p < i && newPrefix − prefixSum [p] > M):
++p
if (ans == none || ans < newPrefix − prefixSum[p]):
ans = newPrefix − prefixSum[p] 5
return ans
prefixSum.add(prefixSum[i−1] + A[i]) return ans
Here we only iterate through A once with O(n). At the same time, the pointer p only iterate through the prefixSum list once with O(n). So in total, the running time is O(n).
Question 5
Design a data structure D that stores a set S of n numbers and performs each of the following operations in O(log n) time. If you use a BST, assume that it is balanced, i.e., the height of the tree is O(log n).
• (2 points) Describe your data structure. If it is a variation on a data structure we learned in class, explain any modification(s) clearly and in detail.
We can have a balanced tree and for each node, besides its value we store extra information: minVal, maxVal, minimumDifference for the minimum value, maxinum value, and minimumDifference between two continuos value in the subtree of this node.
We need to maintain this with O(logn) along the path from root for insert/delete a leaf node.
• (3 points) Write O(log n) time algorithms for each of the following operations:
◦ Insert(D,x) – Insert the number x in S if it is not already present.
◦ Delete(D, x) – Delete the number x from S if it is already present.
◦ ClosestPair(S) – Find the smallest absolute difference of any two elements in S. For example, if S = {34, 21, 2, 7, 12} then ClosestP air(S) = |7 − 2| = 5. Note that multiple pairs might achieve the least value; here even |12 − 7| = 5. You only need to output 5 and not the pair.
Question 6
Given a binary tree T (not necessarily a BST) and a function value : T → Z that looks up a value attribute associated with each node v ∈ T in O(1) time, your task is to find the length of the longest increasing path in T .
In the example below the longest increasing path is shown in red with length 5. 8
72
6 12 40 17
4 9 13 11 23 15 10 1 Solve this problem using dynamic programming.
• (2 points) Clearly define a subproblem, and state the dimension(s) of your DP array/table. For each node we need:
ans[node]: The longest increasing path in the subtree of a node.
inc[node]: The longest increasing path which ends at the node in the subtree of a node. dec[node]: The longest decreasing path which ends at the node in the subtree of a node.
To find the longest length of increasing path in tree T, we find the longest length of increasing path in left tree T.left, the longest length of increasing path in right tree T.right, and the longest increasing path which ends at node T.root + the longest decreasing path which ends at node T.root. Whichever of the three is longer will be the answer.
The dp table size is 3*n.
6
• (2 point) Give a recurrence for the solution of a subproblem in terms of smaller subproblems.
base case: The leaf node, inc[leaf] = dec[leaf] = ans[leaf] = 1
inc[node] = max(1, max(1 + inc[child])), here child is every child of node where value[child] < value[node]. dec[node] = max(1, max(1 + dec[child])), here child is every child of node where value[child] > value[node]. ans[node] = max(max(ans[child]), max(inc[node] + dec[node] – 1)
• (2 points) Write pseudocode for an O(n) algorithm which computes the length of the longest increasing path in T . Analyze the running time of your algorithm and its space requirements.
def
calculate(root):
if root.LeftChild == none:
leftTriple = (0, 0, 0) else :
leftTriple = calculate(root.LeftChild)
i f root . RightChild == none : rightTriple = (0, 0, 0)
else :
rightTriple = calculate(root.RightChild)
li = none
i f root . LeftChild == none | | root . LeftChild . value >= root . value :
li=0 else :
li = leftTriple.inc
ri = none
i f root . RightChild == none | | root . RightChild . Value >= root . value :
ri=0 else :
ri= rightTriple . inc
inc=max(li, ri)+1
ld = none
i f root . LeftChild == none | | root . LeftChild . value <= root . value :
ld = 0 else :
ld = leftTriple.dec
rd = none
i f root . RightChild == none | | root . RightChild . Value <= root . value :
rd = 0 else :
rd= rightTriple . dec
dec=max(ld, rd)+1
ans = max(leftTriple.ans, rightTriple.ans, inc + dec − 1) return (inc , dec , ans)
Time
We DFS among the tree with O(1) operation on each node ,
so the running time is O(n). Space complexity :
complexity :
7
As each node has only one parent, each sub problem is calculate only once, so the space compexity should be the depth of the tree , which is O(logn ).
8