CSCI570_Fall2023

1.5em CSCI-570 Fall 2023 Midterm 1 INSTRUCTIONS • The duration of the exam is 140 minutes, closed book and notes. • No space other than the pages on the exam booklet will be scanned for grading! • If you require an additional page for a question, you can use the extra page provided at the end of this booklet. However please indicate clearly that you are continuing the solution on the additional page.

1. True/False Questions (20 points) Mark the following statements as T or F . No need to provide any justification. a) (T/F) . Prim’s algorithm can be applied to directed weighted graphs. False. b) (T/F) . Let T ( n ) = 3 T ( n 3 ) + O (log n ) be a recurrence equation. Then we can conclude that T ( n ) = Θ( n log n ) by the Master theorem. False. Case 1 of the master theorem: a = 3 , b = 3 c) (T/F) In a dynamic programming formulation, the sub-problems must be mutually independent. False d) (T/F) The main difference between divide and conquer and dy- namic programming is that divide and conquer solves problems in a top-down manner whereas dynamic-programming does this bottom-up. False e) (T/F) There are no known polynomial-time algorithms to solve the 0-1 knapsack problem. True. f) (T/F) If the edge is not part of any MST of G , then it must be the maximum weight edge on some cycle in G . True. g) (T/F) A greedy algorithm can be used to solve any problems that are solved by the dynamic programming. False. h) (T/F) If f = O ( n ) and g = O ( n ), then f ( g ( n )) = Θ( n 2 ). False. Counterexample: f= g = const. i) (T/F) There is a path from any vertex to any other vertex in a connected directed graph. False. That is true for undirected graphs. j) (T/F) Insertion into a binomial heap of size n has an amortized cost of Θ(log n ) False. That is Θ(1).

d) Analyze the runtime complexity of printing in the following code snippet. while(n > 0){ for(int i = 0; i<n; i++){ System.out.println("#"); } n = n/2; } a) Θ(log n ) b) Θ( n ) c) Θ( n 2 ) d) Θ( n log n ) b. Starting from n , the inner for loop runs n times. Second time, it runs n/ 2 times, and then n/ 4 times and so on. n + n/ 2 + n/ 4 + ... + 2 + 1 = 2 n − 1 = O ( n ) e) Which of the following is not a characteristic of a binomial heap? a) Each tree in the heap has a unique rank. b) The root of each tree in the heap has the same value. c) The number of elements in each tree is a power of 2. d) The amortized cost of insertion is constant. b

3. Amortized Cost Analysis (10 points) Recall the example of an unbounded (dynamic) array from lecture with a ”doubling-up resizing policy,” where we showed that the amortized cost per insert operation is a constant. Now we also want to imple- ment a resizing policy for the delete operation. Consider the following options: a) When the array is a half-full after delete, we create a new array of half the size and copy all the elements. Identify a sequence of operations where this approach would not result in a constant amortized cost per insert or delete operation. (5 pts)

Rubrics 3a (5 points): • (upto 3 pt) Correct Description of the working scenario • (upto 2 pts) The description of the scenario is self-explanatory to establish that the cost would not be constant OR Correct calculation of T(n) and showing that T(n)/n = O(n) OR Correct explanation ”in words” that the cost is not constant OR Correct mathematical argument proving that cost would not be constant. • (-2 pts) If the description is very vague, but close to correct solution. Rubrics 3b (5 points): • (upto 3 pts) Correct calculation of T(n). Simply stating T(n) = O(n) without any concrete reasoning or mathematical expression gets 0 points. • (upto 2 pts) Showing that T(n)/n = O(1). Simply stating that T(n)/n = O(n)/n = O(1) gets 0 points. The reasoning should be explained with sequence of operations, and correct T(n) expression. • (-2 pts) If using scenario (sequence of operation) other than 3a and description is vague. Note: If description is clear than no points deduction.

4. Short Problem (10 points) Given a n × n matrix where each of the rows and columns are sorted in ascending order. Design an algorithm to find the k -th smallest element in the matrix using a binary heap. Discuss its runtime complexity. You may assume that k < n . Build a min heap containing the first element of each row using O ( n ) time and then run deleteMin. If the element from the i -th row was deleted, then insert another remaining element in the same row to the min heap. Repeat the procedure k times. The total running time is O ( n + k log n ). As we have k < n , actually we only need the first k × k part of the matrix. Thus the time complexity can be further improved to O ( k + k log k ) = O ( k log k ). Both answers are considered as correct. (4 pts) Build the min-heap (not a max-heap). Run deleteMin or remove the min element each time. (2 pts) Min-heap include the first element of each row. (1 pts) Insert the remaining element from the same row and repeat for k times. (3 pts) O ( n + k log n ) or O ( k log k ) is the final time complexity.

b) (10 points) Design a greedy algorithm that finds the maximum distance in O ( n ) time complexity. a) Suppose none of the equalities holds. We then have 0 < i, j < n − 1. We consider three cases: • A [0] = A [ n − 1] = 0 – i < j : j − 0 > j − i , contradiction – j < i : n − 1 − j > i − j , contradiction • A [0] = A [ n − 1] = 1 – i < j : n − 1 − i > j − i , contradiction – j < i : i − 0 > i − j , contradiction • A [0] ̸ = A [ n − 1]: n − 1 − 0 > | i − j | , contradiction It contradicts in all the cases, so at least one of the equalities holds. b) Solution 1: Find max j so that A [ j ] ̸ = A [0] and min i so that A [ i ] ̸ = A [ n − 1]. Then the maximum distance is max( j, n − 1 − i ). Clearly the algorithm runs in O ( n ). Solution 2: Keep track of the positions of the first and last 0’s and 1’s, compute the maxi- mum distance between 0’s and 1’s according to these positions. Rubrics a) Contradiction assumption (1 pt); 1 pt for each case; 1pt for the conclusion. b) Solution 1: 10 pts for the algorithms (3 pts for max j ; 3 pts for min i ; 4 pts for the final output); give at most 4 pts for the algo- rithm not running in O ( n ). 3 pts for calculating one direction (for example, A [0] and A [ j ]). Solution 2: 10 pts for the algorithms. 3 pts for less than four positions (for example, only consider first 1 and last 0).

6. Divide and Conquer (15 points) Suppose that you are given a square matrix M that has n rows and n columns. Each row and each column contains no duplicates and is already sorted in increasing order. More formally: for each row r of the matrix, M [ r ][ i ] < M [ r ][ j ] whenever i < j , and, for each column c of the matrix, M [ i ][ c ] < M [ j ][ c ] whenever i < j . Design a divide-and- conquer algorithm that finds a given value k in the matrix M . You may assume that n is a power of 2. a) Describe your algorithm in plain English or using pseudocode. (7 points) Plain English: We assume that n is a power of 2, and that the rows and columns of M are indexed 0 , ..., n − 1. All division operations are integer division, i.e. x/ 2 = x/ 2. The general idea is to partition M into four pieces: • M 11 is the submatrix consisting of rows 0 , ..., n 2 − 1 and columns 0 , ..., n 2 − 1. • M 12 is the submatrix consisting of rows 0 , ..., n 2 − 1 and columns n 2 , ..., n − 1. • M 21 is the submatrix consisting of rows n 2 , ..., n − 1 and columns 0 , ..., n 2 − 1. • M 22 is the submatrix consisting of rows n 2 , ..., n − 1 and columns n 2 , ..., n − 1. We notice that if k is less than M [ n/ 2][ n/ 2], then k cannot ap- pear in M 22 , since all entries in M 22 are at least as large as M [ n/ 2][ n/ 2] (based on the given properties of M ). So in this case, we search in M 11 , M 12 , M 21 recursively. Similarly, if k is larger than M [ n/ 2][ n/ 2], then k cannot appear in M 11 , since all entries in M 11 are at most as large as M [ n/ 2][ n/ 2] (based on the given properties of M ). So in this case, we search in M 12 , M 21 , M 22 recursively.

Pseudocode: Algorithm 1 searchAlgorithm ( M, k ) n ← M .length return searchRecurse ( M, k, 0 , 0 , n − 1 , n − 1) Algorithm 2 searchRecurse ( M, k , lowRow,highRow,lowCol,highCol ) halfSize ← ( highRow - lowRow + 1)/2 if k == M [ lowRow+halfSize ][ lowCol+halfSize ] then return “( lowRow+halfSize, lowCol+halfSize )” else if halfSize == 0 then return “Not Found” else if k < M [ lowRow+halfSize ][ lowCol+halfSize ] then ▷ search M 11 answer = searchRecurse ( M, k, lowRow,lowRow+halfSize-1, lowCol,lowCol+halfSize-1 ) else ▷ search M 22 answer = searchRecurse ( M, k, lowRow+halfSize,highRow, lowCol+halfSize,highCol ) end if if answer = “Not Found” then ▷ search M 12 if k not found yet answer = searchRecurse ( M, k, lowRow,lowRow+halfSize-1, lowCol+halfSize,highCol ) end if if answer = “Not Found” then ▷ search M 21 if k not found yet answer = searchRecurse ( M, k, lowRow+halfSize,highRow, lowCol,lowCol+halfSize-1 ) end if return answer

Rubrics (7 points): Plain English: • (2 pts) Specify how the 4 (square) submatrices are defined. • (2 pts) Clearly state / explain the 3 submatrices to search in 2 cases. • (2 pts) Clearly state how to return the indices (e.g., by the 4 parameters like binary search). • (1 pt) Mention the 2 base cases (i.e., equal value or the entire matrix has been searched). • Deduct 1 mark for partially correct. • Searching 4 submatrices is incorrect. Pseudocode: Similarly, • (2 pts) Specify the 4 submatices. • (2 pts) State which submatrices to search in each scenario. • (2 pts) Include more parameters / arguments to index. • (1 pt) Specify the 2 base cases. • You can only write the (private) second algorithm with additional parameters. • Searching 4 submatrices is incorrect.

c) Solve the above equation using the Master Theorem. (3 points) Master Theorem We determine the asymptotic behaviour of T ( n ) using the Master Theorem. The relevant values are a = 3 , b = 2 , f ( n ) = 10. The number of leaves of the recurrence tree is calculated as: n log b a = n log 2 3 . Note that f ( n ) = C 2 ∈ O (1), so f ( n ) ∈ O ( n 0 ). Since log 2 3 ≈ 1 . 585 ... > 0, we can write n 0 = n log 2 3 − ϵ with an ϵ > 0. This proves that f ( n ) ∈ O ( n log 2 3 − ϵ ). This satisfies the condition of Case 1 of the Master Theorem, which tells us that T ( n ) ∈ Θ( n log 2 3 ). Rubrics (3 points): • (1 pt) Correctly define a, b, c, f ( n ). • (2 pts) Specify that it falls under Case 1 and obtain the correct answer. • Answers indicating O ( n 2 ) will be considered incorrect.

7. Dynamic Programming (20 points) Consider a row of n lamp posts standing sequentially. The heights of these lamp posts are H = [ h 0 , h 1 , . . . , h n − 1 ]. Your task is to find a subsequence of lamp posts that contains the maximum number of lamp posts with strictly increasing heights. Example. Suppose we have lamp posts with heights H = [10 , 9 , 2 , 5 , 3 , 7 , 101 , 18]. The maximum subsequence length is 4, and a subsequence is [2 , 3 , 7 , 101]. a) Define (in plain English) sub-problems to be solved. (5 pts) There are two perspectives to answer this question with full cred- its, either should be good: length perspective: dp [ i ], the length of subsequence with max- imum amounts of lamp posts in increasing height, and the end element is the i -th lamp post. or subsequence perspective: s [ i ], the subsequence with maxi- mum amounts of lamp posts in increasing height, and the end element is the i -th lamp post. Rubrics (5 points): • Incorrect or irrelevant definition: -5 points • Improper conversion from LIS into LCS b) Write a recurrence relation for the sub-problems. (8 pts) dp [ i ] = max( dp [ j ] + 1 , dp [ i ]) for 0 < = j < i and h i > h j or s [ i ] = max max length ( s [ j ] + [ i ] , s [ i ]) for 0 < = j < i and h i > h j

pseudocodes (2 pts): for 0 ≤ i ≤ n − 1: s [ i ] = [ i ] //store the element index in subsequence for 0 ≤ j ≤ i − 1: if h i > h j : if dp [ j ] + 1 > dp [ i ]: dp [ i ] = dp [ j ] + 1 s [ i ] = s [ j ] + [ i ] //concatenate two list or for 0 ≤ i ≤ n − 1: for 0 ≤ j ≤ i − 1: if h i > h j : if len( s [ j ]) + 1 > len( s [ i ]): s [ i ] = s [ j ] + [ i ] //concatenate two list Rubrics (5 points: 1 for base, 2 for final, 2 for pseudo): • if recurrence relation uses opt[n-1] by default : pseudocode points: -2 • Wrong base case: -1 point, wrong final answer: -2 points • Missing subsequence or max length as final answer: -1 point • Incorrect pseudocode: -2 points d) What is the complexity of your solution? (2 pts) O ( n 2 )

Rubrics (2 points): • Wrong/missing time complexity: -2 points • NOTE: only time complexity is expected, space complexity is NOT necessary (no points deduction if their space complexity is computed but wrong) • Inefficient algorithm (exponential time complexity): -1 point