answer all

. Graphs with prescribed degree sequences. Given a list of n positive integers d1, d2, . . . , dn, we want to efficiently determine whether there exists an undirected graph G = (V, E) whose nodes have degrees precisely d1, d2, . . . , dn. That is, if V = {v1, . . . , vn}, then the degree of vi should be exactly di. We call (d1, . . . , dn) the degree sequence of G. This graph G should not contain self-loops (edges with both endpoints equal to the same node) or multiple edges between the same pair of nodes. (a) Give an example of d1, d2, d3, d4 where all the di 3 and d1 + d2 + d3 + d4 is even, but for which no graph with degree sequence (d1, d2, d3, d4) exists. (b) Suppose that d1 d2 dn and that there exists a graph G = (V, E) with degree sequence (d1, . . . , dn). We want to show that there must exist a graph that has this degree sequence and where in addition the neighbors of v1 are v2, v3, . . . , vd1+1. The idea is to gradually transform G into a graph with the desired additional property. i. Suppose the neighbors of v1 in G are not v2, v3, . . . , vd1+1. Show that there exists i < j n and u V such that {v1, vi}, {u, vj } / E and {v1, vj }, {u, vi} E. ii. Specify the changes you would make to G to obtain a new graph G = (V, E) with the same degree sequence as G and where (v1, vi) E. iii. Now show that there must be a graph with the given degree sequence but in which v1 has neighbors v2, v3, . . . , vd1+1. (c) Using the result from part (b), describe an algorithm that on input d1, . . . , dn (not necessar- ily sorted) decides whether there exists a graph with this degree sequence. Your algorithm should run in time polynomial in n and in m = n i=1 di. 5.27. Alice wants to throw a party and is deciding whom to call. She has n people to choose from, and she has made up a list of which pairs of these people know each other. She wants to pick as many people as possible, subject to two constraints: at the party, each person should have at least five other people whom they know and five other people whom they don't know. Give an efficient algorithm that takes as input the list of n people and the list of pairs who know each other and outputs the best choice of party invitees. Give the running time in terms of n. 159 5.28. A prefix-free encoding of a finite alphabet assigns each symbol in a binary codeword, such that no codeword is a prefix of another codeword. Show that such an encoding can be represented by a full binary tree in which each leaf corre- sponds to a unique element of , whose codeword is generated by the path from the root to that leaf (interpreting a left branch as 0 and a right branch as 1). 5.29. Ternary Huffman. Trimedia Disks Inc. has developed "ternary" hard disks. Each cell on a disk can now store values 0, 1, or 2 (instead of just 0 or 1). To take advantage of this new technology, provide a modified Huffman algorithm for compressing sequences of characters from an alpha- bet of size n, where the characters occur with known frequencies f1, f2, . . . , fn. Your algorithm should encode each character with a variable-length codeword over the values 0, 1, 2 such that no codeword is a prefix of another codeword and so as to obtain the maximum possible compression. Prove that your algorithm is correct. 5.30. The basic intuition behind Huffman's algorithm, that frequent blocks should have short en- codings and infrequent blocks should have long encodings, is also at work in English, where typical words like I, you, is, and, to, from, and so on are short, and rarely used words like velociraptor are longer. However, words like fire!, help!, and run! are short not because they are frequent, but perhaps because time is precious in situations where they are used. To make things theoretical, suppose we have a file composed of m different words, with frequen- cies f1, . . . , fm. Suppose also that for the ith word, the cost per bit of encoding is ci. Thus, if we find a prefix-free code where the ith word has a codeword of length li, then the total cost of the encoding will be i fi ci li. Show how to modify Huffman's algorithm to find the prefix-free encoding of minimum total cost. 5.31. A server has n customers waiting to be served. The service time required by each customer is known in advance: it is ti minutes for customer i. So if, for example, the customers are served in order of increasing i, then the ith customer has to wait i j=1 tj minutes. We wish to minimize the total waiting time T = n i=1 (time spent waiting by customer i). Give an efficient algorithm for computing the optimal order in which to process the customers. 5.32. Show how to implement the stingy algorithm for Horn formula satisfiability (Section 5.3) in time that is linear in the length of the formula (the number of occurrences of literals in it). (Hint: Use a directed graph, with one node per variable, to represent the implications.) 5.33. Show that for any integer n that is a power of 2, there is an instance of the set cover problem (Section 5.4) with the following properties: i. There are n elements in the base set. ii. The optimal cover uses just two sets. iii. The greedy algorithm picks at least log n sets. Thus the approximation ratio we derived in the chapter is tight.