Computer Science > EXAM > CSE6140_ midterm_solutions - Georgia Institute Of Technology CSE 6140 (All)

CSE6140_ midterm_solutions - Georgia Institute Of Technology CSE 6140

Document Content and Description Below

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-boo... k 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]

Last updated: 2 years ago

Preview 1 out of 8 pages

Buy Now

Instant download

We Accept: