[Solved] CSE421-Homework 3

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 d₁,,d_n of integers design a polynomial time algorithm that construct a tree such that the degree of vertex i is d_i. 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 d₁,,d_n there exists a tree with this degree sequence if and only if ^P_i d_i = 2(n 1), and for all i we have d_i 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 a_i 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 i₁,,i_n. Then, job i₁ finishes at time a_i1, job i₂ finishes at time a_i1 + a_i2 and so on. The goal is to find an optimal order to execute these jobs to minimize the average completion time. For example, if a₁ = 3,a₂ = 1,a₃ = 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 a₁,,a_n 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 s₁,,s_n/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.