Class Notes (808,662)
CSI3105 (1)
Lecture

# 3105A111sol.pdf

7 Pages
445 Views

School
University of Ottawa
Department
Computer Science
Course
CSI3105
Professor
Sylvia Boyd
Semester
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

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.