Class Notes
(808,662)

Canada
(493,335)

University of Ottawa
(32,193)

Computer Science
(25)

CSI3105
(1)

Sylvia Boyd
(1)

Lecture

# 3105A111sol.pdf

Unlock Document

University of Ottawa

Computer Science

CSI3105

Sylvia Boyd

Fall

Description

CSI 3105 Assignment 1 -- 2011
Solutions
1. a) boyd(9)
___________|______________ ______
| | |
boyd(4) boyd(7) boyd(8)
| | ____
| | | | | |
boyd(2) boyd(5) boyd(6) boyd(3) boyd(6) boyd(7)
| | ___ | |
| | | | | | | | | |
boyd(0) boyd(3) boyd(4) boyd(1) boyd(4) boyd(5) boyd(1) boyd(4) boyd(5) |
| |_ _ |
| | | | | | |
boyd(0) boyd(3) boyd(4) boyd(0) boyd(3) boyd(4) |
repeat part of tree in circle
on left
b)
n 0 1 2 3 4 5 6 7 8 9
T(n) 1 1 1 1 1 4 7 13 22 37
c)
Claim: T(n) > 3 n/5for n ≥ 5
Proof of Claim: By induction.
Base Case :
(Note: We need to verify the claim for the first 5 values of n, i.e. for n = 5, 6, 7, 8 and 9,
since we need to use the Induction Hypothesis for value n-5 later in the Induction Step).
For n = 5, T(n) = 4 > 3 5/5? Yes! The claim is true for n = 5.
6/5
For n = 6, T(n) = 7 > 3 7/5 Yes! The claim is true for n = 6.
For n = 7, T(n) = 13 > 3 ? Yes! The claim is true for n = 7.
For n = 8, T(n) = 22 > 3 8/5 ? Yes! The claim is true for n = 8.
For n = 9, T(n) = 37 > 3 9/5 ? Yes! The claim is true for n = 9.
Induction Hypothesis (I.H.)
The claim is true for all m such that 5 ≤ m < n, i.e. T(m) > 3 m/5 for all m such that
5 ≤ m < n.
Induction Step (I.S)
Prove the claim is true for n, where n ≥ 10 (note that we have already shown it is true for
n = 5, 6, 7, 8 and 9). Consider the call tree which corresponds to the algorithm. The number of calls for T(n)
is 1 (for the initial call) + T(n-5) (for the left subtree under the initial call) + T(n-2) (for
the middle subtree under the initial call) + T(n-1) (for the right subtree under the initial
call).
Therefore,
T(n) = 1 + T(n-5) + T(n-2) + T(n-1) (from the above explanation)
> 1 + 3 (n-5)/5+ 3 (n-2)/5+ 3 (n-1)/5 (since n≥10 for the I.S., we know
each of n-5, n-2, and n-1 are 3 + 3 + 3 (since 1 > 0)
> 3 (n-5)/5+ 3 (n-5)/5+ 3 (n-5)/5 (since 3 (n-2)>3 (n-5)/, 3(n-1)>3 (n-5))5
(n-5)/5
= 3 (n-5+5)/5 ) (grouping the terms)
= 3 (adding the exponents)
= 3 n/5
Thus T(n) > 3 n/5for n ≥ 5, as required, and the claim is proved.
2. (We assume that the input n is a non-negative integer)
int boydNum(int n)
{
index i;
int b[0..n];
while ((i <= n) && (i <= 4)) {
b[i] = i;
i++
}
for (i = 5; i <= n; i ++)
b[i] = b[i-1] + b[i-2] + b[i-5] + 2;
return b[n];
}
Worst Case Analysis :
Fixed input size : n, the index of the term of the Boyd sequence we wish to find.
Basic operation being counted : Additions and subtractions (but not loop counter
additions, as specified in the question)
Input that gives worst case: All the same.
Analysis:
All the additions/subtractions occur inside the for loop (3 additions and 3 subtractions per
loop). There are n-4 iterations of the for loops, so
W(n) = 6 * (n-4) = 6n – 24. 3.
a) Iteration 1: low = 1, high = 8, mid = 4
Iteration 2: low = 1, high = 3, mid = 2
Iteration 3: low = 1, high = 1, mid = 1
After this: low = 1, high = 0 and we do not enter the loop
Total number of comparisons is 2 per iteration for 3 iterations = 6
From class: W(n) = 2lgn + 2, so W(8) = 2 (lg 8) + 2 = 8
So in this case we get fewer comparisons than worst case.
b) Iteration 1: low = 1, high = 16, mid = 8
Iteration 2: low = 9, high = 16, mid = 12
Iteration 3: low = 9, high = 11, mid = 10
Iteration 4: low = 9, high = 9, mid = 9
After this: low = 9, high = 8, and we do not enter the loop.
Total number of comparisons is 2 per iteration for 4 loop iterations = 8.
From class: W(n) = 2lgn + 2, so W(16) = 2 (lg16) + 2 = 10
So in this case we get fewer comparisons than worst case.
4. a)
Fixed input size: n
Basic operation being counted: multiplications
Input that gives worst case: all the same
Analysis:
First consider the number of multiplications that occur when i = 1. When i = 1, we
have j= 1, 2, 3, ...,n. For each of these values of j, we have the k loop goes from 1 to
j, with two multiplications h

More
Less
Related notes for CSI3105