quiz 2 - alora taylor

Student Name: Alora Taylor J#: J00800720 CSC 515/601, Spring 2024 Instructor: Dr. Natarajan Meghanathan Quiz 2 (Take Home; Due by: March 24th, 11.59 PM) Max. Points: 50 Answering and Submission: You should answer in the space provided. Either type your solutions or scan your answers and include the scanned picture file in the space provided in the document and submit (upload in Canvas) the entire exam as a single word document or PDF file. Note: You should NOT write or use a computer program to answer any of these questions. If you do so, you will get ZERO. Note: The above deadline is a hard deadline. Any submission beyond this deadline will NOT be accepted. Question 1: 10 points Consider a scenario of inserting each element to the “beginning” (i.e., at index 0) of an array-based List with respect to the strategy of doubling the array size whenever it is full. Determine the overall time complexity of the copy/write operations for inserting a sequence of ‘n’ elements (one after the other) to the List. Assume the copy and write operations are the same and count them together. 1. The array starts out with a size of 1, and adding the first element necessitates a single copy and write operation. 2. The array must be enlarged to provide room for the second element when it is inserted. The array size increases to two because the doubling approach is being utilized, and adding the second member necessitates two copy and write operations—one for insertion and one for resizing. 3. The array size must be increased again to 4 in order to insert the third member, necessitating 4 copy and write operations (2 for resizing and 2 for insertion). 4. Likewise, eight copy and write operations are needed to insert the fourth element (four for resizing and four for inserting). 5. Generally, 2^(n-1) copy and write operations are needed to insert the nth element (2^(n- 1) for resizing and 2^(n-1) for inserting). Total operations = 1+2+4+8+2^(n-1) Sum= a(r^n -1)/(r-1) A=first term:1 R= common ratio:2 N= number of terms:n Sum=1(2^n-1)/(2-1) Simplify= 2^n-1 Because of this, inserting 'n' elements requires a total of 2^n - 1 copy and write operations, giving us an O(2^n) overall time complexity in big O notation. 1

Student Name: Alora Taylor J#: J00800720 Question 2: 15 points Consider a scenario wherein 50,000 objects (each of size: 20 bytes) need to be stored in a List using a sequence of insertions. Determine the memory (in bytes) that would need to be allocated to the List if it were to be implemented as an: (i) array; (ii) Singly Linked List and (iii) Doubly Linked List. In the case of the array-based implementation, assume the array size starts from 1 and is doubled every time when the array gets full. i) array: an array of 50000 objects needs 50000*20+1000000 bytes to be allocated ii) singly linked list: a node in a singly linked list requires 20+8=28 bytes since it contains objects and a pointer that stores the address of the next node, which requires 8 bytes. 50000 objects; 50000*28=1400000 bytes iii) doubly linked list: a doubly linked list node requires 20+8+8=36 bytes since it contains objects in addition to pointer_back_node (8 bytes) and pointer_next_node (8 bytes). 2

Student Name: Alora Taylor J#: J00800720 Step Action Stack Output Queue 1 Scan 5(operand) 5 2 Scan * (operator) * 3 Scan 3 (operand) 5 3 4 Scan / (operator) / 5 3 5 Scan 4 (operand) 5 3 4 6 Scan + (operator) + 5 3 4 / 7 Scan 2 (operand) 5 3 4 / 2 8 Scan - (operator) - 5 3 4 / 2 + 9 Scan (operand) 5 3 4 / 2 + 6 10 End 5 3 * 4 / 2 + 6 - Step Action Stack Output Queue 1 Reverse postfix expression -6+2/4*35 2 Apply infix to postfix algorithm - + * 5 3 / 4 2 6 3 Evaluate prefix expression 5 4 Evaluate 6 (operand) 6 5 Evaluate 2 (operand) 2 6 Evaluate 4 (operand) 4 7 Perform 4/2 (operator) 2 8 Evaluate 3 (operand) 3 9 Perform 3*2 (operator) 6 10 Evaluate 5 (operand) 5 11 Perform 5+6 (operator) 11 12 Perform 11-6 (operator) 5 End 5 4

Student Name: Alora Taylor J#: J00800720 Question 4: 12.5 points Consider storing the contents of the array A = {34, 12, 45, 89, 77, 21, 90, 23, 47, 88} in a hash table of size 5. Determine the following: (a) Average number of comparisons for a successful search (b) Average number of comparisons for an unsuccessful search (c) Worst case number of comparisons for an unsuccessful search (d) Load Imbalance Index Hash Table: Slot 0 Slot 1 Slot 2 Slot 3 Slot 4 45, 90 21 12,77,47 23,88 34,89 a) Average comparison = (sum of elements in slots)/(number of non-empty slots) = (2+1+3+2+2)/5=2 b) Average unsuccessful comparison = (number of occupied slots +1)/ (number of non-empty slots) = (5+1)/5=1.2 c) When every slot in a linear probe is taken, with the exception of the last one, the element being searched is hashed to that slot, resulting in the maximum number of comparisons. This is the worst-case situation for a failed search. Worst case unsuccessful comparison= hash table size = 5 d) Load imbalance index = (max length of a slot)/(average length of non-empty slots) Load imbalance index = 3/2=1.5 5