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 am
...[Show More]
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
[Show Less]