Homework III Solution



Problem 1: Job scheduling (KT 7.41)

Suppose you’re managing a collection of processors and must schedule a sequence of jobs over time.

The jobs have the following characteristics. Each job j has an arrival time aj when it is rst available for processing, a length ‘j which indicates how much processing time it needs, and a deadline dj by which it must be nished. (We’ll assume 0 < ‘j dj aj.) Each job can be run on any of the processors, but only on one at a time; it can also be preempted and resumed from where it left o (possibly after a delay) on another processor.

Moreover, the collection of processors is not entirely static either: You have an overall pool of k possible processors; but for each processor i, there is an interval of time [ti; t0i] during which it is available; it is unavailable at all other times.

Given all this data about job requirements and processor availability, you’d like to decide whether the jobs can all be completed or not. Give a polynomial-time algorithm that either produces a schedule completing all jobs by their deadlines or reports (correctly) that no such schedule exists. You may assume that all the parameters associated with the problem are integers.

Example. Suppose we have two jobs J1 and J2. J1 arrives at time 0, is due at time 4, and has length

  1. J2 arrives at time 1, is due at time 3, and has length 2. We also have two processors P1 and P2. P1 is available between times 0 and 4; P2 is available between times 2 and 3. In this case, there is a schedule that gets both jobs done.

At time 0, we start job J1 on processor P1. At time 1, we preempt J1 to start J2 on P1.

At time 2, we resume J1 on P2. (J2 continues processing on P1.)

At time 3, J2 completes by its deadline. P2 ceases to be available, so we move J1 back to P1 to nish its remaining one unit of processing there.

At time 4, J1 completes its processing on P1.

Notice that there is no solution that does not involve preemption and moving of jobs.

Problem 2: Graph cohesiveness (KT 7.46)

In sociology, one often studies a graph G in which nodes represent people and edges represent those who are friends with each other. Let’s assume for purposes of this question that friendship is symmetric, so we can consider an undirected graph.

Now suppose we want to study this graph G, looking for a \close-knit” group of people. One way to formalize this notion would be as follows. For a subset S of nodes, let e(S) denote the number of edges in S-that is, the number of edges that have both ends in S. We de ne the cohesiveness of S as e(S)=jSj. A natural thing to search for would be a set S of people achieving the maximum cohesiveness.

  1. Give a polynomial-time algorithm that takes a rational number and determines whether there exists a set S with cohesiveness at least .

  1. Give a polynomial-time algorithm to nd a set S of nodes with maximum cohesiveness.

Problem 3: Number puzzle

You are trying to solve the following puzzle. You are given the sums for each row and column of an n n matrix of integers in the range 1 : : : ; M, and wish to reconstruct a matrix that is consistent. In other words, your input is M, r1; : : : ; rn, c1; : : : ; cn. Your output should be a matrix ai;j of integers between 1 and M so


that i ai;j = cj for 1 j n and j ai;j = ri for 1 i n; if no such matrix exists, you should output, “Impossible”. Give an e cient algorithm for this problem.

Problem 4: Database projections (KT 7.38)

You’re working with a large database of employee records. For the purposes of this question, we’ll picture the database as a two-dimensional table T with a set R of m rows and a set C of n columns; the rows correspond to individual employees, and the columns correspond to di erent attributes.

To take a simple example, we may have four columns labeled

name, phone number, start date, manager’s name

and a table with ve employees as shown here. Given a subset S of the columns, we can obtain a new, smaller

Table 1: Table with ve employees.


phone number

start date

manager’s name





















table by keeping only the entries that involve columns from S. We will call this new table the projection of

  • onto S, and denote it by T [S]. For example, if S = fname, start dateg, then the projection T [S] would be the table consisting of just the rst and third columns.

There’s a di erent operation on tables that is also useful, which is to permute the columns. Given a permutation p of the columns, we can obtain a new table of the same size as T by simply reordering the columns according to p. We will call this new table the permutation of T by p, and denote it by Tp.

All of this comes into play for your particular application, as follows. You have k di erent subsets of the columns S1; S2; : : : ; Sk that you’re going to be working with a lot, so you’d like to have them available in a readily accessible format. One choice would be to store the k projections T [S1]; T [S2]; : : : ; T [Sk], but this would take up a lot of space. In considering alternatives to this, you learn that you may not need to explicitly project onto each subset, because the underlying database system can deal with a subset of the columns particularly e ciently if (in some order) the members of the subset constitute a pre x of the columns in left-to-right order. So, in our example, the subsets fname, phone numberg and fname, start date, phone number,g constitute pre xes (they’re the rst two and rst three columns from the left, respectively); and as such, they can be processed much more e ciently in this table than a subset such as fname, start dateg, which does not constitute a pre x. (Again, note that a given subset Si does not come with a speci ed order, and so we are interested in whether there is some order under which it forms a pre x of the columns.)

So here’s the question: Given a parameter ‘ < k, can you nd ‘ permutations of the columns p1; p2; : : : ; p so that for every one of the given subsets Si (for i = 1; 2; : : : ; k), it’s the case that the columns in Si constitute a pre x of at least one of the permuted tables Tp1 ; Tp2 ; : : : ; Tp ? We’ll say that such a set of permutations constitutes a valid solution to the problem; if a valid solution exists, it means you only need to store the ‘ permuted tables rather than all k projections. Give a polynomial-time algorithm to solve this problem; for instances on which there is a valid solution, your algorithm should return an appropriate set of ‘ permutations.

Example. Suppose the table is as above, the given subsets are

S1 = fname, phone numberg;

S2 = fname, start dateg;

S3 = fname, manager’s name, start dateg;


and ‘ = 2. Then there is a valid solution to the instance, and it could be achieved by the two permutations

p1 = fname, phone number, start date, manager’s nameg; p2 = fname, start date, manager’s name, phone numberg:

This way, S1 constitutes a pre x of the permuted table Tp1 , and both S2 and S3 constitute pre xes of the permuted table Tp2 .

Problem 5: Maximum likelihood points of failure

A network is described as a directed graph (not necessarily acyclic), with a speci ed source s and destination t. A set of nodes (not including s or t) is a failure point if deleting those nodes disconnects t from s. For each node of the graph, i, a failure probability 0 pi 1 is given. It is assumed that nodes fail independently, so


the failure probability for a set F V is i2F pi. Give an algorithm which, given G and pif ori 2 V , nds the failure point F with the maximum failure probability.