Exam information
Everything below might be subject to changes coming down from the department, school, faculty or university level — if any of it does change, though, you’ll hear about it from either them or me or (more likely) both.
Format and rules.
• Theexamwillbeworth90%ofyourunitmark,withtheremaining10%comingfromtheBlackboard quizzes you’ve been doing all term. See video 1-1 for details of how the quiz marks will be calculated.
• Theexamwillberunindownload/uploadformat—youwillbegivenaccesstoacopyofthePDFata fixed start time (most likely in the morning), and you will need to write, scan and upload your answers in a reasonable format before a fixed end time. The details of the download and upload points are still being sorted out, and you should get some more general communication from the department when they have been. I don’t know for sure yet, but I would expect that uploads in PDF format, text format, or compressed .jpeg or .png format will all be fine. (No 50MB images or .heic files, please!)
• Before starting the exam, you should plan how you’re going to upload your answers, including the ability to scan pictures (e.g. with a flatbed scanner or phone camera) so that you can easily draw diagrams where appropriate. You should also make sure you have a way to easily move a picture from a PDF into a form which you can draw on for rough working. This could be a physical printer, or a PDF reader with an annotation feature, or just a way of copying part of your screen to the clipboard (such as Windows+Shift+S on Windows or Shift-Command-3 on Mac) and a simple graphics program (such as Paint on Windows or Preview on Mac). This will save you a lot of time that would otherwise be spent copying graphs onto bits of paper by hand.
• Theexamwillbetwohourslong,withhalfanhouradditionaluploadtime.Thisisnotthesameas“two hours and twenty-five minutes to work on the exam followed by five minutes’ upload time”, and as far as I know the department is planning to be very strict about this — if you finish uploading your paper two hours and thirty-one minutes after the start time, then it will count as though you missed the exam entirely.
• Youareallowedtoconsultallmaterialsmadeavailableontheunitpageandanynotesyouhavetaken yourself. You are not allowed to consult any other materials, including textbooks and other online sources. (The questions will be written in such a way that other sources won’t help anyway…)
• You are not allowed to work together with others, whether they are taking the unit or not. I will be checking the answers for signs of collaboration, and I will deal with it harshly.
• You can use any calculator you like, although you probably won’t need to.
• Theexamwillbedividedintotwosections.
– Thefirstsectionwillcontainshort-answerquestionsworthatotalof75marks,inasimilarformat
to the Blackboard quizzes. For these questions, you won’t need to show any working, and any working you do show won’t be taken into account — you’ll just need to choose an option, fill in blanks, write down a number, or give some similarly short answer. If you do show working, it’s important that you circle your final answer or otherwise make it very clear what it is.
– The second section will contain long-answer questions worth a total of 75 marks, in a similar format to the problem sheets. For these questions, you should show your working as you will be able to get partial credit even for an incorrect answer.
• Notallthequestionswillbeofequaldifficulty.Isubscribetotheideathataunitmarkof40shouldbe attainable by everyone in the class who’s willing to put effort in, a mark of 70 should show genuinely impressive understanding of the material, and a mark of 90 or more should be a huge achievement that comes round once per year or less. This means the questions will start out relatively easy, to make sure it’s not too hard to get a decent mark, and then get progressively harder, to make sure it’s not too easy
to get a high mark. To help you plan your time, each question (and each part of multi-part questions) will be tagged “short”, “medium” or “long”. In total, 80 marks will be available from short questions, 50 marks will be available from medium questions, and 20 marks will be available from long questions, for a total of 150.
– Short questions will correspond to the easier, non-proof-based questions rated [⋆⋆] on the quizzes and example sheets.
– Mediumquestionswillcorrespondtoanyquestionsrated[⋆⋆]onthequizzesandexamplesheets, or to the easier [⋆⋆⋆] questions. Some of them will require you to prove results or come up with new algorithms, and some of them will be similar to “short” questions but be more involved and require more effort for the same amount of marks.
– Longquestionswillcorrespondtoquestionsrated[⋆⋆⋆]and[⋆⋆⋆⋆]onthequizzesandexample sheets. They are intended to push the best students, and you should not attempt them unless you have already tried all the short and medium questions.
• Your grades will never be curved downwards — for example, an overall unit mark of 70% will always be a First, even if everyone does extremely well. If everyone struggles with the exam and the overall mark is very low, then I might curve your grades upwards, so that (for example) the threshold for a First is less than 70%.
Practice questions.
• I’ve made a mock exam available on the unit page, as well as the two past papers from last year (the original exam and the resit). All three papers have detailed answers available. I very strongly recommend you try some or all of these, because this is the best way to get a sense for the overall difficulty level and for what sort of questions I’m likely to ask. The exam format has changed slightly, but the content and question style are exactly the same. (In particular, that year the exams were presented in a random order with no backtracking allowed, and people were given half an hour of extra time and the questions were divided slightly differently between sections to compensate for this.)
• Towards the end of term, I’ll be making new copies of the Blackboard quizzes which you can take as often as you like for revision purposes, to help you practice for short and medium questions.
• Theproblemsheetquestionsyoudidn’tgothroughintheexampleclassareagreatsourceofpractice for medium and long questions.
• The exercises given in the relevant chapters of the unit’s recommended textbooks (see the “Resource lists” section of the unit page) are great for short, medium and long questions: Cormen, Leiserson, Rivest and Stein; Erickson; Kleinberg and Tardos; and Skiena.
• I’mnotmakingpastpapersfrompreviousyearsavailable,becausetheunithaschangedahugeamount since then. In 2019–20, the unit was 20cp instead of 10cp, taught quite different material, and the exam was in-person and did not allow access to notes. You can probably get copies from the Bristol library, but I wouldn’t bother if I were you — I already repurposed the most useful stuff for the mock exam anyway, and they won’t come with detailed answers.
Examinability.
• Except where specified below, all material appearing in lectures, on Blackboard quizzes, and in the question statements of the problem sheets is examinable.
• The general techniques taught in the unit — for example, how to prove that a problem is NP-hard, or how to find a counterexample to a proposed greedy algorithm — are all examinable, and you may be asked to apply them in unfamiliar situations (particularly for medium and long questions).
• You will not be asked about material linked on the unit page under the resource list — these are just intended as alternative sources if you’re having trouble understanding the lectures or if you’d like more detail on something.
• You will not be asked about the answers to questions in the problem sheets. (For example, I wouldn’t ask you a question about the greedy algorithm for the search problem given as question 2 of sheet 2, but I might ask you to come up with an exchange argument or a greedy-stays-ahead argument for another problem, or for you to remember that the search problem has a fast algorithm.) • You will not be asked about anything specifically flagged as non-examinable in lectures.
• You will not be asked to prove any result stated but not proved in the lecture slides. You will still be expected to know the statement. For example, you won’t be expected to know how to prove the worst- case running time of the Edmonds-Karp algorithm, but you will be expected to know what that running time is.
• You will not be asked about any material which was covered verbally, but not on the lecture slides or in the Blackboard quizzes. The verbal asides are intended to help you understand things, not to be examinable in and of themselves.
• Youwillnotbeaskedaboutanythingspecifictothewayinwhichthematerialispresented.Forexample, you will not be asked to state “Lemma 1 of Lecture 23”, but you may be asked a question which requires you to know that statement. If a result has a standard name, as in the case of e.g. Dirac’s theorem or the Cook-Levin theorem, then you may also be required to know that name.
• You will not be asked about any of the jokes, historical asides, or industrial applications covered in lectures.
Strategy tips.
• Remember that the exam will count for 90% of the unit marks, and the Blackboard quizzes will count for 10%. So if you have half-marks or more in every quiz (which counts as full marks), then you need 45% in the exam for a II.ii, 56% for a II.i, and 67% for a First. Every little helps!
• Even though you will have access to your notes in the exam, it’s very important that you learn them anyway! Even aside from the fact that checking your notes takes time, there will be questions which ask you to apply something you’ve learned in the unit without telling you exactly what you need to apply. You will find these questions much easier if you know the relevant facts already rather than having to reread the lecture notes for the entire unit to find the relevant piece of information. The more of the material you know off the top of your head, the better you will do.
• Ifyouhavebeenstrugglingwiththeunitandhavelimitedtimetorevise,youshouldtrytogetashallow understanding of the entire unit rather than a deep understanding of one or two areas. Being able to answer almost all the short questions and some of the medium questions is a perfectly viable path to a II.i. By contrast, being able to answer almost all the short, medium and long questions on half of the unit but not being able to answer anything on the other half will lead to a II.ii or worse while taking much more work to achieve. There is also no guarantee that any particular topic will come up in the exam.
• If I ask you to prove something on the exam, the standard of rigour I’ll be looking for is: Would this convince your boss that the statement is true? In other words, I know (most of) you aren’t mathematicians, so I’m not testing your ability to write rigorous symbol-heavy proofs like a mathematician would. (Even though I tend to write proofs that way myself in e.g. the problem sheet answers…) I’m testing your ability to see why something has to be true, and to communicate that argument clearly enough to be understood by others and to convince others. If you’ve done that, then you’ll get full marks on the question.