CSE6140/CX4140 - MIDTERM - Fall 2019 reference solutions
Instructions: PLEASE WRITE YOUR NAME and GT ACCOUNT ON EACH PAGE ***VERY CLEARLY
IN BLOCK LETTERS***. NUMBER EACH PAGE.
This is a closed-book exam. However, you
...
CSE6140/CX4140 - MIDTERM - Fall 2019 reference solutions
Instructions: PLEASE WRITE YOUR NAME and GT ACCOUNT ON EACH PAGE ***VERY CLEARLY
IN BLOCK LETTERS***. NUMBER EACH PAGE.
This is a closed-book exam. However, you are allowed to use one sheet of notes (both sides of a
letter-sized sheet of paper) during the exam. No collaboration is permitted.
You have 70 minutes to complete this exam.
The exam has 10 + 14 + 6 + 16 = 46 points in total (FOUR INDEPENDENT QUESTIONS).
It is a good idea to read all the questions before starting.
1 Short questions [10 pts]
(a) (2 pts) What type of algorithm is Dijkstra’s algorithm (seen in the course)? Which problem does it
solve?
Solution
Greedy Algorithm, solves single-source shortest path problem.
(b) (2 pts) For each pair of functions f and g, choose one of f ∈ O(g), f ∈ Θ(g), f ∈ Ω(g) that best
describes their relative asymptotic growth. No justification is necessary.
f = log(n
3
), g = 10 log(n)
Sol: Θ (0.5 pt)
f = n
4
, g = (n log n)
3
Sol: Ω (0.5 pt)
f = 1000n, g = n!
Sol: O (0.5 pt)
f = 2n, g = ( 5
2
)
n
Sol: O (0.5 pt)
1
GT USERNAME: NAME:
(c) (2 pts) Solve T(n) = 7T(n/2) + Θ(n
2
) using the Master Theorem.
Solution
a=7, b=2, d=2
a > bd → Θ(n
log2 7
)
Grading: need not provide the intermediate steps (like values of a, b, d). Giving the correct Θ notation
gets full points. -0.5 points if giving O instead of Θ
(d) (2 pts) Assume that Y is NP-complete and that Y linear-time reduces to X (the transformation from
Y to X uses linear time). Let N denote the size of the input to X. Choose true or false (circle your
choice) for each of the following statements:
i. If there exists an O(N2
) algorithm for X, then P = NP.
True False
Solution: True (1 pt)
ii. If there exists an O(N2
) algorithm for Y, then there exists an O(N2
) algorithm for X.
True False
Solution: False (1 pt)
(e) (2 pts) Draw diagrams to show the relationship between classes P, NP, and NP-complete (in terms of
set inclusion).
Grading: Needs to show both diagrams for these two cases. -1 pt for missing one of them. It’s ok if
the set “all problems” is
[Show More]