(a) (9 points) Give an O(n²) solution by deining a recurrence fornula for f(n). Clearly explain the meaning of your formula and why it can be computed in O(n²) time.

Please select all the correct answer(s) to question 1 to 10. Note that there could be O to 5 correct answ wers. If non answer is correct, answer "none". If you do not wish to answer a question, leave it blank. All 10 answer rs m must be written on the first page of your answer book, and the answer to question 1 must be in the first line, the answer to question 2 must be in the second line, and so on. If you fail to follow these rules then your answers will be ignored. ne of the a 1. (3 points) Let f(n) be the number of additions in the following algorithm.  1.f(n)=2. f(n)=O(n2logn) 3. f(n)=O(n3) 4. f(n)=O(n3logn) 5. f(n)=

2. (3 points) Given two sorted list A and B (in increasing key order), the following recursive algorithn merges A and B into a sorted list C (also in increasing key order). ㆍ If either A or B is empty then the result is the other list. ㆍ If both A or B are not empty, we compare the keys of the first nodes of A and B, and select the smaller one (denoted as s), and remove it from the list. Then we recursively merge the remaining parts of A and B into a new sorted list C', then we concatenate s with C' into the iral sorted list Let f(n, m) be the minimum number of comparisons of this algorithm, where n and m are the numbers of nodes in A and B respectively. f(n,m) is? 1.Ω(n) 2. Ω(m) 3. Ω(n +m) 4. Ω(mn) 5.Ω(mar.(logm +logn))

3. (3 points) We now use the merge algorithm in the previous question to sort a set of keys. We irst make each key a list of a single node. Then we merge the first and the second lists into a sorted list of length two, the third and the fourth lists into a sorted list of length two, and so on. If we start with n keys now we have roughly n/2 sorted list of length two now. We then merge these lists of length two into roughly n/4 sorted list of length four, and so on. Finally we will have a sorted list of length n. Let f(n) denote the mazimum possible total number of comparisons of this algorithm, then f(n) is? Note that all the answers are in little-o notation. 1.o(n) 2. 3.o(nlogn) 4.o(n(logr)2) 5.o(n2)

4. (3 points) A binary minimun heap is a binary tree in which every level is completely full, except the last level, which is filled from the left to right. Here the level of a node is its distance to the root, so the root has leve! O and the children of the root will have level 1, and so on. Also the key of a parent is less than those of its children. For ease of discussion we assume that all keys in the heap are distinct. Now which of the following descriptions about a binary minimum heap of 10 nodes (see the igure below) are correct?1. The second smallest key is always in level 1. 2. The largest key is always in a leaf, ie., a node without any children. 3. The second largest key is always in a leaf. 4. Let n be the number of nodes and we consider the case of arbitrary n, then the height of the tree is θ(logn). 5. Let n be the number of nodes and we consider the case of arbitrary n, then we can find the thind stnallest key of the beap by O(1) key comparisons.

5. (3 points) We will follow the notations from the previous question. We can build a heap from an array of n keys by the following algorithun. A heapify operation for a binary minimum heap combines two heaps and a root into a new heap. For ease of discussion we assume that the array is indexed from l to n, and the left/right child of a node with array index i have array indices 2: and 2i + 1 respectively. We first set each key of the second half of the aray (indexed from n/2 to n) as r:/2 heaps, each has one node. Then we combine two of them and their parent into a heap of three nodes, and so on. If the root is smaller than the roots of both subtrees then we stop. Otherwise we exchange the root with the smaller root from the subtrees, and repeatedly heapify the subtree where the root has just been replaced. Next we heapify the key at n/2 - 1 and all the way back to the root (at index 1). The final result will be a binary minimum heap of n nodes. 1. The minimum number of key comparisons is θ(n). 2. The maximum number of key comparisons is θ(n). 3. Since each heapify on a key may compare it with all the keys down to a leaf, its number of comparisons is no more than the height of the heap, which is O(logn). Also we have O(n) keys to heapify, so the total number of key comparisons is O(n log n). 4. The number of key comparisons is in the same order as the sum of (original, before heapified) levels (as defined in the previous question, the distance to the root) of all keys. 5. The number of key comparisons is mazimized if and only if the largest n/2 keys are in the first half of the array and in decreasing order.

6. (3 points) A randomized quick sort works as follows. For ease of discussion we assur me that the sequence we want to sort, K = (k1,... .,kn), is a pernutution of 1 to n. We randomly and uniformly pick a key & from K. Then we partition K into two subsets - Ki that has keys less than k and K1 that has keys greater than k. Then we recursively sort K1and K2, and combine the results with k to get the sorted sequence. 1. The number of key comparisons will always be max aunized when the keys in K are already sorted. 2. Let |K1| and|K2|be the number of keys in K1 and K2 respectively. The expected value of max(|K1|,|K2|) is n. 3. The algorithm will compare two keys &: and ky at most ouce, so the numnber of key comparisons is O(n2). 4. The probability that the algorithm will compare ky and ly (n2i＞ jZ 1) is 5. Let P= {(i,j)|1≤i，,j ≤ni≠j}. The expected total number of key comparisons is

7. (3 points) We can use a linked list to implement a stack. We assume that we use structure Node with two rembers to represent a node of the linked list. The member data stores the data, and the rnernber next points to the next node in the linked list. Also we use a variable bead to point to the first node of the linked list. head is initialized to NULL. 1. Pushing the value of a variable i into the stack can be implemented as follows.newHead = malloc(sizeof (Node)); newHead-＞data - i; newHead-＞next = = head; head = newHead; 2. Popping the top of the stack into a variable i can be implemented as follows. free(head) ; head-＞data ; head = = head-＞next ; 3.To test if the stack is empty we can check if the head is a NULL pointer. 4. We can improve the push/pop effciency of this stack by adding another pointer tail that points to the end of the linked list, so we can access the Last node in the list in O(1) time. 5. We can improve the push/pop eficiency of this stack by adding another pointer member into every node, so it becomes a double linked list. That is, we can traverse in both directions in this linked

8. (3 points) A randomized linked list sorting algorithm works as follows. We want to build a linked listin which the keys are in increasing order. That is, every node has a smaller key than its successor inthe list. For ease of discussion we assume that the keys are distinct in integers from 1 to n. The algorithnrandomly picks a key from the rem maining keys, and inserts it into the list. This prokeys are inserted. The inserted key k will skip those at the beginning of the list that are smaller thanocess repeats until allit, and will stop at the first key p that are greater than it. We then insert the key k  before p. To ensurethat all keys will stop we assumne that initially the list has only one key, n + 1. After we insert all keyswe will have a sorted linked list from 1 to n + 1.1. Every inserted key will stop exactly once. 2. The smallest key 1 will not skip any keys.3. The largest key n will always skip n–1 keys. 4. The expected number of keys that the key i will skip is Ω(i).5. The key : will skip j if and only if i ＞ j and i is inserted after j is inserted, so the expected valueof the total number of key comparisons is θ(n2).

9. (3 points) A binary search tree is a tree where every n node has at most two children. For ease of discussion we assume that every y node has a distinct key. In addition, all keys in the left subtree are smaller than the key of root, and all keys in the right subtree are larger than the key of the root. A tree node is a leaf if it does not have any children. The height of the tree is the length of the longest path from the root to a leaf. The successor of a node z is the node right after a in increasing order, and the predecessor of a node z is the node right before z in increasing order. 1. We can locate the smallest key in a binary search tree in O(h) time in the worst case, where h is the height of the tree. 2. The height of a binary search tree of n nodes is O(logn.). 3. We can locate the Largest key in a binary search tree in O(logn) time in the worst case, where n is the number of the nodes in the tree. 4. Assume that a node z has two children. We can remove z while still mainteining the sorted order by locating its successor y, connecting y's parent directly to the only child of y (if there is one, otherwise make it null), which effectively removes the node y from the tree, and replacing the key of z with that of y. 5. Assume that a node z has two children. We can remove z z while still maintaining the sorted order by locating its predecessor y, connecting y's parent directly to the only chid of y (iF there is one, otherwise make it null), which effectively removes the node y from the tree, and replacing the key of z with that of y.

10. (3 points) A red-black tree is a binary tree where every node has a color (red or black), and has the following properties.1. The root is black. 2. All paths from the root to a leaf have the same number of black nodes. 3. Every red node must have two black children. For ease of discussion we assu sume that all null pointers (a special pointer to "nothing") point to a special black node. As a result all counting of the second property ends at this special node. 1. If we do not guarantee the first property, but still guarantee the second and the third properties, we will not be able to guarantee that the height of the tree is O(logn). 2. It is possible that there are no red nodes in a red-black tree of 100000 nodes. 3. We insert a key k into a non-empty red-black tree just like into an ordinary binary search tree as a leaf, attach to it two null pointers to the special black node, and then immediately stop without any adjustment. If we color k red, we may violate the second property above. 4. Consider the scenario above. If we color k red, we may violate the third property above. 5. Consider the scenario above. If we color k black, we will violate the second property above.

110年 - 110 國立臺灣大學_碩士班招生考試_部分系所:資料結構與演算法(A)#105777

109年 - 109國立臺灣大學_碩士班招生考試_資訊工程學研究所:資料結構與演算法(A)#106053