CS:3330 Final Exam Announcement
The Final exam for CS:3330 "Algorithms" will be held on Dec 14th (Monday) from 7:30 am to 9:30 am
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.
This exam is over the following material from the text book:
- Section 4.4 (Shortest Paths in Graphs),
- Section 4.5 (The Minimum Spanning Tree Problem),
- Sections 5.1-5.5 (on Divide-and-Conquer Algorithms), and
- Sections 8.1-8.4 (on NP-completeness and Intractability).
In addition to the textbook, you should study
your lecture notes, and posted solutions to homeworks and exams. While the focus of the exam will
be on the topics mentioned above, you should also review older material such as asymptotic notation,
running-time analysis, and basic knowledge of data structures.
There will be 5 problems on the exam and here is some information on each problem.
- This problem is related to the SSSP problem and you'll have to appropriately
modify a shortest path algorithm to solve this efficiently.
- This problem describes a data structure and some operations on it and asks you
to show that the amortized running time of the operations is small. So you'll be
doing amortized analysis for this problem.
- This problem will contain a bunch of short answer questions on MST, MST algorithms,
SSSP, and Dijkstra's shortest path algorithm.
- This problem has two parts. In the first part, I give you a recursive function and
ask you to find its running time by setting up a recurrence and solving it.
In the second part, I suggest a divide-and-conquer approach to solving a problem and
you're asked to write pseudocode for this algorithm.
- This problem contains a bunch of short answer questions on the classes P, NP,
polynomial-time reductions, the class NP-hard, and the class NP-complete. You should be familiar
with decisions problems such as SAT, 3SAT, Min Vertex Cover, Max Ind Set, Subset Sum, etc.
You should also study the polynomial time reductions examples in the textbook that reduce
Min Vertex Cover to Max Ind Set (and vice versa) and 3SAT to Max Ind Set. You should also be
able to show that a given problem belongs to NP and you should be familiar with the overall
recipe of showing problems NP-complete.