CSC236 Summer 2017

Assignment #2: Analysis of Recursive Algorithms

Due July 13th, by 6:00 pm

The aim of this assignment is to give you some practice analyzing runtime and proving correctness of recursive algorithms.

For each question, please write up detailed answers carefully. Make sure that you use notation and terminology correctly,

and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and

terminology, and for making incorrect, unjustied, ambiguous, or vague claims in your solutions. You should clearly cite any

sources or people you consult, other than the course notes, lecture materials, and tutorial exercises.

Your assignment must be typed to produce a PDF document A2.pdf (hand-written submissions are not acceptable).

You may work on the assignment in groups of 1, 2, or 3, and submit a single assignment for the entire group on MarkUs.

1. Consider the following recurrence relations:

(a)

S(n) = (

1; if n = 0

(S(n 1))2 + 2S(n 1) if n > 0

Hint: let T(n) = S(n) + 1, and try to nd a closed form of T(n) rst.

(b)

S(n) =

8

>>>><

>>>>:

0; if n = 0

1; if n = 1

S(n 2) + 2n 1 if n > 1 and n is even

S(n 2) + 3n if n > 1 and n is odd

For each recurrence relation, nd a closed from for S(n) and brie y describe how you get the closed form. Then prove

the closed form is correct. Based on the closed form, state a conjecture for f(n) such that S(n) 2 (f(n)), and prove

the bound is correct.

2. Assume S(n) is monotonic non-decreasing. We do not know the value of S(n) for every n 2 N except when n = 2k

for

some k 2 N, in which case S(n) = n log n + 3n 5. Show that S(n) 2 (n log n) for all n > 0 2 N, not just special

cases.

Hints: you may need to use one of the following facts (or both, or none of them) in your proof:

(a) 8n > 1 2 N; 9k 2 N, such that 2k1 n 2

k

.

(b) for functions f(n); g(n) : N ! R

+, if limn!1 f(n)=g(n) = 1, then f(n) 2 (g(n))

3. Consider the problem of nding the maximum sum of consecutive values in a sequence of integers. For example, the

maximum consecutive sum in 2; 5; 3; 1; 1; 4 is 3 + (1) + (1) + 4 = 5, and the maximum consecutive sum in

1; 2; 3 is 3. Let n be the number of integers in the sequence.

(a) Give a brute force algorithm that solves the problem with worst-case running time O(n

2

), and informally state

why your algorithm would have worst-case running time O(n

2

).

Consider a Divide & Conquer approach to this problem, based on the idea that, for any sequence, either the middle

element is included in the maximum consecutive sum, or it is not. Based on the idea above, consider how many

subproblems the original problem would be split into, and approximately how large each subproblem

Sale!

# Assignment #2: Analysis of Recursive Algorithms

$30.00

## Reviews

There are no reviews yet.