:100: Assessment

The unit is 100% assessed by a 2-hour written exam in the Winter assessment period (i.e. the week following Week 12 of TB1).

This exam is considered open book in the following sense: Candidates may bring to the exam room 1 double-sided A4 page of notes in any format.

In addition, most of the important definitions from the unit are available for your reference at the back of the exam paper.

Here is the exact front- and backmatter of the exam paper that you will see on the day of your exam: :open_book:

The exam is a series of problems to solve in the same style as the weekly problem sheets. There will be questions covering material from all parts of the unit. The difficulty of questions is related to your possible marks in the following way:

  • 1* questions only account for approximately 40% of available marks.
  • 1* and 2* questions account for approximately 70% of available marks.
  • 1*, 2* and 3* questions account for approximately 100% of available marks.

Unfortunately, this is not quite true for the practice paper below, due to the way it was assembled. Partial marks are given for partially correct answers. This is important, because you are unlikely to answer all the 3* question(s) completely correctly in the given time, but it is possible to obtain some marks for an attempt.

The distribution of marks by topic is as follows:

  • 34 marks are available for questions on syntax.
  • 33 marks are available for questions on semantics.
  • 33 marks are available for questions on computability.

However, you should make sure you are confident on all topics because the exam will contain 1, 2 and 3* questions within each of these topics.

Typical examples of the shape of 1* questions (mostly mechanical tasks that require careful use of definitions but very little insight, or recalling facts):

  • Recall some simple facts about the definitions we have studied, and their consequences, such as the meaning of state, decidable, abstract syntax tree, injective, computable etc.
  • Deriving a string in a grammar, giving examples of strings in the language expressed by a grammar.
  • Constructing a parse table for a grammar.
  • Writing a While program to achieve some simple specification, or to show computability of some function.
  • Distinguish different kinds of syntax in the While language, e.g. arithmetic vs Boolean expressions.
  • Deducing the final state after executing a While program from a given starting configuration.
  • Construct a trace or find a final state for a given program in the While semantics.
  • Evaluate expressions in a given state.

Typical examples of the shape of 2* questions (mostly constructing simple objects – programs, equational proofs, trace, grammars etc – to meet given requirements):

  • Construct a grammar to express a certain language.
  • Give an LL(1) grammar equivalent to a given grammar.
  • Reason symbolically about (extensions of) the While language, for example to show the equivalence of two given expressions / statements, including straightforward induction proofs.
  • Construct a trace or find a final state for a given program in extensions of the While semantics.
  • Calculate the strongest post-condition or verify that a Hoare triple is valid for straightline code.
  • Show that a (more complex) function is computable, by writing a While program.
  • Prove simple properties of functions/combinations of functions (injectivity, surjectivity etc).
  • Show that a predicate is decidable/semi-decidable.

A few typical examples of the shape of 3* questions, but 3* questions are often atypical and of a shape that you may have never encountered before during the unit.

  • More intricate induction proofs.
  • Show that a predicate is undecidable.
  • Show that a language can be expressed by a grammar, where there is some insight needed to first simplify the description of the language.
  • Find loop invariants and show that a While program satisfies a given property.

Before the day of the exam, you should be confident in your ability to answer typical 1* and 2* questions.

General feedback sent to students on the overall performance in the 2024 exam, which had a relatively high average mark, can be viewed here. Note: that exam was 3 hours duration (your exam is 2 hours duration) and some of the material has changed this year, so you may find that some of the feedback doesn’t apply.