CS 3130 Design and Analysis of Algorithms Fall 2020 FINAL EXAM [150 points] ——————————————————————————————————————————–
Important: The test should be completed and submitted within 140 minutes. I expect that you will need 2 hours (120 minutes) for solving problems, and I give you 20 minutes for file uploading. Please, make sure that your equipment works properly before you start taking this test! Reserve enough time for file uploading! Questions in the Final Exam are provided on Canvas, so you don’t need to download them. However, the majority of questions are of ‘File Upload’ type, so you have to write or type your solutions and upload your work. I give you an option to combine several questions into one. Just write the number of the corresponding question next to your solution, so that I will understand the structure of your file. Final Exam is comprehensive. It covers material that was included into Test #1 and Test #2, plus sections 7.1, 7.3, 7.4, 8.1, 8.2, 9.4. If some material from the indicated sections was not discussed in video lectures, this material will not be a part of the Final Exam. For example, Strassen’s matrix multiplication algorithm is a part of sec. 5.4, but it was not discussed in video lectures, so it will not be included into the Final Exam. If this exam were taken in the class, the test paper would have 10 pages plus 1 page with bonus problems. On Canvas you will have 15 problems for 150 points plus 3 problems for 15 bonus points. ———————————————————————————————————— The important part of the course is application of mathematical methods to analysis of algorithms. Please, pay attention to Chapter 2, Appendix B and your notes! Also, don’t miss solutions of some recurrence relations discussed after Chapter 2. Use keys to quizzes, homework assignments and tests in your preparation. Review all the algorithms that were introduced
in the course: logic, description in pseudocode, efficiency, examples. In particular, review logic, efficiency and properties of the following sorting algorithms: 1. insertion sort; 2. selection sort; 3. bubble sort (2 versions); 4. quicksort; 5. mergesort; 6. heapsort; 7. sort by counting; 8. distribution sort. Review the implementation of different operations on the following data structures: 1. sequential arrays; 2. heaps; 3. priority queues; 4. binary search trees; 5. AVL trees 6. 2-3 trees; 7. B-trees; 8. hash tables. ——————————————————————————————————– Some possible types of problems: Multiple-choice questions on general properties of different data structures, classification of algorithms and performance characteristics of algorithms (review the best case, average case and worst case performance for each of the algorithms studied in the course). Relative order of growth of functions (review limit calculations). Application of basic principles of algorithm analysis: given a code of an algorithm, find the time efficiency. Solve the given recurrence relation (make sure that you review different ways of solving recurrence relations: backward substitution, Master Theorem, characteristic equation). Questions on the properties of: binary trees (relationships between the number of internal and external nodes, number of links, number of leaves, the height of a given binary tree, internal and external path length, traversals), heaps (review implementation of a heap with a sequential array as well as graphical representation), BST, 2-3 trees, AVL trees, B- trees. Questions on implementation and properties of the algorithms covered in the course. Given a sequence of items; build: 1. a heap; 2. a priority queue; 3. a binary search tree; 4. an AVL tree; 5. a B-tree; 6. a hash table for specific hashing function and collision resolution method. Questions on principles of Dynamic Programming. Questions on Huffman’s code. IMPORTANT: (a) the Final Exam may include problems not listed above; (b) some of the problems listed above may not appear on the Final.