4. (10%) Produce a matrix P that diagonalizes the matrix below:
  

5. (10%) Find the general solutions of

6. (25%) Let u-u(x，y，t) be a function of the space (x.y) and the time t. S=S(s,f) is a function of x and t, and cl and co are constant. Determine whether the method of separation of variables is applicable to the following partial differential equations or not (each has 5 %). The rationale behind your answer needs be given; otherwise, it will not be credited.

7. (25%) Let u=u(xy) be a function of x and y. (x), g(x), f1(y), and g1(y) are given; K and L are positive constant. Solve the problem:  

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

110年 - 110 國立臺灣大學_碩士班招生考試_部分系所:工程數學(E)#100594

109年 - 109國立臺灣大學_碩士班招生考試_化學工程學研究所:工程數學(E)#106052