Academic session	2018-19
Module	Algorithms
Code	COMP0005
Module delivery	1819/A4U/T2/COMP0005 Undergraduate
Related deliveries	None
Prior deliveries	COMP104P
Level	Undergraduate
FHEQ Level	L4
FHEQ credits	15
Term/s	Term 2
Module leader	Yasin, Ifat
Contributors	Yasin, Ifat Cox, Ingemar
Module administrator	Ball, Louisa

Aims

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.

Learning outcomes

On successful completion of the module, a student will be able to:

1. 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:	BSc Computer Science (Year 1) MEng Computer Science (International Programme) (Year 1) MEng Computer Science (Year 1) MEng Mathematical Computation (International Programme) (Year 1) MEng Mathematical Computation (Year 1)
Prerequisites:	In order to be eligible to select this module, students must have taken in Term 1: Theory of Computation (COMP0003)

Content

Searching and sorting algorithms

• Elementary searching – Linear and binary search
• Binary search trees.
• Hash Tables – Hashing, Hash functions

Graph algorithms

• Directed acyclic graphs.
• PERTchart
• Dijkstra’s algorithm
• Bellman-Ford algorithm
• Floyd-Warshall algorithm

Text algorithms

• String matching
• Longest Common Sequence.
• Sequence/subsequence

Analysis of algorithms

• Algorithmic complexity.
• Upper and lower bounds
• O notation.
• Best, worst and average cases.
• Classifications of algorithms.

Linked Lists

• Linked structures
• Singly-linked list, Doubly-linked list
• Circular linked list

Abstract Data Types

• ADTs
• Defining the ADT
• Implementing the ADT
• Implementing the ADT
• Bag ADT
• List-based Implementation
• Queue ADT

Dynamic Programming

• Elements of dynamic programming
• Rod cutting
• Matrix-chain multiplication,
• Optimal binary search trees

Recursion

• Properties
• 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

Greedy Algorithms

• Elements of greedy strategy
• Huffman codes
• Matroids

An indicative reading list is available via http://readinglists.ucl.ac.uk/modules/comp0005.html

Delivery

The module is delivered through a combination of lectures and coursework

Assessment

This module delivery is assessed as below:

#	Title	Weight (%)	Notes
1	Coursework 1	30
2	Coursework 2	30
3	Written examination (2hrs)	40

In order to pass this module delivery, students must achieve an overall weighted module mark of 40%.