SUNY Geneseo Department of Computer Science

Problem Set 11—Greedy Algorithms

CSci 242, Spring 2013

Prof. Doug Baldwin

Due Friday, April 5

Purpose

This exercise reinforces your ability to design and reason about greedy algorithms.

Background

Greedy algorithms are algorithms designed in a style based on building up a globally optimal solution to some problem by accumulating locally optimal steps. The algorithms are “greedy” in the sense that each local optimum is found solely by considering what is best at that step, with no consideration of future steps. Chapter 16 of our textbook discusses greedy algorithms, and we discussed them in general in class on April 2. We also have discussed and will discuss a number of classical examples of specific greedy algorithms, such as Dijkstra’s shortest path algorithm.

Exercise

Solve each of the following problems. For up to 2 points extra credit, code your solutions to one or more problems in the programming language of your choice.

Problem 1

Exercise 16.1-2 in our textbook. In addition to proving the new strategy correct, give pseudocode for an algorithm based on it.

Problem 2

Exercise 16.2-4 in our textbook.

Problem 3

Recall Sleazy Sammy and Phineas Phoole’s competing bus routes from Problem Set 7. (Sleazy Sammy and Phineas Phoole run bus services between Geneseo and points east. Each service is priced per trip segment—i.e., per ride from one stop to the next one on that line. Planning a trip so that you change bus lines at strategic points can therefore affect the total cost of the trip.)

Part A

Phineas and Sammy have changed their bus operations a little bit: both companies now stop at exactly the same cities, but still have different fares for each segment of the trip. Give a greedy algorithm for finding the cheapest trip from Geneseo to other cities, given these new operating rules. Prove that your algorithm really finds the cheapest trip.

Part B

Now suppose Sammy and Phineas change their rules again, and offer “frequent rider” discounts. The requirements for being a “frequent rider” vary from day to day and line to line, as do the discounts. For example, on one day Phineas may offer free trips from Utica to Albany to anyone who has paid for ten rides, while Sammy has no discount for anyone on that day; on the next day Phineas may offer 5% off any ride to anyone who has paid full fare for three rides, while Sammy offers free snacks on the Albany to Rensselaer bus to anyone who has ridden 15 times in the past week, etc. Show that with frequent rider discounts, the greedy strategy from Part A does not necessarily yield a least-cost trip. (Hint: the real reason for the very flexible “frequent rider” rules is so that you can construct your own frequent rider discount offer in answering this part.)

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Please bring a written solution to your meeting; please also bring any code for extra credit in some form that I can both read and run. During the meeting, I will look over your solution, give you my reactions to it, answer any questions you have about it, etc.

Meetings should take about 15 minutes. Sign up either on the paper schedule outside my office or via Google calendar. If you work in a group, the entire group can schedule a single meeting with me. Be sure to have your grading appointment before the end of the day on the due date above.