There are two types of exam elements in this course:

• multiple choice tests, and
• an oral exam.

You get one combined grade based on the two parts. The oral exam has heighest weight.

Multiple-Choice Tests

Read through this entire section many days in advance of the first test.

Test Times

The below are the expected test times and content. If there are cancelations of lectures or exercises before a test date due to illness or other unforseen events, tests may have to be postponed to make sure that the test topics have been covered properly before the date.

Multiple-Choice Test 1: March 2, 2026
10:15	Arrive at U44 no later than this time	Topics from lectures 2/2, 4/2, 16/2, 18/2: Network Flows: Ford-Fulkerson, Edmonds-Karp. Discrete Probability Theory. Randomized Algorithms: Contention Resolution.
10:20	Test starts
11:20	Test ends
Multiple-Choice Test 2: April 7, 2026
10:15	Arrive at U44 no later than this time	Topics from lectures 18/2, 23/2, 4/3, 9/3: Randomized Algorithms: Contention Resolution, Global Minimum Cut, Waiting Times, MAX 3-SAT Approximation, Randomized Quicksort and Selection. Amortized Analysis.
10:20	Test starts
11:20	Test ends
Multiple-Choice Test 3: May 4, 2026
10:15	Arrive at U44 no later than this time	Topics from lectures 16/3, 23/3, 8/4, 13/4, 20/4: Universal and Perfect Hashing. String Matching: Rabin-Karp, Finite Automata, Knuth-Morris-Pratt. Online Algorithms. Deterministic Selection.
10:20	Test starts
11:20	Test ends

Purpose

Having the multiple-choice tests in the course is a supplement to the oral exam; they are not testing the same things. Whereas the oral exam is primarily about being able to explain algorithms and prove complete results about them - similar to what I do in the lectures, the multiple-choice tests are more about being able to apply algorithms and being able to point to central proof techniques or key elements in the proofs. Thus, to a larger extent, they test the work you do in the exercise classes. If you have been doing the exercises, you are probably well prepared for these tests. But even if you do well in these tests, you are not necessarily well prepared for the oral exam, since the focus is quite different. So even if you do well, study hard for the oral exam as well!

Scheduling

There will be multiple exams throughout the course. The plan is to conduct these using the extra lectures that have been scheduled every second week whenever possible and announce these events more than a week in advance. Thus, the tests are conducted in-class and you have to show up for that class at SDU to take the test.

Format and Expectations

No guarantees, but the plan is to have tests with approximately 10 questions, each of which are multiple-choice with four possible answers of which one is the correct one. The plan is to allow 45-60 minutes for the test. This allows you plenty of time for answering, sometimes after minor computation, provided you are up-to-date on the material and the exercises. Naturally, there is not time for learning the material, if you have not followed the course closely enough.

Equipment and Aids

You need your laptop for connecting to Itslearning and taking the exam. It's your own responsibility that your laptop, your connection to wifi, your browser, etc. works and that you can log in to Itslearning and is a participant in the course. Check beforehand - there's no IT help available! Other than accessing Itslearning, you're not allowed to use the Internet. You may use all other aids (books, notes, programs, etc.), except so-called AI tools which include generative transformers such as ChatGPT and many others; SDU does not allow you to use such aids for exams. I suggest you have pen and paper available for small computations you may want to make along the way.

On the Day

Show up at least 15 minutes before test start so I have time to check your student ID (remember to bring it) and set up. As a courtesy to the other students, do not leave the exam until the end, so you don't disturb your fellow students who want to use all their available time.

Scoring

In this course, we use a more fair multi-choice grading algorithm than you may have seen before, focusing on giving you the best chances of communicating the knowledge you have.

Before beginning the explanation, I want to emphasize that all the question are multiple-choice questions, i.e., there is one correct answer and you receive maximum points only if you select that answer and no other answer.

However, if, for instance, you can rule out two out of four answers, you may select the two answers you think contain the correct answer. If you're right, you will receive a positive score, though of course not the maximum score. Thus, you will be able to get credit for partial knowledge.

Another fairness decision in the grading is that there is no cap at zero, which you may have seen in other courses. Thus, you can get negative points for a question. The fairness considerations behind this decision is that the expected value of guessing should be zero.

Below, you can see the scoring table for a question with four possible answers out of which exactly one is correct. You select a number of answers between zero and four, and either you capture the correct answer or you don't. From those two pieces of information, you can see the score in the table, where numbers are rounded to three decimals.

Captured correct answer	Number of selected answers
	0	1	2	3	4
yes	NA	1	0.5	0.208	0
no	0	−0.333	−0.5	−0.623	NA

Disclaimer

I'm forced to use Itslearning for these tests. It has very limited built-in scoring options and may insist on telling you what it thinks your score is. However, after the exam, I can download an Excel sheet with all the test details, i.e., for each student and each question, I can see exactly which entries were selected. Based on that, I will calculate the correct score using the table above. Thus, if Itslearning gives you a score, it's likely incorrect, but it will probably correctly inform you as to which questions you got right.

Oral Exam

The regular exam takes place Monday-Thursday, June 22-25, 2026 (pending approval by the study board). We may end up using only three of those days.

More information will follow later regarding dates, sequence, and room allocation.

Disclaimer: The below is an early draft of a description of the oral exam procedure. It may be revised, questions, curriculum, and other information will be added and/or updated, and further details will be given in a late lecture and exercise session.

Procedure

The examination form is oral exam without preparation time. A list of questions^[1] you might be asked can be found below.

The exam lasts approximately 20 minutes. You'll be in front of the blackboard and you can use that. You will be asked several questions in a variety of topics. You are supposed to answer as directly as possible.

For example, if I ask you to explain why the value of any flow is bounded by the capacity of any cut, you should not start to define network flows, cuts, etc. Instead, you should start directly on the argument. If you need some property of network flows during the argument, it's of course appropriate to use that as a justification for a step in the argumentation, but we don't want to hear the full definition of network flows before we start on the argument.

Thus, the set-up is aimed for a reasonably high pace and focus, so we can discuss several topics. We, the examiner and the censor, will supplement with specific questions when appropriate.

At the end of the course, there will be lots of example questions below and we don't expect photographic memorization of all details and notation. The focus is on understanding and the ability to explain why results hold.

Our selection of questions is online and will depend on how you've handled earlier questions. To illustrate this, in the extreme cases, if you handled one of the easier questions very convincingly, we may proceed with a harder one, and if that also goes well, we'll probably continue with only harder questions to see if the grade should be 10 or 12. On the other hand, if things did not start out well, we may at some point just try for easier questions to see if the grade should be 00, 02, or 4.

Further Advice for an Oral Exam

• You may choose to carry out the exam in Danish or English. This is primarily for the benefit of exchange students or other students with limited Danish skills. However, I see more and more Danish students who choose to use English. I think it's because they think they are pretty good at English and think it's a problem that they don't know all the Danish words for concepts in the curriculum because the course was taught in English. I understand that reasoning, but my experience is that it's not to the students' advantage. It would be better for almost all Danish students to keep it in Danish and then just use the English word for concepts where they don't know the Danish term. There will be no punishment for such mixed Danish/English performances.
• The following is mostly relevant for the more involved harder questions. You have little time compared with a lecture, so speed is important. Don't try to imitate my calm speed when I lecture. I spend time setting the scene, mentioning topics from earlier courses and applications, and I go through the material slowly because you haven't seen it before. When you cover a topic, go through arguments much faster than I do in a lecture. Of course, there are limits; we should be able to understand what you are saying. Don't use the blackboard for sentences (and mostly not for text in general); use it for illustrations, formulas, and deductions.
• On the same note, don't stall. Some students behave like they think they enter with a 12 and then just want to drag out the time, so they don't say anything wrong. That's not how it works. You enter with nothing. Whenever you convince us that there is something non-trivial you can do correctly, your grade increases. If you stall or make wild guesses to questions where you don't know the answer, the time you spent on that comes out of the time you have to explain something correctly. Of course it reflects negatively on you if there are topics where you don't know the material. However, then it's all the more important to move on and demonstrate that you know other parts of the curriculum.
• You cannot use notes during the examination. We cannot give credit for something you read from a piece of paper that someone/something has prepared. Again, we're not big fans of memorization, but there is simply not time for obtaining enough information for giving a grade if we have to discard statements that you've just read from a piece of paper. On the positive side, we're very forgiving wrt. notation, names of things, etc. We're only interested in the understanding. We realize of course that you have to remember something in order to convey your understanding, but it's much easier to remember how an algorithm that you have understood works or what a proof you have understood depends on than it is to remember concrete notation. For example, we're not interested in whether you can write up a sequence of inequalities as they appear in the book. We are interested in why each inequality holds. And that can often be explained, even if the notation is not perfect, and sometimes even without writing the inequality up.
• Try not to panic. I will of course check to see if there are parts of the curriculum you don't know, but many of my questions are meant as a help. If you say something incorrect or unclear, but I think you know it, then I may ask a question so you get a chance to correct or clarify. If you get stuck, I will try to ask a question or give you a hint that will enable you to proceed. So, listen to my questions and be cooperative. I really want you to pass!

Curriculum

• All written material on the literature page at the end of the course, including the books and lecture slides. For the books, you are of course only responsible for the sections that have been announced via the lectures and exercises page at the end of the course.
• All the exercises posed via the lectures and exercises page at the end of the course.

The following summarizes the lecture material.

TBA

Questions

★ marks questions in the harder category.

1. Network Flows.
1. Define the maximum flow problem.
2. Formulate the Max-Flow Min-Cut Theorem and explain the concepts in the formulation.
3. Explain why the value of any flow is bounded by the capacity of any cut.
4. Explain the complexity of the Ford-Fulkerson algorithm in network flows with integer weights.
5. Prove the Max-Flow Min-Cut Theorem. ★


2. Network Flows: Edmonds-Karp and Examples.
1. Without proof, explain Edmonds-Karp's algorithm and its complexity.
2. Prove that when one makes an augmentation in a flow network, then the length of a shortest path to any vertex cannot decrease. ★
3. Assuming the above, prove that Edmonds-Karp's algorithm terminates after \( O(VE) \) augmentations. ★
4. Discuss how network flow algorithms can be used to find a maximum bipartite matching.


3. Randomized Algorithms: Contention Resolution, Global Minimum Cut.
1. Prove that the Contraction Algorithm finds a global min-cut with probability at least \( \frac{1}{\binom{n}{2}} \). ★
2. Explain the Probabilistic Method using Global Minimum Cut as an example.


4. Randomized Algorithms: Waiting Times, MAX 3-SAT Approximation.
1. Prove what the expected waiting time is for collecting \( n \) coupons.
2. Explain how we can know that if there are at most 7 clauses in a MAX 3-SAT problem, then there must exist a satisfying assignment.
3. When assignments are chosen uniformly at random, prove what the expected waiting time is for obtaining an assignment for a MAX 3-SAT problem with \( k \) clauses such that at least \( \frac{7}{8}k \) clauses are satisfied. ★


5. Randomized Quicksort and Selection.
1. Prove that the probability that Randomized Quicksort compares the \( i \)th and the \( j \)th smallest elements is \( \frac{1}{j-i+1} \).
2. Assuming the above, prove that Randomized Quicksort runs in \( O(n \log n) \). ★
3. For Randomized Selection, prove that a partioning is helpful with probability at least \( \frac{1}{2} \).
4. Assuming the above, prove that Randomized Selection has running time \( O(n) \). ★

---

1. ^ Just to avoid confusion: Danes normally refer to discussion points that you can encounter at an oral exam as questions, so I use that terminology as well. But you are not really asked a question; you're are given a topic or (polite) order of something you should tell us about.

 

---