1. (10%) Use generating functions to answer the following questions.

(A) Find the solution of the recurrence relation $a_n = 4a_{n-1} – 3a_{n-2} + 2^n + n + 3 \text{ with } a_0 = 1 \text{ and } a_1 = 4.$
(B) Find the coefficient of $x^{10}$ in the power series of $x^4 / (1 – 3x)^3.$

(A) $a_n = -4 \cdot 2^n + \dfrac{39}{8} \cdot 3^n + \dfrac{19}{8} – \dfrac{7}{4}(n+1) – \dfrac{1}{4}(n+2)(n+1), \, n \geq 0.$
(B) $\binom{3+6-1}{6} \cdot 3^6 = 28 \cdot 3^6 = 20412$

2. (10%) How many relations are there on a set with n elements that are

(A) both reflexive and symmetric?
(B) neither reflexive nor irreflexive?

(A) $2^{\frac{n(n-1)}{2}}$
(B) $2^{n^2} – 2^{n(n-1)+1}$

3. (5%) How many nonisomorphic unrooted trees are there with five vertices?

4. (5%) Multiple answer question. (It is possible that more than one of the choices are correct. Find out all correct choices.)

A hash table of length 10 uses the hash function $h(k) = k \, mod \, 10$ and the linear probing for handling overflow. After inserting 6 values into an initially empty hash table, the table is as shown below. Which one(s) of the following choices gives a possible order in which the key values could have been inserted in the table?

(A) 46, 42, 34, 52, 23, 33
(B) 34, 42, 23, 52, 33, 46
(C) 46, 34, 42, 23, 52, 33
(D) 42, 46, 33, 23, 34, 52
(E) 42, 23, 34, 46, 52, 33

5. (5%) Fill in the six black (I, II, …, and VI) in the following program that implements a queue by using 2 stacks.

.wp-block-code{border:0;padding:0}.wp-block-code>div{overflow:auto}.shcb-language{border:0;clip:rect(1px,1px,1px,1px);-webkit-clip-path:inset(50%);clip-path:inset(50%);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px;word-wrap:normal;word-break:normal}.hljs{box-sizing:border-box}.hljs.shcb-code-table{display:table;width:100%}.hljs.shcb-code-table>.shcb-loc{color:inherit;display:table-row;width:100%}.hljs.shcb-code-table .shcb-loc>span{display:table-cell}.wp-block-code code.hljs:not(.shcb-wrap-lines){white-space:pre}.wp-block-code code.hljs.shcb-wrap-lines{white-space:pre-wrap}.hljs.shcb-line-numbers{border-spacing:0;counter-reset:line}.hljs.shcb-line-numbers>.shcb-loc{counter-increment:line}.hljs.shcb-line-numbers .shcb-loc>span{padding-left:.75em}.hljs.shcb-line-numbers .shcb-loc::before{border-right:1px solid #ddd;content:counter(line);display:table-cell;padding:0 .75em;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;white-space:nowrap;width:1%}class MyQueue<T> {

private:
stack<T> stack1;
stack<T> stack2;

public:
MyQueue()
{
stack1 = new stack<T>();
stack2 = new stack<T>();
}

// enqueue(): Add an element at the rear side of MyQueue
void enqueue(T, e)
{
stack1.push(e);
}

// dequeue(): Remove the front element from MyQueue
T dequeue(T, e)
{
if((__I__).isEmpty())
while(!(__II__).isEmpty())
(__III__).push((__IV__).pop());

T temp = null;

if(!(__V__).isEmpty())
temp = (__VI__).pop();

return temp;
}
}
Code language: C++ (cpp)

6. (5%) AVL Tree.

(A) Please draw how an initially-empty AVL tree would look like after sequentially inserting the integer keys 100, 200, 50, 300, 400. There is no need to show it in a step-by-step fashion; you only need to draw the final result.
(B) Continue the previous sub-problem. Suppose that the integer keys 25, 250, 225, 500, 240, 260 are sequentially inserted into the AVL tree of the previous sub-problem. Draw the AVL tree after all of these integer keys are inserted.

(A)

(B)

7. (5%) Reconstruct and draw the maximum binary heap whose in-order traversal is 2, 16, 7, 62, 5, 9, 188, 14, 78, 10. There is no need to show it in a step-by-step fashion; you only need to draw the final result.

8. (5%) The following algorithm takes an array as input and returns the array with all the duplicate elements removed. For example, if the input array is {1, 3, 3, 2, 4, 2}, the algorithm returns {1, 3, 2, 4}.

S = new empty set
A = new empty dynamic array

for every element x in input array
if not S.member(x) then
S.insert(x)
A.append(x)

return A
Code language: C++ (cpp)

Suppose that the input array has n elements. What is the Big-O complexity of this algorithm, if the set S is implemented as:
(A) a hash table (with the assumption that overflow does not occur)?
(B) a binary search tree?
(C) an AVL tree?

9. (10%) The recurrence $T(n) = 7T(\dfrac{n}{2}) + n^2$ describes the running time of an algorithm A. A completing algorithm A’ has a running time of $T'(n) = aT'(\dfrac{4}{n}) + n^2.$ What is the largest integer value for $a$ such that A’ is asymptotically faster than A?

10. (15%) Consider the following undirected graph G = (V,E).

(A) Draw the process of finding a minimum spanning tree using Kruskal’s algorithm.
(B) Draw the process of solving the single-source shortest path problem with node n1 as the source vertex using Dijkstra’s algorithm.
(C) Starting from n1, find the Depth-First Search (DFS) traversal sequence of G (the priority of node is inversely proportional to the weight of incident edge).

(A)

(B)

(C) $n1 \to n4 \to n6 \to n5 \to n2 \to n3$

11. (18%) Given an ordered file with keys 1, 2, …, 16, determine the number of key comparisons made by a search algorithm A while searching for a specific key K.

(A) A is the binary search algorithm and K is 2.
(B) A is the binary search algorithm and K is 10.
(C) A is the binary search algorithm and K is 15.
(D) A is the Fibonacci search algorithm and K is 2.
(E) A is the Fibonacci search algorithm and K is 10.
(F) A is the Fibonacci search algorithm and K is 15.

12. (7%) Given a store of n items, what’s is the least upper bound (in Big-O notation) of the running time of the solutions to the following problems:

(A) Fractional knapsack problem;
(B) General 0/1 knapsack problem.