DM582 - Advanced Algorithms
 
Spring 2025
Kim Skak Larsen

Home

Exam
There are two types of exam elements in this course: 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 5, 2025
12:30 Arrive at the lecture room no later than this time Topics from lectures 3/2, 6/2, 10/2, 18/2:

Network Flows: Ford-Fulkerson, Edmonds-Karp. Discrete Probability Theory. Randomized Algorithms: Contention Resolution.

12:45 Test starts
13:45 Test ends
Multiple-Choice Test 2: March 31, 2025
12:30 Arrive at the lecture room no later than this time Topics from lectures 18/2, 19/2, 25/2, 4/3:

Randomized Algorithms: Contention Resolution, Global Minimum Cut, Waiting Times, MAX 3-SAT Approximation, Randomized Quicksort and Selection. Amortized Analysis.

12:45 Test starts
13:45 Test ends
Multiple-Choice Test 3: May 5, 2025
12:30 Arrive at the lecture room no later than this time Topics from lectures 11/3, 19/3, 24/3, 2/4, 7/4:

Universal and Perfect Hashing. String Matching: Rabin-Karp, Finite Automata, Knuth-Morris-Pratt. Online Algorithms. Deterministic Selection.

12:45 Test starts
13:45 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 the 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 is scheduled to take place June 24-27, 2025. We may end up only using three of those days. More information will follow later regarding sequence and room allocation.

Procedure

The examination form is oral exam with preparation. When it is your turn for examination, you will draw a question.[1] The list of questions can be found below. Then you will be placed alone in a preparation room. You will have approximately 25-30 minutes of preparation time and you are allowed to use any material that you are bringing yourself, excluding communication devices and 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.

After the preparation time, the actual exam takes place. This part also lasts approximately 25-30 minutes. You should start by presenting material related to the question you drew. Aim for a reasonably high pace and focus on the most interesting material related to the question. You may bring a short list of keywords for the actual exam to remember what you have decided to present. Thus, you are not supposed to use note material, textbooks, transparencies, computer, etc. for this part.

We, the examiner and the censor, will supplement with specific questions when appropriate, and after a while, we will end the discussion of the exam question that you drew and turn to material from other parts of the curriculum. Note that all of this as well as discussions between examiner and censor about the grade is included in the 25-30 minutes, so you have about 12-13 minutes for your own presentation.

Most of the questions below cover a whole lecture or more, so you will have to choose what to cover. You will of course also be evaluated based on your selection of material. If you only present the simplest material, you limit the grade you can obtain. On the other hand, a good presentation of the simple material is better than a poor presentation of the harder material. For most questions, it is natural to first sketch the algorithm or data structure and then present essential elements of the analysis. In most cases, a complete treatment of the analysis is the harder part of the question, but will therefore also enable you to demonstrate the best understanding of the material. Notice that some chapters in the textbook start with some motivating example. Don't spend too much (or any) time on those. It is the core algorithms and data structures we would like to hear about.

Further Advice for an Oral Exam

Curriculum

The following summarizes the lecture material.

Questions

The below is the list of questions you draw from at the exam.
  1. The Ford-Fulkerson Method and the Max-Flow Min-Cut Theorem
  2. The Edmonds-Karp Algorithm
  3. The Contraction Algorithm for Global Minimum Cut / Randomized Approximation of MAX 3-SAT
  4. Randomized Quicksort
  5. Amortized Analysis: The Potential Method with Examples
  6. Perfect Hashing
  7. String Matching
  8. Online Algorithms: The \( k \)-Server Problem
  9. Selection in Expected Linear Time / Selection in Worst-Case Linear Time
  10. Lower Bounds: Adversary Argument Examples
In the questions above, the notation "A / B" means that if you draw that question, you can decide if you tell us about A or B; you're not expected to do both. It's probably clear from all the information above, but just to emphasize, note that for side questions later in the examination, you cannot choose. After you're done presenting some question, not necessarily having anything to do with A / B, I am not going to ask you to tell me about A / B and let you choose. So, you may have prepared A for the eventually that you would draw the A / B question, but I might ask you about B; or rather, I will probably ask you about some concrete part of the topic B.

Textbook material available during the examination

If we don't experience technical problems, the following material from the textbooks can be shown on the projector during the oral exam.
  1. ^ Just to avoid confusion: Danes normally refer to the topics you can draw at an oral exam as questions, so I use that terminology as well, but they are really topics. You are not asked a question (in what you draw), but given a topic you should tell us about.

 


   Data protection at SDUDatabeskyttelse på SDU