Will not have the exam until 12/6 at 5:30 (central time) and must be turned in by 7:15. I do have past exams and review sheet for reference. Topic is data structures with python programming.
Question 1) Write the following function for a singly linked list Review for Exam 3 (Final exam) Scheduled Exam 3 date: 12/6 (T), 2022 General remarks for preparing Exam 3: Pay attention to SCOPE of this exam Review textbook, lectures and discussion sheets carefully. Also remember that assignments only cover part of required materials. Questions similar to exercises or previous exams may appear in the exam (along with other questions). It is possible that exact questions you answered before may appear in the exam. If this is the case, if your answer is wrong, you will receive little or even no partial credits at all. Old materials: BETTER understanding, BETTER answers (Less partial credits) Read this document very carefully and use it to prepare for the exam. Review assignments, classroom exercises and discussion sheets carefully. Also remember that these questions may not cover all the materials you are responsible for. (For example, simple questions in regard to time complexity in Review 2). Let instructor know ASAP if you have any questions. This study guide is subject to minor revision or correction in coming days. Part A. General instructions 1. Important concepts: (a) Big Oh and related concepts. Good understanding of Big Oh, little Oh, Big Omega and Big Theta. Definitions involve quantitative formulas (involving constants c and n0). Correct any misconceptions about Big O: It is an upper bound, but its use is NOT restricted to worst case analysis. (b) NP and NP completeness (c) General idea of algorithm design methods: greedy algorithm, divide and conquer 2. Mathematical induction induction, particularly involving properties related to a particular data structure (such as tree or graph). E. g. For all connected graph G with n vertices, G has at least n−1 edges. 3. Recurrence relation and master theorem. Be able to derive recurrence relations for simple recursive modules and solve recurrence relation using master theorem if applicable. [Master theorem will be provided as an appendix.][Telescope is not required.] 4. Important things about each data structure learned: (i) what is it and why is it needed, (ii) typical operations and (iii) time complexity and other important theoretical results. 5. Remarks on trees and graphs. Due to time constraints in the exam, you may not be asked to perform operations (insert, delete, rotate, etc.) on BST, AVL trees, and other data structures learned before Exam 2. However, you are still responsible to all important concepts and theoretical result about these data structures. Concepts related to tree include: root, nodes, leaf, sibling, descendent, edge, path, length, depth, height, full node, half node, binary tree, complete binary tree, full binary tree, perfect binary tree, etc. Pay particular attention to terminology related to graphs! 6. Sorting algorithms: Be able to execute these algorithms: Shellsort, heapsort, mergesort (and use of mergesort for external sorting), and quicksort. (Review the discussion on quicksort very carefully! Most answers were not clear.) -- Why is Shellsort important? -- Result of time complexity analysis for insertion sort, heapsort, mergesort and quicksort. -- Two important theorem about sorting, and understand the important roles of inversion (what is it?) and decision tree (what is it?) in proving these two theorems. [No detailed proof is required.] -- Understand the work you did in program assignment PA5. -- Under which conditions linear sorting is possible? You should know the basic ideas of bucket sort and radix sort (and may be asked to solve a simple problem using radix sort). 7. Data structures used in dealing with files cannot be stored in memory: B+ trees, extendible hashing, external sorting.(understand motivation and basic ideas of operations) 8. Heaps and heapsort 9. Graphs: · All important concepts, · representation of graphs (for a given graph, be able to show adjacent matrix and adjacent list, and for given adjacent matrix and adjacent list, be able to draw the graph), · be able to perform all three important algorithms (Dijkstra, Prim and Kruskal) with steps, · understand concepts of topological sort, depth first search (DFS) and breadth first search (BFS) and be able to solve simple problems as shown in lecture notes. 10. Big O analysis -- Give the tightest possible upper bound for the worst case running time for a particular problem. This type of question asks you to describe steps needed to solve a particular problem, and based on which you should be able to decide the time complexity. You MUST choose your answer from the following (not given in any particular order), each of which could be reused: O(N2), O(N½), O(N3 log N), O(N log N), O(N), O(N2 log N), O(N5), O(2N), O(N3), O(log N), O(1), O(N4), O(N12), O(NN), O(N6), O(N8), O(N9) You will lose most of your points if your answer for the big Oh analysis is correct but no justification is provided. Example: What is the worst case big-O running time of the following operation (use V and E rather than N in your answers). Find the in-degree of a single vertex whose graph is stored in an adjacency matrix. How to answer this question? First, use one or more English sentences to describe steps needed to solve this problem. Then, based on your answer above, determine time complexity of solving this problem: O( ) 11. Algorithm design approaches (Pay particular attention to greedy algorithms, as well as divide and conquer) Part B. Summary of some important (theoretical) results on data structures and sorting algorithms covered in lectures 3-6 (Review lecture notes and textbook) · Review by yourself: Basic binary search tree (BST) operations (remember: newly inserted element is always a leaf). · AVL tree Unlike the case of AVL tree insertion, in which ONE rotation (single or double) is sufficient to restore the height-balance in an AVL tree, in AVL tree deletion, the trinode restructuring may reduce the height of the subtree (with a new root) by 1, which may cause ancestor of this new root to become unbalanced. · Primary clustering: the tendency for certain open-addressing hash tables collision resolution schemes to create long sequences of filled slots. It is most commonly referred to in the context of problems with linear probing. · Secondary clustering: Although quadratic probing eliminates primary clustering, elements that hash to the same position will probe the same alternative cells. · If quadratic probing is used, and the table size is prime, then a new element can always be inserted if the table is at least half empty. · Strong lower bound (A lower bound for simple sorting algorithms): Any algorithm that sorts by exchanging adjacent elements requires (N2) time on average. (To prove this result, we need the concept of inversion: · An inversion in an array of numbers is any ordered pair (a[i], a[j]) having the property that i
a[j]. · The average number of inversions in an array of N distinct elements is N(N-1)/4. · General Lower Bound for Sorting: Any algorithms for sorting that uses only comparisons requires (N logN) comparisons (and hence time) in the worst case. (N is the size of the input.) · Algorithm as decision trees · Decision trees for sorting – each outcome as a leaf · Any comparison-based sorting algorithm needs log2n! comparisons in the worst case. · NP class and NP completeness: How to show a problem is NP complete? Part C. Additional review questions—not required to turn in. Not a rehearsal of exam 3, but in case any question below is included in the exam, a good answer is expected.-- 1. Big Oh and its relatives. (a) Write down the definition for Big Oh as shown in lecture notes. (b) Show that for f(n)=3n2 - n, it is O(n2). You must use the definition of big Oh as given in lectures. (c) Write down the definition for Oh (Omega Oh) as shown in lecture notes. (d) Show that for f(n)=3n2 - n, it is (n2). You must use the definition of Omega Oh as given in lectures. Write down the definition for Oh (Omega Oh) as shown in lecture notes. (e) Show that for f(n)=3n2 - n, it is (n2). You must use the definition of Omega Oh as given in lectures. (f) Write down the definition for little oh as shown in lecture notes. (g) Show that for f(n)=3n2 - n, it is o(n3). You must use the definition of little oh as given in lectures. 2. Inversion. Recall a question in A5: apply Shellsort for the given input, using the increments {1, 3, 7}. . Solve this problem by filling the following table. Original 12 18 7 2 17 4 3 9 1 13 5 6 Consider 7-sort. If we swap the 18 and 1 from the input 12, 18, 7, 2, 17, 4, 3, 9, 1, 13, 5, 6, how many inversions does that single swap remove? 3. Review of sorting algoirthms. What is the running time of the sorting algorithms for the following inputs (using Big Oh notation on input size N)? A brief justification is needed. Note: You should not just memorize the answers. You should understand why we have these time complexities by reviewing the corresponding algorithms very carefully. Sorting algorithms Sorted input Reverse-order input Random input Insertion sort Mergesort Heapsort Quick sort (median-of-three pivot selection) Quick sort (if the pivot is chosen as the first element) 4. Additional questions on sorting. (a) Is there a comparison-based algorithm to sort 4 elements requires only 5 comparisons? Why or why not? (Justify your answer.) (b) Sort 5, 4, 9, 2, 6, 7, 2, 3 using bucket sort, assuming M = 10. (c) Radix sort on the following input: 56, 903, 53, 47, 202, 263, 346, 547. Follow the steps shown in lecture notes. 5. Math induction (a) Use math induction to prove: 1+3+5+..(2k-1) = k2 (b) Use math induction to prove: A connected undirected graph G with n vertices has at least n−1 edges. (You should follow all the requirements stated in the past, including base case, inductive hypothesis, what need to be proved in general case, and the actual work to conduct the proof – which must use the inductive hypothesis. Note that such reminder will NOT appear in the exam sheet, yet you have to follow all of these steps.) 6. Graphs representation. Represent the following graph using (i) Adjacent matrix, (ii) Adjacent list. 7. Graph algorithms. (a) Apply Prim’s and Kruskal’s algorithms to find MST for the following graph. (b) Apply Dijkstra’s algorithm on this graph to find shortest paths to all other vertices from A. 1