assignment

CS 512 Midterm Exam

Spring 2017

Group 1 Group 2 Group 3

P Question 1.1 Question 2.1 Question 3.1 Question 1.2 Question 2.2 Question 3.2

Question 3.3

P P P

Instructions:

• The questions are divided into three groups. You have to answer all questions in Groups 1 and 2 and 3.

• Provide your answer in the box after each question. If you absolutely need extra space,

use the backs of the pages; but try to avoid it. Keep your answers short and to the point.

• For the design questions (Group 3), if you cannot design an algorithm that achieves the stated running time, design a slower algorithm that is correct. A correct and slow algorithm earns you 50% of the points. A fast and incorrect algorithm earns 0 points.

• In the design questions, you are allowed to use algorithms and data structures you learnt

in class as black boxes, without explaining how they work, as long as these algorithms and data structures do not directly answer the question.

• Read every question carefully before answering. In particular, do not waste time on

an analysis if none is asked for, and do not forget to provide one if it is required.

• This exam has 13 pages, including the title page. Notify me immediately if your copy has fewer than 13 pages.

• Cheating and plagiarizing is not tolerated and will be sanctioned adequately.

1

Question 1.1 (Asymptotic running time) 15 points a. Explain the following two terms.

• Worst-case running time

• Average-case running time

b. Given two algorithms A and B with running times TA(n) and TB(n), what does it mean that TA(n) = O(TB(n)).

2

Question 1.2 (Asymptotic growth) 20 points

a. Sort the following functions by order of growth: !"#!, % &/(

)*% ,2 )*,%

1. 2. 3.

b. Prove that the function f(n) in box 1 and the function g(n) in box 2 satisfy f(n) = o(g(n)). c. Prove that the function g(n) in box 2 and the function h(n) in box 3 satisfy g(n) = o(h(n)).

3

Question 2.1 (Algorithm analysis) 20 points Consider the following procedure: x is an integer MAGIC (x) 1 if x > 0 2 then MAGIC (⌊x/2⌋) 3 if x is odd 4 then print ’1’ 5 else print ’0’ a. Given a positive integer x, what does this procedure print on the screen? Do not prove your

claim. (Your statement should be simple and shouldn’t simply rephrase the computation of the algorithm in mathematical terms.)

b. Let the input “size” be the value of x. Give a recurrence for the running time of the algorithm

in terms of the value of x.

4

c. Solve this recurrence using whatever method you like, in order to determine the running time of procedure MAGIC.

5

Question 2.2 (Correctness proof) 20 points Consider the following procedure: DIVISIBLEBYNINE (x) 1 if x < 10 2 then if x = 0 or x = 9 3 then return “yes” 4 else return “no” 5 else y ← 0 6 while x > 0 7 do y ← y + (x mod 10) 8 x ← ⌊x/10⌋ 9 return DIVISIBLEBYNINE (y) a. Argue that the algorithm always terminates, that is, that the algorithm does not call itself

recursively until all eternity. (Hint: Prove that the value of y in Line 9 is less than the value of x at the beginning of the procedure and draw the right conclusions.)

b. Prove that the algorithm always gives the correct answer. (Hint: Use induction. For the inductive step, argue that y is divisible by 9 if and only if this is true for x. Use the fact that 9 divides 10

k − 1 for any integer k.)

7

Question 3.1 (Greedy algorithms) 25 points You are going on a trip from Halifax to San Francisco. You know that, along the route, there are gas stations at kilometers k1, k2, . . . , kn. You also know that your car can go m kilometers on a tank full of gas. Develop an algorithm that determines at which gas stations to stop so that a. The distance between two consecutive stops is at most m (that is, you can always get from

one stop to the next on a tank full of gas) and b. You make as few stops as possible while respecting the previous condition. The running time of your algorithm should be linear. You do not have to prove that it is. Prove that your algorithm is correct, that is, that it indeed produces a sequence of stops that satisfies the above conditions.

8

Extra space for Question 3.1:

9

Question 3.2 (Divide and conquer) 25 points Let A = (x1, . . . , xn) be an array storing n numbers, and let [a1, b1], . . . , [an, bn] be n intervals with 1 ≤ ai ≤ bi ≤ n, for all 1 ≤ i ≤ n. Your task is to develop an algorithm which, for every interval [ai, bi], computes the value mi = min{xj | ai ≤ j ≤ bi}. Note that your algorithm has to compute all values m1, m2, . . . , mn at the same time. The running time of your algorithm should be O(n lg n). Do not analyze your algorithm and do not prove its correctness.

10

Extra space for Question 3.2:

11

Question 3.3 (Graph algorithms) 25 points Given an undirected graph G, a 3-cycle is a triple of vertices (u, v, w) such that edges (u, v), (u, w), and (v, w) belong to G. Assume that G is given in adjacency list representation. Develop an O(nm)-time algorithm that finds all such cycles in G. Make sure that your algorithm reports every cycle exactly once. Prove that the running time of your algorithm is indeed O(nm).

12

Extra space for Question 3.3:

13