Graph-Theoretic Algorithms Spring 2024 Exams

Home

Outline

Resources

Schedule

Summaries

Assignments

Project

Final

Final exam

Possible time slots

• Wednesday, July 10, 11:00am
• Wednesday, July 10, 1pm (This slot has been taken)
• Wednesday, July 10, 2pm
• Wednesday, July 10, 3pm
• Friday, July 12, 11:00am
• Friday, July 12, 1pm
• Friday, July 12, 2pm
• Friday, July 12, 3pm
• Monday, July 15, 11:00am (This slot has been taken)
• Monday, July 15, 1pm (This slot has been taken)
• Monday, July 15, 3pm (This slot has been taken)

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 typically start with questions about something you likely did already, such as about your project and/or assignment-questions you did not answer previously.
• I will follow up on your answers with questions on related course content. Some typical questions:
  • What is the definition of graph class C? problem P? graph-parameter w?
  • How can you solve problem P on graphs in C?
  • How easy is it to test whether a graph is in C? Or to compute parameter w?
  • Why did we define parameter w? What is it useful for?
• 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.
• Realize that I'm not your enemy; I only want to know whether you've understood the ideas of the course.
• You are specifically 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 very 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. However, I may occasionally slow you down and ask for details.
• 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.