Description
Greedy Algorithms
1. In one or two sentences, describe what a greedy algorithm is. Your definition should be informal,
something you could share with a non computer scientist.
2. There are many different problems all described as “scheduling” problems. In the following questions,
pay attention to the details of the problem setup, as they will change each time!
(a) Let each job have a start time, an end time, and a value. We want to schedule as much value
of non-conflicting jobs as possible. Use a counterexample to show that Earliest Finish First (the
greedy algorithm we used for jobs with all equal value) does NOT work in this case.
(b) Kleinberg, Jon. Algorithm Design (p. 191, q. 7) Now let each job consist of two durations. A
job i must be preprocessed for pi time on a supercomputer, and then finished for fi time on a
standard PC. There are enough PCs available to run all jobs at the same time, but there is only one
supercomputer (which can only run a single job at a time). The completion time of a schedule is
defined as the earliest time when all jobs are done running on both the supercomputer and the PCs.
Give a polynomial time algorithm that finds a schedule with the earliest completion time possible.
CS 577 Assignment 3: Greedy Algorithms
(c) Prove the correctness and efficiency of your algorithm from part (c).
Page 2 of 6
CS 577 Assignment 3: Greedy Algorithms
3. Kleinberg, Jon. Algorithm Design (p. 190, q. 5)
(a) Consider a long straight road with houses scattered along it. We want to place cell phone towers
along the road so that every house is within four miles of at least one tower. Give an efficient
algorithm that achieves this goal using the minimum possible number of towers.
(b) Prove the correctness of your algorithm.
Page 3 of 6
CS 577 Assignment 3: Greedy Algorithms
4. Kleinberg, Jon. Algorithm Design (p. 197, q. 18) Your friends are planning to drive north from Madison
to the town of Superior, Wisconsin over winter break. They have drawn a directed graph with nodes
representing potential stops and edges representing the roads between them.
They have also found a weather forecasting site that can accurately predict how long it will take to
traverse one of the edges on their graph, given the starting time t. This is important because some of
the roads on their graph are affected strongly by the seasons and by extreme weather. It’s guaranteed
that it never takes negative time to traverse an edge, and that you can never arrive earlier by starting
later.
(a) Design an algorithm your friends can use to plot the quickest route. You may assume that they
start at time t = 0, and that the predictions made by the weather forecasting site are accurate.
Page 4 of 6
CS 577 Assignment 3: Greedy Algorithms
(b) Demonstrate how your algorithm works using a small example with 6 nodes. Your demonstration
should include any data structures you maintain during the execution of your algorithm and any
queries you make to the weather forecasting site. For example, if your algorithm maintains a “current
path” that grows from (M)adison to (S)uperior, you might show something like the following table:
Path Total time
M 0
M,A 2
M,A,E 5
M,A,E,F 6
M,A,E 5
M,A,E,H 10
M,A,E,H,S 13
Page 5 of 6
CS 577 Assignment 3: Greedy Algorithms
Coding Question
5. Implement the optimal algorithm for interval scheduling (for a definition of the problem, see the Greedy
slides on Canvas) in either C, C++, C#, Java, or Python. Be efficient and implement it in O(n log n)
time, where n is the number of jobs.
The input will start with an positive integer, giving the number of instances that follow. For each
instance, there will be a positive integer, giving the number of jobs. For each job, there will be a pair of
positive integers i and j, where i < j, and i is the start time, and j is the end time.
A sample input is the following:
2
1
1 4
3
1 2
3 4
2 6
The sample input has two instances. The first instance has one job to schedule with a start time of 1
and an end time of 4. The second instance has 3 jobs.
For each instance, your program should output the number of intervals scheduled on a separate line.
Each output line should be terminated by a newline. The correct output to the sample input would be:
1
2