Examinable Syllabus Checklist

What the exam tests

The Part IA Foundations of Computer Science paper (Paper 1) covers 11 lectures taught in Michaelmas term. The exam typically has 2 questions, each worth 20 marks, testing a mixture of bookwork (definitions, complexity analysis, concepts) and application (writing OCaml functions, reasoning about algorithms, tracing computations). Since 2019 the course uses OCaml syntax; earlier past papers use Standard ML syntax. Students must learn everything in the slide deck unless specifically marked unexaminable.

Syllabus checklist

1. Introduction to Programming (Lecture 1)

• Abstraction levels and interfaces; the abstraction barrier; how it allows one level to change without affecting levels above
• Data types: representation, operations, valid results; floating-point inaccuracy; integer overflow
• Goals of programming: expressions (compute values) vs commands (cause effects); programming in-the-small vs in-the-large
• OCaml basics: let bindings, float vs int, infix operators (*., +., etc.), type inference, type constraints
• Recursive functions: let rec, the if-then-else conditional; mathematical justification via recurrence equations
• The npower function: naive recursive exponentiation, O(n) time, O(n) space
• The power (fast exponentiation) function: divide-and-conquer using squaring, O(log n) time, O(log n) space
• The even function, mod operator, integer division /
• Conversion functions: int_of_float, float_of_int
• Boolean operators: &&, ||, not; relational operators: <, =, <>

2. Recursion and Efficiency (Lecture 2)

• Expression evaluation: reducing E_i to E_{i+1} until a value v is reached; functional programming model
• nsum: naive recursive sum, O(n) time and space; the nesting problem and stack overflow
• summing: iterative (tail-recursive) sum with accumulator, O(n) time, O(1) space
• Recursion vs iteration: tail-recursion only efficient if compiler detects it; KISS principle; closed-form n(n+1)/2
• sillySum: double recursive call, O(2^n) time, O(n) space
• let-bindings for local computation, avoiding repeated evaluation
• Big-O notation: formal definition |f(n)| ≤ c|g(n)| for sufficiently large n; ignoring constant factors
• Simple facts about O notation: constant factors drop out; log base irrelevant; insignificant terms drop out
• Common complexity classes: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) quasi-linear, O(n^2) quadratic, O(n^3) cubic, O(a^n) exponential
• Cost table: npower/nsum O(n) time/space; summing O(n) time O(1) space; power O(log n); sillySum O(2^n)
• Simple recurrence relations: T(n+1)=T(n)+1 → O(n), T(n+1)=T(n)+n → O(n^2), T(n)=T(n/2)+1 → O(log n), T(n)=2T(n/2)+n → O(n log n)

3. Lists (Lecture 3)

• List syntax: [x1; x2; ...; xn], all elements same type; @ (append) and List.rev
• The two list primitives: [] (nil) and :: (cons); :: is O(1); lists as linked structures
• Pattern matching with function and |; exhaustive matching warnings; _ wildcard; type variables 'a, 'b
• null, hd, tl primitives; partial functions raised Match_failure on []
• nlength: naive recursive length, O(n) time and space; addlen: iterative length with accumulator, O(n) time, O(1) space
• append (@): copies first list, O(n) time and space where n is length of first argument; not iterative
• nrev: naive reverse using append, O(n^2) time (n(n+1)/2 conses), O(n) space
• rev_app / rev: efficient reverse with accumulator, O(n) time, O(1) space; reduction in strength (replacing append with cons)
• Strings and characters: char vs string; String.length, ^ concatenation; lexicographic ordering
• Polymorphism in list functions; id type 'a -> 'a; loop type 'a -> 'b (non-terminating)

4. More on Lists (Lecture 4)

• take and drop: divide lists; take copies O(i) time/space; drop skips O(i) time, O(1) space
• Linear search: O(n); ordered search O(log n); indexed lookup O(1); trade-offs
• member: polymorphic equality =; limitations on recursive/function types
• zip and unzip: building and taking apart lists of pairs; wildcard pattern _; pattern matching order
• Building pairs of results: conspair, revUnzip; iterative construction of multiple results at once
• Making change (greedy): succeeds for most coin systems, can fail; raises Failure exception when impossible
• Making change (all solutions): returns int list list; allc local function; base case [[]] for zero amount
• Making change (faster): double accumulator chg and chgs; eliminates :: and @ operations; stepwise refinement
• The greedy algorithm may fail for some coin systems (e.g., making 6 with coins 5 and 2)

5. Sorting (Lecture 5)

• Lower bound on comparison-based sorting: log(n!) ≈ n log n - 1.44n; n! permutations, each comparison halves the set
• Insertion sort: ins inserts into sorted list; insort is O(n^2) average case; simple but slow
• Quicksort: choose pivot, partition into ≤ a and > a, recurse, append; average O(n log n), worst case O(n^2) (already-sorted input)
• Append-free quicksort (quik): accumulator sorted eliminates append; faster in practice
• merge: combining two sorted lists, at most m + n - 1 comparisons; not iterative
• Top-down merge sort: take/drop to split, recursive sort, merge; worst-case O(n log n); safer than quicksort
• Summary: optimal is O(n log n); insertion sort O(n^2); quicksort average O(n log n) worst O(n^2); merge sort always O(n log n)
• Match algorithm to application; non-comparison sorts (radix) can achieve O(n) for restricted inputs

6. Datatypes and Trees (Lecture 6)

• Enumeration types: type vehicle = Bike | Motorbike | Car | Lorry; constructors as patterns; compiler exhaustiveness checking
• Constructors with arguments: e.g., Motorbike of int; different constructors distinguish different types; mixed-type lists via datatypes
• Pattern matching on constructors with arguments: binding values; wildcard _; multiple clauses
• Exceptions: raise, try...with, exception constructors; exn type; exception trace (backtracking)
• Option type: None | Some of 'a as alternative to exceptions; 'a option built-in
• Making change with exceptions: backtracking via exception handler; greedy with undo; can find solutions the greedy algorithm misses
• Binary trees as recursive datatype: type 'a tree = Lf | Br of 'a * 'a tree * 'a tree
• Lists as datatypes: type 'a mylist = Nil | Cons of 'a * 'a mylist
• Tree properties: count (number of branch nodes), depth (longest path), leaves (count of leaves plus 1); leaves(t) = count(t) + 1
• Tree capacity: depth 20 can store 2^20 - 1 ≈ 10^6 elements; short access paths compared with lists

7. Dictionaries and Functional Arrays (Lecture 7)

• Dictionary operations: lookup, update, delete, empty; Missing exception; abstract data types
• Association lists: (key, value) pairs; lookup is O(n); update is O(1) (cons); space linear in updates
• Binary search trees: keys with total order; left subtree smaller, right subtree greater; balanced → O(log n); unbalanced → O(n)
• BST lookup: compare, go left or right; Missing exception with key; O(log n) average
• BST update: copies path only, shares unchanged subtrees; O(log n) time and space average
• Tree traversal: preorder, inorder, postorder (all depth-first); definitions using @; relation: inorder of BST yields sorted list
• Efficient traversal: preord, inord, postord with accumulator; linear time; inord(t, vs) = inorder(t) @ vs
• Arrays: conventional (imperative, in-place update) vs functional (copying, update(A, k, x) returns new array)
• Functional arrays as binary trees: path follows binary code of subscript; always balanced; O(log n) lookup and update
• sub function: divide subscript by 2, follow left (even) or right (odd); when guard clauses; Subscript exception
• update function: copy path, replace leaf with branch if k=1; supports extending array; O(log n)
• Dictionaries in order of decreasing generality, increasing efficiency: linear search → binary search trees → array subscripting

8. Functions as Values (Lecture 8)

• Functions as first-class values: passed as arguments, returned as results, stored in data structures; cannot test equality
• fun notation: anonymous functions; fun x -> E; function keyword for pattern matching; equivalent to let f x = E
• Curried functions: fun a -> fun b -> a ^ b; type string -> string -> string; partial application
• Shorthand for curried functions: let prefix a b = a ^ b; applying prefix "Sir " yields a function
• Curried insertion sort: insort lessequal takes ordering predicate, returns sort function; (<=) and (>=) as function arguments
• map: apply-to-all functional; type ('a -> 'b) -> 'a list -> 'b list; nested map (map double)
• Matrix transpose using map: transp; extract first column with map List.hd, remaining with map List.tl
• Matrix multiplication: dotprod (dot product), matprod using map and partial application of dotprod
• Predicate functionals: exists (lazy || short-circuit), filter (select elements), all (lazy && short-circuit)
• Applications: member via exists, inter via filter, disjoint via all; eliminating ad-hoc function declarations

9. Sequences, or Lazy Lists (Lecture 9)

• Pipeline model: Producer → Filter → … → Filter → Consumer; consumer drives demand; lazy lists join stages
• Lazy lists: possibly infinite; elements computed on demand; avoids waste for many solutions
• OCaml lazy list type: type 'a seq = Nil | Cons of 'a * (unit -> 'a seq); unit type ()
• Delayed evaluation: fun () -> E delays E; head and tail (forces with xf ())
• Infinite sequences: from k generates k, k+1, k+2, ...; tail forces next element
• Consuming sequences: get n s returns first n elements as a list; forces evaluation
• Joining sequences: appendq (loses second if first is infinite); interleave (fair, exchanges arguments)
• Functionals for lazy lists: filterq (forces until match found; may loop forever); iterates f x generates x, f(x), f(f(x)), ...
• Numerical computation: Newton-Raphson square root via iterates and within (convergence test); infinite series as lazy lists
• Key principle: force operations must be enclosed in delays to maintain laziness; get and filterq have unprotected forces

10. Queues and Search Strategies (Lecture 10)

• Breadth-first vs depth-first tree traversal: BFS levels first (nearest solutions); DFS left subtree first (may miss near solutions in right subtree)
• Naive breadth-first (nbreadth): uses list and @; enormous queue, wasteful append; O(b^d) space
• Queue ADT: qempty, qnull, qhd, deq, enq; FIFO discipline
• Efficient functional queues: pair of lists ([x1,...,xm], [y1,...,yn]) representing x1...xm yn...y1
• Queue operations: enq conses to rear list O(1); deq removes from front O(1) amortised; norm reverses rear when front empties
• Amortised analysis: n enq + n deq = 2n conses total; amortised O(1) per operation; worst reversal O(n)
• Efficient BFS with queues (breadth): uses queue type; 200x faster than nbreadth for depth 12 tree
• Iterative deepening: repeated depth-first with increasing depth bounds; O(b^d) time (factor b/(b-1)), O(d) space; trades time for space
• Stack ADT: LIFO discipline; lists implement stacks naturally; depth-first uses stack implicitly/explicitly
• Survey of search methods: depth-first (stack, efficient but incomplete), breadth-first (queue, space-hungry), iterative deepening (depth-first + bounds), best-first (priority queue, heuristic)

11. Elements of Procedural Programming (Lecture 11)

• Procedural programming: state transformation; commands vs expressions; control structures (branching, iteration, procedures)
• OCaml reference primitives: ref E (create), !P (dereference), P := E (assign); type 'a ref
• References are values: can be stored in lists; p := !p + 1 increments contents; let bindings are immutable
• Commands: C1; C2; ...; Cn evaluates sequentially, returns value of Cn; typical command returns ()
• while loop: while B do C done; returns (); example: iterative length computation with references
• Private persistent references: makeAccount returns withdraw function with private balance ref; closure captures reference
• Object-oriented programming via closures: multiple accounts with independent private state; no cross-access
• OCaml arrays: [|...|] syntax; Array.make, Array.init, Array.get, Array.set; 0-indexed; bounds-checked
• Arrays as references holding multiple elements; int ref list vs int list ref; array of arrays for 2D
• Mutable lists: type 'a mlist = Nil | Cons of 'a * 'a mlist ref; linked structures with references
• OCaml vs conventional languages: explicit dereference !; V := E not V = E; safer arrays (bounds-checked); a.(i) <- v alternative syntax

Exam technique

1. Complexity analysis (4-6 marks): State the recurrence relation, identify the growth class, and justify with a sentence or two. For list algorithms, count cons operations or comparisons. For tree algorithms, count recursive calls with respect to tree depth/size. Always give both time and space when relevant.

2. OCaml function writing (8-12 marks): Write clear, well-structured code with proper pattern matching. Use let rec for recursion. Handle base cases first. Use accumulators when efficiency is required. Write polymorphic functions where appropriate. Comment on crucial design decisions.

3. Tracing/explaining code (4-6 marks): Show the step-by-step reduction. For recursive functions, show the nesting. For lazy lists, show when forces and delays occur. For exceptions, trace the handler chain.

4. Discussion/design questions (4-6 marks): Two or three well-developed points with specific references to course concepts. Compare alternatives (e.g., BFS vs DFS vs iterative deepening). Justify design decisions.

Key concepts to memorise

Concept	One-line summary
Tail recursion	Recursive call is the last operation; compiler can reuse stack frame; O(1) space
Accumulator	Extra argument carrying partial result; enables iterative/tail-recursive style
Big-O notation	Asymptotic upper bound ignoring constant factors; f(n) = O(g(n)) if `
:: (cons)	O(1) operation prepending element to list; fundamental list constructor
@ (append)	Copies first list; O(n) time and space; avoid in recursive functions
BST lookup/update	O(log n) average if balanced; copies path only for update; shares unchanged subtrees
Reduction in strength	Replacing expensive operations (e.g., append) with cheap ones (e.g., cons)
Curried function	Returns a function as result; enables partial application; type a -> b -> c
map	Applies function to every list element; type ('a -> 'b) -> 'a list -> 'b list
Lazy list	Tail wrapped in unit -> 'a seq; computed on demand; enables infinite sequences
Functional queue	Pair of lists: ([front], [reversed rear]); amortised O(1) per operation
Iterative deepening	Repeated depth-first with increasing bounds; O(b^d) time, O(d) space
Reference	Mutable cell: ref creates, ! reads, := writes; type 'a ref
while loop	Imperative iteration: while B do C done; returns ()
Closure	Function capturing private mutable state; e.g., makeAccount
Depth-first search	Searches one subtree fully first; O(d) space; may miss near solutions in infinite trees
Breadth-first search	Searches level by level; finds nearest solutions first; O(b^d) space
Functional array	Binary tree indexed by binary code of subscript; O(log n) lookup/update; always balanced
merge	Combines two sorted lists in O(m+n) time; basis of merge sort
Quicksort	Average O(n log n), worst O(n^2); pivot selection critical
Merge sort	Worst-case O(n log n); divide-and-conquer by splitting list; optimal comparison sort