Computer Laboratory

Alex Katovsky


Mathematical Methods For Computer Science

In Michaelmas 2011, I am supervising the part 1b course Mathematical Methods for Computer Science

An illustration of JPEG compression as an application of the Discrete Fourier Transform. Load the Octave file jpeg.m in Octave (it might work in Matlab). There are two parts; the first illustrates the Fourier transform (followed by examples), and the second the Haar Wavelet transform (also followed by examples). To run the second part, you will need to compile the OCT files here. You will need Octave for this.

Logic and Proof

In Michaelmas 2011, I am supervising the part 1b course Logic and Proof

Implementation of some algorithms for the propositional calculus; parsing a propositional formula, converting a propositional formula to Conjunctive Normal Form (CNF), converting a propositional formula to Disjunctive Normal Form (DNF), the Davis - Putnam - Logemann - Loveland (DPLL), and making Binary Decision Diagrams (BDD)

Compiler Construction

In Lent 2011, I am supervising the part 1b course Compiler Construction. Here are some answers to implementation exercises:

Syntax tree interpreter (section 2.1) Simple.sml
Untyped lambda calculus interpreter (section 9.4) with monadic recursive descent parser and examples (including the Y combinator) SimpleLambdaExp.sml
Evaluator, recursive descent parser, intermediate code generator (a small subset of the JVM instruction set, as in the Java assembler Jasmin), and intermediate code interpreter in Java for section 2.1 style language SimpleJavaJasmin.tar
SLR(1) parser (section 14), with examples SLR.hs

Foundations of Computer Science

In Michaelmas 2010, I am supervising the part 1a course Foundations of Computer Science. Here are some of the notes, questions and answers I made (sml code works with SMLNJ):

notes code answers
sup1.pdf sup2.sml
sup2.pdf sup3.sml
sup3.pdf real.sml
parser.pdf parser.sml

A solution to the countdown problem in Haskell: countdown.hs