CSIT 212 FA24 Final Study Guide PDF

CSIT-212 Final 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 algorit...

CSIT-212 Final 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) 2. Algorithm Worst Case Time Complexity Insertion Sort O(n^2) Merge Sort O(nlogn) Heap Sort O(nlogn) Quick Sort O(n^2) Counting Sort O(k+n) Searching Hash Table O(n) Balanced Binary Search O(logn) O(h) Tree Unbalanced Binary O(n) Search Tree Inorder, postorder, O(n) preorder search Cut-Rod O(2n) Longest Common O(m+n) Subsequence Breadth first search O(|V|+|E|) Depth first search O(|V|+|E|) Dijkstras O(VlogV+E) 3. List each linear data structure vs non linear data structure. a. Linear: array, stack, queue, linkedlist b. Nonlinear: Tree, graph, Hash Table 4. Which algorithms utilize the divide and conquer paradigm? Please list all. a. Quicksort, merge sort, binary search 5. What is in-place sorting? provide an example of a sorting algorithm that utilizes in place sorting. a. Does not require additional space (memory) to transform the input b. No additional data structure such as an array i. An example is insertion sort 6. What is not in-place sorting? Provide an example of a sorting algorithm that utilizes not in-place sorting. a. Requires additional space (memory) to transform the input b. Memory is equal to or more than the original input c. Faster than in-place sorting i. Merge Sort 7. Explain the difference between stable and unstable sorting, provide examples for both based on what we have learned. a. Stable sorting: Numbers/elements with the same value appear in the output array in the same order as they do in the input array i. Merge sort b. The order of numbers/elements is not preserved during the sorting process, and may appear in a different order in the output array Quicksort 8. What property does a max-heap have to satisfy? a. A[Parent(i)] ≥ A[i] 9. Explain how we can achieve the best case time complexity for Quicksort. a. Best case time complexity occurs when the pivot divides the array nearly in half  b. O(n log n) 10. What are the three arrays we use for Counting-Sort, what do they do? a. A - which is our input array b. B - Which is our output array c. C - Auxiliary array (extra storage) 11. What policy does a Stack use, and why? a. Last in First Out 12. What policy does a Queue use, and why? a. First in First out 13. Here is an input sequence 123+45**+ use a stack to compute the sum, show all steps. a. 1 2 3 + = 2+3 = 5 b. 1 5 4 5 * = 4*5 = 20 c. 1 5 20 * = 5 20 = 100 d. 1 100 + = 1+100 = 101 e. 101 is the final answer 14. What are the two functions that add and remove from a Stack? a. Push and Pop 15. What attribute of a stack keeps track of the most recent element pushed into the stack? a. Top 16. What two functions add and remove from a Queue? a. Enqueue and Dequeue 17. 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? a. Head and tail 18. Understand and explain a Doubly Linked List, including the attributes and how they work. a. 19. Define all the attributes that make up a tree structure. a. Root b. Parent c. Child d. Leaf e. Key f. edge 20. What is the binary search tree property? a. 21. Given this Binary Search Tree, please list the order of the nodes following Inorder traversal, preorder traversal, and post order traversal. a. In order: 25, 30, 35, 40, 45, 50, 60 b. Postorder: 25, 35, 30, 45, 60, 50, 40 c. Preorder: 40, 30, 25, 35, 50, 45, 60 22. What is the max height and depth of the tree in question 22? a. Height 2 - start from root at 0 b. Depth 2 - count edges 23. What are the 5 properties that satisfy a red black tree? a. 24. What is a sentinel for merge sort and red black tree? a. Essentially a boundary 25. What is chaining in hash tables? a. we place all the elements that hash to the same slot into the same linked list 26. Why do we use dynamic programming? a. Break the problem into several overlapping subproblems b. Solve the subproblems recursively only once, and save the answer in a table c. Combine these solutions to solve the original problem d. We use dynamic programming to solve optimization problems i. Optimization problems are problems that can have a variety of solutions 27. What type of trade off does dynamic programming incur? a. time-memory trade-off. As dynamic programming uses additional memory 28. What algorithm do we use to calculate the minimum number of scalar products? a. Matrix-chain multiplication 29. You do not need the pseudocode, but please ensure you understand LCS-Length(X,Y) and how to fill in tables B and C. For example, If I give you inputs X = ‘XMJAUZ’ and Y =  ‘MZJAWXU’, fill in tables B and C finding the LCS. You can also use the example practice sheet I gave to practice this. ******** 30. What are the two methods in finding the longest common subsequence? a. Brute force b. The optimal substructure property 31. What is the output we want from the LCS algorithm? a. How long the longest common subsequence is and what it is, basically we return the b and c table, then we can use print-lcs to print the LCS 32. What is stored in the C and B table? a. C table: the c table is used to store the lengths of the various subproblems of the LCS. b. B table: the b table is also known as the directional table, and helps in reconstructing the LCS 33. What does each arrow mean? Left, right, diagonal? a. Diagonal Arrow: Indicates that the current characters of both sequences match (x i =y j ) and are part of the LCS. b. Up Arrow: Indicates that the current character of the first sequence (x i ) is not part of the LCS, and the value was derived from the cell above. We exclude character. c. Left Arrow: Indicates that the current character of the second sequence (y j ) is not part of the LCS, and the value was derived from the cell to the left. We exclude this character. 34. What are B-Trees? a. B-trees are balanced search trees designed to work well on disks or other direct access secondary storage devices 35. B-Trees copy pages from where? What does it then do?  a. from disk into main memory as needed and write back onto disk the pages that have changed 36. Every node other than the root must have how many keys? a. t-1