Graph-Theoretic Algorithms Spring 2024 Exams

Home

Outline

Resources

Schedule

Summaries

Assignments

Project

Final

Final exam

Possible time slots

Technicalities

• The exam should take approximately 30-45 minutes. (I am scheduling 60 minute slots to have a short break inbetween.)
• No notes are allowed.
• During the exam, I will provide pencils and paper. You should use these liberally to explain your answers. This is (a) because a picture says more than a thousand words and (b) st so that I have a bit of a record what we covered, in case I want to compare your performance with that of other students. I might also scribble on the paper; please ignore this (this is for my own records of what we talked about.)

Contents

• I will start with assignment-questions, either from our assignments or from the lecture notes (especially the R-questions).
• I will follow up on your answers with questions on related course content. Some typical questions:
  • What is the definition of graph class C?
  • What is the definition of problem P?
  • How can you solve problem P on graphs in C?
  • How easy is it to test whether a graph is in C?
  • What else do you know about C? What problems are easy, which ones are not?
  • How are graph classes C1 and C2 related?
  • Give me a graph that is in C1 but not in C2.
• For the harder proofs and algorithms covered in class: Have an idea of how one would prove/do such a thing, but you don't need to know all the details.
• Everything that was done in class is subject to questioning. This includes projects that were presented within the regular class time (up to June 28).
• The lecture notes cover much material that we didn't see in class. You don't need to study this for the exam (though of course you're welcome to read it anyway and get a few brownie points.)

Hints

• The most important part is to get the overall picture of what was going on in class. Go through the course material again, and at each step, ask yourself "Why did we do this?"
• I recommend to draw a diagram with the different graph classes, indicating somehow who is a sub/super-class and where there are no relationships.
• The course notes have lots of potential assignment questions, not all of which were used. I would expect everyone to be able to do all the "R" questions (for which the relevant material was covered in class).
• Realize that I'm not your enemy; I only want to know whether you've understood the ideas of the course.
• In particular, you are allowed to ask questions during the exam. So if your mind blocks some definition during the exam, do not panic. Just admit to it, and I'll help you along.
• Precise notation is not important, ideas are. A lot of definitions can easily be done in pictures, and you are allowed (in fact, invited) to do so during the exam.
• Be prepared to say "I don't know the answer to this" at some point during the exam. This is perfectly acceptable, as long as it is rare. It is much better to admit to not knowing something (so that we have time to move to another topic where hopefully you'll do better) than to waste time stumbling along trying to piece it together.
• In fact, almost expect to say "I don't know the answer to this" at some point. I will adapt the questions I ask you to the answers you give me; the more good answers, the harder the questions (and the better the grade, obviously).
• You can volunteer knowledge. If you know more about a topic than what I ask, mention what you know, and with any luck I'll go into that direction next.
• I'll likely request to know your favorite part of the course and ask some questions from there. Know which part of the course you're best prepared for.

Grade determination

Thus, if you did all assignments perfectly, then the final exam is worth 40% of your grade. On the other hand, if you do no assignment at all then the final is worth 60% of your grade.