## 贪心

### 第一题

Given a list of n natural numbers $d_1, d_2,…,d_n$, show how to decide in polynomial time whether there exists an undirected graph $G = (V; E)$ whose node degrees are precisely the numbers $d_1, d_2,…,d_n$. $G$ should not contain multiple edges between the same pair of nodes, or “loop” edges with both endpoints equal to the same node.

• The basic idea and pseudo-code

• The greedy-choice property and optimal substructure
• Prove the correctness

• Analyse the complexity

### 第二题

There are n distinct jobs, labeled $J_1, J_2, …, J_n$, which can be performed completely independently of one another. Each jop consists of two stages: first it needs to be preprocessed on the supercomputer, and then it needs to be finished on one of the PCs. Let’s say that job $J_i$ needs $p_i$ seconds of time on the supercomputer, followed by $f_i$ seconds of time on a PC. Since there are at least $n$ PCs available on the premises, the finishing of the jobs can be performed on PCs at the same time. However, the supercomputer can only work on a single job a time without any interruption. For every job, as soon as the preprocessing is done on the supercomputer, it can be handed off to a PC for finishing.

Let’s say that a schedule is an ordering of the jobs for the supercomputer, and the completion time of the schedule is the earlist time at which all jobs have finished processing on the PCs. Give a polynomial-time algorithm that finds a schedule with as small a completion time as possible.

• The basic idea and pseudo-code

• The greedy-choice property and optimal substructure

• Prove the correctness

• Analyse the complexity

### 第五题

Write a program in your favorate language to compress a file using Huffman code and then decompress it. Code information may be contained in the compressed file if you can. Use your program to compress the two files (graph.txt and Aesop_Fables.txt) and compare the results (Huffman code and compression ratio).