Assignment #2: Analysis of Recursive Algorithms



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, unjusti ed, 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:
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.
S(n) =
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
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
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
(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
), and informally state
why your algorithm would have worst-case running time O(n
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


There are no reviews yet.

Be the first to review “Assignment #2: Analysis of Recursive Algorithms”

Your email address will not be published.