• Carleton University

• COMP 3804

Comprehensive Exam DURATION: 2.5 HOURS Prepared  

Student Name:

Student Number:

Instructions

1. All questions must be answered on this examination paper. You may use

both sides of the answer sheets for answers. There are some extra sheets

attached at the end of this examination paper.

2. If you find a question to be ambiguous or unclear, then make, and state, whatever

assumptions you feel are necessary; your mark will then be partly based on the reasonableness of your assumptions.

3. Please answer to the point and do not write everything you know on the topic. Substantial marks will be deducted if your answer is not precise.

4. All logarithms are base 2.

5. Although the sum-total of all the marks is 110, the exam will be treated as if it is

out of 100. Alternatively, you may think of that you need not attempt each and every

question.

Comprehensive Exam 2

Question 1: (2*15=30 marks) Answer TRUE or FALSE. Correct answer is worth (+2)

Marks. Wrong answer is worth (-1) Marks. No answer is worth (0) Marks.

1. Is √1 + √2 + √3 + . . . + √n = O(n3/2)?

—————–

2. If the SUBSET SUM problem can be solved in polynomial time then P=NP?

—————–

3. Is P ⊆ NP?

—————–

4. Let L1 and L2 be two languages corresponding to two decision problems and let

L1 ≤P L2 (under the polynomial time reducibility, where a binary string x is mapped

to the binary string f(x) in polynomial time). Does this imply that if the membership

of x in L1 can be tested in polynomial time then the membership of f(x) in L2 can

also be tested in polynomial time?

—————–

5. Dynamic Programming is a technique to solve NP-Complete Problems in Polynomial

Time.

—————–

6. A min-Heap on n-elements can be constructed in O(n) time.

—————–

7. Given a min-Heap on n-elements, the elements can be reported in sorted order in O(n)

time.

—————–

8. There are two algorithms for a problem. The running time of Algorithm I is expressed

as T(n) = T(n/2) + T(n/4) + n and the running time of Algorithm II is expressed as

T(n) = T(n/3) + T(2n/3) + n. Is the running time of Algorithm II smaller than that

of Algorithm I for large values of n