$30.00
Description
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 a_{j} when it is rst available for processing, a length ‘_{j} which indicates how much processing time it needs, and a deadline d_{j} by which it must be nished. (We’ll assume 0 < ‘_{j} d_{j} a_{j}.) 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 [t_{i}; t^{0}_{i}] 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 polynomialtime 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 J_{1} and J_{2}. J_{1} arrives at time 0, is due at time 4, and has length

J_{2} arrives at time 1, is due at time 3, and has length 2. We also have two processors P_{1} and P_{2}. P_{1} is available between times 0 and 4; P_{2} 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 J_{1} on processor P_{1}. At time 1, we preempt J_{1} to start J_{2} on P_{1}.
At time 2, we resume J_{1} on P_{2}. (J_{2} continues processing on P_{1}.)
At time 3, J_{2} completes by its deadline. P_{2} ceases to be available, so we move J_{1} back to P_{1} to nish its remaining one unit of processing there.
At time 4, J_{1} completes its processing on P_{1}.
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 \closeknit” 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 Sthat 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.

Give a polynomialtime algorithm that takes a rational number and determines whether there exists a set S with cohesiveness at least .

Give a polynomialtime 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, r_{1}; : : : ; r_{n}, c_{1}; : : : ; c_{n}. Your output should be a matrix a_{i;j} of integers between 1 and M so
P P
that _{i} a_{i;j} = c_{j} for 1 j n and _{j} a_{i;j} = r_{i} 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 twodimensional 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.

name
phone number
start date
manager’s name
Alanis
34563
6/13/95
Chelsea
Chelsea
32341
1/20/93
Lou
Elrond
32345
12/19/01
Chelsea
Hal
39000
1/12/97
Chelsea
Raj
33453
7/1/96
Chelsea
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 T_{p}.
All of this comes into play for your particular application, as follows. You have k di erent subsets of the columns S_{1}; S_{2}; : : : ; S_{k} 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 [S_{1}]; T [S_{2}]; : : : ; T [S_{k}], 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 lefttoright 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 S_{i} 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 p_{1}; p_{2}; : : : ; p_{‘} so that for every one of the given subsets S_{i} (for i = 1; 2; : : : ; k), it’s the case that the columns in S_{i} constitute a pre x of at least one of the permuted tables T_{p}_{1} ; T_{p}_{2} ; : : : ; T_{p}_{‘} ? 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 polynomialtime 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
S_{1} = fname, phone numberg;
S_{2} = fname, start dateg;
S_{3} = fname, manager’s name, start dateg;
2
and ‘ = 2. Then there is a valid solution to the instance, and it could be achieved by the two permutations
p_{1} = fname, phone number, start date, manager’s nameg; p_{2} = fname, start date, manager’s name, phone numberg:
This way, S_{1} constitutes a pre x of the permuted table T_{p}_{1} , and both S_{2} and S_{3} constitute pre xes of the permuted table T_{p}_{2} .
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 p_{i} 1 is given. It is assumed that nodes fail independently, so
Q
the failure probability for a set F V is _{i2F} p_{i}. Give an algorithm which, given G and p_{i}f ori 2 V , nds the failure point F with the maximum failure probability.
3