|
| STUDENTS
> Algorithmics
|
Algorithmics
Note:
Whilst every effort is made to keep the syllabus and assessment records correct
for this course, the precise details must be checked with the lecturer(s).
| Code: | GC05
(previously D104)
|
| Year: | MSc |
| Prerequisites: | This course should be taken in conjunction with the core courses for this programme (ie GC01, GC02, GC03 and GC04) |
| Term: | 2 |
| Taught By: | Denise Gorse (50%)
Anthony Steed (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.
|
Content:
| Course Introduction | 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. Exceptions.
Data aggregation: arrays, structures and object references. |
| Linear abstract data types | Stacks and queues. Implementations
with arrays and linked lists. Applications.
Sequences. Implementations with
arrays and linked lists. Circular and double linked lists.
Inheritance relationships between linear linked lists |
| Tables | Linear look-up table.
Linear search.
Binary search. |
| Trees | Definitions of trees.
Binary search tree.
Insertion, deletion, tree traversal and searching. |
| Hash tables | Chaining.
Open addressing.
Choice of hash function. |
| Graphs | Adjacency lists.
Adjacency matrices.
Depth and breadth first traversal. |
| Sorting | Insertion Sort
Mergesort
Quicksort |
| 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
Undecidability; the Halting Problem |
Method of Instruction:
Lecture presentations, coursework and associated class problems .
Assessment:
The course has the following assessment components:
- Written Examination (2.5 hours, 90%)
- Coursework Section (2 pieces, 10%)
To pass this course, students must:
- Obtain an average of at least 50% when the coursework and exam components of a course are weighted together
The examination rubric is:
Answer any 3 questions, at least ONE from EACH of Sections A and B, all questions carry equal marksResources:
Algorithmics - the science of computing. D.
Harel, Addison-Wesley, 1989.
|
