# Difference between revisions of "Chapter 4"

Jump to navigation
Jump to search

(→Heaps) |
|||

Line 94: | Line 94: | ||

===Quicksort=== | ===Quicksort=== | ||

− | :[[4.21]] | + | :[[4.21]]. Use the partitioning idea of quicksort to give an algorithm that finds the median element of an array of <math>n</math> integers in expected <math>O(n)</math> time. (Hint: must you look at both sides of the partition?) |

+ | [[4.21|Solution]] | ||

− | :4.22 | + | :4.22. The ''median'' of a set of <math>n</math> values is the <math>[n/2]</math>th smallest value. |

+ | :(a) Suppose quicksort always pivoted on the median of the current sub-array. How many comparisons would quicksort make then in the worst case? | ||

+ | :(b) Suppose quicksort always pivoted on the <math>[n/3]</math>th smallest value of the current sub-array. How many comparisons would be made then in the worst case? | ||

− | :[[4.23]] | + | :[[4.23]]. Suppose an array <math>A</math> consists of <math>n</math> elements, each of which is ''red'', ''white'', or ''blue'. We seek to sort the elements so that all the ''reds'' come before all the ''whites'', which come before all the ''blues''. The only operations permitted on the keys are: |

+ | ::• ''Examine''(<math>A,i</math>) – report the color of the <math>i</math>th element of <math>A</math>. | ||

+ | ::• ''Swap''(<math>A,i,j</math>) – swap the <math>i</math>th element of <math>A</math> with the <math>j</math>th element. | ||

+ | :Find a correct and efficient algorithm for red–white–blue sorting. There is a linear-time solution. | ||

+ | [[4.23|Solution]] | ||

− | :4.24 | + | :4.24. Give an efficient algorithm to rearrange an array of <math>n</math> keys so that all the negative keys precede all the non-negative keys. Your algorithm must be in-place, meaning you cannot allocate another array to temporarily hold the items. How fast is your algorithm? |

− | :[[4.25]] | + | :[[4.25]]. Consider a given pair of different elements in an input array to be sorted, say <math>z_i</math> and <math>z_j</math> . What is the most number of times <math>z_i</math> and <math>z_j</math> might be compared with each other during an execution of quicksort? |

+ | [[4.25|Solution]] | ||

− | :4.26 | + | :4.26. Define the recursion depth of quicksort as the maximum number of successive recursive calls it makes before hitting the base case. What are the minimum and maximum possible recursion depths for randomized quicksort? |

− | :[[4.27]] | + | :[[4.27]]. Suppose you are given a permutation <math>p</math> of the integers 1 to <math>n</math>, and seek to sort them to be in increasing order <math>[1, . . . , n]</math>. The only operation at your disposal is ''reverse''<math>(p,i,j)</math>, which reverses the elements of a subsequence <math>p_i, . . . , p_j</math> in the permutation. For the permutation [1, 4, 3, 2, 5] one reversal (of the second through fourth elements) suffices to sort. |

− | + | :• Show that it is possible to sort any permutation using <math>O(n)</math> reversals. | |

+ | :• Now suppose that the cost of ''reverse''<math>(p,i,j)</math> is equal to its length, the number of elements in the range, <math>|j - i| + 1</math>. Design an algorithm that sorts <math>p</math> in <math>O(n log^2 n)</math> cost. Analyze the running time and cost of your algorithm and prove correctness. | ||

+ | [[4.27|Solution]] | ||

===Mergesort=== | ===Mergesort=== |

## Revision as of 19:52, 19 September 2020

## Contents

# Sorting

### Applications of Sorting: Numbers

- 4.1. The Grinch is given the job of partitioning players into two teams of players each. Each player has a numerical rating that measures how good he or she is at the game. The Grinch seeks to divide the players as
*unfairly*as possible, so as to create the biggest possible talent imbalance between the teams. Show how the Grinch can do the job in time.

- 4.2. For each of the following problems, give an algorithm that finds the desired numbers within the given amount of time. To keep your answers brief, feel free to use algorithms from the book as subroutines. For the example, , 19 - 3 maximizes the difference, while 8 - 6 minimizes the difference.
- (a) Let be an
*unsorted*array of integers. Give an algorithm that finds the pair that*maximizes*. Your algorithm must run in worst-case time. - (b) Let be a
*sorted*array of integers. Give an algorithm that finds the pair that*maximizes*. Your algorithm must run in worst-case time. - (c) Let be an
*unsorted*array of integers. Give an algorithm that finds the pair that*minimizes*, for . Your algorithm must run in worst-case time. - (d) Let be a
*sorted*array of integers. Give an algorithm that finds the pair that*minimizes*, for . Your algorithm must run in worst-case time.

- 4.3. Take a list of real numbers as input. Design an algorithm that partitions the numbers into pairs, with the property that the partition minimizes the maximum sum of a pair. For example, say we are given the numbers (1,3,5,9). The possible partitions are ((1,3),(5,9)), ((1,5),(3,9)), and ((1,9),(3,5)). The pair sums for these partitions are (4,14), (6,12), and (10,8). Thus, the third partition has 10 as its maximum sum, which is the minimum over the three partitions.

- 4.4. Assume that we are given pairs of items as input, where the first item is a number and the second item is one of three colors (red, blue, or yellow). Further assume that the items are sorted by number. Give an algorithm to sort the items by color (all reds before all blues before all yellows) such that the numbers for identical colors stay sorted.
- For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).

- 4.5. The
*mode*of a bag of numbers is the number that occurs most frequently in the set. The set {4, 6, 2, 4, 3, 1} has a mode of 4. Give an efficient and correct algorithm to compute the mode of a bag of numbers.

- 4.6. Given two sets and (each of size ), and a number , describe an algorithm for finding whether there exists a pair of elements, one from and one from , that add up to . (For partial credit, give a algorithm for this problem.)

- 4.7. Give an efficient algorithm to take the array of citation counts (each count is a non-negative integer) of a researcher’s papers, and compute the researcher’s -index. By definition, a scientist has index if of his or her papers have been cited at least times, while the other papers each have no more than citations.

- 4.8. Outline a reasonable method of solving each of the following problems. Give the order of the worst-case complexity of your methods.
- (a) You are given a pile of thousands of telephone bills and thousands of checks sent in to pay the bills. Find out who did not pay.
- (b) You are given a printed list containing the title, author, call number, and publisher of all the books in a school library and another list of thirty publishers. Find out how many of the books in the library were published by each company.
- (c) You are given all the book checkout cards used in the campus library during the past year, each of which contains the name of the person who took out the book. Determine how many distinct people checked out at least one book.

- 4.9. Given a set of integers and an integer , give an algorithm to test whether of the integers in add up to .

- 4.10. We are given a set of containing real numbers and a real number , and seek efficient algorithms to determine whether two elements of exist whose sum is exactly .
- (a) Assume that is unsorted. Give an algorithm for the problem.
- (b) Assume that is sorted. Give an algorithm for the problem.

- 4.11. Design an algorithm that, given a list of elements, finds all the elements that appear more than times in the list. Then, design an algorithm that, given a list of elements, finds all the elements that appear more than times.

### Applications of Sorting: Intervals and Sets

- 4.12. Give an efficient algorithm to compute the union of sets and , where . The output should be an array of distinct elements that form the union of the sets.
- (a) Assume that and are unsorted arrays. Give an algorithm for the problem.
- (b) Assume that and are sorted arrays. Give an algorithm for the problem.

- 4.13. A camera at the door tracks the entry time and exit time (assume ) for each of persons attending a party. Give an algorithm that analyzes this data to determine the time when the most people were simultaneously present at the party. You may assume that all entry and exit times are distinct (no ties).

- 4.14. Given a list of intervals, specified as pairs, return a list where the overlapping intervals are merged. For the output should be . Your algorithm should run in worst-case time complexity.

- 4.15. You are given a set of intervals on a line, with the th interval described by its left and right endpoints . Give an algorithm to identify a point on the line that is in the largest number of intervals.
- As an example, for no point exists in all four intervals, but is an example of a point in three intervals. You can assume an endpoint counts as being in its interval.

- 4.16. You are given a set of segments on the line, where segment ranges from to . Give an efficient algorithm to select the fewest number of segments whose union completely covers the interval from 0 to .

### Heaps

- 4.17. Devise an algorithm for finding the smallest elements of an unsorted set of integers in .

- 4.18. Give an -time algorithm that merges sorted lists with a total of elements into one sorted list. (Hint: use a heap to speed up the obvious -time algorithm).

- 4.19. You wish to store a set of numbers in either a max-heap or a sorted array. For each application below, state which data structure is better, or if it does not matter. Explain your answers.
- (a) Find the maximum element quickly.
- (b) Delete an element quickly.
- (c) Form the structure quickly.
- (d) Find the minimum element quickly.

- 4.20. (a) Give an efficient algorithm to find the second-largest key among keys. You can do better than comparisons.
- (b) Then, give an efficient algorithm to find the third-largest key among keys. How many key comparisons does your algorithm do in the worst case? Must your algorithm determine which key is largest and second-largest in the process?

### Quicksort

- 4.21. Use the partitioning idea of quicksort to give an algorithm that finds the median element of an array of integers in expected time. (Hint: must you look at both sides of the partition?)

- 4.22. The
*median*of a set of values is the th smallest value. - (a) Suppose quicksort always pivoted on the median of the current sub-array. How many comparisons would quicksort make then in the worst case?
- (b) Suppose quicksort always pivoted on the th smallest value of the current sub-array. How many comparisons would be made then in the worst case?

- 4.23. Suppose an array consists of elements, each of which is
*red*,*white*, or*blue'. We seek to sort the elements so that all the*reds*come before all the*whites*, which come before all the*blues*. The only operations permitted on the keys are:*- •
*Examine*() – report the color of the th element of . - •
*Swap*() – swap the th element of with the th element.

- •
- Find a correct and efficient algorithm for red–white–blue sorting. There is a linear-time solution.

- 4.24. Give an efficient algorithm to rearrange an array of keys so that all the negative keys precede all the non-negative keys. Your algorithm must be in-place, meaning you cannot allocate another array to temporarily hold the items. How fast is your algorithm?

- 4.25. Consider a given pair of different elements in an input array to be sorted, say and . What is the most number of times and might be compared with each other during an execution of quicksort?

- 4.26. Define the recursion depth of quicksort as the maximum number of successive recursive calls it makes before hitting the base case. What are the minimum and maximum possible recursion depths for randomized quicksort?

- 4.27. Suppose you are given a permutation of the integers 1 to , and seek to sort them to be in increasing order . The only operation at your disposal is
*reverse*, which reverses the elements of a subsequence in the permutation. For the permutation [1, 4, 3, 2, 5] one reversal (of the second through fourth elements) suffices to sort. - • Show that it is possible to sort any permutation using reversals.
- • Now suppose that the cost of
*reverse*is equal to its length, the number of elements in the range, . Design an algorithm that sorts in cost. Analyze the running time and cost of your algorithm and prove correctness.

### Mergesort

- 4.28

- 4.30

### Other Sorting Alogrithims

- 4.32

- 4.34

- 4.36

- 4.38

### Lower Bounds

- 4.40

### Searching

- 4.42

### Implementaion Challenges

- 4.44

- 4.46

### Interview Problems

- 4.48

- 4.50

- 4.52

Back to Chapter List