Comp 3170 - Analysis of Algorithms & Data Structures Quiz 2 (WITH CORRECT ANSWERS)

Document Content and Description Below

Comp 3170 - Analysis of Algorithms & Data Structures Quiz 2 University of Manitoba - Winter 2018 March 28, 2018 Write your name and student id here: ‘For every complex problem there is an an ... swer that is clear, simple, and wrong.’ Henry Mencken • Do not open this booklet until instructed. • You are not allowed to use any printed/written material, laptops, guns, cell-phones, etc. Please turn off your cell phones and put them in your bags. • Manage your time. We start the exam at 10:30 and end the quiz at 11:20. You have 50 minutes. • There are 4 pages (including this cover page). Write your answers in the provided boxes. • In the unlikely case that you find the exam too long/hard, do not panic. The marks will be scaled so that the highest mark gets the full mark. • There are more important things in life than this quiz. So, relax and smile. Also, there are more important components to this course than this quiz. So, relax further and smile more (but still manage your time while relaxing). This study source was downloaded by 100000834091502 from CourseHero.com on 11-18-2022 09:23:27 GMT -06:00 https://www.coursehero.com/file/34292929/quiz2pdf/ 1. Short Answer (26 marks) Provide your short answers in the provided boxes. There is no need to justify your answers. 1. True or False: If a problem belongs to class P, then it belongs to class NP True Notes: If you can solve a decision problem in polynomial time (i.e., the problem is in P), you can of-course check a candidate solution (a certificate) of the problem in polynomial time as well (i.e., it is in NP also) 2. True or False: Collinearity is an NP-complete problem False Notes: A naive solution for collinearity is to check every triplet of points and check in constant time whether they lie on the same line; this can be done in O(n 3 ) which is polynomial. 3. Consider a problem E is reduced to problem H in time Θ(n 2 ). (a) True or False: Assume there is an algorithm that solves H in O(n 2 log n). We can conclude there is an algorithm that solves E in O(n 2 log n). True Notes: A direct consequence of the reduction. (b) True or False: Assume there is an algorithm that solves E in O(n 3 ). We can conclude there is an algorithm that solves H in O(n 3 ) as well. False Notes: An algorithm for the easy problem cannot be used for solving an arbitrary instance of the hard problem; reduction only creates particular, specific instances of the hard problem and not all of them. (c) True or False: Assume we know any algorithm for E runs in Ω(n log n). We can conclude any algorithm for H runs in Ω(n log n) as well. False Notes: We cannot conclude any statement in terms of lower/upper bounds when the reduction time (here Θ(n 2 )) dominates the existing bounds (here n log n). As an example, consider the element-distinction problem (P1) which asks whether an array of n numbers include two equal numbers. This problem cannot be solved in Ω(n log n). Let P2 be another problem which asks whether a set of n numbers include 0 as one its elements; clearly, P2 can be solved in linear time. Consider the following reduction from P1 to P2. Given an array A of size n as an instance of P1, create an array B of size n as an instance of P2 as follows. B includes all integers from 2 to n + 1. In addition, it includes either 0 or 1: consider all pairs of elements in A; if any two were equal, 0 is added to B otherwise 1 is added. Note that this reduction has time Θ(n 2 ). Clearly, two numbers in A sum to 0 iff 0 is present in B. However, can we conclude that any algorithm for P2 runs in Ω(n log n)? the answer is no. The issue here is that during the reduction, most of the difficulty of P1 is taken away. In other words, the reduction is too expensive. 4. True or False: Assume P is an NP-complete problem. Then, there is no polynomial time algorithm for P, assuming P 6= NP. True 5. True or False: A candidate solution for an NP-complete problem can be checked in polynomial time. True Notes: Definition of NP. 6. True or False: Bin packing problem belongs to NP. True 7. True or False: The following multi-set is a y [Show More]

Last updated: 3 years ago

Preview 1 out of 4 pages