This programme provides students with systematic knowledge and experience of the theoretical foundations and practice of computing at an advanced level. It is built around taught core modules such as Algorithm Design and Analysis, Data Structures and their Implementation in C++, Parallel and Distributed Algorithms, which are complemented by a wide range of optional modules for multimedia, optimisation, string processing and the web. The final part of the programme is an individual project which is closely linked with the Department's research activities.
Lectures; tutorials; seminars; laboratory sessions; optional career planning workshops. Assessed through: coursework; written examinations; final project report.
To introduce strategies for the design of algorithms which are efficient in terms of time and space requirements.
On successfully completing this module you should understand the basic techniques for designing algorithms for fundamental computational problems.
Algorithms and computational complexity
Algorithm design techniques:
Dynamic programming: matrix chain multiplication
Greedy algorithms: Huffman codes
Selecting the k-th smallest element of a list - a practical method
Selecting the k-th smallest element of a list - an optimal method
Lower bound on the time complexity of computing the median
Data structures for set manipulation problems:
Fundamental operations on sets
The union-find algorithm
Representations of directed and undirected graphs:
Adjacency-matrix and adjacency-list representations
Breadth-first and depth-first search using adjacency lists
Computing connected components of a graph
Strongly-connected and biconnected components
Strassen matrix multiplication algorithm
The Four Russians boolean matrix multiplication
LUP decomposition of matrices
Applications of LUP decomposition
Integer and polynomial arithmetic:
Integer and polynomial multiplication and division
Greatest common divisors and Euclid's algorithm
To provide you with an introduction and overview to the computational aspects of parallel and distributed computing. To introduce several important parallel computing models that capture the essence of existing and proposed types of synchronous and asynchronous parallel computers. To study typical models for distributed computing. To study a few typical algorithms for each model, selected from various basic areas such as sorting, selection, graphs, matrices, numerical problems, and computational geometry. To provide an important skill for those who may work with large applications since these usually must be implemented on a parallel or distributed system, due to their memory space and speed requirements.
On successfully completing this module you should understand a number of different models of parallel and distributed computing and understand the basic techniques for designing algorithms in these models.
PART I: Parallel Models and Algorithms
Models of Parallel Computation:
PRAMs; Scan Vector Model; Complexity measures
Designing Parallel Algorithms:
Basic PRAM techniques; Doubling technique; Summation trees and prefix summation
Graph models of networks; Network properties; Searching and sorting on meshes
Sorting and Searching on PRAMs:
Merge sort; Compare-exchange sorts; Batcher‟s sorting algorithms; Computing the Median
List ranking; Tree contraction; Connected components; Minimum spanning tree; All-pairs shortest path
Convex hulls; Closest pair of points; Visibility
PART II: Distributed Models and Algorithms
Concepts of distributed computation:
Termination; Failure tolerance; Network topology
Random walks; Introduction to Markov processes; Random walks (hitting time, cover time (s.t)-connectivity
Broadcasting; Robust distributed networks
To understand the major concepts and problems of computational molecular biology. To appreciate the importance of these concepts in a wide diversity of practical applications. To learn which of the computational molecular biology problems have efficient algorithmic solutions and which are intractable (for example, which belong to the NP-complete complexity class). For some intractable problems, to understand how heuristic approaches to problem solutions may yield fast but only approximate solutions.
On completing the module you should be able to design exact and efficient algorithms as well as approximation schemes and heuristics for some of the most important algorithms underlying the field of computational molecular biology, or bioinformatics. You will also be able to reason why efficient algorithms for certain problems might not be possible.
Basic concepts: Definitions and notions from Molecular Biology; DNA Sequence Analysis
Hamming and Levenshtein distances
Dynamic programming algorithm
Substitution matrices (BLOSSUM, PAM) and scoring
Seq vs Seq (Fasta, Dynamic Programming)
Seq vs Databank (BLAST)
Whole genome alignment
Multiple sequence alignment
Approximate string matching:
String matching with "don't cares"
Searching with differences
Searching with mismatches
Regular expressions, acceptor and donor sites
Secondary structure prediction:
Minimal free energy (Zuker's approach)
Mapping and rearrangements
Clustering and classification techniques
The aim of this module is to define, analyse and compare abstract models of computation and their associated programming paradigms.
On successfully completing the module you should be able to demonstrate a deep knowledge and understanding of the fundamentals of formal languages and the principal models of computation and be able to work with theoretical/research-based knowledge at the forefront of the subject; judiciously apply and combine tools and techniques (frequently in novel ways) to solve a range of complex subject-specific problems with minimal direction; analyse subject material, draw inferences, and find relationships that demand that innovative thinking be engaged in and creativity be exhibited in formulating solutions; critically evaluate, exercise judgement, and compare and contrast relevant material with minimal guidance and to consider and argue for alternative, novel approaches; demonstrate a high degree of independence in managing your own learning and reflecting upon it in order to complete research tasks autonomously.
Introduction to abstract models of computation
Finite Automata, Push-Down Automata and applications to parsing
To introduce both theoretical and practical aspects of cryptography, authentication and information security.
On successful completion of this module, you should be able to understand the relevant mathematical techniques associated with cryptography; understand the principles of cryptographic techniques and perform implementations of selected algorithms in this area; appreciate the application of security techniques in solving real-life security problems in practical systems.
You should note that this module contains several advanced mathematical techniques. For students having a reasonable mathematical background, it should not be a problem. Explanations are given during the lectures/tutorials and examples are studied in details. Nevertheless, an in-depth understanding of these techniques is required for the examination and personal work has to be anticipated.
Basic terminology and concepts:
Goals of cryptography, terminology and notation players; Basic cryptographic functions
Number theory preliminaries:
Congruent modulo n, equivalent class modulo n; Integer modulo n (Zn):
Relatively prime; Euler‟s theorem; Fermat‟s little theorem:
EEA (Extended Euclidean Algorithm)
CRT (Chinese Remainder Theorem)
Block ciphers (substitution, transposition, product); Stream ciphers; Modes of operation (ECB, CBC, CFB, OFB)
Block cipher: DES (Data Encryption Standard), AES (Advanced Encryption Standard)
Public-key: RSA (Rivest-Shamir-Adelman), El gamal
One-way hash function: SHA and MD5 (Message Digest 5)
Symmetric and asymmetric techniques (Diffie-Hellman, Needham-Schroeder, Otway-Rees)
Public-key encryption, basic and advanced Kerberos protocols
Authentication and identification:
Concepts; Fiat-Shamir and Feige-Fiat-Shamir protocols; Zero-knowledge identification protocol
Classification; Digital signature schemes: RSA; El-Gamal; DSA (Digital Signature Algorithm) and DSS (Digital Signature Standard)
Password systems: number of acceptable passwords for a given password policy, exhaustive search
Introduction to viruses, secure communication, social engineering (phishing), firewalls, buffer overflow, denial of services
The aims of this module are to study methods for handling and compressing various kinds of data, such as text, images, audio and video data and understand data compression techniques for multimedia and other applications, in particular to the Internet.
On successfully completing this module you should have depth and systematic understanding of the principles of data compression, be able to apply different compression methods for text, image, audio, and video data, and extend their applications in different aspects of computing.
Raw multimedia data representation
Transmission medium characteristics
Adaptive and non-adaptive methods
Lossy and lossless compression
Theoretical limits of compressibility
Entropy coders: Huffman coding, arithmetic coding
Dictionary coding methods: LZ77, LZW
Other text compression methods: PPM
Standard text compression utilities: compress, zip
Monochrome and grayscale compression
Image formats: PCX, TIFF, BMP, DIB, GIF, EPS, WMF, TGA, CGM, HPGL, JPEG and PNG
JPEG compression (using Discrete Cosine Transform)
JPEG 2000 (using wavelets)
Frame-by-frame compression: M-JPEG
Inter-frame compression: MPEG
Video formats: M-JPEG, MPEG, AVI and MOV
Speech coding: ADPCM, LPC
CD-quality audio: MPEG layer 3
Audio formats: WAV, VOC, SND and MIDI
Computer system applications
Communication network applications
Broadcast media applications
Consumer electronics applications
Managing compressed data:
Self-identifying compressed data
Error-proofing compression algorithms
Interaction between compression and other functions
Interaction between compression algorithms
Operating on compressed data
Archiving compressed data
Hypermedia and interactive applications, MHEG
Interactive virtual reality, VRML
To introduce various discrete optimisation problems, efficient algorithms for solving these problems, and general algorithmic techniques, which can be applied to a wide range of optimisation problems. The emphasis is put on network optimisation problems and on general optimisation techniques. To discuss applications of optimisation problems in communication systems, computer networks, manufacturing, scheduling, and resource allocation.
On successfully completing this module you will be able to express computational problems from various application areas as (discrete) optimisation problems; will be familiar with commonly used algorithms and main algorithmic techniques for optimisation problems; will understand the principles underpinning the discussed algorithms; will be able to select an appropriate algorithm for a given optimisation problem or to develop a new algorithm based on a general algorithmic technique; will be able to analyse the running time of the developed algorithmic solutions.
Single-source shortest-paths problem:
The Bellman-Ford algorithm
Shortest paths in directed acyclic graphs
All-pairs shortest paths:
Network flow problems:
Maximum flows, Minimum-cost flows and Multicommodity flows, and their applications
Maximum matching problem and its applications to resource allocation problems
The Ford-Fulkerson method for the maximum-flow problem
The Successive-shortest-paths algorithm for the minimum-cost flow problem
Linear programming (LP):
Basic properties of LP problems
LP formulation of network flow problems
Computationally hard optimisation problems:
Polynomial-time problems and NP problems
NP-hard optimisation problems
Optimisation techniques for NP-hard problems:
Branch-and-bound method for finding exact solutions
Simulated annealing Genetic algorithms
This unit is devoted to algorithms processing strings and texts efficiently. These types of algorithms are used for software design in the domains of operating systems utilities, search engines on the Internet, data retrieval systems, analysis of genetic sequences, and natural language processing, for example.
On completing the module, you should be able to design and implement exact and efficient algorithms for matching patterns in textual data, building indexes for files, and more generally for solving algorithmic problems on strings and sequences.
Periods in strings
Finite automata and regular expressions
Exact pattern matching:
Brute-force algorithms for pattern matching
The Knuth-Morris-Pratt algorithm
The Boyer-Moore algorithm
The Karp-Rabin algorithm
Multiple pattern matching:
The Aho-Corasick automaton
Two-dimensional pattern matching
Structures for indexes:
Regular Pattern Matching
From regular expression to automata
Simulation of deterministic automata
2:1 honours UK BSc degree, or equivalent, in computer science, mathematics, physics, chemistry, electrical engineering, or a joint degree in two such subjects. Competence in a high level programming language such as Pascal, C, C++, Java, etc, to the level expected at the end of the first year of a BSc honours degree in computer science. We may lower entry qualifications for students with substantial relevant work experience.
Your application will be reviewed by the admissions tutor and we aim to respond to applications within four weeks, although this may take longer during busy and holiday periods.
Please submit a one page personal statement with your application, explaining why you wish to apply for this programme and why you feel it matches your interests, academic background, and, if relevant, your career plans. Please include transcript of subjects taken in the relevant degrees and copies of all certificates and relevant qualifications mentioned in your application.
At King's we have one of the largest research groups on algorithm design in the UK and our annual algorithms workshop attracts top-ranked international scientists. As algorithms have such a big impact for practical solutions we are also collaborating with companies from sectors such as mobile phones, finance and biomedicine.
My research interests focus on designing algorithms that find approximate solutions for such problems and enable the user to control the trade-off between the computational time required and the quality of the solution found within this time. This involves looking very carefully at the structure of a problem and the input data required as well as analysing the performance of the developed algorithm. I am using design methods that utilise the power of randomness and are often based on local search techniques. It is truly amazing to see what difference these algorithms make with respect to finding solutions to a problem and the size of input data that they can handle.