Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

Advanced Algorithms. Week 1 Practice Problems

Advanced Algorithms.

Week 1 Practice Problems

Back to the course page

Acknowledgements

These questions are from Chapter 4 of Jeff Erickson’s textbook on Algorithms.

Problem 1. Alternate Greedy Schedules

The GreedySchedule algorithm we described for the class scheduling problem is not the only greedy strategy we could have tried. For each of the following alternative greedy strategies, either prove that the resulting algorithm always constructs an optimal schedule, or describe a small input example for which the algorithm does not produce an optimal schedule.

Assume that all algorithms break ties arbitrarily (that is, in a manner that is completely out of your control).

[Hint: Three of these algorithms are actually correct.]

  1. Choose the course xxx that ends last, discard classes that conflict with xxx, and recurse.

  2. Choose the course xxx that starts first, discard all classes that conflict with xxx, and recurse.

  3. Choose the course xxx that starts last, discard all classes that conflict with xxx, and recurse.

  4. Choose the course xxx with shortest duration, discard all classes that conflict with xxx, and recurse.

  5. Choose a course xxx that conflicts with the fewest other courses, discard all classes that conflict with xxx, and recurse.

  6. If no classes conflict, choose them all. Otherwise, discard the course with longest duration and recurse.

  7. If no classes conflict, choose them all. Otherwise, discard a course that conflicts with the most other courses and recurse.

  8. Let xxx be the class with the earliest start time, and let yyy be the class with the second earliest start time.

  • If xxx and yyy are disjoint, choose xxx and recurse on everything but xxx.

  • If xxx completely contains yyy, discard xxx and recurse.

  • Otherwise, discard yyy and recurse.

  1. If any course xxx completely contains another course, discard xxx and recurse. Otherwise, choose the course yyy that ends last, discard all classes that conflict with yyy, and recurse.
Problem 2. Weighted Scheduling

Now consider a weighted version of the class scheduling problem, where different classes offer different number of credit hours (totally unrelated to the duration of the class lectures). Your goal is now to choose a set of non-conflicting classes that give you the largest possible number of credit hours, given arrays of start times, end times, and credit hours as input.

  1. Prove that the greedy algorithm described at the beginning of this chapter-Choose the class that ends first and recurse-does not always return an optimal schedule.

  2. Prove that none of the greedy algorithms described in Exercise 1 always return an optimal schedule. [Hint: Solve Exercise 1 first; the algorithms that don’t work there don’t work here, either.]

  3. BONUS QUESTION Describe and analyze an algorithm that always computes an optimal schedule. [Hint: Your algorithm will not be greedy.]

Problem 3. Finding a Cover

Let XXX be a set of nnn intervals on the real line. We say that a subset of intervals Y⊆XY \subseteq XY⊆X covers XXX if the union of all intervals in YYY is equal to the union of all intervals in XXX. The size of a cover is just the number of intervals.

Describe and analyze an efficient algorithm to compute the smallest cover of XXX. Assume that your input consists of two arrays L[1…n]L[1 \ldots n]L[1…n] and R[1..n]R[1 . . n]R[1..n], representing the left and right endpoints of the intervals in XXX. If you use a greedy algorithm, you must prove that it is correct.

A set of intervals, with a cover (shaded) of size 7.

Problem 4. Finding a Stabbing Set

Let XXX be a set of nnn intervals on the real line. We say that a set PPP of points stabs XXX if every interval in XXX contains at least one point in PPP. Describe and analyze an efficient algorithm to compute the smallest set of points that stabs XXX. Assume that your input consists of two arrays L[1..n]L[1 . . n]L[1..n] and R[1..n]R[1 . . n]R[1..n], representing the left and right endpoints of the intervals in XXX. As usual, If you use a greedy algorithm, you must prove that it is correct.

A set of intervals stabbed by four points (shown here as vertical segments).

Problem 5. Proper Coloring

Let XXX be a set of nnn intervals on the real line. A proper coloring of XXX assigns a color to each interval, so that any two overlapping intervals are assigned different colors. Describe and analyze an efficient algorithm to compute the minimum number of colors needed to properly color XXX. Assume that your input consists of two arrays L[1..n]L[1 . . n]L[1..n] and R[1..n]R[1 . . n]R[1..n], representing the left and right endpoints of the intervals in XXX. As usual, if you use a greedy algorithm, you must prove that it is correct.

A proper coloring of a set of intervals using five colors.

Problem 6. Stable Matchings
  1. Prove that it is possible for the Gale-Shapley algorithm to perform Ω(n2)\Omega\left(n^{2}\right)Ω(n2) offers before termination.

    (You need to describe both a suitable input and a sequence of Ω(n2)\Omega\left(n^{2}\right)Ω(n2) valid offers.)

  2. Describe for any integer nnn a set of preferences for nnn men and nnn women that forces the Gale-Shapley algorithm to execute Ω(n2)\Omega\left(n^{2}\right)Ω(n2) rounds, no matter which valid proposal is made in each round.

    [Hint: Part (b) implies part (a).]

Problem 7. A Unique Stable Matching

Describe and analyze an efficient algorithm to determine whether a given set of men and women preferences has to have a unique stable matching.


© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos

×