CSE421-Homework 3 Solved

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

 

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 Pi 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  3. For this instance, the optimal order to minimize average completion time is 2,1,3 which gives the average completion  

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.