Algorithm Design Techniques
Due: Sep 22, 2005 in class
Late assignments -10% per day, including
weekends. Hand in late assignments to the T.A.
If you work closely with someone else, indicate the person's name(s)
on your homework.
The final write-up of each assignment must, however, be your own work.
1. (Greedy) Read the course notes
on selection .
( http://www.cs.mcgill.ca/~avis/courses/360/notes/selection.pdf )
Let G=(V,E) be a connected graph. Let A and B be two forests on the
vertex set V where B has more edges than A.
Prove that P3 holds, ie. that there is an edge in B that can be added
to A such that the result is still a forest.
2. A Larman graph is a graph
G=(V,E) with |E| = 2*|V| - 3 edges, and the property that every subset
A of vertices spans at most 2*|A| - 3 edges. (A subset of vertices A
spans an edge with endpoints u
and v if both u and v are in A).
Show that these graphs satisfy properties P1, P2, P3 and hence the
greedy selection algorithm would work here:
ie. to find a maximum weight Larman graph in a weighted complete graph.
Hint: A tree can be defined
as follows: It is a graph G=(V,E) with |V|-1 edges, such that every
subset A of vertices spans at most |A|-1 edges. P1,P2,P3 hold and so
greedy can be used to find the maximum weight tree in a weighted
3. In a two processor scheduling problem we have a set of n
tasks, and for each task i, a processing time ti.
The problem is to assign each task to a processor in such a way
as to minimize the length of the schedule.
Each processor can handle one task at a time, and once started on a
task must continue until the task is finished.
The length of a schedule is the earliest time at which both processors
are idle and all tasks have been completed.
Develop a dynamic programming algorithm for this problem and prove it
Program your method and find the minimum length schedule for the 13
tasks with processing times
109345 57643 45692
129443 349221 128564 50983 30877
214998 32155 22318 263993 349822
Can you find a faster method for this input?