NOTE: I initially created this site while still at University, and stopped updating it several years ago. I'm leaving it here as most of the stuff here is probably still true, but please note that most is almost certainly out of date.

I've started making an up-to-date CV at cv.dalelane.co.uk

 Education Degree Final Year Modules Industrial Placement Second Year Modules First Year Modules Final Year Project Specification Transcript Technical School Other
Education :: Degree > Second Year Modules
This page contains more detailed information about the modules I took during the second year of my Computing degree.
Aims
To introduce the capabilities of different kinds of machines, to explore the relationship between Turing machines and algorithms, and to explore the limitations of Turing computability.
To introduce the Lambda calculus.
Objectives
Students should appreciate the limitations of finite-state machines, and the availability of different possible standard formalisations of Turing machines. Students should understand what can and cannot be computed using Turing machines, and the relationship between Turing machines and algorithms. In the lambda calculus, students should be able to find normal forms, when these exist, using alpha and beta reduction.
Content
• Languages and regular expressions
• The basic properties of finite-state machines
• Nondeterministic finite-state machines
• What can and cannot be computed using finite-state machines
• Turing Machines
• Connecting standard Turing Machines together Grammars, languages and the Chomsky classification
• Introduction to Church's Thesis
• Universal Turing Machines and limitations of Turing computability
• Undecidability
• The Halting Problem
• Reduction of one unsolvable problem to another
• Lambda calculus
• Alpha and Beta reduction
• Confluence
• Church-Rosser Theorem
Aims
To convey to students the idea that programming can be presented as a systematic process of calculation with mathematically secure foundations.
Objectives
Students should be able to develop modest programs systematically with a complete understanding of the mathematical foundations of the method advocated, and should understand the relationship between formal and informal methods for practical use.
Content
• Programs, specifications, code, refinement
• Types, invariants and feasibility
• Assignment and sequencing
• Control structures: alternatives and iteration
• Introduction to data refinement
• Dijkstra's weakest precondition and language semantics in terms of it
• Basic Theorems for the Alternative and Iterative Constructs and their relevance to program development
• Use of the weakest precondition as a basis for the refinement calculus
• Proving refinement laws from first principles; deriving one refinement law from another
Aims
To gain experience of working with other people and, on a small scale, some of the problems that arise in the development of software.
Objective
To carry out the full cycle of the first phase of development of a software package, namely; requirements analysis, design, implementation, documentation, testing and delivery.
To know the main terms of the Data Protection Act and be able to explain its application in a variety of contexts.
Content
Project Management:
• Practice of software engineering techniques
• Controlling software development
• Project planning / management
• Design
• Quality assurance
• Testing
Professional Issues:
• Professional responsibilities: codes of professional practice, chartered engineers
• Legal responsibilities: Data Protection Act, Computer Misuse Act, Consumer Protection Act
• Intellectual property rights
• Contracts
Aims
To present a detailed account of some fundamentally important and widely used algorithms.
To induce an appreciation of the design and implementation of a selection of algorithms.
Objectives
To learn the general principles of effective algorithms design and analysis on some famous examples, which are used as fundamental subroutines in major computational procedures.
To be able to apply these principles in the development of algorithms and make an informed choice between basic subroutines and data structures.
Content
• Algorithms and complexity
• Main principles of effective algorithms design: recursion, divide-and-conquer, dynamic programming
• Sorting and order statistics
• Strassen's algorithm for matrix multiplication and solving systems of linear equations
• Arithmetic operations over integers and polynomials (including Karatsuba's algorithm), Fast Fourier Transform method
• Greedy algorithms
• Basic graph algorithms: minimum spanning trees, shortest paths, network flows
• Number-theoretic algorithms: integer factorization, primality testing, the RSA public key cryptosystem
• Complexity classes P and NP
• NP completeness
Aims
To give an introduction to the processes involved in compilation and the use of compiler generation tools and compiler support.
Objectives
To know the phases of the compilation process and how to implement them.
To be able to choose between different techniques and different representations, depending on the problem to be solved.
Content
Formal grammars, lexical analysis using lex, parsing by recursive descent and by yacc, error handling in the parsing process, intermediate code representations, type checking, simple code generation. The interface to the operating system. Design of run-time systems and issues in storage management, including garbage collection.
Aims
To provide a grounding in the principles behind object oriented languages and how they are realised, in order to enable the student both to use any object oriented language and to use any language in an object oriented way.
Objectives
To be able to classify a given object oriented language into the categories identified above
To describe the differences between those categories and to know the principles involved in implementing a language belonging to any one of those categories.
Given a problem description, to be able to design suitable class hierarchies.
To be able to read, understand and write programs in C++ and EuLisp.
Content
• Introduction: definition of inheritance and identification of the subclasses of the family of OO languages
• Simple (single) inheritance
• Extending arithmetic: Complex number arithmetic in C++ (overloading, message-passing) and EuLisp (generics)
• Sequence and iterators: For classical data structures (list, vector) in C++ and EuLisp
• Polymorphism
• Integration of user-defined sequence classes
• Modelling OO mechanisms: Modelling message passing and class hierarchies
• A method determination algorithm for generic functions
• Advanced topics: Multiple inheritance and the superclass linearization problem.
• Meta-object protocols
Aims
To give the student an appreciation of the foundations of programming by considering functions as units of computation l-calculus and combinatory logic.
To raise the issue of correctness and to develop a critical attitude toward computing in general and logic programming in particular.
To illustrate how the various mathematical principles discussed in this Unit are translated in practical programming languages.
Objectives
Students should be able to perform reductions in two reduction systems, and to prove elementary theorms in and about these calculi.
To understand enough logic so that correct logic programming is possible.
To be able to apply the theories of mathematical logic to the development of programming languages, to contrast pure rewriting with environment based interpretation operating over different domains (eg. values and types).
To be able to read, understand and write programs in EuLisp.
Content
• String rewriting systems
• Church-Rosser ideas
• Zermelo Fraenkel set theory
• Types and sets
• Operations on types
• Examples in C and ML
• Functions as graphs, and functions as rules or processes
• Pure lambda calculus
• Reduction
• Ordered pairs
• Numerals in lambda calculus
• Lisp
• Scott domain theory
• Logic
• Logical validity
• Logical consequence
• Conjunctive normal form
• Clausal form
• Semantic tableau methods
• Prolog
• Resolution and unification
Aims
To inform students of the rapid change in computing via an analysis of the history and development of the computing industry and subject.
The course aims to do two things. First, to remove the almost mystical belief that computers can do anything. Secondly, to encourage students to question the appropriateness of computer systems as a solution to any given problem.
Objectives
Describe the major trends and changes in hardware, programming languages and software; explain the evolution of the computing industry; extrapolate current trends in the industry, while realising the weakness of extrapolation. Students should be able to demonstrate reasoned arguments for and against the use of computer technology. They should be able to compare machine and human intelligence. They should understand the dangers of compulsive use of computers; and the hazards that a computer solution may introduce.
Content
• The pre-history (Pascal, Babbage, Turing etc.)
• 1940s and 1950s: the birth of an industry and a subject
• Semiconductor technology and its evolution
• 1960s and 1970s: the 'range' concept
• IBM and the Seven Dwarfs
• High-level languages
• Operating systems
• The growth of on-line access
• The rise of the mini-computer
• Workstations and Unix
• Growth of networking
• 'Professionalism'
• The PC Market: Intel and Microsoft
• Where we are now. What computers do; what programmers do.
• Machines: engineering a computer system.
• Humans: language, understanding and reason.
• Human and machine problem solving
• Eliza-like systems
• Artificial intelligence
• Programming as a compulsion
Aims
To present an introductory account of the theory and practice of databases.
Objectives
To demonstrate understanding of the basic structure of relational database systems and to be able to construct small databases.
Content
• Network and relational models
• Completeness of relational models
• Codd's classification of canonical forms: first, second, third and fourth normal forms.
• Keys
• join
• SQL query language
Aims
To provide an introduction to the techniques of representing, rendering, and displaying computer graphics, with assessed coursework.
Objectives
Students will be able to distinguish modelling from rendering. They will be able to describe the relevant components of Euclidean geometry and their relationships to matrix algebra formulations. Students will know the difference between solid and surface modelling and be able to describe typical computer representations of each. Rendering for raster displays will be explainable in detail, including lighting models and a variety visual effects and defects.
Content
• Basic mechanisms, concepts and techniques for raster graphics
• Output and input devices
• Packages
• Co-ordinate systems, Euclidean geometry and transformations
• Modelling: Mesh models and their representation
• Constructive solid geometry and its representation
• Specialised models
• Rendering
• Raster images
• Illumination models
• Meshes and hidden-surface removal
• Scan-line rendering
• Ray-casting
• Visual effects and defects
• Resolution
• Aliasing
• Colour
Aims
This unit aims to give the student confidence and competence in C programming, shell programming and problem solving using tools. It does this through a combination of laboratory sessions, project work and supporting lectures. Objectives: To have students demonstrate a mastery of C at a level above single file simple I/O programs, experience interfacing to programs whose inner workings are not known, learn to adapt or combine existing tools to build solutions and practice in a professional approach to programming and presentation.
Content
• Further C
• Multiple file programs
• User interfaces
• The C library
• Storage allocation mechanisms (malloc, calloc, realloc, alloca)
• Using standards
• Make
• Installing packages
• String processing: grep, egrep, fgrep, sesd, awk, prl
• Shell variables and programs
• Unix utilities such as tr, tar, In, find, sort, uniq sargs, etc.
• General utilities such as gnuplot, Tcl/tk, LaTeX, HTML etc.

Last updated: 6 Nov 2005

Site design: Dale Lane

Education :: Degree > Second Year Modules