This database contains the 2018-19 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).
To develop programming and problem solving skills, to encourage a thoughtful approach to analysis and design problems, to familiarise students with logical and mathematical inference and argumentation.
On successful completion of the module, a student will be able to:
- apply this knowledge to specification of algorithms and logic programming.
Availability and prerequisites
This module delivery is available for selection on the below-listed programmes. The relevant programme structure will specify whether the module is core, optional, or elective.
In order to be eligible to select this module as optional or elective, where available, students must meet all prerequisite conditions to the satisfaction of the module leader. Places for students taking the module as optional or elective are limited and will be allocated according to the department’s module selection policy.
Programmes on which available:
In order to be eligible to select this module, students must have taken in Term 1:
Searching and sorting algorithms
- Elementary searching – Linear and binary search
- Binary search trees.
- Hash Tables – Hashing, Hash functions
- Directed acyclic graphs.
- Dijkstra’s algorithm
- Bellman-Ford algorithm
- Floyd-Warshall algorithm
- String matching
- Longest Common Sequence.
Analysis of algorithms
- Algorithmic complexity.
- Upper and lower bounds
- O notation.
- Best, worst and average cases.
- Classifications of algorithms.
- Linked structures
- Singly-linked list, Doubly-linked list
- Circular linked list
Abstract Data Types
- Defining the ADT
- Implementing the ADT
- Implementing the ADT
- Bag ADT
- List-based Implementation
- Queue ADT
- Elements of dynamic programming
- Rod cutting
- Matrix-chain multiplication,
- Optimal binary search trees
- Run time stack, tail recursion
- Recursive applications, recursive binary search, exponential operation
Analysis of searching and sorting algorithms
- Binary search.
- Selection sort, Insertion sort, mergesort, quicksort, radix sort
- Bubble sort, lower bounds for sorting
- Working with sorted lists
- Heapsort, building a heap, heaspsort algorithm, priority queues
- Elements of greedy strategy
- Huffman codes
An indicative reading list is available via http://readinglists.ucl.ac.uk/modules/comp0005.html
The module is delivered through a combination of lectures and coursework
This module delivery is assessed as below:
Written examination (2hrs)
In order to pass this Module Delivery, students must:
- achieve an overall weighted Module mark of at least 40.00%;
AND, when taken as part of BSc Computer Science; MEng Computer Science, and MEng Mathematical Computation:
- achieve a mark of at least 30.00% in any Components of assessment weighed ≥ 30% of the module.
Where a Component comprises multiple Assessment Tasks, the minimum mark applies to the overall component.