Class Notes
(807,242)

Canada
(492,664)

University of Toronto St. George
(42,781)

Computer Science
(737)

CSC165H1
(160)

Nathalie Fournier
(31)

Lecture

# tut07handout.pdf

Unlock Document

University of Toronto St. George

Computer Science

CSC165H1

Nathalie Fournier

Fall

Description

CSC165H1F Tutorial # 7 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).
Dept. of Computer Science, University of Toronto, St. George Campus Page 1 of 3 CSC165H1F Tutorial # 7 Fall 2011
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.

More
Less
Related notes for CSC165H1