Midterm 2010 PDF

Preview

Summary

Download Midterm 2010 PDF

Description

Q1:45Seconds Q2:



lg n i 0

(lg n  i )

Lower Bound: d = ½ Upper Bound: d= 1

Q3: False True False False True True False False True True

Q4: a) aaAbBA Balanced b) aaabbBABAA Error: Not-Balance c) abBbaABABa Error: Not-Balance

Q5: Lower Bound Guess: T (n) ≥ cn (log7 n + 1) = Ω (n lgn) Upper Bound Guess: T (n) ≤ O (n lgn) T (n) = Θ (n lgn)



Ryerson University Department of Electrical & Computer Engineering COE428 Midterm Examination Name:________________________

March, 8, 2010 Section:________

ID #:________________________ Time: 60 min. Examiner (Circle the name of your Professor): O. Das, R. Sedaghat Write your name on each page. Pages without a name will not be graded. Answer all of the following questions in the space provided. Closed book. No Calculator, No questions

_________________________________________________________________________ 1) An algorithm takes time roughly equal to cn2 where c = 2. When the input size is 1000, it takes 5 second to execute. Which of the following are possible times for a problem size of 3000? Circle the correct answer. 45, 68, 21, 11, 17, 115 2) 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.

Page 2 Name:________________________

Section:________

3) Let f(n) = (n3) Circle True or False for each statement below. (Marks deducted for wrong answers) True or false: f(n) = O(n2) True or false: f(n) = O(n3 lgn3) True or false: f(n) = Θ(2lg n) True or false: f(n) = O(n1.5) True or false: f(n) = Ω(n3) True or false: f(n) = Ω(n lgn3) True or false: f(n) = Θ(n2 lgn2) True or false: f(n) = O(2lg n) True or false: f(n) = Ω(n1.5) True or false: f(n) = O(n3)

Page 3 Name:________________________

Section:________

4) Use the standard "Balance" algorithm to determine if the following expressions are balanced. (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 lowercase letters and end-tags are upper-case letters. For example, "aA" balances but "aB" does not balance.) The standard algorithm processes each tag until: It encounters an error or the input sequence ends. For each sequence below, show how the stack evolves as each tag is processed. If an error occurs, stop processing a nd i ndicate t he t ype of error. (Note: as sume t he s tack has unl imited capacity s o an overflow cannot occur; underflow errors, however, can happen.) a) aaAbBA b) aaabbBABAA c) abBbaABABa

Page 4 Name:________________________

Section:________

5) Consider the following sort algorithm: Step 1: If there are no numbers or only 1 number to sort, then stop Step 2: Otherwise, split the array A[1..n] into 2 sub-arrays, one with the size n / 7 and the other with the size 6n / 7 Step 3: Sort the sub-array at left Step 4: Solve the sub-array at right Step 5: Merge both sub-arrays Step 6: Return to Step 1

a) What is the time T of each step (as a function of n)? Step 1: Step 2: Step 3: Step 4: Step 5: Step 6: b) Calculate the total time T(n) of the algorithm.

c) Draw the recursion tree for T(n) to guess the complexity of T(n).

Page 5 Name:________________________

Section:________...