代写接单

欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top

DIDATES This is a OPEN book examination. All submitted work must be done individually without consulting someone Section in a separate book...... Semester 2, 2005

 Page X of XY This information is only necessary if Semester 1- Practice, 2022 SEAT NUMBER: _______________________________ comp9123 Data Structures and Algorithms FULL NAME: _______________________________ SID: _______________________________ 2 hours 10 minutes Duration: 2h30m Reading time: 10 mins Computer Science EXAMINATION EXAM WRITING TIME: the paper is NOT TO BE REMOVED READING TIME: FROM EXAM ROOM. EXAM CONDITIONS: comp9123 final exam (s1, 2022) Faculty of ECONOMICS & BUSINESS CONFIDENTIAL EXAM PAPER ECON2002 – INTERMEDIATE MICROECONOMICS This paper is not to be removed from the exam venue. else’s help, in accordance with the University’s “Academic Dishonesty and Plagiarism” policies. MATERIALS PERMITTED IN THE EXAM VENUE: MATERIALS TO BE SUPPLIED TO STUDENTS: INSTRUCTIONS TO STUDENTS: Type your answers in your text editor (Latex, Word, etc.) and convert it into a pdf file. Submit this pdf file via Canvas. No other file format will be accepted. Hand- written responses will not be accepted. Start by typing you student ID at the top of the first page of your submission. Do not type your name. Submit only your answers to the questions. Do not copy the questions. Do not copy any text from the permitted materials. Always write your answers in your own words. For examiner use only: Problem 1 2 3 4 Total Marks Out of 10 10 20 20 60 Dennis\Desktop\Exam Typing Page 2 of 4 page 1 of 5 N Practice Exam Problem 1. a) Analyze the time complexity of this algorithm. [3 marks] comp9123 final exam (s1, 2022) 1: 2: 3: 4: 5: 6: def Compute(A) result ← 0 for i = 0; i < n; i + + do if A[i] > i then result ← result + A[i] return result b) Solve the following recursion: ��T(n/2) + O(1) c) We are planning a board games event and we’re using one of the shelves in my office to store the games. Unfortunately the shelf only has a certain amount of space S, so we need to carefully pick which games we want to bring. Every game takes some space si and has a fun factor fi that indicates how much fun it is to play that game (for 1 ≤ i ≤ n). We want to maximize the amount of fun we’ll have, so we want to maximize the sum of the fun factors of the games we pick (i.e., max ∑ fi), while picked game i making sure that the games fit on my shelf, so the sum of the space the games we pick take should be at most S (i.e., ∑ si ≤ S). For simplicity, you can picked game i assume that all fi, si, and S are all distinct positive integers. The strategy of PickLargest is to always pick the game with the highest fun factor until my shelf is full: it sorts the games by their fun factor fi in decreasing order and adds a game when its required space is less than the remaining space on the shelf. [3 marks] [4 marks] T(n)= O(1) for n > 1 forn=1 1: 2: 3: 4: 5: 6: 7: 8: 9: def PickLargest(all fi and si, S) currentSpace ← 0 currentFun ← 0 Sort games by fi and renumber such that f1 ≥ f2 ≥ ... ≥ fn fori←1;i≤n;i++do if currentSpace + si ≤ S then currentSpace ← currentSpace + si ◃ Pick the ith game currentFun ← currentFun + fi return currentFun Show that PickLargest doesn’t always return the correct solution by giving a counterexample. page 2 of 5 comp9123 final exam (s1, 2022) Problem 2. Consider the following edge weighted undirected graph G: B5C 10 2 A74F 6 3 D1E Your task is to: a) Compute a minimum spanning tree T of G. List the edges in T. b) Indicate the order in which the edges are added by Kruskal’s algorithm. (You do not have to explain your answer.) [7 marks] [3 marks] page 3 of 5 comp9123 final exam (s1, 2022) Problem 3. Consider the Dynamic Matrix ADT for representing an matrix A = {ai,j}n that supports the following operations: • create(): creates a 1 × 1 matrix where a1,1 = 0. • set/get(i, j): set or get the value of the entry ai,j. • increase-size: If the current size of the matrix is n×n, increase it to n+1×n+1 such that the new entries are set of 0. In other words, A becomes A′ such that a′ =ai,j if1≤i,j≤n,anda′ =0otherwise. i,j i,j Your task is to come up with a data structure implementation for the Dynamic Matrix ADT that uses O(n2) space, where n is the size of the matrix, and create, set, get take O(1) and increase-size takes O(n) time. Remember to: a) Describe your data structure implementation in plain English. b) Prove the correctness of your data structure. c) Analyze the time and space complexity of your data structure. [8 marks] [7 marks] [5 marks] i,j=1 page 4 of 5 comp9123 final exam (s1, 2022) Problem 4. Let G be a connected undirected graph on n vertices. We say that two distinct spanning trees T and S of G are one swap away from each other if |T ∩ S| = n − 2; that is, T and S differ in only one edge. For two distinct spanning trees T and S we say that R1, R2, . . . , Rk form a swapping sequence from T to S if: 1. R1 = T, 2. Rk =S,and 3. for any 1 ≤ i < k, the trees Ri and Ri+1 are one swap away from each other Your task is to design a polynomial time algorithm that given G and two spanning trees T and S of G, constructs a minimum length swapping sequence. Remember to: a) Describe your algorithm in plain English. b) Prove the correctness of your algorithm. c) Analyze the time complexity of your algorithm. [8 marks] [7 marks] [5 marks] page 5 of 5 

51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468