The Final Exam for Spring 2018 CS:3330 "Algorithms" will be held on Monday, May 7th from 5:30 pm to 7:30 pm in W128 CB (Chemistry Building).

During the exam you can use any written/printed material you bring, including books and lecture notes; in other words, this is an open book/notes exam. Make sure you bring everything that you feel you will need to the exam because you will not be allowed to share or borrow material with classmates during the exam. You will have to turn off and remove from your vicinity all electronic devices including cell phones, lap tops, calculators, dictionaries, etc.

The exam is worth 200 points, which is 20% of your final grade. Here is a brief description of the structure of the exam.

• Problem 1. (40 points) This problem will be a variant of problem(s) from Exams 1 and 2. The best preparation for this problem is to carefully study correct solutions to these problems (either your solution, if it is marked correct or the solutions I have provided). This would be a good way to review older material.

• Problem 2. (50 points) On Dynamic Programming. Make sure you know to solve the problems in Homework 10. I will send out a solution on Monday, but it is important to be able to solve problems such as the ones in the homework on your own.

• Problem 3. (40 points) On Minimum Spanning Tree algorithms (Kruskal's algorithm and Prim's algorithm) and the Disjoint Set Union Find data structure used to efficiently implement Kruskal's algorithm.

• Problem 4. (50 points) On approximation algorithms, especially greedy ones, for Set Cover and problems in Homework 9 such as Bin Packing. For this problem, be prepared to construct counterexamples also.

• Problem 5. (20 points) On Search Problems, NP, polynomial-time reductions, NP-hard, and NP-complete. This will be a True/False or a Multiple Choice problem meant to test your understanding of these concepts.