Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMPSCI 320
City COMPUTER SCIENCE 320 Applied Algorithmics (Time allowed: THREE hours) NOTE: • This is a two part exam: Multiple Choice Questions and Short An- swer Questions. • Check that the VERSION number above matches the VERSION CODE number on the Teleform sheet. • This exam has several multichoice questions totaling 30 marks; each is worth 2 marks for a correct answer (0 marks for any missing or wrong answer). • Any answers for the multichoice questions (which you want marked) must be entered on the Teleform sheet. • This exam has several short answer questions totaling 30 marks (in- dividual marks listed below each question part). Write answers in the provided spaces of this script. • Enter your Student ID# and Name on both the Teleform sheet and all pages 7–14 of this Question/Answer booklet. • Books and electronic devices are NOT allowed. • Show all work. Page 1 of 14 VERSION 1 COMPSCI 320 SECTION 1: Multiple Choice Questions 1) Suppose that there are 3 studentsA,B,C and 3 summer scholarship supervisorsX, Y, Z with preferences as follows: A : X > Y > Z,B : X > Y > Z,C : X > Y > Z, X : C > B > A, Y : C > B > A,Z : C > B > A. Consider the matching A : X,B : Y,C : Z. Which of the following is a blocking pair? [2 marks] A. (A,B) B. (B,Z) C. (A,X) D. (C,Z) E. (B,X) 2) Suppose that there are 3 students A,B,C and 3 summer scholarship supervisors X, Y, Z with preferences as follows: A : X > Y > Z,B : X > Y > Z,C : X > Y > Z, X : C > B > A, Y : C > B > A,Z : C > B > A. What is the Gale-Shapley solution to the stable matching problem? [2 marks] A. A : Z,B : X,C : Y B. A : X,B : Y,C : Z C. A : Z,B : Y,C : X D. A : Y,B : X,C : Z E. A : Y,B : Z,C : X 3) Consider the function f(n) = nc log2 n where c > 1 is a constant. For which integer values of b is it b-smooth? [2 marks] A. b > 2 B. b ≥ c C. b ≤ c D. b = c E. b ≥ 1 4) Consider an algorithm that divides the input into 10 subproblems each of size one-third of the original, takes time proportional to the square of the input problem size to perform the divide step, and does the conquer step in linear time. It will have asymptotic running time in Θ(f(n)) where f(n) =: [2 marks] A. n log3 n Page 2 of 14 VERSION 1 COMPSCI 320 B. n2 C. n2 log3 n D. nlog3 10 E. n3 5) When computing 317 mod 5 using the divide-and-conquer algorithm from class, what is the number of multiplications used? [2 marks] A. 8 B. 6 C. 16 D. 4 E. 5 6) For this question, ignore all floors and ceilings. The coolsort algorithm satisfies the running time recurrence (for n > 1) T (n) = 3T (n/3) + n whereas crudsort has running time Cn2 for some C with 0 < C < 1. The optimal cutoff N for a hybrid algorithm that uses coolsort on large inputs and switches to crudsort on instances of size at most N is: [2 marks] A. 1 B. 3 2C C. 3C D. 27 E. 3C 7) Recall the BFPRT linear-time median-finding algorithm from lectures. Suppose that instead of using subarrays of size 5, we used subarrays of size 9. What would happen to the speed of the algorithm? [2 marks] A. asymptotically slower B. no change of the asymptotic order, but it would be slower C. no change D. asymptotically faster E. no change of the asymptotic order, but it would be faster Page 3 of 14 VERSION 1 COMPSCI 320 8) Consider the knapsack problem with integer constraints, weight limit 3 and items having respective values v1 = 1, v2 = 2, v3 = 10 and weights w1 = 1, w2 = 3, w3 = 5. Let G be the value of the solution found by the greedy algorithm and H the optimal value. Then: [2 marks] A. G = H − 1 B. G = H + 1 C. G = H + 2 D. G = H E. G = H − 4 9) Consider the greedy change-making algorithm used in Zorg, where the currency has infinitely many coins of denominations 1, 4, 6, 10 squergs. Which statement is false? [2 marks] A. if we don’t use the 1-squerg coin, we can’t make change for 299 squergs B. if we don’t use the 1-squerg coin, the largest even number of squergs for which we cannot make change is strictly greater than 2 C. we can make change for any positive integer number of squergs D. the solution is optimal for the input 17 E. the solution is not optimal for the input 12 10) Suppose that in a post-Covid world the Auckland International Film Festival comes back to town. There are far too many movies on your “must watch” list for you to see them all, since their times conflict and each is only shown once. If you decide to watch as many complete movies as possible, which strategy will be best? [2 marks] A. choose them in increasing order of finishing time B. choose them in increasing order of starting time C. choose them in increasing order of movie length D. choose them in decreasing order of number of conflicts E. none of the other answers is correct Page 4 of 14 VERSION 1 COMPSCI 320 11) Consider the knapsack problem with integer constraints, weight limit 4 and items having respective values v1 = 1, v2 = 2, v3 = 4 and weights w1 = 1, w2 = 2, w3 = 3. Complete the following Dynamic Programming table-based solution. What is the sum of the five latest entries (just the ones you computed) of your completed table? Weight 0 1 2 3 4 Item 1 0 1 1 1 1 Item 2 0 1 2 Item 3 0 1 [2 marks] A. 13 B. 12 C. 16 D. 14 E. 15 12) Consider two decision problems X and Y . Suppose that X ≤P Y . Which of the following can we infer? [2 marks] A. If Y cannot be solved in polynomial time, then neither can X . B. At least two of the other answers can be inferred. C. X can be solved in polynomial time iff Y can be solved in polynomial time. D. If X can be solved in polynomial time, then so can Y . E. If X cannot be solved in polynomial time, then neither can Y . 13) Given a graph G = (V,E) of order n, size m and m = O(n), how difficult is it to solve the 3-COLOR problem? [2 marks] A. O(mn) using maximum flow. B. O(m + n) using BFS or DFS. C. Not even Dr. Dinneen knows. D. Ω(3n) using brute force. E. It is a NP-complete problem. Page 5 of 14 VERSION 1 COMPSCI 320 14) Suppose P 6= NP . Which of the following are still possible? [2 marks] A. O(nlog logn) algorithm for 3-SAT. B. All but one of the other answers is possible. C. O(1.5n) time algorithm for HAMILTON-CYCLE. D. P = co-NP E. O(n3) algorithm for factoring n-bit integers. 15) What is the maximum flow from s to t in the following network? [2 marks] A. 15 B. 16 C. 12 D. 13 E. 14 Page 6 of 14 QUESTION/ANSWER BOOKLET Student ID: Name: COMPSCI 320 SECTION 2: Short Answer Questions 1) Divide-and-Conquer: One of your CS320 teachers has proposed the following “goofy” sorting algorithm: procedure goofySort(A, i, j); begin if A[i] > A[j] then swap A[i] and A[j]; if i + 1 ≥ j then return; k ← b(j − i + 1)/3c; goofySort(A,i,j-k); goofySort(A,i+k,j); goofySort(A,i,j-k); end A. Provide a brief justification that goofySort(A,3,5) correctly sorts the array A[3..5]. Gen- eralize this argument to give a brief justification that goofySort(A,1,n) correctly sorts the array A[1..n]. [3 marks] Page 7 of 14 QUESTION/ANSWER BOOKLET Student ID: Name: COMPSCI 320 B. Write down an approximate recurrence for the worst-case running time of goofySort. From this obtain a tight asymptotic (Θ-notation) bound on the worst case running time using this divide-and-conquer theorem: Assume T (n) = aT (n/b) + g(n), where g(n) is O(nc), is the total time for a divide and conquer algorithm, where a is a positive integer and b > 0 and c ≥ 0 are reals. Then: T (n) = Θ(nc), if a < bc Θ(nc log n), if a = bc Θ(nlogb a), if a > bc [3 marks] C. Compare the worst-case running time of goofySort with that of bubble sort, merge sort, heapsort and quicksort. [2 marks] Page 8 of 14 QUESTION/ANSWER BOOKLET Student ID: Name: COMPSCI 320 2) Dynamic Programming: Consider this variation of the edit distance (sequence alignment) problem for strings of digits 0, 1, . . . , 9. As input, we have two sequences of digits X = x1x2x3 · · ·xm and Y = y1y2y3 · · · yn and we want to minimize the alignment between the two strings but with exponential gap penal- ties. If we have a gap of length one then a penalty 2 is counted, a gap of length two then a penalty of 22 = 4 is counted, and a gap of length k then a penalty of 2k (instead of 2k) is counted. Furthermore, we assume the mismatch penalty for aligning two digits xi and yj is the value |xi − yj|. A. For the input X = 1230034 and Y = 14834 what is the minimum alignment? Is it unique? [2 marks] B. Give a polynomial-time dynamic programming solution for this problem, formulated as a Bellman recurrence. Justify your answer. [5 marks] Page 9 of 14 QUESTION/ANSWER BOOKLET Student ID: Name: COMPSCI 320 3) NP-Completeness: A. Informally define what it means for a problem to be NP-hard and NP-complete. (Please explain the concepts at a level that your kindergarten teacher would understand.) [2 marks] B. Formally define what it means for a problem to be NP-hard and NP-complete. (Please explain the concepts at a mathematical level that a ‘real’ computer scientist should understand.) [2 marks] Page 10 of 14 QUESTION/ANSWER BOOKLET Student ID: Name: COMPSCI 320 C. Using graph (vertex) coloring as an example, explain the differences between decision, search and optimization problems. Indicate how, via self-reduction techniques, that these are polynomial-time equivalent. [3 marks] Page 11 of 14 QUESTION/ANSWER BOOKLET Student ID: Name: COMPSCI 320 4) Network Flow: For this question, consider the following network flow graph with edge capacities. We want to find the maximum flow from node s to node t. Suppose we have an initial flow, as indicated by the following flow/capacity labels. A. Draw the residual edges on the following set of nodes, indicating their flows. [2 marks] Page 12 of 14 QUESTION/ANSWER BOOKLET Student ID: Name: COMPSCI 320 B. What is an augmenting flow path (for this initial flow) with maximum bottleneck? [2 marks] C. What is the final maximum network flow (given as an integer)? Show flow/capacities on this drawing by writing X/ in front of the listed capacities, where X denotes the flow. [2 marks] D. Indicate all min-cuts of this network flow graph. [2 marks] Page 13 of 14 QUESTION/ANSWER BOOKLET Student ID: Name: COMPSCI 320 (for examiner use only) Question #: 1 2 3 4 Total Possible marks: 8 7 7 8 30 Awarded marks: Page 14 of 14
- 经济Economics
- 金融Finance
- 会计Accounting
- 工商管理Business Management
- 计算机computer science
- 商业分析business analysis
- 法律Law
- 管理Management
- 市场营销Marketing
- 哲学Philosophy
- 心理学Psychology
- 物理Physical
- 统计学statistics
- 电气工程electric engineering
- 化学chemistry
- 生物biology
- 数学mathematics
- 语言学linguistics
- 土木工程civil engineering
- 工程力学engineering mechanics
- 艺术art
PROFESSIONAL HELP!
在线咨询
立即下单
Wechat：THEend8_ 
Email：