This is my finalThe University of Western Ontario Department of Computer Science CS2210B Final...

Question

This is my finalThe University of Western Ontario Department of Computer Science CS2210B Final Take-home Examination April 24, 2020 11 pages, 17 questions 24 hours Last Name: First Name: Student Number: Instructions • Write your name and student number on the cover page of your submission. • The examination has a total of 100 marks. • You are required to finish the exam in the 24 hours period from Apr. 24, 9AM to Apr. 25, 9AM. No late submissions will be accepted. • When you are done, submit a single PDF file to the OWL and make sure it contains all your answers, including multiple choices and written answers. 1 Part 1: Multiple Choice Each multiple choice question is worth 4 marks. You can choose one answers for each question. Important note: When asked to compute the time complexity of an algorithm, you need to give the tightest characterization of the order of the time complexity. So, for example, if the time complexity of an algorithm is f(n) = cn2 for some constant c > 0, while it is true that f(n) is O(n4), this answer will be considered incorrect, as the tightest order of f(n) is O(n2). 1. Which of the following functions is O(n2)? (A) 16n + 3 (B) n2 + 15n + 2n (C) n + 12(n + 1)(n2 + 4) (D) n + n3 (E) n(12n + 3n2) 2. A set S of n data items is to be stored in a data structure. For which of the following data structures the order in which the data items from S are inserted does not affect the final data structure (i.e. the data structure will be exactly the same regardless of the order in which the data items are inserted). (A) A (2, 4)-tree. (B) An AVL tree. (C) A hash table where collisions are resolved using linear probing. (D) A B-tree of order log n. (E) None of the above. 3. Consider the following algorithm: Algorithm B(G, u) Input: Undirected, connected graph G, and vertex u of G. Mark(u) c← 0 For each edge (u, v) incident on u do if (u, v) is not labelled then if v is not marked then { Label (u, v) as discovery c← 1 + c + B(G, v) } else { Label (u, v) as back c← c + 1 } return c What value does the above algorithm return? (A) The number of vertices of G. (B) The number of edges labelled as back (C) The number of connected components of G. (D) The sum of the degrees of all the nodes. (E) The number of edges of G. 2 4. How many different binary search trees containing the keys 1, 2, 3, 4 can be built such that a preorder traversal of the tree visits the node with key 2 first? (A) 2 (B) 3 (C) 4 (D) 5 (E) 8 5. Consider the following algorithm. Algorithm process(A,n) Input: Array A storing n integer values. for i← 1 to n− 1 do { j ← 0 while (j  n edges. All vertices are initially un-marked and they are stored in an array V . Consider the following algorithm: Algorithm traversal(G) Input: Undirected, connected graph G. c← 0 for i← 0 to n− 1 do { u← V [i] for each edge (u, v) incident on u do { Mark u if v is not marked then c← c + 1 } } Assume that G is stored in an adjacency list. What is the time complexity of algorithm traverse(G) in the worst case? (A) O(n) (B) O(n2) (C) O(n× degree(u)) (D) O(m) (E) O(nm) 5 Part 2: Written Questions Write your answers in the order of questions. To answer the next two questions you can use any of the algorithms studied in class. Indicate how to model each problem with a graph, which algorithm you would use, and which changes (if any) you need to make to the algorithm to answer each question. For example, let the problem be to find a shortest way of driving from city A to city B given a road map M . Your answer might be: • Graph model: Build a graph G = (V,E), where every node is a city of M and every edge is a road. The length of an edge is the length of the corresponding road. • Algorithm: Use Dijkstra’s algorithm to compute a shortest path from node A to node B. This is the shortest way of driving from city A to city B. 11. (6 marks) Let H1, H2, . . . ,Hn be a set of n houses that need to be connected to a power station H0, so they all have electrical power. The distance between Hi and Hj is d(i, j) for all i, j = 0, 1, 2, . . . , n, i 6= j. Describe an algorithm that computes the minimum length of electrical wire that is needed to connect H0 to all the houses. Note that each house does not need to be directly connected to H0. For example, for the following set of houses a wire that runs from H0 to H2 and then to H3 can be used to supply electricity to both H2 and H3. For the following set of houses, the minimum length of wire needed is 10; the wiring in an optimum solution is shown in bold. Note. Not all distances are shown between houses and power station, as otherwise the figure would be too hard to understand. (3 marks)Graph model: (3 marks)Algorithm: 12. (6 marks) Consider a set of n cars parked in a parking lot with a single exit. We wish to find the order in which all the cars can be moved out of the parking lot. Describe an algorithm to determine the order in which the cars need to move out of the parking lot. (Hint. Build a directed graph G = (V,E). What do the vertices represent? Which edges are needed to represent the constraints in the order in which the cars can move out of the parking lot?) (3 marks)Graph model: (3 marks)Algorithm: 6 13. (16 marks) The following questions refer to the time complexity of the following algorithm. T is a (2, 4) tree storing n data items and G = (V,E) is an undirected connected graph with n nodes and m > n edges. Each node u stores a value, denoted as u.key. Operation get(k) returns either the data item in T with key k or null if no data item has that key. Algorithm check(u) In: Node u of graph G = (V,E). c← 0 Mark(u) for each edge (u, v) incident on u do { if T .get(v.key) 6= null then c← c + 1 if v is not marked then c← c+check(v) } return c Assume that G is stored in an adjacency list: i) (6 marks) Ignoring recursive calls, how many operations are performed every time that the algorithm is invoked? You must explain your answer. (As explanation you may annotate the different parts of the algorithm with the number of operations that they perform.) ii) (4 marks) What is the total number of invocations or calls to the algorithm that are performed (including the initial call)? You must explain your answer. iii) (4 marks) What is the total number of operations performed by the algorithm? Explain. iv) (2 mark) What is the order of the time complexity? Explain. 7 14. (8 marks) Consider the following AVL tree. Insert the key 10 into this tree and re-balance if needed. You must use the algorithm studied in class for inserting data in an AVL tree. You must show all intermediate trees and necessary steps. Explain how you handle the re-balancing if needed. 8 15. (8 marks) Consider the following AVL tree. Delete the key 14 and re-balance the tree if needed. You must use the algorithm studied in class for removing data from an AVL tree. You must show all intermediate trees and necessary steps. Explain how you handle the re-balancing if needed. 9 16. (8 marks) Consider the following graph. Which nodes, and in which order, are marked by the Prim’s algorithm if it starts at vertex 1? You must use the algorithm learned in class for processing and show the necessary intermediate steps. Draw your resulting minimum spanning tree on the graph. 10 17. (8 marks) Insert the value 41 in the following (2,

The University of Western Ontario Department of Computer Science CS2210B Final Take-home Examination April 24, 2020 11 pages, 17 questions 24 hours Last Name: First Name: Student Number: Instructions...

Get Answer To This Question

Related Questions & Answers

Submit New Assignment