CS570 Spring 2024 Exam 1 Solutions Rubrics

CS570 Spring2024: Analysis of Algorithms Exam I Points Points Problem 1 20 Problem 5 10 Problem 2 9 Problem 6 20 Problem 3 9 Problem 7 16 Problem 4 6 Problem 8 10 Total 100 Instructions: 1. This is a 2-hr exam. Closed book. No electronic devices or internet access. One 8.5x11 cheat sheet allowed. 2. 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. 3. No space other than the pages in the exam booklet will be scanned for grading. 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. 8. This exam is printed double sided. Check and use the back of each page.

1) 20 pts Mark the following statements as TRUE or FALSE by circling the correct answer. No need to provide any justification. [ TRUE /FALSE ] A bipartite graph cannot contain an odd-length cycle. [ TRUE/ FALSE ] There exists an algorithm with worst-case running time complexity O (log n ) for finding the smallest element of a binary max-heap with n elements . [ TRUE /FALSE ] There exists an algorithm with worst-case running time complexity O ( n ) for merging two binomial min-heaps of size n . [ TRUE /FALSE ] Removing any element from a binary heap (not necessarily the root) and then reheapifying to maintain the heap property can be accomplished in O (log n ) time, where n is the number of elements in the heap. [ TRUE/ FALSE ] If a Directed Acyclic Graph G is weakly connected and has n ≥ 2 vertices and n -1 edges, then G must have a unique topological ordering. [ TRUE/ FALSE ] Dijkstra’s algorithm will work correctly as long as the graph has no more than one negative weight edge. [ TRUE /FALSE ] Every tree is a bipartite graph. [ TRUE /FALSE ] The amortized cost of an operation can be lower than the worst-case cost of that operation. [ TRUE /FALSE ] The amortized cost of an operation can be higher than the worst-case cost of that operation.

2) 9 pts (3 pts each) Circle ALL correct answers (no partial credit when missing some of the correct answers). No need to provide any justification. i- In a graph G with n nodes and n +5 edges, where k ≥ 7 edges have the same weight, every minimum spanning tree of G will have at least… a) 2 edges with the same weight. b) 3 edges with the same weight. c) 4 edges with the same weight. d) None of the above ii- What is the solution to the recurrence equation T ( n ) = 2 T ( n /2) + 3 n + sqrt( n )? a) T ( n ) = 𝚹 ( n sqrt( n )) b) T ( n ) = 𝚹 ( n log 2 n ) c) T ( n ) = 𝚹 ( n log n ) d) None of the above iii- What is the solution to the recurrence T ( n ) = 2 T ( n /2) + 3 n log n + 2 n ? a) T ( n ) = 𝚹 ( n log n ) b) T ( n ) = 𝚹 ( n ) c) T ( n ) = 𝚹 ( n log 2 n ) d) T ( n ) = 𝚹 ( n 2 )

3) 9 pts For each of the following algorithms, use the Master Method to determine its running time in terms of big-O, and if the Master Method cannot be applied explain why. a. Algorithm A , which solves problems of size n by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions to the subproblems in linear time. b. Algorithm B , which solves problems of size n by recursively solving two subproblems each of size n -1 and then combining the solutions in constant time. c. Algorithm C , which solves problems of size n by dividing them into nine subproblems of size n /3, recursively solving each subproblem, and then combining the solutions in O ( n 2 ) time. The running times T A , T B , T C of the algorithms satisfy the following recurrence relations: T A (n) = 5T(n/2) + O(n) T B (n) = 2T(n − 1) + O(1) T C (n) = 9T(n/3) + O(n 2 ). Functions T A and T C can be found by the Master Theorem : T A (n) = O( ) T C (n) = O( ) = O(n 2 logn). For T B we have T B (n) = 2T B (n − 1) + O(1) = 2 2 TB(n − 2) + 2 · O(1) = 2 3 T(n − 3) + 3 ·O(1) =··· = 2 n T(1) + n · O(1). Thus, T B (n) = O(2 n ).

5) 10 pts Consider a collection of n integer-valued variables x 1 , ..., x n and a collection of m constraints, where in each constraint, two variables are constrained to be equal (e.g. x i =x j ) or unequal (e.g. x i ≠ x j ). Depending on the constraints, it may be impossible to assign values to the variables without violating at least one constraint. For example, the following collection of constraints cannot all be satisfied simultaneously: x 1 =x 2 , x 2 =x 3 , x 3 =x 4 , x 4 ≠x 2. Design an algorithm (hint: graph based) that takes as input m constraints over n variables and decides in O ( m + n ) time whether the given set of constraints can be satisfied. Analyze the worst-case running time complexity of your algorithm. 5 points for solutions that run in O( m 2 ) Let G = (V, E) be the following graph: G has a node corresponding to every variable x i , and there is an edge (x i , x j ) if x i = x j is an equality constraint. Full Points: We do a Depth First Search of G to find all its connected components. For each node X i , if it is in the k-th connected component of G, we assign it a mark k. Now for each inequality constraint x i x j , we check to see if x i and x j occur in different connected components of G . If there is some inequality constraint x i x j such that x i and x j occur in the same connected component of G, then we report that the constraints are unsatisfiable. If there is no such constraint, then we report satisfiable. Finding all connected components takes O(m+n). checking all inequality takes O(m). Overall complexity is O(m+n) Common major errors: 1) Including all constraints as edges and not just for equality constraints. These attempts typically follow up with 2) below. 2) Finding cycles (any cycles or odd-length cycles) - cycles containing zero or two or more inequality constraints does not force insatisfiability, only the ones with exactly one inequality do force it. Finding just any cycle is easy with BFS/DFS but finding one with certain property (e.g. Number of edges of certain type) is not easy, certainly not with brute force. 3) “Processing” all constraints in whichever order. This will not work, ALL equality constraints need to be taken into account first and THEN check for satisfiability of inequalities. 4) BFS/DFS on weighted graphs 5) Missing the fact that we may get multiple connected components from BFS/DFS and not just one tree. 6) Use of directed edges - unnecessary and often incorrect 5 Points: For each inequality x i x j run BFS or DFS from x j to see if x i is reachable. If it is then the set of constraints are not satisfiable. Run time = O(m*(m+n)) = O( m 2 )

2 Points: Construct a graph containing N nodes, the i-th node is corresponding to the integer x i . Only for each equality constraint x i = x j , draw an undirected edge from x i to x j . Before applying for regrading Q5, please check for common incorrect approaches listed above - it would help to check if your algorithm can pass the following examples correctly. [1] x1 noeq x2, x2 noeq x3, x3 noeq x1 (this graph is not bipartie) [2] x1 eq x2, x3 eq x4, x1 noeq x3, x2 noeq x4 (there is a cycle, but the graph is valid) [3] x1 eq x3, x2 eq x3, x2 eq x4, x4 noeq x1 (no loop in directed graph) [4] x1 eq x2, x3 eq x4, x2 eq x4, x4 noeq x1 (sequentially coloring will cause problem when handling x2 eq x4) 6) 20 pts Consider the Minimum Leaf-Constrained Spanning Tree (MLCST) Problem, defined below: Given an undirected weighted graph G = ( V , E , w ) and a subset of vertices U ⊆ V , find the least-weight spanning tree T in G in which each vertex in U is a leaf of T . If no such tree exists, your algorithm should indicate so. a. Design an algorithm for this problem with worst-case running time O ( |E| log |V| ). (10 pts) b. Analyze the worst-case running time complexity of your algorithm. (5 pts) c. Give an example of a graph G and a set of vertices U ⊆ V for which such an MLCST does not exist. (5 pts) Solution: A MLCST T of G consists of a least-weight edge incident to u and another vertex v ∈ V - U for each vertex u ∈ U, and the edges of a MST of G - U. Consider an arbitrary MLCST T of G. For each vertex u ∈ U, u is a leaf of T, so T contains exactly one edge incident to u. If this edge is not an edge of least-weight among those incident to u and some other vertex v ∈ V - U, then removing this edge from T and adding a least-weight edge incident to u and a vertex v ∈ V - U yields a LCST of G with

run Prim’s algorithm from A as root, it can include the AB edge, which produces the wrong MLCST. Checking if U = V can be done in O(|V|) time. Finding the cardinality of V also takes O(|V|). We can check if G - U is connected in O(|E| + |V|) using either BFS or DFS. We can find the MST T of G - U in O(|E| log |V|) using either Prim’s or Kruskal’s algorithm. We can find Eu and the minimum edge in Eu for all u ∈ U in O(|E|) time. Therefore, the worst-case time complexity of our algorithm is O(|E| log |V|) Give an example of a disconnected graph. Or, if U = V, give an example of a graph containing at least 3 vertices. Or, if U ≠ V, give an example of a graph G which becomes disconnected when we remove the vertices in U from G. Rubric Algorithms: Using Approach I +1 point for correctly handling the U = V case. +1 point for correctly identifying the case when U ≠ V and a LCST is not possible if G - U is disconnected. +1 point for correctly identifying the case when U ≠ V and a LCST is not possible if Eu = Ø for any vertex u ∈ U. +4 points for finding MST on G - U. +3 points for correctly adding the minimum edge (u, v), u ∈ U and v ∈ V - U, for each vertex u ∈ U. Using Approach II +1 point for correctly handling the U = V case +1 point for correctly identifying the case when U ≠ V and a LCST is not possible if the final tree contains less than |V| - 1 edges. +4 points for correctly handling a (u, v) edge when u ∈ U and v ∈ V - U. +2 points for correctly handling a (u, v) edge when both u and v ∈ U. +2 points for correctly handling a (u, v) edge when both u and v ∈ V - U. Worst-case running time analysis We give full points even if the algorithm in a) is wrong. +2 points for showing some working +3 points for writing the correct runtime +5 points for correct example.

7) 16 pts Consider two lists, L 1 of length n and L 2 of length m . We say that L 2 is a subsequence of L 1 if we can delete certain elements from L 1 so that the remaining sequence is equal to L 2 . This means that there exists m indices i 1 < … < i m such that L 1 [ i j ] = L 2 [ j ] for each j . Design an efficient algorithm that detects if L 2 is a subsequence of L 1 and outputs the indices i 1 , . . . , i m if L 2 is a subsequence of L 1 (8 pts), analyze your algorithm’s worst-case running time (3 pts), and prove that your algorithm is correct (5 pts). Solution: The algorithm is a greedy algorithm that makes one pass over both lists. It starts with pointers at the first element of each list, repeatedly incrementing the pointer on L 1 until it finds an element i such that L 1 [i] = L 2 [1] . This value i is the output i 1 , and at this point, the algorithm increments the pointer on L 2 to point to the second element while also incrementing the pointer on the first list to point to the i+1 st element. The process repeats until both lists have been traversed. Here is the pseudocode: j = 1, k=1 for k = 1, . . . , m do while L 1 [j] != L 2 [k] do j ← j + 1 end while i k = j (in the solution) j ← j + 1, k ← k + 1 end for This algorithm stays ahead of any other possible solution in the sense that among all possible subsequences, it outputs the one with the lowest indices i 1 < . . . < i m . More formally, for any other partial subsequence M’ (consisting of indices

8) 10 pts You are assigned n tasks, numbered from 1 to n . There are m dependence relations between the tasks. For the i -th dependence relation, ( u i , v i ) indicates that task u i should be finished before starting task v i . You can only process one task at a time. Design an efficient algorithm for deciding whether it is possible to finish all tasks without violating any dependence relations. Your solution should run in linear time with respect to n and m . (7pts) Analyze the worst-case running time complexity of your solution. (3 pts) Brief solution to the problem a) Construct the directed graph for the dependence relations. b) Using topological sort to decide whether this graph is acyclic. c) These tasks can be finished if and only if the graph is acyclic.

Additional Space

Additional Space