tut07solution.pdf

4 Pages
122 Views
Unlock Document

Department
Computer Science
Course
CSC165H1
Professor
Nathalie Fournier
Semester
Fall

Description
CSC165H1F Tutorial # 7 | Sample Solutions Fall 2011 1. Write a detailed, structured proof that 8f : N ! R ;8g : N ! R ;g 2 O(f) ) g 2 O(f ) 2 (where f and g are de▯ned in the obvious way: 8n 2 N;f (n) = f(n) ▯ f(n), and similarly for g). (I show only the ▯nished proof here, not its development.) + + Assume f : N ! R and g : N ! R . Assume g 2 O(f). + Then 9c 2 R ;9B 2 N;8n 2 N;n > B ) g(n) 6 c ▯ f(n). # de▯nition of O Let c 0 R + and B 20N be such that 8n 2 N;n > B ) g(n0 6 c ▯ f(n).0 2 2 # Show that g 2 O(f ): Let c = c . Then c 2 R . + # because c 2 R + 1 0 1 0 Let B 1 B . 0hen B 2 N.1 # because B 20N Assume n 2 N and n > B = B . 1 0 Then g(n) 6 c 0 f(n) (because n > B ),0 so g (n) = g(n) ▯ g(n) 6 (c ▯ f(n)) ▯ (c ▯ f(n)) = c ▯ f(n) ▯ f(n) = c ▯ f (n). 0 0 0 1 Hence, 8n 2 N;n > B ) 1 (n) 6 c ▯ f (1). 2 + 2 2 Then 9c 2 R ;9B 2 N;8n 2 N;n > B ) g (n) 6 c ▯ f (n). Thus, g 2 O(f ).2 # by de▯nition of O 2 2 Therefore, g 2 O(f) ) g 2 O(f ). Then, 8f : N ! R ;8g : N ! R ;g 2 O(f) ) g 2 O(f ). 2 2. Prove that T (n) 2 ▯(n ), where BFT is the algorithm below. BFT BFT(E;n): 1. i n ▯ 1 2. while i > 0: 3. P[i] ▯1 4. Q[i] ▯1 5. i i ▯ 1 6. P[0] n 7. Q[0] 0 8. t 0 9. h 0 10. while h 6 t: 11. i 0 12. while i < n: 13. if E[Q[h]][i] 6= 0 and P[i] < 0: 14. P[i] Q[h] 15. t t + 1 16. Q[t] i 17. i i + 1 18. h h + 1 (Although this is not directly relevant to the question, this algorithm carries out a breadth-▯rst traversal of the graph on n vertices whose adjacency matrix is stored in E.) 2 2 2 We show that T BFT (n) 2 ▯(n ) by proving T BFT (n) 2 O(n ) and T BFT (n) 2 (n ). Dept. of Computer Science, University of Toronto, St. George Campus Page 1 of 4 CSC165H1F Tutorial # 7 | Sample Solutions Fall 2011 TBFT (n) 2 O(n ) : + Let c = 16 and B = 1. Then, c 2 R and B 2 N. Assume n 2 N, n > B = 1, and E is an arbitrary input of size n. One of the tricky features of this algorithm is that the main loop depends on the values of h and t, but the algorithm does not explicitly bound either value. To prove an upper bound on T BFT(n), we start by proving a bound on the value of t. Namely, we show that at any point during the execution of the algorithm, t 6 n. From lines 1{9, when the main loop (lines 10{18) begins execution, h = t = 0, P[0] = n, Q[0] = 0, and P[i] = Q[i] = ▯1 for i = 1;2;:::;n ▯ 1. Note that the value of t is changed only on line 15, and this line is executed only when P[i] < 0 (among other conditions). Moreover, each time t is incremented, the value of Q[t] is set to a natural number (on line 16), so that at any point during the execution of the algorithm, Q[0:::t] 2 N and Q[t + 1:::n ▯ 1] = ▯1. Since h 6 t (from line 10), this means that Q[h] > 0 is always true inside the main loop. Hence, on line 14, the assignment P[i] = Q[h] guarantees that P[i] > 0 from that point on. This means that the value of t can increase at most once for each value of i = 0;1;:::;n ▯ 1 (it increases only when P[i] < 0, at which point P[i] is set to a natural number), i.e., t 6 n. From the algorithm, ▯ line 1 takes 1 step; ▯ lines 2{5 take 4 steps for one iteration, and are executed exactly n ▯ 1 times (once for each value of i = n ▯ 1;n ▯ 2;:::;1), plus 1 more step for the last execution of line 2, for a total of 4(n ▯ 1) + 1 = 4n ▯ 3 steps; ▯ lines 6{9 take 4 steps; ▯ lines 12{17 take at most 6 steps for one iteration (if the condition of the if statement is true at every iteration), and are executed exactly n times (once for each value of i = 0;1;:::;n ▯ 1), plus 1 more step for the last execution of line 12, for a total of at most 6n + 1 steps; ▯ lines 10{18 take at most 6n + 1 + 3 = 6n + 4 steps for one iteration, and are executed at 2 most n times (since t 6 n, as shown above), for a total of at most 6n + 4n steps; ▯ so in total, the algorithm takes at most 1 + 4n ▯ 3 + 4 + 6n + 4n = 6n + 8n + 2 steps. Since n > 1, this means that the number of steps executed by the algorithm on input (E;n) is 6 6n + 8n + 2 6 6n + 8n + 2n = 16n . 2 Since (E;n) was arbitrary, 8n 2 N;n > 1 ) T BFT (n) 6 16n . 2 Therefore, TBFT (n) 2 O(n ). TBFT (n) 2 (n ): + Let c = 1 and B = 1. Then, c 2 R and B 2 N. Assume n 2 N and n > B = 1. Consider an input (E;n) such that E[i][j] = 1 for all indices 0 6 i < n;0 6 j < n. The ▯rst time that lines 12{17 are executed, the condition of the if statement will be true for all values of i = 0;1;:::;n ▯ 1 so at the end of the loop, t will have value at least n (since t starts at 0 and gets incremented n times). Since lines 12{17 always get executed exactly n times (once for each value of i = 0;1;:::;n ▯ 1), they take at least n steps. This means that lines 10{18 will get executed for every value of h = 0;1;:::;n ▯ 1 (at least), 2 and take at least n steps at each iteration, for a total of at least n steps. So the number of steps on input (E;n) is > n . 2 2 Hence, 8n 2 N;n > 1 ) T BFT (n) > n . Therefore, TBFT (n) 2 (n 2). Dept. of Computer Science, University of Toronto, St. George Campus Page 2 of 4 CSC165H1F Tutorial # 7 | Sample Solutions Fall 2011 3. Find a tight bound on the worst-case running time of the following algorithm. (This example was started during lecture, but it was not ▯nished.) # Precondition: L is a list that contains n
More Less

Related notes for CSC165H1

Log In


OR

Join OneClass

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

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit