|
|
Graph-Theoretic Algorithms
Spring 2017
Exams
| 
|
Final exam
Final exams are individually scheduled oral exams.
Possible time slots
Here are possible slots. Email me a list of 5 slots that would work
for you; I will let you know which one you're scheduled into.
- Monday, July 17, 9-10am
- Monday, July 17, 10-11am
(This slot has been taken)
- Monday, July 17, 11-12noon
- Monday, July 17, 3-4pm
- Monday, July 17, 4-5pm
- Thursday, Aug 3, 9-10am
- Thursday, Aug 3, 10-11am
(This slot has been taken)
- Thursday, Aug 3, 12-1pm
(This slot has been taken)
- Thursday, Aug 3, 1-2pm
(This slot has been taken)
- Thursday, Aug 3, 3-4pm
(This slot has been taken)
- Thursday, Aug 3, 4-5pm
(This slot has been taken)
- Friday, Aug 4, 9-10am
(This slot has been taken)
- Friday, Aug 4, 10-11am
(This slot has been taken)
- Friday, Aug 4, 1-2pm
(This slot has been taken)
- Friday, Aug 4, 3-4pm
(This slot has been taken)
- Friday, Aug 4, 4-5pm
(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 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.
- 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
The weight of the final exam is 70% -A where
A is the credit (out of a maximum of 30%) that you got for assignments.
If you attempt an assignment, but did not get the right answer,
the credit for it automatically transfers to the final.
Thus, if you did all assignments perfectly, then the final exam
is worth only 40% of your grade. On the other hand, if you do no assignment
at all then the final is worth 70% of your grade.
