CIS 315, Intermediate Algorithms
Winter 2020
Assignment 7
Well done! This is the last assignment.
Due 5 PM Wednesday, March 11, 2020.
[15 “normal” credits + 10 extra credits]
1. Illustrate the Ford-Fulkerson algorithm for the graph of Figure 1 (on next page). [5 points]
2. Exercise 5.18, part (a), left column only (DPV). Now, only consider the left column of the
table for problem 5.18: characters blank, e, t, a, o, i, n, s, h with the given frequencies.
Show the tree construction, and also the resultant Huffman encoding of these characters. [5
points]
3. You are running a software company and have a series of n jobs that must be pre-processed
first on a supercomputer before being moved to a smaller PC. You have only one supercomputer,
but you have n PCs so the second stage can be performed in parallel. More
specifically, your jobs are described as J1 = (s1, f1), J2 = (s2, f2), . . . , Jn = (sn, fn), where
job Ji needs si units of time to be pre-processed on the super-computer and fi units of time
on the PC.
You need to work out an order in which to give the jobs to the super-computer. As soon as
the first job is done on the super-computer, it can be moved to the PC for finishing; at that
point a second job can be given to the super-computer; when the second job is done it can go
straight to a PC since the PCs can work in parallel, and so on. So if the jobs are processed
in the order given, job Ji finishes at time (Pi
k=1 sk) + fi
A schedule is an ordering of the jobs to be given to the super-computer. The completion time
is the point at which all jobs have finished being processed on the PCs. We wish to minimize
the completion time.
(a) Give an efficient (greedy!) algorithm for computing the optimal order in which to process
the jobs so that the completion time is minimized. [5 points]
(b) Prove the greedy choice your algorithm makes is correct. (Tip: Recall what we did
during the class for the task scheduling problem.) [10 extra points]
Figure 1: Flow graph with capacities