Algorithm Design
The lectures are about how to develop algorithms in a way that they are guaranteed to meet their specification -- so-called "correct-by-construction" algorithm design. The implementations of the algorithms are typically very short, but challenging. Additional supporting material (particularly on logical reasoning) will also be presented.
This is an advanced course. Students taking the module will be expected to already have good programming skills. Algorithms are presented in an idealised pseudo-code so no knowledge of a particular programming language is assumed.
Course Information
- Convenor: Roland Backhouse
- Module Code: G54ALG
- Duration: Autumn 2012, Semester 1
- Method and frequency of class: Two hours of lectures per week:
- Wednesday, 11:00-12:00 in C60 (CS building)
- Thursday, 10:00-11:00 in C60 (CS building)
- Method of assessment: Coursework (50%) and an unseen 2-hour examination (50%)
Literature
|
My book Program
Construction. |
Additional Texts:
- Anne Kaldewaij. The Derivation of Algorithms
- David Gries. The Science of Programming
Model Examination Paper
The module convenor for this module changed in 2011. Examination papers set before January 2012 are therefore not indicative of the examination that will be set. Below is a model examination paper. (Note: in the actual examination paper there will be a choice of three out of five questions, not three out of four.
Coursework
There will be two courseworks, a formative and a summative coursework. Both will be marked and solutions discussed in lectures. The marks for the formative coursework DO NOT count towards the final assessment and are for feedback purposes only. The marks for the summative coursework DO contribute 25% towards the final assessment.- Formative coursework. Deadline: 3pm, Friday, 2nd November. Model Solutions.
- Summative coursework. Deadline: 3pm, Friday, 7th December.
Lecture notes
Lectures will involve adding to "skeletons". Copies of the skeletons can be found below. NOTE. These skeletons are provisional and may be added to and/or changed during the course of the semester.- Algorithm Design. Administrative Information. A Search Problem.
- Quantifiers. Notation and Calculational Rules
- Small Examples. Sorting and Searching.
- Raster-display Algorithms. Bresenham-like algorithms.
- Counting Intersections. An exercise in algorithmic problem solving.
- Verification-Construction Rules
- Constructing Verification Conditions
- Choosing Data Structures. Data structures for elementary graph searching.
- Using Quantifiers. Example of dynamic programming.
- Spelling Correction. An example of finding shortest paths.
- Searching Graphs. Topological Search. Wagner's shortest-path algorithm. The A* algorithm.
- Kleene Algebra Kleene/Regular algebra as the basis for path-finding.
- Matrix Multiplication A standard textbook example of the use of dynamic programming. (Not examinable.)
Remember to bring copies of these skeletons to every lecture.
Occasionally, additional material will be made available below. If you miss a lecture, ask a colleague for the lecture notes. Do not rely on the notes being posted here.
Supplementary Material
- Computing Disasters and Binary Search (Seminar. Some parts are used in the introductory lectures.)
- Modern is not Better. (Examples of incorrect implementations of binary search in recently published textbooks.)
- Raster-Display Algorithms
- Dynamic Programming
Getting Help
If you have any questions on the module, please come to see me immediately after the lecture or in my office (room B30).
If you do have difficulty getting hold of me then send an email suggesting a time and day that you would like to come and see me. (But please keep email traffic to a minimum.)