(Solved): Design And Analysis Of Algorithms Exam

Final Exam Name: CSCE411 Design and Analysis of Algorithms Apr. 30th, 2021 Texas A&M University Prof. Juan Garay Instructions (please read carefully before start!) • This take-home exam contains 11 pages (including this cover page) and 10 questions. Total of points is 100. • You will have till May 5th 4:30 p.m., 2021 to finish the exam. You must work on your own, and no collaboration or help from any resources other than those made available in class (lecture notes, texts, homework problems, etc.) is permitted. • Submit your solutions in PDF on Google Classroom before the deadline, either scanned or typeset in LATEX. Name the PDF file ‘<your last name> FINAL.pdf’. If you choose to hand-write and scan, print out this exam sheet and write your solutions on it. Do your best to fit your answers into the space provided, and attach extra papers only if necessary. If you typeset in LATEX, use the provided TeX file. No other formats are accepted. • For problems that require you to provide an algorithm, you must give a precise description of the algorithm, together with the pesudocode, a proof of correctness and an analysis of its running time. Grade Table (for instructor use only) Question Points Score 1 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10 10 Total: 100 CSCE 411 Final Exam - Page 2 of 11 Spring 2021 1. (10 points) Is the function dlg ne! polynomially bounded? Is the function dlg lg ne! polynomially bounded? CSCE 411 Final Exam - Page 3 of 11 Spring 2021 2. (10 points) Suppose that you want to output 0 with probability 1/2 and 1 with probability 1/2. At your disposal is a procedure Biased-Random, that outputs either 0 or 1. It outputs 1 with some probability p and 0 with probability 1− p, where 0 < p < 1, but you do not know what p is. Give an algorithm that uses Biased-Random as a subroutine, and returns an unbiased answer, returning 0 with probability 1/2 and 1 with probability 1/2. What is the expected running time of your algorithm as a function of p? CSCE 411 Final Exam - Page 4 of 11 Spring 2021 3. (10 points) Consider the problem of determining whether an arbitrary sequence {x1, x2, . . . , xn} of n numbers contains repeated occurrences of some number. Show that this can be done in Θ(n lg n) time. CSCE 411 Final Exam - Page 5 of 11 Spring 2021 4. (10 points) Let H1 and H2 be two hash functions. Define H(x) def = H1(x) ‖ H2(x). Prove that if at least one of H1 and H2 is collision resistant, then H is collision resistant. CSCE 411 Final Exam - Page 6 of 11 Spring 2021 5. (10 points) We can sort a given set of n numbers by first building a binary search tree containing these numbers (using Tree-Insert repeatedly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worst-case and best-case running times for this sorting algorithm? CSCE 411 Final Exam - Page 7 of 11 Spring 2021 6. (10 points) Let T be an MST of a graph G, and let L be the sorted list of the edge weights of T. Show that for any other MST T′ of G, the list L is also the sorted list of the edge weights of T′. CSCE 411 Final Exam - Page 8 of 11 Spring 2021 7. (10 points) A bipartite graph is k-regular if |L| = |R| and every vertex (regardless of which side it is on) has exactly k neighbors. Prove or refute: Every k-regular bipartite graph has a perfect matching. CSCE 411 Final Exam - Page 9 of 11 Spring 2021 8. (10 points) Suppose you are given a set L of n line segments in the plane, where each segment has one endpoint on the vertical line x = 0 and one endpoint on the vertical line x = 1, and all 2n endpoints are distinct. Describe and analyze an algorithm to compute the largest subset of L in which no pair of segments intersects. CSCE 411 Final Exam - Page 10 of 11 Spring 2021 9. (10 points) Define the optimization problem LONGEST-PATH-LENGTH as the relation that associates each instance of an undirected graph and two vertices with the number of edges in a longest simple path between the two vertices. Define the decision problem LONGEST-PATH = {〈G, u, v, k〉 : G = (V, E) is an undirected graph, u, v ∈ V, k ≥ 0 is an integer, and there exists a simple path from u to v in G consisting of at least k edges}. Show that the optimization problem LONGEST-PATH-LENGTH can be solved in polynomial time if and only if LONGEST-PATH ∈ P . CSCE 411 Final Exam - Page 11 of 11 Spring 2021 10. (10 points) Show that if an algorithm makes at most a constant number of calls to polynomial-time subroutines and performs an additional amount of work that also takes polynomial time, then it runs in polynomial time. Also show that a polynomial number of calls to polynomial-time subroutines may result in an exponential-time algorithm.

Design And Analysis Of Algorithms Exam

Related Study Services

Post your Answer - free or at a fee

Answer Review

Design And Analysis Of Algorithms Exam

Related Study Services

Post your Answer - free or at a fee

Login to your tutor account to post an answer