Skip to main content

CS3

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).

VLSI (Very Large Scale Integration, Mike Rogers)

       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

Compiler Construction (Colin Burgess)

       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 (Maurice Flower)

     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.

Software Engineering (with VDM, Dr. P.F. Gibbins)

     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.

Analysis of Algorithms (Ian Holyer)

       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.

Advanced Architectures (Derek Paddon)

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.

Programming Methodology (Fraser Duncan)

       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.

Computer Graphics (Eric Lewis)

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)

Computable Functions and Unsolvable Problems
(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.

Artificial Intelligence (Jim Baldwin, Eng Maths)

     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.