York University
CSC 3101
CSE 3101 Final exam Dec 16, 2017
1. (6 points) Prove that the following algorithm for finding Fibonacci numbers is correct.
Recall that for Fibonacci numbers Fn; n 2 Z; n ≥ 0, are defined as F0 = 1; F1 = F2 = 1
and for n > 1, Fn = Fn-1 + Fn-2. Assume that \for i = 1 to k" implies that the body of
the loop is executed k times.
Fib(n)
...[Show More]
CSE 3101 Final exam Dec 16, 2017
1. (6 points) Prove that the following algorithm for finding Fibonacci numbers is correct.
Recall that for Fibonacci numbers Fn; n 2 Z; n ≥ 0, are defined as F0 = 1; F1 = F2 = 1
and for n > 1, Fn = Fn-1 + Fn-2. Assume that \for i = 1 to k" implies that the body of
the loop is executed k times.
Fib(n)
1 // return the n-th Fibonacci number Fn
2 if n = 0
3 then return 0
4 else last 0
5 current 1
6 for i 2 to n
7 do temp last + current
8 last current
9 current temp
10 return current
page 2 of 14
CSE 3101 Final exam Dec 16, 2017
2. (4 points) Suppose T(1) = 1 and for n > 1,
T(n) = 8T n2 + n4:
Solve this recurrence using the Master Theorem. You are not permitted to use results or
theorems from any book other than our text for this question.
3. (4 points) Suppose you have an array of n integers whose values are from the range
[1; :::; npn], and each integer is a multiple of pn. Describe a o(n log n) algorithm for
this problem. You are not allowed to use radix sort. You can assume that n is a perfect
square.
page 3 of 14
CSE 3101 Final exam Dec 16, 2017
4. (6 points) Consider the following method. Assume again that \for i = 1 to k" implies that
the body of the loop is executed k times.
Mystery(n)
1 r 0
2 for i 1 to n - 1
3 do for j i + 1 to n
4 do for k 1 to j
5 do r r + 1
6 return r
(a) (5 points) Find the value returned by the above method as a function of n.
(b) (1 point) Express the above as a Θ() expression. No proof is needed.
page 4 of 14
CSE 3101 Final exam Dec 16, 2017
5. (8 points) Let T[1::n] be a sorted array of n distinct integers.
(a) (4 points) Give a O(log n) time algorithm to find an index i such that T[i] = i (if one
exists).
(b) (4 points) Prove that your algorithm in part (a) is correct
page 5 of 14
CSE 3101 Final exam Dec 16, 2017
6. (4 points) For this question you will use recursion to find the sum of the numbers in an
array. Your algorithms must have O(n) running time in each case, and should do O(1)
work outside of the recursive calls, i.e. you are not allowed to use loops.
(a) (2 points) Write a function to find the sum of the n numbers in an array A[1:::n] using
one recursive call.
[Show Less]
