COMPGC05 - Algorithmics
This database contains the 2017-18 versions of syllabuses.
Note: Whilst every effort is made to keep the syllabus and assessment records correct, the precise details must be checked with the lecturer(s).
|Prerequisites||This course should be taken in conjunction with the core courses for MSc Computer Science and MSc Financial Computing.|
|Taught By||Denise Gorse (50%)|
Jens Krinke (50%)
|Aims||To introduce more formal aspects of algorithms and data structures than in the first term. Properties of data types such as queues and search trees. Techniques for analysing the complexity and decidability of algorithms. Formal models of computation.|
|Learning Outcomes||Knowledge of a selection of standard data structures and abstract data types. The ability to choose appropriate data structures for programming problems. Understanding of a variety of common algorithms and why some are more efficient than others. Ability to discuss uncomputable and intractable algorithms.|
- Introduction to data structures and abstract data types.
- Abstract data types and Java classes.
- Language facilities.
- Model of storage in imperative languages.
- Cells, l-values and r-values.
- Data aggregation:
- Object references.
Linear abstract data types
- Stacks and queues.
- Implementations with arrays and linked lists.
- Circular and double linked lists.
- Inheritance relationships between linear linked lists.
- Linear look-up table.
- Linear search.
- Binary search.
- Definitions of trees.
- Binary search tree.
- Tree traversal.
- Open addressing.
- Choice of hash function.
- Adjacency lists.
- Adjacency matrices.
- Depth and breadth first traversal.
Analysis of Algorithms
- Empirical vs theoretical analysis.
- Algorithmic complexity.
- O notation.
- Best, worst, and average cases.
- Sums of series.
- Simple summation formulae.
Analysis of earlier examples
- Includes linear and binary search.
Limits of Computation
- Tractable and intractable problems.
- The complexity classes P, NP, NPC.
- The Halting Problem.
Method of Instruction
Lecture presentations, coursework and associated class problems.
The course has the following assessment components
- Written Examination (2.5 hours, 85%)
- Coursework Section (15%, 5 pieces for 2% each, 1 piece for 5%)
To pass this course, students must:
- Obtain an overall pass mark of 50% for all sections combined.
Reading list available via the UCL Library catalogue.