Difference between revisions of "Chapter 4"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
Line 3: Line 3:
 
===Applications of Sorting: Numbers===
 
===Applications of Sorting: Numbers===
  
:[[4.1]]
+
:[[4.1]]. The Grinch is given the job of partitioning <math>2n</math> players into two teams of <math>n</math> 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 <math>O(n log n)</math> time.
 +
[[4.1|Solution]]
  
  
:4.2
+
: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, <math>S = {6, 13, 19, 3, 8}</math>, 19 - 3 maximizes the difference, while 8 - 6 minimizes the difference.
 +
:(a) Let <math>S</math> be an ''unsorted'' array of <math>n</math> integers. Give an algorithm that finds the pair <math>x, y \in S</math> that ''maximizes'' <math>|x-y|</math>. Your algorithm must run in <math>O(n)</math> worst-case time.
 +
:(b) Let <math>S</math> be a ''sorted'' array of <math>n</math> integers. Give an algorithm that finds the pair <math>x, y \in S</math> that ''maximizes'' <math>|x - y|</math>. Your algorithm must run in <math>O(1)</math> worst-case time.
 +
:(c) Let <math>S</math> be an ''unsorted'' array of <math>n</math> integers. Give an algorithm that finds the pair <math>x, y \in S</math> that ''minimizes'' <math>|x - y|</math>, for <math>x \neq y</math>. Your algorithm must run in <math>O(n log n)</math> worst-case time.
 +
:(d) Let <math>S</math> be a ''sorted'' array of <math>n</math> integers. Give an algorithm that finds the pair <math>x, y \in S</math> that ''minimizes'' <math>|x - y|</math>, for <math>x \neq y</math>. Your algorithm must run in <math>O(n)</math> worst-case time.
  
  
:[[4.3]]
+
:[[4.3]]. Take a list of <math>2n</math> real numbers as input. Design an <math>O(n log n)</math> algorithm that partitions the numbers into <math>n</math> 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.3|Solution]]
  
  
:4.4
+
:4.4. Assume that we are given <math>n</math> 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 <math>O(n)</math> 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).
  
  

Revision as of 15:28, 18 September 2020

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.

Solution


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. Solution


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


4.6


4.7


4.8


4.9


4.10


4.11

Applicatoins of Sorting: Intervals and Sets

4.12


4.13


4.14


4.15


4.16


Heaps

4.17


4.18


4.19


4.20


Quicksort

4.21


4.22


4.23


4.24


4.25


4.26


4.27


Mergesort

4.28


4.29


4.30


Other Sorting Alogrithims

4.31


4.32


4.33


4.34


4.35


4.36


4.37


4.38


Lower Bounds

4.39


4.40


Searching

4.41


4.42


Implementaion Challenges

4.43


4.44


4.45


4.46

Interview Problems

4.47


4.48


4.49


4.50


4.51


4.52


4.53


Back to Chapter List