task08

WEEK 08 Name: Collaborators (if any): 1. Tasks 1.1. True or False. Choose T or F for each of the following statements and briefly explain why. (1) T/F In the potential method for amortized analysis, the potential energy should never go negative. (2) T/F The quicksort algorithm that uses linear-time median finding to run in worst-case O ( n log n ) time requires Θ( n ) auxiliary space. (1) True. Energy can’t be negative (2) The worst case scenario would be O(logN) 2. Exercises/Problems 2.1. Amortized Analysis. Design a data structure to maintain a set S of n dis- tinct integers that supports the following two operations: (1) Insert ( x, S ) : insert integer x into S (2) Remove.Bottom.Half ( S ) : remove the smallest ⌈ n 2 ⌉ integers from S Describe your algorithm and give the worse-case time complexity of the two operations. Then carry out an amortized analysis to make Insert(x, S) run in amortized O(1) time, and Remove.Bottom.Half(S) run in amortized 0 time. (1) For the insert I would use a mean Heap data structure and for every oper- ation we would be getting a O(1) (2) For the Remove bottom half assuming I want to remove half of the numbers in S. I would take the length of S and start removing n/2 times the numbers in my heap that are on the right. Assuming the bigger numbers are on the left. Date : November 5, 2023. 1

2 WEEK 08 2.2. Quicksort. Write up some code for a quicksort algorithm. Be sure to specify which pivot selection method you are using (reminder on pivot selection choices from lecture: always pick the fist element as pivot, always pick the lat element as pivot, pick the median as pivot, or pick a random pivot). Code should be clearly commented to provide context and steps taken. 1 # Function to find the p a r t i t i o n p o s i t i o n 2 def p a r t i t i o n ( array , low , high ) : 3 4 # Choose the rightmost element as pivot 5 pivot = array [ high ] 6 7 # Pointer f o r greater element 8 i = low − 1 9 10 # Traverse through a l l elements 11 # compare each element with pivot 12 f o r j in range ( low , high ) : 13 i f array [ j ] <= pivot : 14 15 # I f element smaller than pivot i s found 16 # swap i t with the greater element pointed by i 17 i = i + 1 18 19 # Swapping element at i with element at j 20 ( array [ i ] , array [ j ] ) = ( array [ j ] , array [ i ] ) 21 22 # Swap the pivot element with 23 # the greater element s p e c i f i e d by i 24 ( array [ i + 1 ] , array [ high ] ) = ( array [ high ] , array [ i + 1 ] ) 25 26 # Return the p o s i t i o n from where p a r t i t i o n i s done 27 return i + 1 28 29 30 # Function to perform quicksort 31 def quicksort ( array , low , high ) : 32 i f low < high : 33 34 # Find pivot element such that 35 # element smaller than pivot are on the l e f t 36 # element greater than pivot are on the right 37 pi = p a r t i t i o n ( array , low , high ) 38 39 # Recursive c a l l on the l e f t of pivot 40 quicksort ( array , low , pi − 1)