Table of contents
  1. Blackboard quizzes
  2. Exam
    1. Format and rules
    2. Practice questions
    3. Examinability
    4. Strategy tips

Your unit mark will be split into two parts. 10% will come from Blackboard quizzes, which are called “in-class tests” on eVision but are neither in-class nor tests. The remaining 90% will come from an exam in January.

Blackboard quizzes

  • There are 10 quizzes in total, one per week, and they are equally weighted (so each quiz counts for 10% of your “in-class tests” mark and 1% of your unit mark).
  • Quizzes are always due at midday on Friday in the week of release. The university standard late penalties will apply.
  • The quizzes are not tests. There is no time limit, you can leave the page and come back, you can (and should!) work on quizzes together with your friends, and you are free to use any online or offline resources you want.
  • If your raw mark on a quiz is greater than 50%, then it will be set to 100% in the final grade calculation. Otherwise, it will remain unchanged. For example, a student who gets 55% in nine quizzes and 45% in one quiz will get a total mark of 94.5%.
  • The intention is that thanks to the “rounding” above, almost everyone will get full marks on almost every quiz. They are explicitly intended not to gauge your ability, but to nudge you into keeping up with the unit.
  • Immediately after you’ve submitted your quiz, you can (and should!) check to see exactly what you got wrong and why.
  • The quizzes are hosted on Blackboard. They are linked from the table in the main hub, or you can see them all here.
  • There is a dummy quiz available here which is worth no credit, is completely optional, and has no educational value. Take it if you want to make sure that Blackboard quizzes work well on your browser.

Exam

The information below is now final.

Format and rules

  • The exam will be in-person and on-paper.

  • The exam will be two hours long.

  • The exam will be open-note. This means you will be allowed to bring four pages of handwritten or printed A4 notes with you to the exam room - these can be double-sided. You will not be allowed to access the unit lecture notes or any other resources, and you will not be allowed to work with others.

  • Non-programmable calculators are allowed, although you probably won’t need one. Programmable calculators are not allowed.

  • The exam will be divided into two sections.
    • The first section will contain short-answer questions worth a total of 75 marks, in a similar format 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.

  • Not all the questions will be of equal difficulty. I subscribe to the idea that a unit mark of 40 should be 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 pass, and then get progressively harder, to make sure it’s not too easy to get a high mark. In particular, you are not expected to finish the exam, and it’s worth taking a little extra time to make sure you haven’t thrown away marks with a silly mistake on the easier questions.

  • Roughly 70-75 out of 150 marks will be available from questions similar to those rated [*] or the easier questions rated [**] on the quizzes and example sheets. They might ask you to remember a fact from lectures, apply a definition, or carry out a simple algorithm like interval scheduling.
  • Roughly 60-65 out of 150 marks will be available from questions similar to the harder questions rated [**] and the easier questions rated [***] on the quizzes and example sheets. Of these, 30-35 marks will be from compulsory questions, and 30 marks will be from a “choose two from four” question set calibrated to be of roughly equal difficulty, but to test different algorithm design skills. Some of them will require you to prove results or come up with new algorithms, and some of them will require you to carry out more involved algorithms like Ford-Fulkerson.

  • 15 out of 150 marks will be available from questions similar to the harder questions rated [***] and those rated [****] on the quizzes and example sheets. They are intended to push the very best students, and you should not attempt them unless you have already tried all the other questions. This will be the last question on the paper, which will ask you to choose one of three parts to attempt.

  • Information about mark moderation is TBD for now. I won’t “curve” marks under any circumstances, but I may moderate them upwards if faculty rules permit. (The difference is one of motivation - curving marks is a matter of forcing everyone’s marks to fit a pre-set distribution no matter how good they are, while moderation comes from comparing the scripts near the grade boundary to the intended learning outcomes of the unit and making a principled decision on whether the exam was too hard.)

Practice questions

  • The syllabus will be the same as in previous years, but the exam format has changed. As such, I’ve combined the more useful parts of past papers into practice papers:
  • Note that I’ve written the answers to these papers quite mathematically to minimise the chance of misunderstandings. You do not need to write your own answers this way. For something like e.g. a reduction question, you’ll get full marks if a) I can tell what your reduction is, b) it’s a valid reduction, and c) it’s clear from what you’ve written that you understand why it works, with most of the marks going to a) and b).
  • New copies of the Blackboard quizzes are available here - you can take these as often as you like for revision purposes.
  • The problem sheet questions we didn’t go through in the example class are a great source of practice for the harder questions on the paper.
  • The exercises given in the relevant chapters of the unit’s recommended textbooks (see here) are great practice for questions of all difficulties.

Examinability

  • All material appearing in video lectures and on Blackboard quizzes is examinable, with the following exceptions:
    • If a result is stated in lectures but not proved, then the proof is non-examinable. 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.
    • Anything stated verbally in a lecture but not written on the slides is non-examinable.
    • All historical asides, industrial applications, and jokes are non-examinable.
    • Anything intrinsic to the way the material is presented is non-examinable. For example, I’d never ask you to state “Lemma 1 of Lecture 23”, but you I might ask a question which requires you to know that the lemma is true, or how the proof works. If a result has a standard name, then that name is examinable - for example, I might ask you to state Dirac’s theorem or the Cook-Levin theorem.
    • Anything specifically flagged as non-examinable is non-examinable. (Duh.)
  • Anything in the following materials is non-examinable unless it also appears in a video lecture or Blackboard quiz:
    • Anything discussed in the Q&As but not covered in the lectures and quizzes.
    • Anything specific to the problem sheets. The general techniques they teach are examinable — for example, how to prove that a problem is NP-hard, or how to find a counterexample to a proposed greedy algorithm — but the specific questions and answers are not.
    • Anything linked on the unit pages under readings and resources. They’re just intended as alternative sources if you’re having trouble understanding the lectures or if you’d like more detail on something.

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 34% in the exam to pass, 45% in the exam for a II.ii, 56% for a II.i, and 67% for a First. Every little helps!
  • Being able to bring notes into the exam is incredibly powerful, and you should prepare them carefully. You don’t have anywhere near enough space to just print out the lecture notes and bring them in. Instead, you should try to distill the concepts down to the very basics, to the point where you can reconstruct them from just a few reminder notes. In doing so, you will not only get an immediate advantage in the exam, you will also have made an excellent start on understanding and revising the material.
  • If you have been struggling with the unit and have limited time to revise, you should try to get a shallow understanding of the entire unit rather than a deep understanding of one or two areas. Being able to answer almost all the easier questions and some of the harder questions is a sensible path to a II.i, and being able to answer a decent proportion of the easier questions and no harder questions is a sensible path to a pass. By contrast, being able to answer almost all of the 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. By the same token, while I try and cover a large proportion of the unit material in the exam, inevitably some topics come up more than others and some topics don’t come up at all.
  • 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. In particular, you do not need anywhere near the level of rigour or formality shown in problem sheet solutions to get full marks.