MTH6105 Algorithmic Graph Theory

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 do too!

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.
Back to MTH6105 Main Page