# 证明贪婪算法可以将多处理器作业调度工作的平均完成时间最小化

假设 P 个处理器有均匀分的 N 分作业，则有最小调度时间 $C=\sum_{k=1}^{N}(N=k+1)t_{ik}$ ; 若 P 个处理器有不均分的 N 份作业，这里假设所有处理器处理的总调度时间一致，则由小到大排序好后仍由最小平均完成时间。

# 设作业 $j_1,j_2,...j_n$ 为输人，其中的每一个作业都要花一个时间单位来完成。如果每个作业 $j_i$ 在时间限度 $t$ 内完成，那么将挣得 $d_i$ 美元，但若在时间限度以后完成则挣不到钱。

# 给出一个 $O(N)$ 贪婪算法求解该问题

使用无向图存储输入，用类似 Dijkstra 算法的方法安排 $j_i$ , 遍历满足条件时标记。

# 修改你的算法以得到 $O(N\log{N})$ 的时间界。

存储输入的数据结构换成堆（优先队列），使用堆的查找。

# 编码文件有一部分必须是指示 Huffman 编码的文件头。给一种方法构建大小最多为 O (N) 的文件头（除符号外），其 N 是符号的个数。

使用栈实现推入和联合两种操作由全单节点树生成霍夫曼树可以得到。

# 证明 Huffman 编码生成最优的前缀码。

大致思路见霍夫曼编码最优性的一个简单证明概述。

# 证明：如果符号是按照频率排序的，那么 Huffman 算法可以以线性时间实现

使用两个队列，Q1 存全部单节点树，Q2 为空，从 Q1 开始出队合并多节点树，入 Q2 队列，重复，不过要与 Q2 做比较，有则 Q1 和 Q2 出队合并，无则 Q1 出队后入 Q2 队，如此往复直至 Q1 空和 Q2 只剩一个树。最后的运行时间为线性时间。

# 用 Huffman 算法写出一个程序实现文件压缩 (和解压缩)

注意，该程序生成的 Huffman 编码虽然是二进制的，但未存入文件时是以 char 类型单个存储每个二进制数，只有存入文件时才真正转化为二进制数，但解压缩时，又把二进制数转化为 char 类型放进结构体来比较，这也是程序里位操作的意义所在。

文件压缩

	int File_Compress(HuffManTree T, FILE ifp, FILE ofp, long Len) {
	fseek(ifp, 0, SEEK_SET);
	fseek(ofp, 8, SEEK_SET);

	unsigned char c;
	char buf[512] = {0};
	int per = 10, CurPer = 0;
	int len, i;
	long FileLength = 8;
	// Convert the ascii characters of the original file to Huffman encoding
	while (!feof(ifp)) {
	c = fgetc(ifp);
	CurPer++;
	for (i = 0; i < T->num; i++) {
	if (c == T->header[i].Char) break;
	}
	strcat(buf, T->header[i].bits);

	len = strlen(buf);
	c = 0;
	// Convert Huffman encoding into a bit stream.
	// (actually a Huffman encoding a single char to store a bit)
	while (len >= 8) {
	for (i = 0; i < 8; i++) {
	if (buf[i] == '1') c = (c << 1) \| 1;
	else c = c << 1;
	}
	fwrite(&c, 1, 1, ofp);
	FileLength++;
	strcpy(buf, buf + 8);
	len = strlen(buf);
	}
	// Show progress
	if (100 * CurPer /Len > per) {
	printfPercent(per);
	per += 10;
	}
	if (CurPer == Len) break;
	}
	printfPercent(100);

	// When there are less than eight characters remaining.
	if (len > 0) {
	strcat(buf, "00000000");
	for (i = 0; i < 8; i++) {
	if (buf[i] == '1') c = (c << 1) \| 1;
	else c = c << 1;
	}
	fwrite(&c, 1, 1, ofp);
	FileLength++;
	}

	// Write the number of characters in the original file
	// and the number of compressed characters.
	fseek(ofp, 0, SEEK_SET);
	fwrite(&Len, 1, sizeof(Len), ofp);
	fwrite(&FileLength, sizeof(FileLength), 1, ofp);

	// Write Huffman encoding information to the output document.
	fseek(ofp, FileLength, SEEK_SET);
	fwrite(&T->num, sizeof(T->num), 1, ofp);
	for (int i = 0; i < T->num; i++) {
	fwrite(&(T->header[i].Char), 1, 1, ofp);
	FileLength++;

	len = strlen(T->header[i].bits);
	fwrite(&len, 1, 1, ofp);
	FileLength++;

	if (len % 8 != 0) {
	for (int j = len % 8; j < 8; j++)
	strcat(T->header[i].bits, "0");
	}

	while (T->header[i].bits[0] != 0) {
	c = 0;
	for (int j = 0; j < 8; j++) {
	if (T->header[i].bits[j] == '1')
	c = (c << 1) \| 1;
	else
	c = c << 1;
	}
	strcpy(T->header[i].bits, T->header[i].bits + 8);
	fwrite(&c, 1, 1, ofp);
	FileLength++;
	}
	}
	return FileLength;
	}

文件解压缩

	void File_UnCompress(HuffManCode T, FILE ifp, FILE ofp, int Len) {
	char buf[255], bx[255];
	int CurPer = 0, per = 10;
	int i, tmp, len1, num = T->num;
	unsigned int len = strlen(T->Set[num-1].bits);
	unsigned char c;

	fseek(ifp, 8, SEEK_SET);
	bx[0] = 0;
	// Read compressed files and convert
	while (CurPer != Len) {
	while (strlen(bx) < len) {
	fread(&c, 1, 1, ifp);
	tmp = c;
	_itoa(tmp, buf, 2);
	len1 = strlen(buf);
	for (int j = 8; j > len1; j--) {
	strcat(bx, "0");
	}
	strcat(bx, buf);
	}
	for (i = 0; i < num; i++) {
	if (memcmp(T->Set[i].bits, bx, T->Set[i].Length) == 0)
	break;
	}
	strcpy(bx, bx + T->Set[i].Length);
	c = T->Set[i].Char;
	fwrite(&c, 1, 1, ofp);
	CurPer++;

	// Show progress
	if (100 * CurPer / Len > per) {
	printfPercent(per);
	per += 10;
	}
	}
	printfPercent(100);
	}

# 解释如何以时间 $O(N\log{N})$ 实现首次适合算法和最佳适合算法

首次合适算法：用伸展树或最小堆进行装箱，只要有空闲的能装的就用。
最佳合适算法：使用伸展树存储空白区域容量，找最合适的，不是最合适的继续伸展。

# 编写一个程序比较各种装箱试探方法 (在时间上和所用箱子的数量上) 的性能。

下项适合算法

	// printf() can be changed to array linked list storage.
	int NextFit(double A[], int N, double Capacity) {
	int res = 1;
	double bin_rem = Capacity;

	for (int i = 0; i < N; i++) {
	if (A[i] > bin_rem) {
	res++;
	printf(" (");
	bin_rem = Capacity - A[i];
	printf("%.2f", A[i]);
	} else {
	bin_rem -= A[i];
	printf(" %.2f", A[i]);
	}
	}
	return res;
	}

首次适合算法

	// printf() can be changed to array linked list storage.
	int FirstFit(double A[], int N, double Capacity) {
	int res = 0;
	double bin_rem[9];
	for (int i = 0; i < N; i++) {
	int j;
	for (j = 0; j < res; j++) {
	if (bin_rem[j] >= A[i]) {
	bin_rem[j] -= A[i];
	printf("%d: %.2f\n", j, A[i]);
	break;
	}
	}
	if (j == res) {
	bin_rem[res] = Capacity - A[i];
	printf("%d: %.2f\n", res, A[i]);
	res++;

	}
	}
	return res;
	}

最佳适合算法

	// printf() can be changed to array linked list storage.
	int BestFit(double A[], int N, double Capacity) {
	int res = 0;
	double bin_rem[10], min; // N = 10
	int j, bi;

	for (int i = 0; i < N; i++) {
	min = Capacity + 0.1;
	bi = 0;

	for (j = 0; j < res; j++) {
	if(bin_rem[j] >= A[i] && bin_rem[j] - A[i] < min) {
	bi = j;
	min = bin_rem[j] - A[i];
	}
	}

	if (min == Capacity + 0.1) {
	bin_rem[res] = Capacity - A[i];
	printf("%d: %.2f\n", res, A[i]);
	res++;
	} else {
	bin_rem[bi] -= A[i];
	printf("%d: %.2f\n", bi, A[i]);
	}
	}
	return res;
	}

最坏适合算法

	// printf() can be changed to array linked list storage.
	int WorstFit(double A[], int N, double Capacity) {
	int res = 0;
	double bin_rem[10], max; // N = 10
	int wi, j;

	for (int i = 0; i < N; i++) {
	max = -1.0, wi = 0;

	for (j = 0; j < res; j++) {
	if (bin_rem[j] >= A[i] && bin_rem[j] - A[i] > max) {
	wi = j;
	max = bin_rem[j] - A[i];
	}
	}

	if (max == -1.0) {
	bin_rem[res] = Capacity - A[i];
	printf("%d: %.2f\n", res, A[i]);
	res++;
	} else {
	bin_rem[wi] -= A[i];
	printf("%d: %.2f\n", wi, A[i]);
	}
	}
	return res;
	}

首次合适递减算法

	int FirstFit_Decreasing(double A[], int N, double Capacity) {
	Sort(A, N);
	return FirstFit(A, N, Capacity);
	}

最坏合适递减算法

	int BestFit_Decreasing(double A[], int N, double Capacity) {
	Sort(A, N);
	return BestFit(A, N, Capacity);
	}

# 证明定理 10.7。

证明过程实际和定理 10.6 过程一致，只是原始的表达式换了。

# 证明定理 10.8。

使用归纳证明可以得出结论，当 $k=1$ 时。 $T(N)=O(N)$ 明显成立。当 $k$ 逐渐增大，可得出最终结论。

# 将 N 个点放入一个单位方格中。证明最近一对点之间的距离为 $O(N^{1/2})$

单位方格划分为 N-1 份，且每份宽为 $1/\sqrt {N-1} $, 假设总共点有 N 个，则必有两个在一个方格内，则可认为最短距离在 0 到 $2/\sqrt{N-1}$ .

# 论证对于最近点算法，在带内的平均点数是 $O(\sqrt{N})$ 。提示：利用前一道练习的结果。

在前一道题的基础上，假设有 N 个点，且带的宽度为 $O(1/\sqrt{N})$ , 并覆盖在单位方格内，我们期待相似的点落在带上，因此可以假设所有点落在带上，则有 $O(N/\sqrt{N})$ 点在带上，所以在带内的平均点数可以是 $O(\sqrt{N})$

# 编写一个程序实现最近点对算法.

# 使用三分化中项的中项方法，快速选择算法的渐近运行时间是多少？

O (N) 的附加工作，O (N/3) 的递归，O (2N/3) 的枢纽元范围选择。所以 $T(N)=T(2N/3)+T(N/3)+O(N)$ , 总运行时间为 $O(\log{N})$ 。

# 证明七分化中项的中项的快速选择算法是线性的。为什么证明中不用七分化中项的中项方法

同样这需要 O (N) 的附加工作，O (N/7) 的递归，O (5N/7) 的枢纽元范围选择，所以 $T(N)=T(5N/7)+T(N/7)+O(N)$ ，如果它在某些场景运行时间是线性时间，我们会采用它。

# 实现第 7 章中的快速选择算法，快速选择便用五分化中项的中项方法，并实现 10.2.3 节末尾的抽样算法。比较它们的运行时间。

快速选择算法

	/Place the kth smallest element in the kth position./
	/Beacause arrays start at 0, this will be index k-1./
	void QSelect(int A[],int k,int Left,int Right)
	{
	int i,j;
	int Pivot;

	if(Left+Cutoff<=Right)
	{
	Pivot = Median3(A,Left,Right);
	// Pivot = Median5(A,Left,Right);
	i = Left;j = Right-1;
	for(;;)
	{
	while(A[++i]<Pivot){}
	while(A[--j]>Pivot){}
	if(i<j)
	Swap(&A[i],&A[j]);
	else
	break;
	}
	Swap(&A[i],&A[Right-1]);//Restore Pivot

	if(k<=i)
	QSelect(A,k,Left,i-1);
	else if(k>i+1)
	QSelect(A,k,i+1,Right);
	}
	else//Do an Insertion Sort on the subarray
	InsertSort(A+Left,Right-Left+1);
	}

五分中项抽样算法

	static int Median5(int A[], int Left,int Right) {
	int N = Right - Left + 1;
	// int tmp[N][5], count = 0;
	int tmp[10][5], count = 0;
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	tmp[i][j] = A[count++];
	}
	}

	int M[5];
	for (int i = 0; i < N; i++) {
	M[i] = Median3(tmp[i], 0, 4);
	}

	return Median3(M, 0, 4);
	}

# 许多用于计算五分化中项的中项的信息都被丢弃了。指出怎样通过更仔细地使用这些信息减少比较的次数

用于五项中分法计算中项时有各有百分之三十的元素是小于或大于枢纽元的，这类可以通过额外的工作避免再次进入主程序的比较中。

	double Closest_Point(Point T, int N) {
	qsort(T->P, N, sizeof(_point), Compare_X);
	Point_Print(T, N);
	return Rec(T, 0, N-1);
	}