These are the syllabuses for the third year of the computer science course in 1986-7. Note the mention of Multics (the more sophisticated predecessor to Unix, running on a central shared university computer).
An introduction to the principles of integrated circuit and systems
design. The course is based on nMos technology, and will use design software
implemented on MULTICS, including cell libraries. Topics covered are: the
basis of devices, circuits and fabrication, including inverters, gates,
registers and programmable logic arrays; systems design and implementation;
description of LSI designs; architectures appropriate for VLSI. Students will
be expected to implement a small design as part of the course assignment.
Text: Computational Aspects of VLSI, J.D. Ullman,Computer Science Press
This course follows on from the last 18 lectures of CS2A and describes
how various parts of a compiler can be designed and constructed. The main
topics covered are parsing and code generation. Practical work using PASCAL is
an essential part of the course.
Prerequisites: CS2A essential. Please see me if you have not done CS2A
Recommended book: Principles of Compiler design by A.V. Aho and
J.D. Ullman (Addison-Wesley)
or Compilers: Principles, Techniques and Tools by
A.V. Aho, R. Sethi and J.D. Ullman.
Databases management, Database systems. Data, Hardware, Software, Users.
Operational data. Data independence. Relational, Hierarchical, Network
systems
Database architecture. External, Conceptual, Internal levels. Mappings,
Database administrator.
Relational systems. Query languages. Structured Query Language, SQL.
Data definition. Data manipulation. Data dictionary. Views. Embedded
SQL Relational algebra. Relational calculus. INGRES.
Normalisation. Normal forms.
The course is divided into two components of 15 lectures each. Each
component is taught in Autumn Term 1986.
(1) PRINCIPLES OF PROGRAMMING LANGUAGES
Syllabus: Kinds of programming language: Syntax, semantics and
pragmatics. The Chomsky hierarchy: parsers for context-free and regular
grammars. Operational and axiomatic semantics for fragments of PASCAL.
Declarations, environments and bindings. The semantics of functional
languages. Resolution theorem-proving and the logic of Prolog.
Exercises include writing parsers and implementing interpreters in Prolog.
There is no set book.
(2) FORMAL SPECIFICATION
Syllabus: Logic notation, proofs, invariants, structural induction, map
notation, sequence notation, formal proofs about specifications, implementing
specifications directly into Prolog.
Set text: Systematic Software Development using VDM, C.B. Jones,
Prentice-Hall.
Estimation of running times of algorithms. Use of methods such as
recursion, "divide and conquer", dynamic programming in the design of efficient
algorithms.
Use of data structures such as trees and graphs in the design of fast
algorithms. Examples of applications in computer Science, and also in such
areas as numerical analysis, geometry, text processing, electronics etc.
Importance of polynomial-time algorithms. The travelling salesman
problem and others for which only exponential-time, exhaustive search
techniques are known. The theory of Turing machines and NP Completeness for
analysing such problems.
Prerequisites: CS1 - CS2 desirable.
BOOKS: "Algorithms" by R. Sedgewick published by Addison Wesley; "The Design
and Analysis of Computer Algorithms" by Aho, Hopcroft & Ullman published by
Addison Wesley; Data Structures & Program Design" by Kruse published by
Prentice Hall.
FPS This course will compare and contrast alternative approaches to the
design of computer systems, with particular emphasis on the use of parallel
hardware to achieve high processing rates.
Syllabus: Introduction to the concept of parallelism. Outline of the
alternative approaches to the design of computer systems. Advanced design; the
formal basis.
Single Instruction Single Data Stream Computers:
Recent developments in von Neumann architectures; RISC.
Single Instruction Multiple Data Stream Computers:-
(a) Vector processors; CDC STAR, Cyber 205, CRAY 1, CRAY X-MP,
AP120B, ASC.
(b) Array processors: ILLIAC IV, ICL DAP, CLIP4, BSP, MPP.
Multiple Instruction Multiple Data Stream Computers:-
(a) Multiprocessors: Cmmp, Cm*S-1, CYBA-M.
(b) Message passing multiprocessors: Inmos Transputer.
(c) Data flow multiprocessors: MIT data flow, Manchester data flow.
(d) Recursive machines: Newcastle recursive machine, Xerox recursive
machine.
(e) Reduction machines: SKIM, ALICE.
(f) Data base computers: IDM 500, DIRECT.
(g) Tree machines: X-tree, P-tree, DAC.
Parallelism and its relationship to form computer models will be analysed.
This course is concerned with the development of a systematic approach
to program writing. It is based on, and closely follows
J. ARSAC : fundamentals of Programming. Academic Press 1985
(Arsac is a long standing member of the IFIP Working Group on
Programming Methodology)
The iterative, recurrent and recursive forms of a program are studied,
together with means for passing from one form to another. Syntactic and
semantic program transformations are introduced as basic techniques in
analytical programming. As the course proceeds the accepted notions of
programming language, program structure, data type, and program correctness are
examined critically.
AIM - To give the student a basic grounding in the fundamental concepts of
computer graphics.
Introduction - graphics applications in commerce, engineering, education,
entertainment, etc.
Hardware - description of various input and output devices with particular
emphasis on raster graphics displays.
Scan conversion for points, lines and solid areas - polygon filling.
Windowing and clipping.
Geometrical transformations in 2-D and 3-D - translations scaling, rotations,
projections, etc.
Curves and surfaces - splines, Bezier curves.
Hidden lines and hidden surfaces.
Shading, colouring, rendering.
Graphics packages and standards - GINO-F, GKS.
Design of user interface.
BOOKS: Fundamentals of Interactive Computer Graphics,
Foley & Van Dam, (Addison-Wesley)
Principles of Interactive Computer Graphics,
Newman & Sproull, (McGraw-Hill)
Procedural Elements for Computer Graphics,
Rogers (McGraw-Hill)
Mathematical Elements for Computer Graphics,
Rogers (McGraw-Hill)
Computer Graphics, Hearn & Baker, (Prentice-Hall)
Computer Graphics, Berger, (Benjamin/Cummings)
The aim of this course is to give a precise mathematical characterisation
of those functions whose values can be computed and of those problems which can
be solved by a computer. It should be of interest to computer scientists,
particularly those who have taken CS3.4 Analysis of Algorithms, and also to
pure mathematicians, particularly those who have taken H3.11 Logic or H3.10
Foundations of Mathematics. But none of these are prerequisites.
Various simple types of machine e.g. Turing Machine, and rudimentary
programming languages with very few types of instruction (e.g. just X:=X+1,
IF X=0 THEN X:X-1 and GO TO i) are introduced and convincing arguments given in
support of Church's Thesis, that these machines and languages are general
purpose, i.e. capable of computing any function that is in any sense
computable. An equivalent definition of computable, of a more familiar
mathematical form is given in terms of recursive functions, i.e. functions
definable by various kinds of recursive or inductive definition. It is proved
that various problems about programs or machines are not capable of being
solved by programs or machines. For example it is not possible to write a
program which will decide whether an arbitrary program will halt on given input
data. Indeed there is a remarkable theorem of Rice which says that any
property of programs which depends only on their input/output behaviour is
incapable of being decided by a program. Many combinatorial and mathematical
problems have also been shown to be unsolvable by computer and the course
finishes with a proof of the undecidability of first order logic, and of the
logic programming language Prolog. The definition of recursive procedures and
their replacement by nonrecursive ones is also discussed.
Prerequisites: The ability to formulate concepts precisely and to reason
about them, particularly by the method of induction. No
knowledge of programming is assumed.
Books: Kfoury, Moll & Arbib: "A programming approach to computability",
Springer. Need not be bought; confined to library.
The course introduces the student to certain techniques of A.I. associated
with such general areas as search, automatic deduction and theorem proving,
induction and machine learning, expert systems, natural language understanding,
scene analysis and robotics.
An in depth treatment of Prolog is given and used to illustrate the above
techniques with actual computer implementations. Course work is a necessary
part of the course and the student is expected to implement applications on the
Computer.
The limitations of Prolog as a logic programming language are discussed
along with implementation details of the language.
Inference is not restricted to classical logic but includes a discussion
of non-standard logics including a general treatment of uncertainty, logic,
production systems and conceptual graphs.
Prerequisites: First order predicate logic and prolog would be useful.
Additional lectures could be given.