CSC165H1 Lecture Notes - Precondition
29 Oct 2012
School
Department
Course
Professor
3
CSC165H1 Full Course Notes
Verified Note
3 documents
Document Summary
Fall 2011: write a detailed, structured proof that. Fall 2011: prove that tbft(n) (n2), where bft is the algorithm below. Bft(e, n): i n 1 while i > 0: Q[i] 1 i i 1. Q[0] 0 t 0 h 0 while h (cid:54) t: i 0 while i < n: if e[q[h]][i] (cid:54)= 0 and p [i] < 0: P [i] q[h] t t + 1. Q[t] i i i + 1 h h + 1. 18. (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. ) Fall 2011: 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 > 0 real numbers. max 0 for i 0, 1, .
