# Difference between revisions of "Chapter 4"

Jump to navigation
Jump to search

Line 22: | Line 22: | ||

− | :[[4.5]] | + | :[[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 <math>n</math> numbers. |

+ | [[4.5|Solution]] | ||

− | :4.6 | + | :4.6. Given two sets <math>S_1</math> and <math>S_2</math> (each of size <math>n</math>), and a number <math>x</math>, describe an <math>O(n log n)</math> algorithm for finding whether there exists a pair of elements, one from <math>S_1</math> and one from <math>S_2</math>, that add up to <math>x</math>. (For partial credit, give a <math>\Theta(n^2)</math> algorithm for this problem.) |

− | :[[4.7]] | + | :[[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 <math>h</math>-index. By definition, a scientist has index <math>h</math> if <math>h</math> of his or her <math>n</math> papers have been cited at least <math>h</math> times, while the other <math>n-h</math> papers each have no more than <math>h</math> citations. |

+ | [[4.7|Solution]] | ||

− | :4.8 | + | :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]] | + | :[[4.9]]. Given a set <math>S</math> of <math>n</math> integers and an integer <math>T</math>, give an <math>O(n^{k-1}log n)</math> algorithm to test whether <math>k</math> of the integers in <math>S</math> add up to <math>T. |

+ | [[4.9|Solution]] | ||

− | :4.10 | + | :4.10. We are given a set of <math>S</math> containing <math>n</math> real numbers and a real number <math>x</math>, and seek efficient algorithms to determine whether two elements of <math>S</math> exist whose sum is exactly <math>x</math>. |

+ | :(a) Assume that <math>S</math> is unsorted. Give an <math>O(n log n)</math> algorithm for the problem. | ||

+ | :(b) Assume that <math>S</math> is sorted. Give an <math>O(n)</math> algorithm for the problem. | ||

− | :[[4.11]] | + | :[[4.11]]. Design an <math>O(n)</math> algorithm that, given a list of <math>n</math> elements, finds all the elements that appear more than <math>n/2</math> times in the list. Then, design an <math>O(n)</math> algorithm that, given a list of <math>n</math> elements, finds all the elements that appear more than <math>n/4</math> times. |

+ | [[4.11|Solution]] | ||

===Applicatoins of Sorting: Intervals and Sets=== | ===Applicatoins of Sorting: Intervals and Sets=== |

## Revision as of 18: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**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(n log n)}**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 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.

### Applicatoins of Sorting: Intervals and Sets

- 4.12

- 4.14

- 4.16

### Heaps

- 4.18

- 4.20

### Quicksort

- 4.22

- 4.24

- 4.26

### 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