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)

(John Shepherdson, Maths)

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.