Question
CISY 254-Midterm Exam Info- Summer 2018 Logistics Thursday, July 12th, 7:00 8:00 Note: 6:00 6:45 will be a lecture on Queues 6:45 7:00 break 8:00-9:30 will be lab time to work on a Lab on Queues (if done with the exam early, you will not be able to use computers until after the exam ends 8:00) Closed Note / Closed Book/ Closed Computer No Electronic Devices Paper Based exam, 5 questions, 20 points each Topics: Big-o() i. Given an algebraic formula for the number of steps, determine the Big-O) [for examples see Homework 1-#5 and Data Structure Lab 0141 ] ii. Given an algorithm, determine the algebraic formula for the number of steps, determine the Big-0() (algorithm will be based on an array of ints - there will be two questions like this) (Similar to Data Structure Lab 01-#2 ) Example: Given a fully populated array of n integers called data, (data.length is n) also also an array of n integers called count (already initialized to 0), for datafi], the number of elements in data from data[0] to data[n-1] that are equal to datali] is stored in countli], consider this algorithm for (i-0; i
Explanation / Answer
i) The term with max exponent power will be detrmining the BIg-O complexity. Like for sum = n*(n+1)/2 = (n^2)/2 + n/2 Max power is on n^2 term, hence this determined the complexity = O(n^2) ii) a) Both inner and outer loop run for n steps, n^2 total steps` b) O(n^2) iii) int count = 0; Node *p = head; int sum = 0; while(p != NULL) { sum += p->data; p = p->next; count++; } double avg = sum/count; count = 0; p = head; while(p != NULL) { if(avg data) { count++; } p = p->next; } // print count of more than avg nodes ===== Complexity: We first traverse n nodes, to figure out the sum and count. Then again we traverse n nodes to find nodes carrying value more than avg. Hence 2n steps Complexity(O(n)), since we dont consider constant term in complexity. iv) Node newnode = new Node("Mango"); newnode.next = cursor; previous.next = newnode;