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.