Exam2-Herve-Solutions

pdf

School

University of Maryland, College Park *

*We aren’t endorsed by this school

Course

351

Subject

Computer Science

Date

Feb 20, 2024

Type

pdf

Pages

Uploaded by SargentClover11186

CMSC351 Fall 2022 Exam 2 Herv´ e’s Solutions NAME (Neatly): UID (Neatly): Instructions: Please do all problems on the pages and in the spaces provided. This exam will be scanned into Gradescope and if your answers are not in the correct locations they will not be found or graded!

. THIS PAGE INTENTIONALLY LEFT BLANK! DO NOT USE!

1. Fill in the following as True or False . Any answers that are unclear will be marked as [10 pts] incorrect. Statement True/False Quick Sort is worst-case Θ( n 2 ). True Merge Sort is best-case Θ( n ). False The Master theorem possibly applies to T ( n ) = T ( n − 10) + 8 False If T ( n ) = T ( n − 1) + 1 and T (0) = 1, then T ( n ) = Θ( n ) True Tree Sort is another comparison-based sorting algorithm; its worst case running time is Θ( n ) False 2. We are trying to apply the Master theorem to T ( n ) = T (3 n/ 4) + n + 7 What are the values [6 pts] for a , b and f ( n )? a 1 b 4/3 f ( n ) n + 7 3. Using a 1-indexed array representing a heap, fill in the 4 values below [8 pts] parent index left child index right child index 22 44 45 2 99 2 100 2 100 + 1

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

4. An algorithm has the following formula for its running time: T 1( n ) = 3 T 1( n/ 3) + n T 1(1) = 1 (a) If we try to apply the Master theorem, what would be the values of a , b , and f ( n )? [3 pts] Solution: a = 3, b = 3, f ( n ) = n (b) Use the Master theorem to find the Θ of T 1( n ). Show your work. [8pts] Solution: log b a = log 3 3 = 1 Case number 1? Is f ( n ) = n = O ( n c ) for some c < 1? No; we are not in case number 1 Case number 2? Is f ( n ) = n = Θ( n 1 ) ? Yes. We are in case number 2. T ( n ) = Θ( n lg n ).

(c) Use the Master theorem to find the Θ of T 2( n ) = 9 T 2( n/ 3) + n 2 √ n Show your work. [8pts] Solution: log 3 9 = log 3 9 = 2 Case number 1? Is f ( n ) = n 2 √ n = O ( n c ) for some c < 2? No; we are not in case number 1 Case number 2? Is f ( n ) = n 2 √ n = Θ( n 2 ) ? No; we are not in case number 2. Case number 3? Is f ( n ) = n 2 √ n = Ω( n c ) for some c > 2? Yes, for example c = 2.1 ? We are in case number 3. T ( n ) = Θ( n 2 √ n ).

5. We are performing binary search on the array below. Luckily, after exactly 2 equality compar- isons, we find the value we were searching for. What possible value(s) were we searching for? [6 pts] index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 value 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 Possible Solution: 1st equality comparison is at index (0 + 16) / 2 = 8, with 80 Going left, the 2nd equality comparison is either at index (0+7) / 2 = 3 or at index (9+16) / 2 = 12. Thus, we were searching for either 30 or 120 6. An algorithm has the following formula for its running time: T ( n ) = 8 T ( n/ 8) + n T (1) = 1 (a) Using derivation (drilling down), find an exact formula to express T(n) as a function of T( n/ 8 k ). Drill down at least 2 times. Solution: [8 pts] We have: T ( n ) = 8(8 T ( n/ 8 2 ) + n/ 8) + n T ( n ) = 8 2 T ( n/ 8 2 ) + 2 n T ( n ) = 8 2 (8 T ( n/ 8 3 ) + n/ 8 2 ) + 2 n T ( n ) = 8 3 T ( n/ 8 3 ) + 3 n T ( n ) = 8 3 (8 T ( n/ 8 4 ) + n/ 8 3 ) + 3 n T ( n ) = 8 4 T ( n/ 8 4 ) + 4 n T ( n ) = 8 k T ( n/ 8 k ) + kn

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

(b) Find an exact formula for T ( n ) as a function of n . You do NOT need to prove it (it would be a proof by induction). You can assume that n is a power of 8. [5 pts] Solution: We have: T ( n ) = 8 k T ( n/ 8 k ) + kn The base case is reached when n/ 8 k = 1 which is when n = 8 k so lg n = k lg 8 so lg n = 3 k and so k = 1 3 lg n . Thus: T ( n ) = nT (1) + n (lg n/ 3) = n + n (lg n/ 3) (c) Based on your exact formula for T ( n ), what is the Θ of T ( n ) (you do not need a formal proof but the logic must be correct)? If you are not comfortable with your derivation [5 pts] result, you can use the Master theorem (showing your work) for this part of the question (and you will get full credit for this part if correct). Solution: Θ( n lg n ) Using the Master theorem, log b a = log 8 8 = 1 We are in case 2. T ( n ) = Θ( n lg n )

7. Here is an array representing a heap: index 0 1 2 3 4 5 6 7 8 value 400 150 230 100 110 170 130 20 25 (a) Draw the corresponding tree [3 pts] Solution: 400 150 100 20 25 110 230 170 130 (b) Delete once from the heap, i.e. show the heap after the deletion. Do not just show the resulting heap, show the heap after every step. Use the next page if you need extra space. [10 pts] Solution: We delete 400, 25 takes its place 25 150 100 20 110 230 170 130

Note to the TAs: if students leave 400 in the old location in the tree as 25, that is fine, no deduction (because that is how we showed heap sort works). We start heapifying on 25, swapping 25 and 230 230 150 100 20 110 25 170 130 We keep heapifying on 25, swapping 25 and 170 230 150 100 20 110 170 25 130 We are done

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

8. We are considering 2 strategies to search for values in an unsorted array: Strategy A: Sequential search for all the searches Strategy B: Sorting the array using merge sort, then performing all the searches as efficiently as possible. Assume that merge sort takes exactly 2 n lg n (guaranteed) in order to sort an array of n integers. The array contains n numbers (we expect n to be big) and we will be performing exactly n/ 4 searches. We are only interested in the worst case scenario. (a) With strategy A, how many comparisons will you make for all the n/ 4 searches, in the worst case? [5 pts] Solution: n 2 / 4 comparisons (we are performing n/4 searches and each search can involve n com- parisons since we are searching sequentially) (b) With strategy B, how will you search (i.e. what algorithm would you use)? [5 pts] Solution: Using binary search, since the array will have been sorted. (c) With strategy B, what is Θ of performing everything that you need to do so that you can perform all the n/4 searches (not one search but all of them), in the worst case? Show your work. [5 pts] Solution: Sorting the array will take Θ( n lg n ) and each search will take lg n comparisons in the worst case using binary search. Thus: Total = Θ( n lg n ) + ( n/ 4) lg n = Θ( n lg n ) (d) With n expected to be big ( ≥ 1000), which strategy do think is best and why? [5 pts] Solution: Strategy B. It is Θ( n lg n ) Strategy A is Θ( n 2 )

Exam2-Herve-Solutions

Related Documents