Midterm Study Guide (1).docx

CSIT-212 Midterm Study Guide - Remember that this final will be fully comprehensive of the entire course. Fill it out and familiarize yourself with all concepts. 1. Fill in the table with the worst case and best case (if any) Big O time complexities for each algorithm. a. Remember...

CSIT-212 Midterm Study Guide - Remember that this final will be fully comprehensive of the entire course. Fill it out and familiarize yourself with all concepts. 1. Fill in the table with the worst case and best case (if any) Big O time complexities for each algorithm. a. Remember O(h) is actually O(logn) ------------------------------------- -------------------------- Algorithm Time Complexity Insertion Sort O(n\^2) Merge Sort O(nlogn) Heap Sort O(nlogn) Quick Sort O(n\^2) \-\-\-- O(nlogn) Counting Sort O(k+n) Searching Hash Table O(1) \-\-- O(n) BST Tree-Search O(h) BST Insert/Delete O(h) Inorder, postorder, preorder search O(n) ------------------------------------- -------------------------- 2. List each linear data structure vs non linear data structure. b. Linear i. Linked list ii. Arrays iii. Stacks and queue c. Non linear iv. Trees v. Graphs vi. Hash table 3. What is recursion? Please provide an example. d. When a problem breaks itself down into smaller objects. e. Calls upon itself f. An example is factorials 4. Which algorithms utilize the divide and conquer paradigm? **Please list all**. g. Merge sort h. Quick sort i. Heap sort 5. What are the **three steps** that make up the **divide and conquer** paradigm? j. Divide -- break into smaller problems k. Conquer -- recursively solve the problem l. Combine -- combine the solutions 6. Write out and explain the pseudocode Merge(A,p,q,r) from Merge Sort (I will provide pseudocode on the exam, but you need to study how the pseudocode functions). m. Takes a given array and splits it into two arrays n. Left sub array and right sub array o. Completes them independently and combines itself back into a whole array in an ordered sequence vii. Splits into two subarrays left and right, continues to break the subarrays array into individual "chunks" elements, compares, rearranges, and combines, until it sorts both left and right subarray. p. Merge sort uses sentinel nodes 7. What is in-place sorting? provide an example of a sorting algorithm that utilizes in place sorting. q. Sorting algorithm that does not need extra memory to sort the elements, it sorts in the same array as the input. r. Insertion sort, quick sort 8. What is not in-place sorting? Provide an example of a sorting algorithm that utilizes not in-place sorting. s. Requires additional memory -- may use extra array to store elements t. Merge sort 9. Explain the difference between stable and unstable sorting, provide examples for both based on what we have learned. u. Stable viii. When the numbers/elements with the same value appear in the same order in the output as it did in the input ix. Its important when the order of equal elements have significant meanings x. Insertion sort, merge sort v. Unstable xi. Output values are not preserved as it would be in stabled, so the input order is different then the output order for elements that are the same xii. Faster because it is not necessarily ensuring the elements that are the same are in the same order, faster \> accuracy. xiii. Heap sort and quick sort 10. Write out the and explain the pseudocode Max-Heapify(A,i), (I will provide pseudocode on the exam, but you need to study how the pseudocode functions) w. Takes an input array and creates sub arrays (left and right) each element of the array goes down the left or right sub array and to place each element in order by index to sort them and also satisfying the property of a max heap x. you see if the left child is less than or equal to the value of the parent y. 11. What property does a max-heap have to satisfy? z. The parent must be greater than or equal the child a. A\[Parent(i)\] \>= A\[i\] b. Min heap is the reverse 12. Write out and explain the pseudocode Partition(A,p,r) from Quicksor (I will provide pseudocode on the exam, but you need to study how the pseudocode functions)t. 13. Explain how we can achieve the best case time complexity for Quicksort. c. The pivot point ensure the split is practically equal xiv. Big O(nlogn) 14. What are the three arrays we use for Counting-Sort, what do they do? d. A is the input array e. B is the output array f. C is the extra storage array 15. What policy does a Stack use, and why? g. Last in first out 16. What policy does a Queue use, and why? h. First in First out 17. Here is an input sequence 123+45\*\*+ use a stack to compute the sum, show all steps. i. Push 1 to the stack j. Push 2 to stack k. Push 3 to stack l. We encounter a plus sign, so we pop the previous two elements m. And we do addition, so 2+3=5 we push 5 to the stack our stack is now 1,5 n. We push 4 o. We push 5, our stack is now 1,5,4,5 p. We encounter a \* we pop the previous two elements 4 and 5 and multiply q. We push 20 to the stack, our stack is 1,5,20 r. We encounter a \* we pop 20 and 5 and multiply s. We push 100 to the stack t. We encounter a + sign so we pop the previous two elements 100,1 u. We add 100 and 1, and push 101 to the stack 18. What are the two functions that add and remove from a Stack? v. Push and pop 19. What attribute of a stack keeps track of the most recent element pushed into the stack? w. top 20. What two functions add and remove from a Queue? x. Enqueue and dequeue 21. What are the two attributes that keep track of the index of the first element, and the index of the next location a new element can be inserted? y. Head and tail 22. Understand and explain a Doubly Linked List, including the attributes and how they work. 23. Write out and explain the pseudocode for List-Insert and List-Delete (I will provide pseudocode on the exam, but you need to study how the pseudocode functions) 24. Define **all** the attributes that make up a tree structure. z. Key a. Parent b. Left c. Right d. Edge e. Siblings f. Nodes g. Leaves h. Root 25. What is the binary search tree property? i. Y.key \= x.key 26. Given this Binary Search Tree, please list the order of the nodes following Inorder traversal, preorder traversal, and post order traversal. k. Inorder -- 25, 30, 35, 40, 45, 50, 60 l. Preorder -- 40, 30, 25, 35, 50, 45, 60 m. Postorder - 25, 35, 30, 45, 60, 50, 40 27. What is the max height and depth of the tree in question 22? n. Height -- 2 o. Depth - 2 28. Write out and explain the pseudocode for Iterative-Tree-Search(x,k) 29. Write out and explain the process of inserting a new node into the tree, and transplanting when deleting. Please explain your knowledge of both. (I will provide pseudocode on the exam, but you need to study how the pseudocode functions). 30. What are the 5 properties that satisfy a red black tree? 31. What is a sentinel for merge sort and red black tree? p. A marker/boundary 32. What is chaining in hash tables? q. It is a linked list, we chain the elements at the same index in the hash table by chaining them in linked lists