Ch01 AVL

After merging two Leftist Heaps H1 and H2 of different NPL's, the NPL of the resulted Leftist Heap will be no more than max(NPL of H1, NPL of H2)

There exists an AVL tree of depth 6 (the depth of the root is 0) containing 31 nodes.

Ch02 Red Black Tree & B+ Tree

Insert $(7, 15, 9, 11, 5, 8, 19, 18)$ into an initially empty 2-3 tree (with splitting), and then delete 7. Which one of the following statements is FALSE about the resulting tree?

• A. there are 3 leaf nodes
• B. 13 and 15 are in the same node
• C. the parent of the node containing 18 has 3 children
• D. the first key stored in the root is 11

In a red-black tree, the number of internal nodes in the subtree rooted at x is no more than $2^{bh(x)} - 1$ where $bh(x)$ is the black height of x. (T or F)

Ch04 Leftist Heap & Skew Heap

By definition, for a light node $p$ in a skew heap, the number of descendants of $p$'s right subtree is no more than 1/2 of the number of descendants of $p$.

Ch05 Binomial Queue

For a binomial queue, ___ takes a constant time on average.

• A. merging
• B. find-max
• C. delete-min
• D. insertion

Ch06 Backtracking

For the Turnpike reconstruction algorithm of $N$ points, assuming that the distance set $D$ is maintained as an AVL tree, the running time is $O(N^{2} \log n)$ if no backtracking happens.

Given the following game tree, the red node will be pruned with $\alpha$-$\beta$ pruning algorithm if and only if ___.

• A. $6\leq x\leq13$
• B. $x\geq13$
• C. $6\leq x\leq9$
• D. $x\ge 9$

Ch07 Divide and Conquer

Recall that in the merge sort, we divide the input list into two groups of equal size, sort them recursively, and merge them into one sorted list. Now consider a variant of the merge sort. In this variant, we divide the input list into $\sqrt{n}$ groups of equal size, where $n$ is the input size. What is the worst case running time of this variant? (You may use the fact that merging $k$ sorted lists takes $O(m \log k)$ where $m$ is the total number of elements in these lists.)

• A. $O(n \log^2 n)$
• B. $O(n \log n)$
• C. None of the other options is correct
• D. $O(n \log n \log \log n)$

Recall that, to solve the cloest pair problem, the first step of the divide-and-conquer algorithm divides the point set into $L$ and $R$ according to hte x-coordinate. Is the following statement true or false?

• In the combine step of this algorithm, it is always to find the closest pair with one point in $L$ and the other in $R$.

Consider the following pseudo-code.

strang($a_{1},\ldots,a_{n}$):

1. if $n\le 2022$ then return
2. strange($a_{1},\ldots,a_{\lfloor n/2 \rfloor}$)
3. strange($a_{\lfloor n/4 \rfloor},\ldots,a_{\lfloor 3n/4 \rfloor}$)
4. for $i=1$ to $n$:
5. $\quad$for $j=1$ to $\lfloor \sqrt n \rfloor$:
6. $\quad\quad$print($a_{i}+a_{j}$)
7. strange($a_{\lfloor n/4 + 1 \rfloor},\ldots,a_{\lfloor 3n/4 \rfloor}$)
8. strange($a_{\lfloor n/2 + 1\rfloor},\ldots,a_{n}$)

What is the running time of this pseudo-code? Your answer should be as tight as possible. (You may assume that $n$ is a power of 2.)

• A. None of the order options is correct.
• B. $O(n^{1.5})$
• C. $O(n^{1.5}) \log n$
• D. $O(n^{2})$

Consider the following pseudo-code.

strange($a_{1},\ldots,a_{n}$)

1. if $n\leq2022$ then return
2. strange($a_{1},\ldots,a_{\lfloor n/2 \rfloor}$)
3. for $i=1$ to $n$:
4. $\quad$for $j=1$ to $\lfloor \sqrt n \rfloor$:
5. $\quad\quad$print($a_{i}+a_{j}$)
6. strange($a_{\lfloor n/2 +1\rfloor}, \ldots, a_{n}$)

What is the running time of this pseudo-code? Your answer should be as tight as possible. (You may assume that $n$ is a power of 2.)

• A. None of the order options is correct.
• B. $O(n^{1.5})$
• C. $O(n^{1.5}) \log n$
• D. $O(n^{2})$

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

• A. $O(N^{\log 7 / \log 3})$
• B. $O(\log^{2} N)$
• C. $O(\log N)$
• D. $O(N)$

Is this asymptotic upper bound for the following recursive $T(n)$ is correct?

• $T(n) = T(n^{1/3}) + T(n^{2/3}) + \log n$. Then $T(n) = O(\log n \log \log n)$.

Ch10 NP

If $L_{1} \leq_{p} L_{2}$ and $L_2 \in NP$, then $L_1 \in NP$. (T/F)

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.

The following problem is in co-NP. (T/F)

• Given a positive integer $k$, is $k$ a prime number?

Ch11 Approximation

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).

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 decided 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 serveral 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

As we know there is a 2-approximation algorithm for the Vertex Cover problem. Then we must be able to obtain a 2-approximation algortithm for the Clique problem, since the Clique problem can be polynomially reduced to the Vertex Cover problem. (T/F)

Ch12 Local Search

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'$ to be the neighbor of $S$ that 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) \geq 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 $2w(A, B) \geq w(A^*, B^*)$.
• D. The algorithm terminates after at most $O(|V|^2)$ flips.

Ch14 Parallel

Which one of the following statements about the Maximum Finding is False?

• A. Parallel random sampling algorithm can run with $O(\log n)$ work load.
• B. Common CRCW can be used to solve the access conflicts in this problem.
• C. It can be solved by summation algorithm with time complexity being $O(\log n)$.
• D. There exists parallel algorithm solving the problem in constant time.

When we solve the summation problem via designing the parallel algorithms, we shorten the aasymptotic time complexity but take more asymptotic work loads comparing with the sequential algorithms.

There is an array $A$, $A[i]=i\space (1\leq i\leq1024)$. If we use Balanced Binary Trees Parallel Algorithm to calculate the Prefix-Sum of $A$. Define $C(h,i)=\sum_{k=1}^{\alpha} A(k)$, where $(0,\alpha)$ is the rightmost descendant leaf of node $(h,i)$. Node $(h,i)$ indicates the $i$-th node in height $h$. For example, the root is node $(10,1)$ and leaves are node $(0,i)\space 1\leq i\leq1024$. The value of $C(2,223)$ is

• A. $398278$
• B. $30708$
• C. $1701$
• D. $6796$

Ch15 External Sorting

If only one tape drive is available to perform the external sorting, then the tape access time for any algorithm will be $\Omega(N^2)$ (T/F)

Given 100,000,000 records, each 256 bytes, and an internal memory size of 128MB, if a simple 2-way merge is used, how many passes do we have to do?

• A. 10
• B. 9
• C. 8
• D. 7

We have 4 tapes for 3-way external merge sorting. How shall we distribute 31 runs into 3 tapes, such that the total number of passes is minimized?

• A. 15 runs on Tape 1, 9 runs on Tape 2, and 7 runs on Tape 3.
• B. 13 runs on Tape 1, 11 runs on Tape 2, and 7 runs on Tape 3.
• C. 13 runs on Tape 1, 10 runs on Tape 2, and 8 runs on Tape 3.
• D. 11 runs on Tape 1, 10 runs on Tape 2, and 10 runs on Tape 3.

Suppose we have the internal memory that can handle 12 numbers at a time, and the following two runs on the tapes:

Run 1: 1, 3, 5, 7, 8, 9, 10, 12 Run 2: 2, 4, 6, 15, 20, 25, 30, 32

Use 2-way merge with 4 input buffers and 2 output buffers for parallel operations. Which of the following three operations are NOT done in parallel?

• A. 1 and 2 are written onto the third tape; 3 and 4 are merged into an output buffer; 6 and 15 are read into an input buffer
• B. 3 and 4 are written onto the third tape; 5 and 6 are merged into an output buffer; 8 and 9 are read into an input buffer
• C. 5 and 6 are written onto the third tape; 7 and 8 are merged into an output buffer; 20 and 25 are read into an input buffer
• D. 7 and 8 are written onto the third tape; 9 and 15 are merged into an output buffer; 10 and 12 are read into an input buffer

Ex01 Amortized Analysis

A $n$-nodes AVL tree $T$ performs insertion or deletion in the worst case that costs $a_0 \lg n + b_0$, $a_1 \lg n + b_1$, respectively, where $a_0, a_1, b_0, b_1$ are constants. Now, we start from an empty tree, perform a sequence of n insertions or deletions in the AVL tree. To analysis the amortized cost per insertion or deletion, we define a potential function $\Phi(T) = a_1 \sum_{i=1}^{n} \lg i$. What is the amortized cost per insertion or deletion?

• A. $O(\lg n)$ for insertion, $O(1)$ for deletion
• B. $O(1)$ for insertion, $O(\lg n)$ for deletion
• C. $O(\lg n)$ for insertion, $O(\lg n)$ for deletion
• D. $O(1)$ for insertion, $O(1)$ for deletion

We have a binary counter of k bits. Each time we conduct an increment on the counter: $x \equiv x + 1 \pmod{2^k}$ and the cost of the increment is the number of bits we need to flip. For example, when $k = 3$, currently we have $x = 010$, after increment we have $x = 011$. Then this increment costs 1 because only 1 bit flips after increment. If we conduct the increment again, $x = 100$. Then this increment costs 3 because we flip 3 bits. Now we conduct n consecutive increments and estimate the total cost. Which of the following statements are TRUE?

1. If the initial value of the counter is 0, the total cost is $O(n)$
2. If the initial value of the counter is 0, the total cost is $O(n \log k)$
3. If n = $\Omega(k)$, the total cost is $O(n)$
4. If n = $\Omega(k)$, the total cost is $O(n \log k)$

• A. 2 and 4
• B. 2 and 3
• C. 1 and 3
• D. 1 and 4

In this problem, we would like to find the amortized cost of insertion in a dynamic table $T$. Initially the size of the table $T$ is 1. The cost of insertion is $1$ if the table is not full. When an item is inserted into a full table, the table $T$ is expanded as a new table of size $5$ times larger. Then, we copy all the elements of the old table into this new table, and insert the item in the new table.

Let $num(T)$ be the number of elements in the table $T$, and $size(T)$ be the total number of slots of the table. Let $D_i$ denote the table after applying the $i$-th operation on $D_{i-1}$.

Which of the following potential function $\Phi(D_i)$ can help us achieve $O(1)$ amortized cost per insertion?

• A. $\Phi(D_{i}) = num(T) + \dfrac{size(T)}{5}$
• B. $\Phi(D_{i}) = \dfrac{5}{4} \left( num(T) + \dfrac{size(T)}{5} \right)$
• C. $\Phi(D_{i})=\dfrac{5}{4}(num(T) - \dfrac{size(T)}{5})$
• D. $\Phi(D_{i}) = num(T) - \dfrac{size(T)}{5}$

Other Problems

Consider a bipartite graph $G(A,B,E)$. (Recall that a graph $G$ is bipartite if the vertex set of $G$ can be partitioned into $A$ and $B$ such that all the edges of $G$ have one endpoint in $A$ and the other in $B$.) A matching in $G$ is a subset $M$ of $E$ such that no two edges in $M$ have a common vertex. A vertex cover is a subset $C$ of $V$, where every edge in $E$ must have at least one endpoint in $C$. Denote by $|S|$ the cardinality of a set $S$. Which of the following statements is true?

• A. For a minimum vertex cover $C$, $|C| = \min\{|A|,|B|\}$.
• B. Exactly one of the other options is wrong.
• C. For any vertex cover $C$ and any matching $M$, $|C| \ge |M|$.
• D. For a minimum vertex cover $C$ and a maximum matching $M$, $|C| = |M|$.

Consider two disjoint sorted arrays $A[1\ldots n]$ and $B[1\ldots m]$, we would like to compute the $k$-th smallest element in the union of the two arrays, where $k\le \min{m,n}$. Please choose the smallest possible running time among the following options:

• A. $O(\log n)$
• B. $\min\{O(\log m), O(\log n)\}$
• C. $O(\log m)$
• D. $O(\log k)$