|
|
Graph-Theoretic Algorithms
Spring 2020
Exams
| 
|
Final exam
Final exams are individually scheduled oral exams.
By default these will be held during an online meeting
(using an online whiteboard), and at a mutually agreed-upon
time. This should typically in the final assessment week (Aug 7-15),
but other dates may be possible.
Should UW have re-opened by August so that limited contact
is permitted, then I would much prefer to hold final exams
in my office. To be discussed.
Technicalities
- The exam should take approximately 30-45 minutes.
- No notes are allowed.
- During the exam, you should use the (online) whiteboard to explain
your answers, mostly in pictures. 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 notes on the board; 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 related review-questions that I will post beforehand.
- 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.
- 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.
- 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
The weight of the final exam is 60% - Q - A where
Q and A are the credit (out of a maximum of 9% resp. 27%) that you got for
the exercises and assignments.
Thus, if you did all quizzes and assignments perfectly, then the final exam
is worth only 24% of your grade. On the other hand, if you do not do them
at all then the final is worth 60% of your grade.
