4 of 55

Problem 1 – Practice a Reduction

BasicStableMatching

Input: A set of k horses and k riders. Each horse has a preference list of all k riders, and each rider has a preference list of all k horses.

Output: A stable matching among the k horses and k riders.

5 of 55

Problem 1 – Practice a Reduction

Work through this problem with the people around you, and then we’ll go over it together!

6 of 55

Problem 1 – Practice a Reduction

Give a 1-2 sentence summary of your idea.

7 of 55

Problem 1 – Practice a Reduction

Give a 1-2 sentence summary of your idea.

Create an instance where each horse has 3 copies (one per ride) and extra “fake” riders to balance the sides. Modify the preference list to represent what the agents want in the problem.

8 of 55

Problem 1 – Practice a Reduction

Give the algorithm you’re going to run.

9 of 55

Problem 1 – Practice a Reduction

Give the algorithm you’re going to run.

10 of 55

Problem 1 – Practice a Reduction

Give a 1-2 sentence summary of the idea of your proof.

11 of 55

Problem 1 – Practice a Reduction

Give a 1-2 sentence summary of the idea of your proof.

The Basic algorithm doesn’t produce blocking pairs, so we won’t either (once we delete the dummies).

12 of 55

Problem 1 – Practice a Reduction

Write a proof of correctness.

13 of 55

Problem 1 – Practice a Reduction

Write a proof of correctness.

14 of 55

Problem 1 – Practice a Reduction

15 of 55

Problem 1 – Practice a Reduction

16 of 55

Graph Algorithms

17 of 55

Problem 2 – Running Out of Rooms

18 of 55

Problem 2 – Running Out of Rooms

Swati [123 Fake St., 200 State St.]

Ewin [200 State St., 1000 Main St.]

Xin [null, 123 Fake St.]

Victor [567 Broadway, null]

Output: Easy Movement and [Victor, Ewin, Swati, Xin].

There are other valid lists to return here, you only need to give one.

Swati [123 Fake St., 200 State St.]

Ewin [200 State St., 1000 Main St.]

Xin [1000 Main St, 123 Fake St.]

Victor [567 Broadway, null]

Output: No Easy Movement and

[Swati, Ewin, Xin].

There is no easy movement in this example, because none of Swati, Ewin, and Xin can move first – they each need one of the others to go first.

19 of 55

Problem 2 – Running Out of Rooms

Work through this problem with the people around you, and then we’ll go over it together!

20 of 55

Problem 2 – Running Out of Rooms

Describe an algorithm to solve this problem.

21 of 55

Problem 2 – Running Out of Rooms

Describe an algorithm to solve this problem.

22 of 55

Problem 2 – Running Out of Rooms

Give some intuition for why your algorithm is correct. (Don’t write a full proof of correctness).

23 of 55

Problem 2 – Running Out of Rooms

Give some intuition for why your algorithm is correct. (Don’t write a full proof of correctness).

24 of 55

Problem 2 – Running Out of Rooms

25 of 55

Problem 2 – Running Out of Rooms

26 of 55

Greedy Algorithms

27 of 55

Problem 3 – Interval Covering

Work through this problem with the people around you, and then we’ll go over it together!

28 of 55

Problem 3 – Interval Covering

Key Idea Take the next interval that helps, i.e. that covers a new point; among all such intervals (if more than

one) take one that goes the farthest right.

29 of 55

Problem 3 – Interval Covering

Key Idea Take the next interval that helps, i.e. that covers a new point; among all such intervals (if more than

one) take one that goes the farthest right.

function IntervalCovering(𝒳)

𝒴 ← ∅

Sort 𝒳 by increasing start, breaking ties by decreasing end.

Let y be the start time of the first element of 𝒳

while 𝒳 ≠ ∅ do

Let I = [s, e] be the element remaining in 𝒳, with latest end time among those starting y or earlier.

𝒴 ← 𝒴 ∪ {I}

Delete all elements of X with endtime e or earlier

y ← first uncovered point past e

30 of 55

Problem 3 – Interval Covering

Correctness:

31 of 55

Problem 3 – Interval Covering

32 of 55

Problem 3 – Interval Covering

33 of 55

Problem 3 – Interval Covering

Running Time:

34 of 55

Problem 3 – Interval Covering

35 of 55

Divide and Conquer

36 of 55

Problem 4 – on handout

37 of 55

Dynamic Programming

38 of 55

Problem 5 – �Longest Palindromic Subsequence

39 of 55

Problem 5.1 – Write the Dynamic Program

Formulate the problem recursively – what are you looking for (in English!!), and what parameters will you need as you’re doing the calculation? �
Write a recurrence for solving the problem you defined in the last part (the recurrence is for the answer, not the running time).�
What is your final answer (e.g. what parameters for the recurrence do you need? Is it a single value or the max/min of a set of values?)? �
Give a brief justification for why your recurrence is correct. You do not need a formal inductive proof, but your intuition will likely resemble one.

Work through this problem with the people around you, and then we’ll go over it together!

40 of 55

Problem 5.1 – Write the Dynamic Program

Formulate the problem recursively – what are you looking for (in English!!), and what parameters will you need as you’re doing the calculation�

41 of 55

Problem 5.1 – Write the Dynamic Program

Formulate the problem recursively – what are you looking for (in English!!), and what parameters will you need as you’re doing the calculation?

Let OPT(i, j) be the length of the longest palindromic subsequence among indices i, ..., j.

42 of 55

Problem 5.1 – Write the Dynamic Program

Write a recurrence for solving the problem you defined in the last part (the recurrence is for the answer, not the running time).

43 of 55

Problem 5.1 – Write the Dynamic Program

Write a recurrence for solving the problem you defined in the last part (the recurrence is for the answer, not the running time).

44 of 55

Problem 5.1 – Write the Dynamic Program

What is your final answer (e.g. what parameters for the recurrence do you need? Is it a single value or the max/min of a set of values?)?

45 of 55

Problem 5.1 – Write the Dynamic Program

What is your final answer (e.g. what parameters for the recurrence do you need? Is it a single value or the max/min of a set of values?)?

46 of 55

Problem 5.1 – Write the Dynamic Program

Give a brief justification for why your recurrence is correct. You do not need a formal inductive proof, but your intuition will likely resemble one.

47 of 55

Problem 5.1 – Write the Dynamic Program

Give a brief justification for why your recurrence is correct. You do not need a formal inductive proof, but your intuition will likely resemble one.

48 of 55

Problem 5.2 – Analyze the Dynamic Program

Describe a memoization structure for your algorithm.�
Describe a filling order for your memoization structure.�
State and justify the running time of an iterative solution.�

Work through this problem with the people around you, and then we’ll go over it together!

49 of 55

Problem 5.2 – Analyze the Dynamic Program

Describe a memoization structure for your algorithm.

50 of 55

Problem 5.2 – Analyze the Dynamic Program

Describe a memoization structure for your algorithm.

51 of 55

Problem 5.2 – Analyze the Dynamic Program

Write a recurrence for solving the problem you defined in the last part (the recurrence is for the answer, not the running time).

52 of 55

Problem 5.2 – Analyze the Dynamic Program

Write a recurrence for solving the problem you defined in the last part (the recurrence is for the answer, not the running time).

53 of 55

Problem 5.2 – Analyze the Dynamic Program

What is your final answer (e.g. what parameters for the recurrence do you need? Is it a single value or the max/min of a set of values?)?

54 of 55

Problem 5.2 – Analyze the Dynamic Program

What is your final answer (e.g. what parameters for the recurrence do you need? Is it a single value or the max/min of a set of values?)?

55 of 55

That’s All, Folks!

Thanks for coming to section this week!

Any questions?