Assignment 4 - assign PDF

Preview

Summary

assign...

Description

Fundamental Algorithms CSCI-GA.1170-003/Fall 2020 Homework 4 Problem 1. (3 points) Consider the following game: • Choose a number between 1 and 6 inclusive. • Roll three six-sided dice. • Win one point for each die that matches your number and lose one point if no die matches. Does the game favor the player of the house? (Use formula (C.34) from the CLRS appendix.) Problem 2. (3 points) Answer the following questions about quicksort (assume non-randomized quicksort as given in CLRS): (a) Illustrate the operation of quicksort on array A by giving the pivot and the resulting values in A for each partitioning. A = 〈7, 13, 5, 17, 19, 3, 11, 2〉. (b) Is quicksort stable? Prove that it is or give a counterexample. p (c) A particular version of PARTITION runs in Θ(n n) time but guarantees a balanced split every time – each partition contains one half of the original elements. Compare the worstcase running time of quicksort based on this PARTITION with the standard version. (d) What is the running time of quicksort when all elements of A have the same value? (e) What is the running time of quicksort when A contains distinct elements sorted in decreasing order? (f) Investigate pivots in its implementation of quicksort.

and explain how Java selects the

Problem 3. (2 points) In the lecture, we demonstrated that the 101 : running time of O(n lg n) for quicksort.

9 10

splits result in the

Generalize that result to the 1 − α : α splits, where 0 < α ≤ 1/2 is a constant. (Review figure 7.4 and the surrounding text in CLRS.) Problem 4. (4 points) Show that quicksort’s best-case running time is Ω(n lg n). As we did with the worst case in the lecture, be careful not to assume that the best case is 2n to 2n or some other specific split; we want to formulate a recurrence that works regardless of what the actual best case turns out to be. Review section 7.4.1 in CLRS to get started. This is the end of the assignment. 1...