COE 428 Midterm: COE428 - Winter 2010 Midterm

• School: Ryerson University
• Department: Computer Engineering
• Course: COE 428
• Professor: All

Document Summary

Examiner (circle the name of your professor): o. das, r. sedaghat. Pages without a name will not be graded. Answer all of the following questions in the space provided. ________________________________________________________________________: an algorithm takes time roughly equal to cn2 where c = 2. When the input size is 1000, it takes 5 second. 45, 68, 21, 11, 17, 115: given the recurrence t(n) = t(n/2) + lgn. Draw the recursion tree and guess the asymptotic tight bound for t(n). Then use the substitution method to verify your answer. Circle true or false for each statement below. (marks deducted for wrong answers) Page 3 (the standard "balance" algorithm assumes that the input is a sequence of start-tags and end-tags. Each tag is processed sequentially and a stack push or pop operation is performed. Here, start-tags are lower- case letters and end-tags are upper-case letters. For example, "aa" balances but "ab" does not balance. ) It encounters an error or the input sequence ends.