IIT Madras - CSE Department - CS5800 ADSA - 2021 Instructions 1. Even if one of the following items below is not followed, your answer sheet may not be evaluated 2. On the first page write your name and roll number. 3. Clearly mark the question numbers. 4. If you have a doubt in any question Make an assumption and answer the question. Due credit will be given 5. On the first page mention that approximate time at which the question paper was downloaded. 6. On the first page mention the time at which network connection on all your personal devices were turned off. 7. On each page, have a page number in the clearly visible corner. 8. After you have finished the exam, on the first page mention the total number of sheets in the answer book. 9. Please write this message on the first page- Honour Code: I have not engaged in any dishonest means to answer this question paper. I have maintained a high level of decency and dignity in attempting this question paper. I understand that my quest for knowledge is life-long, while this exam will end in just 180minutes. I understand with pride, dignity, and decency that I do not have to resort to cheating in exams 10. At the bottom of the first page, please put your signature with date, time, location, pin code. 11. Scan and upload. 1 Part I - 4 marks per question 1. Compare the worst-case running times of QUICKSORT and RANDOMIZED-QUICKSORT. Given an interpretation of the expected running time of RANDOMIZED-QUICKSORT. 2. Consider the given two functions f1 and f2: f1(n) = n if n is even and f1(n) = 2n if n is odd. f2(n) = 2n + 1 if n is even and f2(n) = n if n is odd. What is the asymptotic relationship between the two functions? Justify your answer. 3. Consider the following array or records, each with a string and an integer with maximum value 5. Rahul Baadal Priya Jose Ameen 2 5 4 2 5 What is the output array of records if the given array is sorted using COUNTING-SORT. Justify your answer. 4. Define a universal class of hash functions. Give one example of a universal class of hash functions. What are the key steps in the proof that your example is indeed a universal class of hash functions? 5. Consider the following flow network. (a) What is the value of a maximum flow in this network? (b) Give a flow that achieves the maximum flow? (c) For the flow that you give, draw the residual network. (d) What is the value of minimum s-t cut in the residual network? How is this related to the minimum s-t cut in the given flow network (e) Consider the initial flow to be the zero flow, draw the residual network, and give one augmenting path, and the flow value augmented on the path that you give. Page 2 6. Recall that during a DFS of directed graph G each vertex u has a discovery time and finish time denoted by u.d and u.f, respectively. What is the relationship between u.d and u.f? Further, what are the relationships possible between the discovery and finish times of two vertices u and v? Coming to the edges, what is the classfication of the edges after a DFS has been performed? 7. For the matrix chain A1A2A3A4 with dimensions 35, 52, 210, 102 respectively fill the m[i, j] values as in Figure 15.5 of the textbook. 8. Design a linear time algorithm for the longest path problem in an input tree (connected acyclic undirected graph). 9. Consider the problem LONGEST-PATH = {< G, k >| G has a path with at leastk edges }. Answer the following questions: a. What is an input instance of the LONGEST-PATH problem? b. What is an yes-instance of the LONGEST-PATH problem? c. Show that the LONGEST-PATH problem is in NP. Define a witness function ( called certificate in the text book) and the verifier. 10. Consider the k-SAT problem {F | F is a satisfiable boolean formula in product of sum form and each clause has k literals } List all the points about the complexity status of the 2-SAT problem and the 3-SAT problem. Justify your answers. 11. Tabulate the name of the scientists whose results have been presented in the text book. The columns must be < Concept, Name(s) of the scientists, Year, Any other detail >. 2 Part II - 7 marks per question 1. What is the selection problem. Recall that in the algorithm SELECT, the input elements are divided into groups of 5. (A) Will the algorithm work in linear time if they are divided into groups of 3? (B) Will the algorithm work in linear time if they are divided into groups of 7? Explain you answers. 2. Consider the following approach to solve the matrix chain multiplication problem: identify a pair of adjacent matrices A and B in the chain which can be multiplied using the least number of multiplications, mutiply them, insert the product matrix C in place of A and B. Recurse on the resulting smaller chain of matrices. Is this guaranteed to give the optimum number of multiplications? Give a clear justification for your answer. 3. What is the output order for the following task scheduling problems related to the table below? Justify your answer. Page 3 (A) When all the tasks are scheduled using greedy algorithm on a single processor, with given wi (B) When all the tasks are scheduled using greedy algorithm on a single processor, with each penalty wi replaced by 80 - wi ai 1 2 3 4 5 6 7 di 4 2 4 3 1 4 6 wi 70 60 50 40 30 20 10 (1) where ai = unit-time task di = deadline for task ai wi = penalty if task ai is not finished by time di 4. Define the activity selection problem in which all the activities have the same weight. Consider the weighted version of the activity selection problem: There are n activities, and the i-th activity has a weight wi = 0, and the goal is to select a set of nonintersecting activities and maximize the sum total weight. What is the structure of an optimum solution? Give a recursive formulation of the optimum, and use this to design an efficient algorithm. 5. On an input directed acyclic graph, design an algorithm to output all topological orderings of the vertices. Your answer must argue the following a. Each topological ordering is output once, and no topological ordering is output twice. b. The time between two outputs is O(V + E), where V is the number of vertices in the given graph and E is the number of edges in the given graph. 6. What is the goal of perfect hashing? Explain with clear reference to the Lemmas in the text how a universal hash family is used to achieve the goal of perfect hashing. Assuming that n keys are to be stored using perfect hashing, give a clear bound on the space used, and the time to create the hash table. 7. Answer the follwing questions. a. Expand the abbreviations P and NP. b. Define the sets P and NP, and state the relationship between the two. Justify your answer. clearly. c. Formulate the natural decision problem related to maximum cardinality matching in bipartite graphs. Does this belong to NP? d. Formulate the natural decision problem for the maximum flow in a flow network. Does this belong to P? e. Describe a polynomial time reduction from matching in bipartite graphs to the flow problem. 8. State the 3-Coloring problem. Show that it is NP-Complete. Page 4

Attachments:

main.pdf