MTH6105 Algorithmic Graph Theory
Frequently Asked Questions
These are some questions which you have emailed me about. If you
don't find any answer to your question then email me and I will add your
question to the list below — if you want to know then probably others
Back to MTH6105 Main Page
- Do I need to be able to read or write pseudocode for the exam?
- NO! Pseudocode was the method we used to specify exactly how each
algorithm worked. You DO need to know how the algorithms work on a given
input graph and you may find the the pseudocode helps you with the
details while revising.
- Do I need to remember how to prove the correctness of the algorithms?
- NO! There will be 2 or 3 proof questions on the exam but they will
concern small questions of graph theory and they will be 'unseen'.
- Do I need to be able to analyse the complexity of the algorithms?
- NO! But you do need to understand what, say O(n^2) means. You may be
asked to explain why a particular bit of a given algorithm has
complexity O(n^2) or O(n) or O(|E|).
- Should I be revising all the questions from all the courseworks?
- On each coursework Question 1 is a proof question and it will
certainly improve your chances for these parts of the exam if you read
and understand the solutions. Better still, try them first! (Some are
harder than you will see on the exam, but you should be able to have a
go at any of them given a bit of time). The 'For Credit' question on
each coursework concerns running one of the main algorithms on an input
graph. So these correspond to the main mark-winners on the exam
(although the graphs will be a bit smaller in the exam).
- Should I be reading the 'Keevash notes'?
- I tried to cover everything you need in the exam and the summary
notes on the website. However, if you are aiming high then you should be
reading as much supplementary material as possible. This includes the
web links which I gave on each weekly web page. Obviously the Keevash
notes are the most relevant supplementary material since the module is
based on them.
- I took detailed notes during lectures, so are my notes all I need?
- You should certainly cross-check your notes against the ones I
posted on the website — occasionally I corrected mistakes or thought of a
better example than one I went through in class.
- Do I need to know everything in the on-line notes?
- NO! I quite often added things for background information, or I
meant to cover them in lectures but didn't have time — in which case I
won't have put them in the exam.
- Can I choose whether to show the steps of Dijkstra's algorithm and Prim's algorithm using a table or a series of graphs?
- YES! The questions will specifically say you can use either. A table
is quicker but the graphical approach makes it easier to see what is
going on - choose which is best for you.