AC
The re-exam will be oral.
There are 9 exam topics, which approximately correspond to the 13 lectures.
A: Greedy algorithms: general principles and an example algorithm.
Greedy algorithms do not always yield optimal solutions, but for many problems they do.
- _- What is the general structure of a greedy optimization algorithm?
-
Which two properties have to be proven to prove that a greedy algorithm finds an optimal solution?
-
What is the greedy-choice property?
-
What is the greedy choice in the Huffman algorithm? At each step, always select and merge the two nodes with the lowest frequencies.
-
A: Dynamic programming: general principles and an example algorithm.
Whenever a problem exhibits optimal substructure, we have a good clue that dynamic programming might apply
goals
- to understand the principles of dynamic programming;
- to understand the example dynamic programming algorithms for activity selection and edit distance;
- to be able to apply the dynamic programming algorithm design technique._
A: Network flow: definitions, Ford-Fulkerson method, and Edmonds-Karp algorithm.
A: External-memory algorithms: general principles and the multiway merge-sort algorithm.
A: Parallel algorithms: general principles and the parallel merge-sort algorithm.
A: Amortized analysis: general principles, different methods, and the analysis of the dynamic table.
C: Formal languages; deterministic, multi-tape, and nondeterministic Turing machines; Church-Turing thesis; halting problem and why it is not computable; closure properties.
C: Computable and computably-enumerable languages; (mapping) reductions and how to use them to prove computability properties about languages; example reduction between halting problem and acceptance problem; Rice’s theorem.
C: Classes P and NP; closure properties; “P vs. NP” problem; polynomial-time reductions and how to use them to prove complexity properties about languages; NP-hardness and NP-completeness. (Note that this list does not include the proof that SAT is NP-complete.)
First, you randomly select 2 (one A topic and one C topic) out of the exam topics. Then, you choose one topic as the primary topic and the other one as the secondary topic.
For the primary topic, you may give a 4-minute presentation to cover basic concepts (e.g., definitions) and general principles (e.g., algorithms) of the topic, and also a concrete example that explains how the general principles are used in the example. You are expected to have prepared for all the topics before the exam, and there will be no separate preparation time once a topic has been selected. The presentation will be supplemented by questions from the examiners (ca. another 4 minutes). The presentation will not have slides, but you are allowed to use the blackboard/whiteboard. As material for the presentation, you are allowed to have a sheet with notes (maximum 1 page per topic). It is recommended that you have a list of items that you want to talk about, but be aware to not only read from your notes.
Then, the examiners will ask questions from the secondary topic (another 6 minutes).
Note that both topics are weighted equally and that there will be more questions about the secondary topic. So make sure to prepare well for both parts of the course.
To prepare yourself for the re-exam, we suggest that you:
Prepare a presentation for each topic that uses a concrete example to explain both basic concepts (e.g., definitions) and general principles (e.g., algorithms). Rehearse all presentation topics before the exam.
Go through the lecture slides (some of the questions will relate to the basic concepts presented in the slides).
Go through the exercises (some of the questions will relate to how you would address some of those exercises).