Algorithm Design Techniques

 COMP-360              Assignment 1              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 complete graph.
______________________________________________________________________________________________________________________________

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 is correct.
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?