Design and Analysis of Algorithms Assignment 2 PDF

Design and Analysis of Algorithms (CS/AI 2102) Assignment-2 Please adhere to these instructions: 1. If you feel any question is ambiguous, clearly state your assumption(s) and solve it accordingly. 2. Submit your written assignment on October 22nd, 2024 at th...

Design and Analysis of Algorithms (CS/AI 2102) Assignment-2 Please adhere to these instructions: 1. If you feel any question is ambiguous, clearly state your assumption(s) and solve it accordingly. 2. Submit your written assignment on October 22nd, 2024 at the start of the lecture session. No early or late submissions are allowed. 3. You can discuss with peers, but you must write in your own words. Avoid plagia- rism at all costs. 1. Perform depth-first search on each of the following graphs; whenever there is a choice of vertices, pick the one that is alphabetically first. Classify each edge as a tree edge, forward edge, back edge, or cross edge, and give the pre and post number of each vertex. C A B C D B E D E A F H F G H G Graph (a) Graph (b) 2. Run the DFS-based topological ordering algorithm on the following directed graph. Whenever you have a choice of vertices to explore, always pick the one that is alphabetically first. A D G C F B E H (a) Indicate the pre- and post-numbers of the nodes. (b) What are the sources and sinks of the graph? (c) What topological ordering is found by the algorithm? 1  (d) How many topological orderings does this graph have? 3. The reverse of a directed graph G = (V, E) is another directed graph GR = (V, E R ) on the same vertex set, but with all edges reversed; that is, E R = {(v, u) ∶ (u, v) ∈ E}. Give a linear-time algorithm for computing the reverse of a graph in adjacency list format. 4. Run the strongly connected components (SCCs) algorithm on the following directed graphs G. When doing DFS on GR (the reverse graph): whenever there is a choice of vertices to explore, always pick the one that is alphabetically first. A C D A B C B F E D E F G H J G H I I Graph (b) Graph (a) In each case, answer the following questions: (a) In what order are the strongly connected components (SCCs) found? (b) Which are source SCCs and which are sink SCCs? (c) Draw the “metagraph” (each meta-node is an SCC of G). (d) What is the minimum number of edges you must add to this graph to make it strongly connected? 5. Either prove or give a counterexample: if {u, v} is an edge in an undirected graph, and during depth-first search post(u) < post(v), then v is an ancestor of u in the DFS tree. 6. Suppose a CS curriculum consists of n courses, all of them mandatory. The prerequisite graph G has a node for each course, and an edge from course v to course w if and only if v is a prerequisite for w. Find an algorithm that works directly with this graph representation, and computes the minimum number of semesters necessary to complete the curriculum (assume that a student can take any number of courses in one semester). The running time of your algorithm should be linear. 7. Give an efficient algorithm which takes as input a directed graph G = (V, E), and determines whether or not there is a vertex s ∈ V from which all other vertices are reachable. 8. Give a linear-time algorithm for the following task. Input: A directed acyclic graph G. 2  Question: Does G contain a directed path that touches every vertex exactly once? 9. Suppose Dijkstra’s algorithm is run on the following graph, starting at node A. 1 2 1 A B C D 8 6 4 6 2 1 4 E F G H 5 1 1 (a) Draw a table showing the intermediate distance values of all the nodes at each iteration of the algorithm. (b) Show the final shortest-path tree. 10. Just like the previous problem, but this time with the Bellman-Ford algorithm. -2 2 A C D 4 6 7 1 3 B S 5 F -4 6 -2 -2 1 G H E 3 1 -1 I 11. Give an efficient algorithm that takes as input a directed acyclic graph G = (V, E), and two vertices s, t ∈ V , and outputs the number of different directed paths from s to t in G. 12. Often there are multiple shortest paths between two nodes of a graph. Give a linear-time algorithm for the following task. Input: Undirected graph G = (V, E) with unit edge lengths; nodes u, v ∈ V. Output: The number of distinct shortest paths from u to v. 13. Consider a directed graph in which the only negative edges are those that leave s; all other edges are positive. Can Dijkstra’s algorithm, started at s, fail on such a graph? Prove your answer. 14. Give an algorithm that takes as input a directed graph with positive edge lengths, and returns the length of the shortest cycle in the graph. If the graph is acyclic, the algorithm should report it. Your algorithm should take time at most O(∣V ∣3 ). 3 15. Dijkstra’s algorithm always out-puts correct shortest distances from a source vertex even if we run it on any weighted graphs with negative edge weights. 16. Give a linear-time algorithm for the following task. Input: Undirected graph G(V, E) with unit edge lengths; nodes u, v ∈ V. Output: The number of distinct shortest paths from u to v. 17. Prove that for the array prev computed by Dijkstra’s algorithm, the edges {u, prev[u]} (for all u ∈ V ) form a tree. 18. A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. For instance, if S is 5, 15, −30, 10, −5, 40, 10, then 15, −30, 10 is a contiguous subsequence but 5, 15, 40 is not. Give a linear-time algorithm for the following task: Input: A list of numbers, a1 , a2 ,... , an. Output: The contiguous subsequence of maximum sum (a subsequence of length zero has sum zero). For the preceding example, the answer would be 10, −5, 40, 10, with a sum of 55. (Hint: For each j ∈ {1, 2,... , n}, consider contiguous subsequences ending exactly at position j.) 19. You are given a string of n characters s[1...n], which you believe to be a corrupted text document in which all punctuation has vanished (so that it looks something like ”itwasthebestoftimes...”). You wish to reconstruct the document using a dictionary, which is available in the form of a Boolean function dict(): for any string w, true if w is a valid word, dict(w) = { f alse otherwise. (a) Give a dynamic programming algorithm that determines whether the string s[.] can be reconstituted as a sequence of valid words. The running time should be at most O(n2 ), assuming calls to dict take unit time. (b) In the event that the string is valid, make your algorithm output the corresponding se- quence of words. 20. A subsequence is palindromic if it is the same whether read left to right or right to left. For instance, the sequence A, C, G, T, G, T, C, A, A, A, A, T, C, G has many palindromic subsequences, including A, C, G, C, A and A, A, A, A (on the other hand, the subsequence A, C, T is not palindromic). Devise an algorithm that takes a sequence x[1...n] and returns the (length of the) longest palindromic subsequence. Its running time should be O(n2 ). 21. Given two strings x = x1 x2... xn and y = y1 y2... ym , we wish to find the length of their longest common subsequence, that is, the largest k for which there are indices i1 < i2 <... < ik and j1 < j2 <... < jk with xi1 xi2... xik = yj1 yj2... yjk. Show how to do this in time O(mn). 4 22. Give an O(nt) algorithm for the following task. Input: A list of n positive integers a1 , a2 ,... , an ; a positive integer t. Question: Does some subset of the ai ’s add up to t? (You can use each ai at most once.) (Hint: Look at subproblems of the form “does a subset of {a1 , a2 ,... , ai } add up to s?”) 5