CS2 Lecture Log
This contains a brief report of each of the lectures that have taken place in
CS2. It will be updated after each lecture to show if the lecture plan has
been followed. If you are missing handouts please go to the ITO in room 1502.
Wed 10 October: (mc)
Handed out notes 1 and 1a, and the handout for Practical 1.
Covered note 1. Briefly introduced Practical 1, including the example
instruction 'jump'. Overhead transparencies associated
with Practical 1 are available at the ITO.
Wed 17 October: (mc)
Handed out note 2. Covered note. Covered example of how to write
test files for Practical 1. Overhead associated with Practical 1 is
available at the ITO.
Wed 24 October: (mc)
Handed out note 3. Covered note.
Wed 31 October: (mc)
Handed out note 4. Covered note.
Wed 7 November: (mc)
Handed out note 5. Covered note.
Wed 14 November: (mc)
Handed out note 6. Covered note.
Wed 21 November: (mc)
Handed out note 7. Covered note.
Wed 28 November: (mc)
Handed out note 8. Covered note.
Wed 5 December: (mc)
Handed out note 9. Covered note.
Wed 9 January: (mc)
Handed out note 10. Covered note.
Fri 11 January: (mc)
Handed out note 11. Covered note.
Mon 14 January: (mc)
Handed out note 12. Covered note.
Fri 12 October: (grohe)
Handed out note 1. Covered note. There is a bug in the version I
handed out (in the Combination Lock automaton). I replaced the lecture
notes on the web by a corrected version.
Fri 19 October: (grohe)
Handed out note 2. Covered note, apart
from Theorem 2.7, which is included as an extra example in the notes,
but will not be treated in lectures.
Fri 27 October: (grohe)
Handed out note 3. Covered note.
Fri 2 November: (grohe)
Handed out note 4. Covered note. Included example conversion from
regular expressin to NFA that is not in the note.
Fri 9 November: (grohe)
Handed out note 5. Covered note.
Fri 16 November: (grohe)
Handed out note 6. Covered note. Included example for running the
"just in time" algorithm.
Fri 23 November: (stark) Handed out note 7.
Presented a range of languages used for communicating with and between
computers. Overview of how processing them breaks down into lexing,
parsing and interpretation. Demonstrated small language for
describing electrical circuits. For those who were there, the
handwriting guy is Luc
Devroye, the obfuscated C
flight simulator was by Banks in 1998, and you can find lots of
postscript mazes here, here and here.
Mon 26 November: (stark) Handed out note 8 and
practical 3 (Software Engineering). Gave an introduction to
generative grammars, and context-free grammars in particular. Here
are some links for material on Noam Chomsky, also Braess and
Fri 30 November: (stark) Handed out note 9.
Top-down versus bottom-up parsing; predictive parsing; how to write a
parser using recursive descent.
Predictive parsing means never
having to say you're sorry.
Fri 7 December: (stark) Handed out note 10.
Problems with grammars and how to fix them: ambiguity, left factoring,
left recursion. LL and LR parsing. Brief introduction to the idea of
a `parsing engine'. Slides from
Mon 7 January: (stark) Handed out note 11 and
practical 4 (Grammars and Parsing). Recap of predictive parsing.
Parsing tables and how to use them to drive a parse engine.
Demonstration of practical 4 application. Overview of
First and Follow sets. Slides from
Fri 18 January: (stark) Handed out note 12
together with worked example. Description of automatic generation of
lexers and parsers. Details of JFlex and Java CUP
specifications of the circuit description language. How a bottom-up
parsing engine operates; advantages over top-down parsers. Shakespeare to C converter.
Monday 16th October: (soa)
Handed out note 1. Covered note.
Monday 23rd October: (Michael.Fourman)
Handed out note 2. Covered note.
Monday 30th October: (soa)
Covered note 3. The fire drill meant that copies of the lecture note
were not available for handing out at the lecture. They can be collected from
Monday 6th November: (soa) Handed out Practical 2.
Covered note 4. Used examples of a healthcare system to illustrate
the form, structure and contents of a requirements document.
Monday 13th November: (Michael.Fourman)
Covered note 5. Used examples from a healthcare system to illustrate
requirements capture and analysis. Discussed functional specification
using the example in the notes.
Monday 20th November: (soa)
Covered note 6. Discussed two examples of software failures and their
lessons for S/E with respect to dependability. Also briefly covered
Friday 8th December: (Michael.Fourman)
Covered note 7.
Mon 28 January: (cdw) Handed out and covered note 1. Reviewed basic
database systems concepts and outlined different kinds of database
systems. Introduced SQL programming for relational database systems.
Mon 4 February: (cdw) Handed out and covered note 2. Continued
with basic SQL programming.
Mon 11 February: (cdw) Handed out and covered note 3. The lecture dealt with Joins and Subqueries in SQL. Some errors were detected on the slides, so an updated version of the slides has now been placed on the web page.
Mon 18 February: (cdw) Handed out and covered note 4. The lecture dealt (briefly) with the remaining SQL concepts (creating tables and views, inserting/updating values, deleting values/tables/views, and indexes). Practical 6 on SQL programming with Java and JDBC was also issued and discussed briefly.
Mon 25 February: (cdw) Handed out and covered note 5 on Entity-Relationship (ER) modelling for databases.
Mon 4 March: (hst) Covered all but last few slides of note 6 on Ethernet, TCP/IP and BIND/DNS. Notes now online and will be handed out on Friday
Mon 22 April: (hst) Finished Ethernet etc., covered most of HTML
Mon 29 April: (hst) Finished HTML, first half of SGML/XML
Mon 6 May: (hst) Finished XML, started style, got through CSS
Mon 13 May: (Richard Tobin) Finished style (XSLT)
Algorithms and Data Structures
- Wednesday 30 January: (grohe) Covered Note 1.
- Wednesday 6 February: (grohe) Covered Note 2. In addition, I said a few words on average case complexity (see slide 9 of Lecture 1).
- Wednesday 13 February: (grohe) Covered Note 3.
- Friday 15 February: (grohe) Covered Note 4.
- Wednesday 20 February: (grohe) Covered Note 5.
- Wednesday 27 February: (grohe) Covered Note 6.
- Wednesday 17 April: (grohe) Covered Note 7.
- Friday 24 April: (grohe) Covered Note 8.
- Wednesday 1 May: (grohe) Covered Note 9.
Advanced Programming in Java
Friday 1 February: (stark) Note 1.
Object-oriented programming in general, Java in particular. Objects
as state+behaviour. Fields, methods, constructors; overloading;
Friday 8 February: (stark) Note 2. Modular
programming, and how Java supports it. Packages within packages;
Inheritance. Compile-time types, run-time types. Dynamic
Demonstrated the Bean Shell
tool: to run this locally, type
beansh for the GUI or
beansh-cli for command line. The web browser
example is in the same directory.
Friday 22 February: (stark) Note 3. Unicode characters and Java strings;
identity and equality in object-oriented programming; streams for
binary I/O; readers and writers for text I/O. Don Knuth and literate programming.
Friday 1 March: (stark) Note 4. Remedial
Java: base types
boolean. Advanced Java: Reasons for concurrent
programming, threads vs. processes, scheduling possibilities, threads
in Java. Next Java lecture is Wednesday.
Wednesday 6 March: (stark) Note 5. Basic
Java: variables and parameters; hiding, aliasing, null pointer
exceptions. Advanced Java: Managing safety and
liveness in multithreaded programs. Java's use of
monitors with synchronized code blocks and
wait/notify communication. Copies of Hoare's paper on
monitors are available outside the ITO, and also online as an ACM Classic Paper.
Friday 8 March: (stark) Note 6. Basic Java:
Arrays. Advanced Java: Collection classes; the separation between
specification and implementation.
Friday 19 April: (stark) Note 7. Testing Java classes,
and how it isn't the same as debugging. The
javap tool. Christopher Alexander and design patterns. Examples of patterns
in Java classes. Benefits and limitations of OO patterns.
Introduction to the visitor pattern. For more, read the note, Chapter 16 of Eckel
1st edition, or (much better) do the exercises.
Wednesday 24 April: (stark) Note 8. Basic Java:
Walk through a small complete program doing textual I/O. Using
XEmacs/JDE to compile code and trace errors. Advanced: Overview of
Swing, layout managers, demonstration of SwingSet2. Swing as an
adaptive GUI, and the significance of not being
Friday 3 May: (stark) Note 9. Sample sheet
of some compiler error messages; demonstration of what they mean and
how to fix them. Outline of nested and inner classes: reasons for
seeking more lightweight classes, and what they offer.
links: the Design Patterns
Java Companion, the Big Ball of Mud and The Selfish Class
Friday 10 May: (stark) Note 10. Garbage
collection for an object-oriented language. Assertions:
preconditions, postconditions, invariants. Language additions: Java 1.4, Eiffel.
Distinction between runtime assertions and compile-time (or earlier)
verification. Floyd-Hoare logic, proofs and ESC/Java.