Homework

约 4740 个字 43 行代码 11 张图片 预计阅读时间 16 分钟

Abstract

本部分用以记录每周发布在 PTA 上作业题的客观题，部分题目 看我心情 会写解析。

Homework 1

2-1 Insert 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree. Which one of the following statements is FALSE?

• A. 4 is the root

• B. 3 and 7 are siblings

• C. 2 and 6 are siblings

• D. 9 is the parent of 7

Solution

正确答案：B

2-2 For the result of accessing the keys 3, 9, 1, 5 in order in the splay tree in the following figure, which one of the following statements is FALSE?

• A. 5 is the root

• B. 1 and 9 are siblings

• C. 6 and 10 are siblings

• D. 3 is the parent of 4

Solution

正确答案：D

2-3 If the depth of an AVL tree is 6 (the depth of an empty tree is defined to be -1), then the minimum possible number of nodes in this tree is:

• A. 13

• B. 17

• C. 20

• D. 33

Solution

正确答案：D

我们有

\[ n_h = \left\{ \begin{array}{l} 1 & (h = 0) \\ 2 & (h = 1) \\ n_{h-1} + n_{h-2} + 1 & (h > 1) \end{array} \right. \]

注意是从 \(h = 0\) 开始的，代入计算即可，\(n_6 = 8n_1 + 5n_0 + 12 = 33\)。

2-4 When doing amortized analysis, which one of the following statements is FALSE?

• A. Aggregate analysis shows that for all \(n\), a sequence of \(n\) operations takes worst-case time \(T(n)\) in total. Then the amortized cost per operation is therefore \(T(n)/n\)

• B. For potential method, a good potential function should always assume its maximum at the start of the sequence

• C. For accounting method, when an operation's amortized cost exceeds its actual cost, we save the difference as credit to pay for later operations whose amortized cost is less than their actual cost

• D. The difference between aggregate analysis and accounting method is that the later one assumes that the amortized costs of the operations may differ from each other

Solution

正确答案：B

正确表述为 minimum。

2-5 Consider the following buffer management problem. Initially the buffer size (the number of blocks) is one. Each block can accommodate exactly one item. As soon as a new item arrives, check if there is an available block. If yes, put the item into the block, induced a cost of one. Otherwise, the buffer size is doubled, and then the item is able to put into. Moreover, the old items have to be moved into the new buffer so it costs \(k+1\) to make this insertion, where \(k\) is the number of old items. Clearly, if there are \(N\) items, the worst-case cost for one insertion can be \(\Omega (N)\). To show that the average cost is \(O(1)\), let us turn to the amortized analysis. To simplify the problem, assume that the buffer is full after all the \(N\) items are placed. Which of the following potential functions works?

• A. The number of items currently in the buffer

• B. The opposite number of items currently in the buffer

• C. The number of available blocks currently in the buffer

• D. The opposite number of available blocks in the buffer

Solution

正确答案：D

证明过程引用本题解析：

设 \(size \; i\) 为第 \(i\) 次插入前 buffer 的大小。

直观理解的话，势能函数要做到在开销较大的操作时使总势能降低。检查几个选项，对于缓冲区已满时的插入操作，我们记 $ \hat{c_i} = c_i + \phi_i - \phi_{i-1}$，缓冲区可用的 block 数为 \(k\)，则 D 选项有 \(\phi_i - \phi_{i-1} = -k - 0 = -k\)，可以使得总势能降低，而其它选项都不可以，因此选 D。

Homework 2

1-1 A 2-3 tree with 3 nonleaf nodes must have 18 keys at most.

• T

• F

Solution

正确答案：T

2-1 In the red-black tree that results after successively inserting the keys 41; 38; 31; 12; 19; 8 into an initially empty red-black tree, which one of the following statements is FALSE?

• A. 38 is the root

• B. 19 and 41 are siblings, and they are both red

• C. 12 and 31 are siblings, and they are both black

• D. 8 is red

Solution

正确答案：B

2-2 After deleting 15 from the red-black tree given in the figure, which one of the following statements must be FALSE?

• A. 11 is the parent of 17, and 11 is black

• B. 17 is the parent of 11, and 11 is red

• C. 11 is the parent of 17, and 11 is red

• D. 17 is the parent of 11, and 17 is black

Solution

正确答案：C

如果 11 是 17 的父节点且为红色，则其左右子树黑高不相等。

2-3 Insert 3, 1, 4, 5, 9, 2, 6, 8, 7, 0 into an initially empty 2-3 tree (with splitting). Which one of the following statements is FALSE?

• A. 7 and 8 are in the same node

• B. the parent of the node containing 5 has 3 children

• C. the first key stored in the root is 6

• D. there are 5 leaf nodes

Solution

正确答案：A

2-4 After deleting 9 from the 2-3 tree given in the figure, which one of the following statements is FALSE?

• A. the root is full

• B. the second key stored in the root is 6

• C. 6 and 8 are in the same node

• D. 6 and 5 are in the same node

Solution

正确答案：D

2-5 Which of the following statements concerning a B+ tree of order \(M\) is TRUE?

• A. the root always has between 2 and \(M\) children

• B. not all leaves are at the same depth

• C. leaves and nonleaf nodes have some key values in common

• D. all nonleaf nodes have between \(\lceil M/2\rceil\) and \(M\) children

Solution

正确答案：C

Homework 3

1-1 In distributed indexing, document-partitioned strategy is to store on each node all the documents that contain the terms in a certain range.

• T

• F

Solution

正确答案：F

描述的是 term-partitioned strategy，document-partitioned strategy 指将文档集合切分，每个节点包含一部分文档。前者指的是将词典切分，每个节点包含一部分词条。

1-2 When evaluating the performance of data retrieval, it is important to measure the relevancy of the answer set.

• T

• F

Solution

正确答案：F

answer set relevancy 是 information retrieval 的指标，而非 data retrieval。后者主要考虑响应时间、索引占用空间等指标。

1-3 Precision is more important than recall when evaluating the explosive detection in airport security.

• T

• F

Solution

正确答案：F

1-4 While accessing a term by hashing in an inverted file index, range searches are expensive.

• T

• F

Solution

正确答案：T

2-1 When measuring the relevancy of the answer set, if the precision is high but the recall is low, it means that:

• A.most of the relevant documents are retrieved, but too many irrelevant documents are returned as well

• B.most of the retrieved documents are relevant, but still a lot of relevant documents are missed

• C.most of the relevant documents are retrieved, but the benchmark set is not large enough

• D.most of the retrieved documents are relevant, but the benchmark set is not large enough

Solution

正确答案：B

2-2 Which of the following is NOT concerned for measuring a search engine?

• A.How fast does it index

• B.How fast does it search

• C.How friendly is the interface

• D.How relevant is the answer set

Solution

正确答案：C

2-3 There are 28000 documents in the database. The statistic data for one query are shown in the following table. The recall is: __

	Relevant	Irrelevant
Retrieved	4000	12000
Not Retrieved	8000	4000

• A.14%

• B.25%

• C.33%

• D.50%

Solution

正确答案：C

Homework 4

1-1 The result of inserting keys 1 to \(2^k -1\) for any \(k>4\) in order into an initially empty skew heap is always a full binary tree.

• T

• F

Solution

正确答案：T

1-2 The right path of a skew heap can be arbitrarily long.

• T

• F

Solution

正确答案：T

不同于左偏堆维护一个 Npl（null path length）并要求 Npl(Left) >= Npl(Right)，从而使得右路径长度最多为 \(O(logN)\)，斜堆没有任何严格结构限制，其 \(O(logN)\) 是摊还的，可能会出现开销较大的单次操作，最坏情况下退化为链表。

2-1 Merge the two leftist heaps in the following figure. Which one of the following statements is FALSE?

• A.2 is the root with 11 being its right child

• B.the depths of 9 and 12 are the same

• C.21 is the deepest node with 11 being its parent

• D.the null path length of 4 is less than that of 2

Solution

正确答案：D

合并后的左偏堆中 4 的 npl 为 2，2 的 npl 也为 2，因此 D 是错误的。

2-2 We can perform BuildHeap for leftist heaps by considering each element as a one-node leftist heap, placing all these heaps on a queue, and performing the following step: Until only one heap is on the queue, dequeue two heaps, merge them, and enqueue the result. Which one of the following statements is FALSE?

• A.in the \(k\)-th run, \(\lceil N/2^k \rceil\) leftist heaps are formed, each contains \(2^k\) nodes

• B.the worst case is when \(N=2^K\) for some integer \(K\)

• C.the time complexity \(T(N) = O(\frac{N}{2}log 2^0 + \frac{N}{2^2}log 2^1 + \frac{N}{2^3}log 2^2 + \cdots + \frac{N}{2^K}log 2^{K-1})\) for some integer \(K\) so that \(N=2^K\)

• D.the worst case time complexity of this algorithm is \(\Theta (NlogN)\)

Solution

正确答案：D

2-3 Insert keys 1 to 15 in order into an initially empty skew heap. Which one of the following statements is FALSE?

• A.the resulting tree is a complete binary tree

• B.there are 6 leaf nodes

• C.6 is the left child of 2

• D.11 is the right child of 7

Solution

正确答案：B

2-4 Merge the two skew heaps in the following figure. Which one of the following statements is FALSE?

• A.15 is the right child of 8

• B.14 is the right child of 6

• C.1 is the root

• D.9 is the right child of 3

Solution

正确答案：A

5-1 Merge two leftist heaps

The function is to merge two leftist heaps H1 and H2.

PriorityQueue Merge( PriorityQueue H1, PriorityQueue H2 )
{ 
  if (H1==NULL) return H2;
  if (H2==NULL) return H1;
  if ( ) (3 分)
    swap(H1, H2);  //swap H1 and H2
  if ( H1->Left == NULL )
    ( ) (3 分)
  else {
    H1->Right = Merge( H1->Right, H2 );
    if ( H1->Left->Npl < H1->Right->Npl )
        SwapChildren( H1 );  //swap the left child and right child of H1
        ( ) (3 分)
  }
  return H1;
}

solution

1. H1->Element > H2->Element
2. H1->Left = H2
3. H1->Npl = H1->Right->Npl + 1

Homework 5

2-1 Which of the following binomial trees can represent a binomial queue of size 42?

• A.\(B_0\) \(B_1\) \(B_2\) \(B_3\) \(B_4\) \(B_5\)

• B.\(B_1\) \(B_3\) \(B_5\)

• C.\(B_1\) \(B_5\)

• D.\(B_2\) \(B_4\)

Solution

正确答案：B

有 \(42 = \text{101010}_2\)，即 \(B_5 B_3 B_1\)。

2-2 For a binomial queue, __ takes a constant time on average.

• A.merging

• B.find-max

• C.delete-min

• D.insertion

Solution

正确答案：D

插入等价于二进制 + 1，使用聚合法做摊还分析，假设连续插入 N 次，则总的进位次数为

\[ \text{Total Cost} = N(1 + \frac{1}{2} + \frac{1}{4} + \dots) = 2N \]

平均每次插入的代价为 \(\frac{2N}{N} = 2 = O(1)\)，最坏情况下是 \(O(logN)\)。

其它选项中，merge 的复杂度为 \(O(logN)\)，find-max 的复杂度为 \(O(N)\)，delete-min 的复杂度为 \(O(logN)\)。

2-3 Merge the two binomial queues in the following figure. Which one of the following statements must be FALSE?

• A.there are two binomial trees after merging, which are \(B_2\) and \(B_4\)

• B.13 and 15 are the children of 4

• C.if 23 is a child of 2, then 12 must be another child of 2

• D.if 4 is a child of 2, then 23 must be another child of 2

Solution

正确答案：D

2-4 Delete the minimum number from the given binomial queues in the following figure. Which one of the following statements must be FALSE?

• A.there are two binomial trees after deletion, which are \(B_1\) and \(B_2\)

• B.11 and 15 can be the children of 4

• C.29 can never be the root of any resulting binomial tree

• D.if 29 is a child of 4, then 15 must be the root of \(B_1\)

Solution

正确答案：C

显然 29 可以作为 \(B_1\) 的根。

5-1 BinQueue_Find

The functions BinQueue_Find and Recur_Find are to find X in a binomial queue H. Return the node pointer if found, otherwise return NULL.

BinTree BinQueue_Find( BinQueue H, ElementType X )
{
    BinTree T, result = NULL;
    int i, j; 

    for( i=0, j=1; j<=H->CurrentSize; i++, j*=2) {  /* for each tree in H */
        T= H->TheTrees[i];
        if ( X ( )(2 分) ){  /* if need to search inside this tree */
            result = Recur_Find(T, X);
            if ( result != NULL ) return result;
        } 
    }
    return result;
}

BinTree Recur_Find( BinTree T, ElementType X )
{
    BinTree result = NULL;
    if ( X==T->Element ) return T;
    if ( T->LeftChild!=NULL ){
        result = Recur_Find(T->LeftChild, X);
        if ( result!=NULL ) return result;
    } 
    if ( ( )(2 分) )
        result = Recur_Find(T->NextSibling, X);
    return result;
}

Solution

1. >= T->Element
2. T->NextSibling != NULL

Homework 6

2-1 In the Tic-tac-toe game, a "goodness" function of a position is defined as \(f(P) = W_{computer} - W_{human}\)where \(W\) is the number of potential wins at position \(P\).In the following figure, O represents the computer and X the human. What is the goodness of the position of the figure?

• A.-1

• B.0

• C.4

• D.5

Solution

正确答案：B

这里对 potential wins 的定义为当前局面下所有可能取胜的线路，因此 \(W_{\text{computer}} = 3\)，\(W_{\text{human}} = 3\)，故 \(f(P) = 3 - 3 = 0\)。

2-2 Given the following game tree, which node is the first one to be pruned with α-β pruning algorithm?

• A.a

• B.b

• C.c

• D.d

Solution

正确答案：C

Homework 7

2-1 When solving a problem with input size \(N\) by divide and conquer, if at each stage the problem is divided into 8 sub-problems of equal size \(N/3\), and the conquer step takes \(O(N^2 logN)\) to form the solution from the sub-solutions, then the overall time complexity is __.

• A.\(O(N^2 logN)\)

• B.\(O(N^2 log^2 N)\)

• C.\(O(N^3 logN)\)

• D.\(O(N^{log8/log3})\)

Solution

正确答案：A

\(T(N) = 8T(N/3) + O(N^2 \log{N})\)，则 \(a = 8, b^k = 3^2 = 9\)，故 \(T(N) = O(N^k \log^p{N}) = O(N^2 logN)\)。

2-2 To solve a problem with input size \(N\) by divide and conquer algorithm, among the following methods, __ is the worst.

• A.divide into 2 sub-problems of equal complexity \(N/3\) and conquer in \(O(N)\)

• B.divide into 2 sub-problems of equal complexity \(N/3\) and conquer in \(O(NlogN)\)

• C.divide into 3 sub-problems of equal complexity \(N/2\) and conquer in \(O(N)\)

• D.divide into 3 sub-problems of equal complexity \(N/3\) and conquer in \(O(NlogN)\)

Solution

正确答案：C

2-3 3-way-mergesort : Suppose instead of dividing in two halves at each step of the mergesort, we divide into three one thirds, sort each part, and finally combine all of them using a three-way-merge. What is the overall time complexity of this algorithm ?

• A.\(O(n(\log^2 n))\)

• B.\(O(n^2 \log n)\)

• C.\(O(n\log n)\)

• D.\(O(n)\)

Solution

正确答案：C

2-4 Which one of the following is the lowest upper bound of \(T(n)\) for the following recursion \(T(n) = 2T(\sqrt{n}) + \log n\)?

• A.\(O(\log n\log \log n)\)

• B.\(O(\log^2 n)\)

• C.\(O(n\log n)\)

• D.\(O(n^2)\)

Solution

正确答案：A

Homework 8

2-1 Rod-cutting Problem: Given a rod of total length \(N\) inches and a table of selling prices \(P_L\) for lengths \(L = 1, 2, \cdots , M\). You are asked to find the maximum revenue \(R_N\) obtainable by cutting up the rod and selling the pieces. For example, based on the following table of prices, if we are to sell an 8-inch rod, the optimal solution is to cut it into two pieces of lengths 2 and 6, which produces revenue \(R_8 = P_2 +P_6 = 5+17 = 22\). And if we are to sell a 3-inch rod, the best way is not to cut it at all.

Length L	1	2	3	4	5	6	7	8	9	10
Price PL​	1	5	8	9	10	17	17	20	23	28

Which one of the following statements is FALSE?

• A.This problem can be solved by dynamic programming

• B.The time complexity of this algorithm is \(O(N^2)\)

• C.If \(N\le M\), we have \(R_N = \max \lbrace P_N , \max_{1\le i < N} \lbrace R_i + R_{N-i} \rbrace \rbrace\)

• D.If \(N>M\), we have \(R_N = \max_{1\le i < N} \lbrace R_i + R_{N-M} \rbrace\)

Solution

正确答案：D

显然可以应用动态规划求解，写出递推关系式：

\[ \text{if} \; N > M, R_N = \max_{1 \leq i < N} \lbrace R_i + R_{N-i} \rbrace \\[1.5em] \text{if} \; N \leq M, R_N = \max \lbrace P_N , \max_{1\le i < N} \lbrace R_i + R_{N-i} \rbrace \rbrace \]

可知 D 错误。错误的点在于不应将 \(N - M\) 单独作为递归的一种子结构，这忽略了其它潜在的切割策略。

2-2 In dynamic programming, we derive a recurrence relation for the solution to one subproblem in terms of solutions to other subproblems. To turn this relation into a bottom up dynamic programming algorithm, we need an order to fill in the solution cells in a table, such that all needed subproblems are solved before solving a subproblem. Among the following relations, which one is impossible to be computed?

• A.\(A(i, j) = min (A(i-1,j), A(i,j-1), A(i-1,j-1))\)

• B.\(A(i, j) = F(A(min\{i, j\} - 1, min\{i, j\} - 1), A(max\{i, j\} - 1, max\{i, j\} -1))\)

• C.\(A(i, j) = F(A(i, j -1), A(i - 1, j - 1), A(i - 1, j + 1))\)

• D.\(A(i,j) = F(A(i-2, j-2), A(i+2,j+2))\)

Solution

正确答案：D

前三者都有可行的计算顺序，例如 A 可以用 外层 i 内层 j 的双层循环完成；B 只依赖于主对角线上的元素 \(A(k, k)\)，可以先算出所有的主对角线元素，之后所有 \(A(i, j)\) 的值都可计算；C 类似于 A；但 D 选项中 \(A(i, j)\) 与 \(A(i+2, j+2)\) 相互依赖，不可计算。

2-3 Given a recurrence equation \(f_{i,j,k} =f_{i,j+1,k}+\min_{0 \le l \le k}\{f_{i-1,j,l}+w_{j,l}\}\). To solve this equation in an iterative way, we cannot fill up a table as follows:

• A.for k in 0 to n: for i in 0 to n: for j in n to 0

• B.for i in 0 to n: for j in 0 to n: for k in 0 to n

• C.for i in 0 to n: for j in n to 0: for k in n to 0

• D.for i in 0 to n: for j in n to 0: for k in 0 to n

Solution

正确答案：B

根据递推式，\(f_{i,j,k}\) 依赖于 \(f_{i,j+1,k}\) 与 \(f_{i-1,j,l}\)，为保证 i - 1 与 j + 1 在 i 与 j 之前计算完毕，i 循环的顺序应为 0 - n，j 应为 n - 0，k 的顺序在这里不会影响结果。因此 B 选项是错误的。

Homework 9

1-1 Let S be the set of activities in Activity Selection Problem. Then the earliest finish activity \(a_m\) must be included in all the maximum-size subset of mutually compatible activities of S.

• T

• F

Solution

正确答案：F

1-2 Let \(C\) be an alphabet in which each character \(c\) in \(C\) has frequency \(c.freq\). If the size of \(C\) is \(n\), the length of the optimal prefix code for any character \(c\) is not greater than \(n-1\).

• T

• F

Solution

正确答案：T

2-1 Consider the problem of making change for \(n\) cents using the fewest number of coins. Assume that each coin's value is an integer.The coins of the lowest denomination（面额） is the cent.

(I) Suppose that the available coins are quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent). The greedy algorithm always yields an optimal solution.

(II) Suppose that the available coins are in the denominations that are powers of c, that is, the denominations are \(c^0\), \(c^1\), ..., \(c^k\) for some integers \(c>1\) and \(k>=1\). The greedy algorithm always yields an optimal solution.

(III) Given any set of \(k\) different coin denominations which includes a penny (1 cent) so that there is a solution for every value of \(n\), greedy algorithm always yields an optimal solution.

Which of the following is correct?

• A.Statement (I) is false.

• B.Statement (II) is false.

• C.Statement (III) is false.

• D.All of the three statements are correct.

Solution

正确答案：C

前两种情况下，较大面额的硬币可以被较小面额的硬币精确表示，贪心总是局部最优的，因此是正确的；第三种情况下则不一定成立，例如我们有 1, 20, 50 三种面额的硬币，需要表示 60，此时最优策略应该是 20 × 3，而不是贪心所得的 50 + 10 × 1。对于第三种情况我们应使用动规求解。

Homework 10

1-1 If \(L_1 \leq_p L_2\) and \(L_2 \in NP\), then \(L_1 \in NP\).

• T

• F

1-2 All NP-complete problems are NP problems.

• T

• F

1-3 All the languages can be decided by a non-deterministic machine.

• T

• F

1-4 All NP problems can be solved in polynomial time in a non-deterministic machine.

• T

• F

1-5 If a problem can be solved by dynamic programming, it must be solved in polynomial time.

• T

• F

2-1 Among the following problems, __ is NOT an NP-complete problem.

• A.Vertex cover problem

• B.Hamiltonian cycle problem

• C.Halting problem

• D.Satisfiability problem

2-2 Suppose Q is a problem in NP, but not necessarily NP-complete. Which of the following is FALSE?

• A.A polynomial-time algorithm for SAT would sufficiently imply a polynomial-time algorithm for Q.

• B.A polynomial-time algorithm for Q would sufficiently imply a polynomial-time algorithm for SAT.

• C.If Q \(\notin P\), then \(P \neq NP\).

• D.If Q is NP-hard, then Q is NP-complete.

Homework 11

1-3 Suppose ALG is an \(\alpha\)-approximation algorithm for an optimization problem \(\Pi\) whose approximation ratio is tight. Then for every \(\epsilon > 0\) there is no (\(\alpha - \epsilon\))-approximation algorithm for \(\Pi\) unless P = NP.

• T

• F

1-4 As we know there is a 2-approximation algorithm for the Vertex Cover problem. Then we must be able to obtain a 2-approximation algorithm for the Clique problem, since the Clique problem can be polynomially reduced to the Vertex Cover problem.

• T

• F

2-1 For the bin-packing problem: let \(S=\sum S_i\). Which of the following statements is FALSE?

• A.The number of bins used by the next-fit heuristic is never more than \(\lceil 2S\rceil\)

• B.The number of bins used by the first-fit heuristic is never more than \(\lceil 2S\rceil\)

• C.The next-fit heuristic leaves at most one bin less than half full

• D.The first-fit heuristic leaves at most one bin less than half full

2-2 To approximate a maximum spanning tree \(T\) of an undirected graph \(G=(V,E)\) with distinct edge weights \(w(u,v)\) on each edge \((u,v)\in E\), let's denote the set of maximum-weight edges incident on each vertex by \(S\). Also let \(w(E')=\sum_{(u,v)\in E'} w(u,v)\) for any edge set \(E'\). Which of the following statements is TRUE?

• A.\(S=T\) for any graph \(G\)

• B.\(S\ne T\) for any graph \(G\)

• C.\(w(S) \ge w(T)/2\) for any graph \(G\)

• D.None of the above

2-3 Assume that you are a real world Chinese postman, which have learned an awesome course "Advanced Data Structures and Algorithm Analysis" (ADS). Given a 2-dimensional map indicating \(N\) positions \(p_i(x_i,y_i)\) of your post office and all the addresses you must visit, you'd like to find a shortest path starting and finishing both at your post office, and visit all the addresses at least once in the circuit. Fortunately, you have a magic item "Bamboo copter & Hopter" from "Doraemon", which makes sure that you can fly between two positions using the directed distance (or displacement).

("Bamboo copter & Hopter", japan12.com/bamboo-copter-hopter)

However, reviewing the knowledge in the ADS course, it is an \(NPC\) problem! Wasting too much time in finding the shortest path is unwise, so you decide to design a \(2-approximation\) algorithm as follows, to achieve an acceptable solution.

Compute a minimum spanning tree T connecting all the addresses.
Regard the post office as the root of T.
Start at the post office.
Visit the addresses in order of a _____ of T.
Finish at the post office.

There are several methods of traversal which can be filled in the blank of the above algorithm. Assume that \(P\neq NP\), how many methods of traversal listed below can fulfill the requirement?

Level-Order Traversal

Pre-Order Traversal

Post-Order Traversal

• A.0

• B.1

• C.2

• D.3

Homework 12

1-1 For the graph given in the following figure, if we start from deleting the black vertex, then local search can always find the minimum vertex cover.

• T

• F

1-2 We are given a set of sites \(S=\{ s_1, s_2, \cdots, s_n\}\) in the plane, and we want to choose a set of \(k\) centers \(C=\{ c_1, c_2, \cdots, c_k\}\) so that the maximum distance from a site to the nearest center is minimized. Here \(c_i\) can be an arbitrary point in the plane.

A local search algorithm arbitrarily choose \(k\) points in the plane to be the centers, then

• (1) divide \(S\) into \(k\) sets, where \(S_i\) is the set of all sites for which \(c_i\) is the nearest center; and
• (2) for each \(S_i\), compute the central position as a new center for all the sites in \(S_i\).

If steps (1) and (2) cause the covering radius to strictly decrease, we perform another iteration, otherwise the algorithm stops.

When the above local search algorithm terminates, the covering radius of its solution is at most 2 times the optimal covering radius.

• T

• F

1-3 Local search algorithm can be used to solve lots of classic problems, such as SAT and \(N\)-Queen problems. Define the configuration of SAT to be \(X\) = vector of assignments of \(N\) boolean variables, and that of \(N\)-Queen to be \(Y\) = positions of the \(N\) queens in each column. The sizes of the search spaces of SAT and \(N\)-Queen are \(O(2^N)\) and \(O(N^N)\), respectively.

• T

• F

2-1 Spanning Tree Problem: Given an undirected graph \(G = (V, E)\), where \(|V | = n\) and \(|E| = m\). Let \(F\) be the set of all spanning trees of \(G\). Define \(d(u)\) to be the degree of a vertex \(u \in V\). Define \(w(e)\) to be the weight of an edge \(e \in E\).We have the following three variants of spanning tree problems:

• (1) Max Leaf Spanning Tree: find a spanning tree \(T \in F\) with a maximum number of leaves.
• (2) Minimum Spanning Tree: find a spanning tree \(T \in F\) with a minimum total weight of all the edges in \(T\).
• (3) Minimum Degree Spanning Tree: find a spanning tree \(T \in F\) such that its maximum degree of all the vertices is the smallest.

For a pair of edges \((e, e')\) where \(e \in T\) and \(e' \in (G-T)\) such that \(e\) belongs to the unique cycle of \(T\cup e'\), we define edge-swap\((e, e')\) to be \((T-e)\cup e'\).

Here is a local search algorithm:

T = any spanning tree in F;
while (there is an edge-swap(e, e') which reduces Cost(T)) {
    T = T - e + e';
}
return T;

Here Cost(T) is the number of leaves in T in Max Leaf Spanning Tree; or is the total weight of T in Minimum Spanning Tree; or else is the minimum degree of T in Minimum Degree Spanning Tree.

Which of the following statements is TRUE?

• A.The local search always return an optimal solution for Max Leaf Spanning Tree

• B.The local search always return an optimal solution for Minimum Spanning Tree

• C.The local search always return an optimal solution for Minimum Degree Spanning Tree

• D.For neither of the problems that this local search always return an optimal solution

2-2 There are \(n\) jobs, and each job \(j\) has a processing time \(t_j\). We will use a local search algorithm to partition the jobs into two groups A and B, where set A is assigned to machine \(M_1\) and set B to \(M_2\). The time needed to process all of the jobs on the two machines is \(T_1 = \sum_{j\in A} t_j\), \(T_2 = \sum_{j\in B} t_j\). The problem is to minimize \(|T_1 - T_2|\).

Local search: Start by assigning jobs \(1, \ldots, n/2\) to \(M_1\), and the rest to \(M_2\).The local moves are to move a single job from one machine to the other, and we only move a job if the move decreases the absolute difference in the processing times. Which of the following statement is true?

• A.The problem is NP-hard and the local search algorithm will not terminate.

• B.When there are many candidate jobs that can be moved to reduce the absolute difference, if we always move the job \(j\) with maximum \(t_j\), then the local search terminates in at most \(n\) moves.

• C.The local search algorithm always returns an optimal solution.

• D.The local search algorithm always returns a local solution with \(\frac{1}{2} T_1 \leq T_2 \leq 2 T_1\).

2-3 Max-cut problem: Given an undirected graph \(G = (V, E)\) with positive integer edge weights \(w_e\), find a node partition \((A, B)\) such that \(w(A, B)\), the total weight of edges crossing the cut, is maximized. Let us define \(S'\) be the neighbor of \(S\) such that \(S'\) can be obtained from \(S\) by moving one node from \(A\) to \(B\), or one from \(B\) to \(A\). We only choose a node which, when flipped, increases the cut value by at least \(w(A,B)/|V|\). Then which of the following is true?

• A.Upon the termination of the algorithm, the algorithm returns a cut \((A, B)\) so that \(2.5 w(A, B) \ge w(A^*, B^*)\), where \((A^*, B^*)\) is an optimal partition.

• B.The algorithm terminates after at most \(O(\log |V| \log W)\) flips, where \(W\) is the total weight of edges.

• C.Upon the termination of the algorithm, the algorithm returns a cut \((A, B)\) so that \(2 w(A, B) \ge w(A^*, B^*)\).

• D.The algorithm terminates after at most \(O(|V|^2)\) flips.