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 answer that is clear, si
...
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 answer 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]
