18_222_2022-1_midterm-practice-questions

COSC 222, 2022 Term 1 Practice Midterm 1) [2 marks] Rank by increasing asymptotic worst-case time complexity the following functions: A. n 3 − 2 n 2 B. 20log n + 4 C. n log n 2 D. n – n 1/3 E. √ n F. e n  Consider the following code: MyClass.java public class MyClass { public boolean isEven( int n ) { return (( n & 1) == 0); } int recur( int n ) { if ( n ==0) return 2; if ( n ==1) return 3; if (isEven( n )) return n * n ; return 2* n +1; } } MyClassTest.java Import … class MyClassTest { private MyClass m ; @BeforeEach void setUpBeforeClass() throws Exception { this . m = new MyClass(); } @Test void testIsEven() { assertTrue ( m .isEven(0) & ! m .isEven(1) & ! m .isEven(3)); } @Test void testRecur_base() { assertTrue ( m .recur(0)==2); assertTrue ( m .recur(1)==3); } @Test void testRecur_general() { assertTrue ( m .recur(7)==15); } } Use the following terminology to evaluate the quality of unit tests. Insufficient ; more tests are needed to ensure code quality (as defined in labs for the course) Inappropriate ; some tests violate fundamental unit testing rules 2) [2 marks] You analyze the unit testing for this code as A. Insufficient and inappropriate B. Sufficient, but inappropriate C. Appropriate, but insufficient D. Good; satisfies all code quality rules 1 / 4

 Consider the following graph 3) [1 mark] Select the correct graph representation A. 0->1->2->4 1->0->3 2->0->4 3->1 4->0->2 B. 0->1->3 1->0->3->4 2->0->4 3->1 4->0->2 C. 0->1->2->4 1->3 2->0->4 3->1 4->0->2 D. 0->1->2->4 1->0->3 2->0->4 3->2 4->0->2 E. 0->1->2->4 1->0->3 2->0->4 3->1->2 4->0->2  Consider the following graph 4) [3 marks] Applying Dijkstra’s shortest path algorithm starting from node 0, select the order in which the nodes are added to the explored set. A. 0, 3, 2, 1 B. 0, 2, 3, 1 C. 0, 2, 1, 3 D. 2, 0, 3, 1 E. 2, 0, 1, 3 2 / 4 3 0 1 2 4 2 3

 A company wishes to perform the following operations on its data (assume there are m transactions and n customers and n is less than m). Each transaction includes customer name, address, purchase amount, and date a. Input a new transaction including customer name, address, purchase amount, and date b. List the top 5 customers by total purchases made till now c. List all purchases made by a customer (assume there are h purchases) d. Update customer information 7) [2 marks] Select the closest asymptotic worst-case time complexity for the above operations when the data structure used is an unsorted list A. Quadratic O ( n 2 + m 2 + nm ) B. Linear O ( n + m ) C. Log linear O ( ( n + m ) log ( n + m ) ) D. Logarithmic O ( log ( n + m ) ) E. Exponential O ( 2 n + 2 m ) 8) [2 marks] Select the closest asymptotic worst-case space complexity for the above operations when the data structure used is an unsorted list A. Quadratic O ( n 2 + m 2 + nm ) B. Linear O ( n + m ) C. Log linear O ( ( n + m ) log ( n + m ) ) D. Logarithmic O ( log ( n + m ) ) E. Exponential O ( 2 n + 2 m ) [Open answer] Propose a combination of data structures that improves the time complexity; indicate the time complexity of your data structure, e.g., 9) a. Array indexed on age, O(1) 9) [2 marks] Data structure(s): 10) [1 mark] a. time complexity 11) [1 mark] b. time complexity 12) [1 mark] c. time complexity 13) [1 mark] d. time complexity  [Open answer] You are given 2 arrays A and B of sizes n and m respectively. Array A contains pairs of objects storing a key and a value. Array B contains similar information i.e., objects with a key and an associated value. Explain an algorithm to list all the objects as key in array A, value in array A, and value in array B for which the key in array B is equal to the key in array A. For example, Array A Array B Key Value Key Value 1 Mary 1 London 42 Linda 64 Paris 84 Jennifer 84 New York The output should be Key Value A Value B 1 Mary London 84 Jennifer New York Indicate the complexity of your algorithm (space and time) including of any pre-processing step performed to speed the listing operation (if any). You can assume that the keys are integer valued, and all the data is known beforehand (offline algorithm). 14) [4 marks; Open answer] 4 / 4