Description
P1) Given a connected graph G with m ≥ n edges. Design an algorithm that runs in time O(m+n)
and orients edges of G such that the indegree of every vertex is at least 1. For example, in
the following picture given the graph in the left, we can orient as shown in the right and the
in-degree of every vertex will be at least 1. Output the orientation of each edge; so for this
example you may output
1 → 3, 3 → 2, 2 → 1, 2 → 4
1 2
3
4 1 2
3
4
P2) Given a sequence d1, . . . , dn of integers design a polynomial time algorithm that construct a
tree such that the degree of vertex i is di
. If no such tree exists your algorithm must output
“Impossible”. For example, given the sequence 2, 3, 1, 2, 1, 1 you can output the following tree:
Note that the specific labels of the nodes of the tree is not important. We only want to have
1 node of degree 3, 2 nodes of degree 2 and 3 nodes of degree 1.
Hint: Show that for every sequence d1, . . . , dn there exists a tree with this degree sequence if
and only if P
i
di = 2(n − 1), and for all i we have di ≥ 1. Also, you may have to argue that
if the sum of n integers is less than 2n then one of them is at most 1.
P3) Given n jobs 1, . . . , n, let ai be the processing time of job i. We have one processor to execute
all of these jobs. Say we process these jobs in the order i1, . . . , in. Then, job i1 finishes at time
ai1
, job i2 finishes at time ai1 + ai2
and so on. The goal is to find an optimal order to execute
these jobs to minimize the average completion time. For example, if a1 = 3, a2 = 1, a3 = 5,
then if we execute them in the order, 3,2,1, job 3 finishes at time 5, job 2 finishes at time
6 and job 1 finishes at time 9. So, the average completion time is 5+6+9
3 = 20/3. For this
instance, the optimal order to minimize average completion time is 2, 1, 3 which gives the
average completion 1+4+9
3 = 13/3.
P4) Given a sequence of n real numbers a1, . . . , an where n is even, design a polynomial time
algorithm to partition these numbers into n/2 pairs in the following way: For each pair we
compute the sum of its numbers. Denote s1, . . . , sn/2
these n/2 sums. Your algorithm should
3-1
find the partition which minimizes the maximum sum. For example, given numbers 3, −1, 2, 7
you should output the following partition: {3, 2}, {−1, 7}. In such a case the maximum sum
is 7 + (−1) = 6.
P5) Extra Credit: Suppose G is a 3-colorable graph with n vertices, i.e., it is possible to color
the vertices of G with 3 colors such that the endpoints of every edge have distinct colors.
Design a polynomial time algorithm that colors vertices of G with O(
√
n) many colors.
3-2
