DATA ANALYSIS > EXAM > midterm. Exam - Université de Saint-Boniface COMP 3170 (All)

midterm. Exam - Université de Saint-Boniface COMP 3170

Document Content and Description Below

Comp 3170 - Analysis of Algorithms & Data Structures Midterm Shahin Kamalli University of Manitoba - Winter 2018 March 2, 2018 Write your name and student id here: Peter Griffin ‘What makes a river so restful to people is that it doesn’t have any doubt - it is sure to get where it is going, and it doesn’t want to go anywhere else.’ Hal Boyle • Do not open this booklet until instructed. • You are not allowed to use any printed/written material, laptops/cell-phones. Please turn off your cell phones and put them in your bags. • Manage your time. We start the exam at 10:30 and end the exam at 11:25. You have 55 minutes. • There are 6 pages (including this cover page). Write your answers in the provided boxes. • In the unlikely case that you find the exam too long/hard, do not panic. The marks will be scaled so that the highest mark gets the full mark. • There are more important things in life than this exam. So, relax and smile. Also, there are more important components to this course than the midterm. So, relax further and smile more (but still manage your time while relaxing). 1. Short Answer (20 marks) Provide your short answers in the provided boxes. There is no need to justify your answers. 1. True or False: n 1.001 ∈ ω(n log n) True Note: In general, remember that n (for > 0) is asymptotically larger than poly-logarithmic functions like log n or log10000 n. 2. True or False: n log log n log n ∈ o(n) True Note: log log n is asymptotically smaller than log n. 3. Consider the following pseudocode: foo(n) 1. i ← 1 2. prod ← 1 3. while i < min{n, 2018} do 4. for j = i to n do 5. prod ← prod × j 6. i ← i × 3 7. return prod What is the worst-case running time of foo(n)? Express your answer using Θ-notation in terms of n, and be as precise as possible. Θ(n) Note: In the asymptotic sense, min{n, 2018} = 2018 (since we consider arbitrary large values of n in the asymptotic analysis). So, the while loop iterates a constant number of time. The second loop runs in Θ(n) in a in its longest iteration. 4. Assume T(1) = 5 and T(n) = 9T(n/3)+n 2 . Give an expression for the run-time of T(n) using Θ notation. You might use Master theorem. Only the final answer is required. Case 2 of Master theorem gives T(n) ∈ Θ(n 2 log n) 5. True or false: The cost of QuickSort and QuickSelect are the same, if the same pivot-choosing algorithm is used. False Note: The cost of QuickSort is always more than QuickSelect. For example, with the best pivot-selection which takes the median, QuickSort runs in Θ(n log n) and QuickSelect runs in Θ(n). 6. True or false: Quick-select runs in Θ(n) in the average case. True 7. True or false: Using an augmented AVL tree, it is possible to find the median of n items in o(n). True Note: Median is a special case of selection, which can be done Θ(log n) in a properly augmented AVL tree. 8. True or false: A binary search tree can have height Θ(n). True Note: consider a chain of nodes so that each internal node has only one node with smaller key on its left. Marking Scheme: parts 3 and 4 each

[Show More]

Last updated: 3 years ago

Preview 1 out of 6 pages

Buy Now

Instant download