EECS 2011 Term Test Summer 2020 Lassonde School of Engineering York University Duration: Take-home Exam Aids Allowed: Open book Student Number: Family Name(s): Given Name(s): This term test consists...

Clear answers with comments, answers are checked for plagiarism so no answer from online or other sources.


EECS 2011 Term Test Summer 2020 Lassonde School of Engineering York University Duration: Take-home Exam Aids Allowed: Open book Student Number: Family Name(s): Given Name(s): This term test consists of three questions on 5 pages (including this one). You have 24 hours to complete this midterm. This exam will be available on June 18, 2020 at 6 a.m. in Moodle. You will need to fill in the answers by hand and upload these to the Moodle submission site by 6 a.m. on June 19, 2020. Your writing must be legible. By taking this exam, you are committing to completing this exam on your own without collaborating with anyone else. We will be checking for plagiarism. Please do not email the instructor or the TAs regarding any questions related to this exam. Make necessary assumptions and complete the test. When writing code, assume all input is valid unless indicated otherwise (i.e., do not waste time writing code to perform error- checking). Also, assume that the necessary library files have been included. Comments are not required (except where indicated), but may help us give you partial credit, especially when your solution is incomplete. Marking Guide: Q1 : 25 marks Q2 : 20 marks Q3 : 15 marks Total : 60 marks Good Luck! Page 1 of 5 EECS 2011 Term Test Question 1. [25 marks] Please provide short answers to each one of the following sub-questions. You may show your work as needed for part marks. a) What is the algorithmic complexity with respect to n of the following code snippet? [5 Marks] int k=0; for (int i = 0; i < n;="" i++)="" {="" for="" (int="" j="i+1;" j=""> i; j--) { k=i; while(k>0){ k=k/2; System.out.println("*"); } } } b) What is the algorithmic complexity with respect to n of the following code snippet? [5 Marks] int count = 0; for (int i=1; i<=n; i="i*2)" for="" (int="" j="1;"><=n; j++)="" for="" (int="" k="n;" k="">0; k = k/2) System.out.println("*"); c) What is the algorithmic complexity with respect to n of the following code snippet? [5 Marks] public int f(int n){ if(n>0){ return f(n-1)/2+n+n; } d) What is the algorithmic complexity with respect to n of the following code snippet? [5 Marks] public int f(int n){ if(n>0){ return f(n/2)+1; } e) What is the algorithmic complexity with respect to n of the following code snippet? [5 Marks] public int f(int n){ if(n>0){ return 2*f(n/2)+1; } Page 2 of 5 Summer 2020 Question 2. [20 marks] a) [15 Marks] Assume that there are n integers stored in a Queue. Your task is to sort these integers in increasing order where the front of the Queue contains the smallest value and the end of the Queue contains the largest value. You can use a Stack to temporarily store the content of the Queue as needed. You cannot use any other data structures for temporary storage. You cannot implement any helper functions. Assume that you have access to the following functions that support interface operations on Stacks belonging to the class LinkedListStack: • public void push(E e); • public E pop(); • public int isEmpty(); where E is a generic type. You can also assume that you have access to the following interface operations on Queues belonging to the class LinkedListQueue: • public void enqueue(E e); • public E dequeue(); • public int isEmpty(); You will implement the following function: public void sortQueue(LinkedListQueue Q); b) [5 Marks] What is the computational complexity of this function in terms of n? n represents the number elements currently stored in the Queue. Page 3 of 5 EECS 2011 Term Test Question 3. [15 marks] Consider two linked lists containing nodes that are stored in descending order (highest to lowest value of elements). Each node in the linked list is defined via the generic Node class and the following operations are supported on each node entity: • public E getElement() • public Node getNext() • public void setNext(Node n) E in this case is an integer. Your task is to implement the following function: public Node mergeAscending(Node L1, Node L2); that merges the two linked lists L1 and L2 in place so that the resulting list contains nodes in ascending order. L1 is the reference to the beginning of the first linked list, L2 is the reference to the beginning of the second linked list. Both of these linked lists contain nodes arranged so that the value stored in element member of each node will be larger than that in the next node (i.e. descending order). The head of the merged list can be stored in a global variable Node head that is defined outside of this function. Both lists can be of different lengths. You cannot implement additional helper functions. There is no need to set the last node in the merged list to NULL as this will be done after the function call in the testing function. You will implement this function using recursion with no additional helper functions or the creation of new nodes. Page 4 of 5 Summer 2020 Some Useful Formulae n−1∑ i=0 (a + di) = n 2 [2a + (n− 1)d] a n−1∑ i=0 ri = a (1− rn) 1− r logan = logbn logba loga(nm) = loga(n) + loga(m) loga( n m ) = loga(n)− loga(m) loga(n!) ∈ O(nlog2(n)) Page 5 of 5