1. (5%) Among all n-digit numbers, how many of them contain the digits 2 and 7 but not the digits 0, 8, 9?

2. (5%) In how many ways can 2n people be divided into n pairs?

3. (7%) Let R be a transitive and reflexive relation on A. Let T be a relation on A such that (a,b) is in T if and only if both (a,b) and (b,a) are in R. Show that T is an equivalence relation.

Reflexive: Since $\forall a \in A, \, (a,a) \in R$ so $(a,a) \in T$ too.
Symmetric: If $(a,b) \in T,$ that means $(a,b) \in R \land (b,a) \in R,$ so $(b,a) \text{ is also } \in T.$
Transitive: Assume $(a,b) \text{ and } (b,c) \in T,$ then $(a,b),(b,c),(b,a),(c,b) \text{ is also } \in R.$ Since $R$ satisfies transitive, $(a,c) \text{ and } (c,a) \in R,$ so both of them also belongs to T.
Since T satisfies reflexive, symmetric and transitive, so it is an equivalence relation.

4. (8%) Given a recursive definition of $a_n: \, a_1 = 1; \, a_{k+1} = 3a_k + 1 \text{ for } k \geq 1,$ please derive a close-form formula for $a_n,$ and then prove that your formula is correct. (Hint: Write down the first six numbers $(a_1,a_2,a_3,a_4,a_5,a_6)$ and guess the formula).

5. (8%) Prove by induction that $3^{2n} – 1$ is divisible by 8 for all $n \geq 1.$

When $n = 1, \, 3^2 – 1 = 8$ is divisible by 8.
Assume when $n = k – 1,$ the hypotesis is correct.
When $n = k, \, 3^{2k} – 1 = (3^{2k-2} – 1) \times 3^2 + 8.$
Since $3^{2k-1} – 1$ is divisible by 8, so it’s obvious that $(3^{2k-2} – 1) \times 3^2 + 8$ is also divisible by 8.

6. (10%) Answer the following questions about binary trees.

(a) Given an initially empty min heap H, draw the min heap after the following operations: insert 34, insert 12, insert 28, delete-min, insert 9, insert 30, insert 15, and insert 5.
(b) Treat H as a priority queue where a key with a smaller value is of higher priority. Draw H after popping three keys out of it.
(c) Insert the three keys popped out from H in question (b) into an initially empty binary tree T, and then insert three other keys 45, 3, and 12. Draw T after completing these operations.

(a)

(b)

(c)

7. (6%) Answer the following questions about triangular matrix.

(a) In a lower triangular matrix, A, with n rows. What’s the total number of nonzero terms?
(b) Since storing a triangular matrix as a two dimensional array wastes space, we would like to find a way to store only the nonzero terms of the triangular matrix in a one dimensional array. Find the index of $A_{i,j}$ in a one dimensional array $b$ if we store $A_{1,1}$ at $b[0].$

8. (8%) Consider the following graph G represented by an adjacency list. Assume the dfn[3] = 5 and dfn[4] = 6 after we invoke the function dfnlow (as shown below) with the call dfnlow(5, -1) being executed. Then, after the function dfnlow(5, -1) is invoked,

(a) what is the value of dfn[1]?
(b) what is the value of low[1]?
(c) what is the value of low[2]?

The C declarations for adjacency list representation and function dfnlow():

#define MIN2 (x,y) ((x) < (y) ? (x) : (y))
#define MAX_VERTICES 100

typedef struct node *node_pointer;
typedef struct node {
int vertex;
struct node *link;
};
node_pointer graph[MAX_VERTICES];

int dfn[MAX_VERTICES], low[MAX_VERTICES];
int num;

void dfnlow(int u, int v)
{
/* v is the parent of u (if any). It is assumed that all entries of all dfn[] and low[] have been initialized to -1 and num been initialized to 0. */
node_pointer ptr;
int w;
dfn[u] = low[u] = num++;

for (ptr = graph[u]; ptr; ptr = ptr -> link) {
w = ptr -> vertex;

if (dfn[w] < 0) { /* w is an unvisited vertex */
dfnlow(w, u);
low[u] = MIN2(low[u], low[w]);
}
else if (w != v)
low[u] = MIN2(low[u], dfn[w]);
}
}

9. (9%) In heap sort, function adjust, heapInitialization, and heapSort (as shown below) are used. The function adjust starts with a binary tree whose left and right subtrees are max heaps and rearranges records so that the entire binary tree is a max heap, and the functions heapInitialization and heapSort use a series of adjusts to initialize the heap and perform a heap sort on a[1:n], respectively. Please analyze the complexities of:

(a) adjust.
(b) heapInitialization.
(c) heapSort.

The C declarations for heap and functions adjust(), heapInitialization(), and heapSort():

heapSort():
#define SWAP (x,y,t) ((t) = (x), (x) = (y), (y) = (t))

typedef struct {
int key;
} element;

void adjust(element a[], int root, int n)
{
int child, rootkey;
element temp;
temp = a[root];
rootkey = a[root].key;
child = 2 * root; /* left child */

while(child <= n) {
if ((child < n) && (a[child].key < a[child+1].key))
child++;

if (rootkey > a[child].key) /* compare root and max. child */
break;
else {
a[child / 2] = a[child]; /* move to parent */
child *= 2;
}
}
a[child / 2] = temp;
}

void heapInitialization(element a[], int n)
{
int i;
element temp;

for (i = n/2; i > 0; i--)
adjust(a, i, n);
}

void heapSort(element a[], int n)
{
int i;
element temp;

for (i = n-1; i > 0; i--) {
SWAP(a[1], a[i+1], temp);
adjust(a, 1, i);
}
}

10. (6%) Let n be an integer, and S be a set of integers, with range from 1 to $n^2.$ It is known that S has at least $\sqrt{n}$ items. Explain in details how to sort S in $O(|S|)$ time.

Pass 1: 針對 $key \, i \% \sqrt{n}$
Pass 2: 針對 $[key \, \dfrac{i}{\sqrt{n}}] \% \sqrt{n}$
Pass 3: 針對 $[key \, \dfrac{i}{n}] \% \sqrt{n}$
Pass 4: 針對 $[key \, \dfrac{i}{n \sqrt{n}}] \% \sqrt{n}$
Total time: $4 \times O(\sqrt{n}) = O(\sqrt{n})$

11. (4%)

(a) Explain why it takes at least 4 comparisons, in the worst case, to sort four distinct numbers.
(b) Show how to sort four distinct numbers with at most 4 comparisons.

(a)

$2^h \geq 4! \to h \geq lg4! > 4,$ 取$h = 5 \to$ 樹高等於5（比較4次）
(b) 把decision tree畫出來

12. (7%)

(a) Let S be a set of n positive integers, and we are interested if we can select some of the integers from S so that their sum is exactly m, Explain in detail how this can be done in $O(nm)$ time.
(b) The above problem is called a subset sum problem, which is NP-hard. So far, no polynomial-time algorithms are known to solve an NP-hard problem. Explain why an $O(nm)$-time algorithm is not considered as a polynomial-time algorithm for the subset sum problem.

(a)

$\begin{cases} S(i,j) = S(i-1,j) \text{ or } S(i-1,j-w_i)\\ S(0,j) = 0\\ S(i,0) = 1 \end{cases}$

(b) $m$需用$2^k$個bits存，因此時間複雜度為$O(2^k \times n)$ not polynomial.

13. (6%) Testing gifted or mediocre: m students take an exam which has n questions. Gifted students get all n answers right. Mediocre students get less than n/2 answers right. Grade all the exams, giving all gifted students an ‘A’ and all mediocre students a ‘C’.

Algorithm 1:
1. For each student, grade at most the first n/2 questions in order – stop as soon as you see a wrong answer.
2. If you’ve seen a wrong answer, give grade ‘C’. Otherwise give grade ‘A’.
Algorithm 2:
1. For each student, choose 10 questions at random and grade them.
2. If you’ve seen a wrong answer, give grade ‘C’. Otherwise give grade ‘A’.
Algorithm 3:
1. For each student, repeatedly choose a question at random and grade it, until you have graded n/2 correct answers or seen a wrong answer.
2. If you’ve seen a wrong answer, give grade ‘C’. Otherwise give grade ‘A’.

Explain the correctness and the running time of these three algorithms.

14. (6%)

(a) What is an optimal Huffman code for the set of frequencies, $\{1,1,2,3,5,8\},$ based on the first six Fibonacci numbers?
(b) Generalize your answer to find the optimal code when the frequencies are the first n Fibonacci numbers.

(a)
Fib[1] = 11111
Fib[2] = 11110
Fib[3] = 1110
Fib[4] = 110
Fib[5] = 10
Fib[6] = 0
(b)
Fib[1] = 111…11 (n-1個1)
Fib[2] = 111…10 (n-2個1)
Fib[3] = 11…10 (n-3個1)
.
.
.
Fib[n] = 0

15. (5%) The constrained 1-center problem: Given n planar points and a straight line L, find a smallest circle, whose center is restricted to lying on L, to cover these n points. The following lists an algorithm for solving this problem. Evaluate the time complexity, $T(n),$ of this algorithm using the recurrence relation of $T(n).$

Input: n points and a straight line $L:y = y’.$
Output: The constrained 1-center on L.

Step 1. If n is no more than 2, solve this problem by a brute-force method.
Step 2. Form disjoint pairs of points $(p_1,p_2),(p_3,p_4),…,(p_{n-1},p_n).$ If n is odd, let the final pair be $(p_n,p_1).$
Step 3. For each pair of points, $(p_i,p_{i+1}),$ find the point $x_{i,i+1}$ on L such that $d(p_i,x_{i,i+1}) = d(p_{i+1},x_{i,i+1}).$
Step 4. Find the median of the $\lceil n/2 \rceil$ numbers of $x_{i,i+1}$’s. Denote it as $x_m.$
Step 5. Calculate the distance between $p_i$ and $x_m$ for all i. Let $p_j$ be the point which is the farthest from $x_m.$ Let $x_j$ denote the projection of $p_j$ onto L. If $x_j$ is to the left (right) of $x_m,$ then the optimal solution, $x^*,$ must be to the left (right) of $\lambda_m.$
Step 6. If $x^* < x_m,$ for each $x_{i,i+1} > x_m,$ prune the point $p_i$ if $p_i$ is closer to $x_m$ than $p_{i+1};$ otherwise prune the point $p_{i+1}.$ If $x^* > x_m,$ for each $x_{i,i+1} < x_m,$ prune the point $p_i$ if $p_i$ is closer to $x_m$ than $p_{i+1};$ otherwise prune the point $p_{i+1}.$
Step 7. Go to step 1.

### 4 留言

1. #### 🍡

您好，請問第 14 題 (b) 的答案為何不是
Fib[1] = 111…11 (n-1個1)
Fib[2] = 111…10 (n-2個1)
Fib[3] = 11…10 (n-3個1)
.
.
.
Fib[n] = 0
因為若按照原本的解答，將 n=6 代入會和 (a) 的答案不符。

2. #### 瑞斯

不好意思
請問那題radix sort是不是只要做到Pass 4就可以停了呢?