Chapter Notes 4 11 Exercises

This page is a generated reference surface for selective reading. It exists to keep the learner apps guide-first while still preserving source access.

Learning objectives

• Explain the main ideas and vocabulary in Chapter Notes 4 11 Exercises.
• Work through the source examples for Chapter Notes 4 11 Exercises without depending on raw chunk order.
• Use Chapter Notes 4 11 Exercises as selective reference when learner modules point back to The Algorithm Design Manual.

Prerequisites

• None curated yet.

Module targets

• module-03-graph-algorithms

AI companion modes

• Explain simply
• Socratic tutor
• Quiz me
• Challenge my understanding
• Diagnose my confusion
• Generate extra practice
• Revision mode
• Connect forward / backward

Source-of-truth note

This unit is anchored to The Algorithm Design Manual and the source chapter "Chapter Notes 4 11 Exercises". Use external resources only to clarify, extend, or modernize details without replacing the chapter's conceptual spine.

External enrichment

No chapter-specific enrichment resources are curated yet. Add them in the unit manifest when a source clearly improves learning.

Source provenance

• Primary source: The Algorithm Design Manual
• Source chapter: Chapter Notes 4 11 Exercises
• Raw source file: 057-chapter-notes-4-11-exercises.md

Merged source

Chapter Notes 4 11 Exercises

Chapter Notes 4.11 Exercises

Chapter Notes 4.11 Exercises

Applications of Sorting

4-1. [3] The Grinch is given the job of partitioning 2nplayers into two teams of n players each. Each player has a numerical rating that measures how good he/she is at the game. He seeks to divide the players as unfairly as possible, so as to create the biggest possible talent imbalance between teamAand teamB. Show how the

Grinch can do the job inO(nlogn) time.

4-2. [3] 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,S={6,13,19,3,8},

19−3 maximizes the difference, while 8−6 minimizes the difference.

(a) LetSbe anunsortedarray ofnintegers. Give an algorithm that finds the pair

x, y ∈Sthatmaximizes|x−y|. Your algorithm must run inO(n) worst-case time.

(b) Let Sbe a sorted array of nintegers. Give an algorithm that finds the pair

x, y ∈Sthatmaximizes|x−y|. Your algorithm must run inO(1) worst-case time.

(c) LetSbe anunsortedarray ofnintegers. Give an algorithm that finds the pair

x, y ∈Sthatminimizes|x−y|, for x̸=y. Your algorithm must run inO(nlogn)

worst-case time.

(d) Let Sbe a sorted array of nintegers. Give an algorithm that finds the pair

x, y ∈S that minimizes |x−y|, for x ̸=y. Your algorithm must run in O(n)

worst-case time.

4-3. [3]Take a sequence of 2nreal numbers as input. Design anO(nlogn) algorithm that partitions the numbers intonpairs, 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. [3] Assume that we are given npairs 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 O(n) 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. [3] Themodeof a set 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 set ofnnumbers.

4-6. [3]Given two setsS1andS2(each of sizen), and a numberx, describe anO(nlogn)

algorithm for finding whether there exists a pair of elements, one fromS1 and one

from S

2, that add up to x. (For partial credit, give a Θ(n) algorithm for this problem.) 4-7. [3] 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 list containing the title, author, call number and publisher of all the books in a school library and another list of 30 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-8. [4 ] Given a set ofScontainingnreal numbers, and a real numberx. We seek an

algorithm to determine whether two elements ofSexist whose sum is exactlyx.

(a) Assume thatSis unsorted. Give anO(nlogn) algorithm for the problem.

(b) Assume thatSis sorted. Give anO(n) algorithm for the problem.

4-9. [4 ] Give an efficient algorithm to compute the union of sets Aand B, where n= max(|A|,|B|). The output should be an array of distinct elements that form the union of the sets, such that they appear more than once in the union.

(a) Assume that Aand Bare unsorted. Give an O(nlogn) algorithm for the problem.

(b) Assume thatAandBare sorted. Give anO(n) algorithm for the problem.

4-10. [5] Given a set Sof nintegers and an integer T, give an O(nk−1logn) algorithm to test whetherkof the integers in Sadd up toT.

4-11. [6 ] Design anO(n) algorithm that, given a list ofnelements, finds all the elements that appear more thann/2 times in the list. Then, design anO(n) algorithm that, given a list ofnelements, finds all the elements that appear more thann/4 times.

Heaps 4-12. [3] Devise an algorithm for finding theksmallest elements of an unsorted set ofn integers in O(n+klogn).

4-13. [5] You wish to store a set of nnumbers 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) Want to find the maximum element quickly.

(b) Want to be able to delete an element quickly.

(c) Want to be able to form the structure quickly.

(d) Want to find the minimum element quickly.

4-14. [5] Give anO(nlogk)-time algorithm that mergesksorted lists with a total of n elements into one sorted list. (Hint: use a heap to speed up the elementaryO(kn)time algorithm).

4-15. [5] (a) Give an efficient algorithm to find the second-largest key among nkeys.

You can do better than 2n−3 comparisons.

(b) Then, give an efficient algorithm to find the third-largest key among nkeys.

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-16. [3]Use the partitioning idea of quicksort to give an algorithm that finds themedian element of an array of nintegers in expected O(n) time. (Hint: must you look at both sides of the partition?) 4-17. [3] Themedianof a set of nvalues is the ⌈n/2⌉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 were always to pivot on the⌈n/3⌉th smallest value of the current sub-array. How many comparisons would be made then in the worst case?

4-18. [5] Suppose an arrayAconsists ofnelements, each of which isred, white, or blue.

We seek to sort the elements so that all theredscome before all thewhites, which come before all thebluesThe only operation permitted on the keys are

• Examine(A,i)- report the color of theith element ofA.

• Swap(A,i,j)- swap theith element ofAwith thejth element.

Find a correct and efficient algorithm for red-white-blue sorting. There is a lineartime solution.

4-19. [5] Aninversionof a permutation is a pair of elements that are out of order.

(a) Show that a permutation ofnitems has at mostn(n−1)/2 inversions. Which permutation(s) have exactlyn(n−1)/2 inversions?

(b) Let P be a permutation and Pr be the reversal of this permutation. Show thatPandPr have a total of exactlyn(n−1)/2 inversions.

(c) Use the previous result to argue that the expected number of inversions in a random permutation isn(n−1)/4.

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

Other Sorting Algorithms 4-21. [5] Stable sorting algorithms leave equal-key items in the same relative order as in the original permutation. Explain what must be done to ensure that mergesort is a stable sorting algorithm.

4-22. [3] Show thatnpositive integers in the range 1 to kcan be sorted in O(nlogk)

time. The interesting case is whenk << n.

4-23. [5] We seek to sort a sequenceSof nintegers with many duplications, such that the number of distinct integers in Sis O(logn). Give an O(nlog logn) worst-case time algorithm to sort such sequences.

√

4-24. [5] LetA[1..n] be an array such that the firstn− nelements are already sorted (though we know nothing about the remaining elements). Give an algorithm that sorts Ain substantially better thannlognsteps.

4-25. [5] Assume that the arrayA[1..n] only has numbers from{1, . . . , n2}but that at most log lognof these numbers ever appear. Devise an algorithm that sorts Ain substantially less thanO(nlogn).

4-26. [5] Consider the problem of sorting a sequence ofn0's and 1's using comparisons.

For each comparison of two values xandy, the algorithm learns which of x < y,

x=y, or x > yholds.

(a) Give an algorithm to sort inn−1 comparisons in the worst case. Show that your algorithm is optimal.

(b) Give an algorithm to sort in 2n/3 comparisons in the average case (assuming each of theninputs is 0 or 1 with equal probability). Show that your algorithm is optimal.

4-27. [6] Let P be a simple, but not necessarily convex, polygon and q an arbitrary point not necessarily in P. Design an efficient algorithm to find a line segment originating from q that intersects the maximum number of edges of P. In other words, if standing at pointq, in what direction should you aim a gun so the bullet will go through the largest number of walls. A bullet through a vertex of P gets credit for only one wall. AnO(nlogn) algorithm is possible.

Lower Bounds 4-28. [5] In one of my research papers [Ski88], I discovered a comparison-based sorting

√