Aims

Knowledge of a range of key application areas where algorithmic solutions are required.
Understand the key issues in algorithm design.
Understand what makes a "good" algorithm.
Explore range of techniques that can be employed in the design of various types of algorithm.
Analyse the properties of key algorithms in terms of their time and space complexity.
Provide practical experience of implementing a range of algorithms.

This module provides an introduction to the design and analysis of algorithms. It begins by considering a range of illustrative application areas including sorting, searching and numerical algorithms. It then looks in more detail at key techniques for designing algorithmic solutions and introduces approaches for analysing algorithms.

Outline Of Syllabus

Discrete Structures – basics of counting
•       Solving recurrence relations
•       Common examples
•       The Master theorem
Discrete Structures – graphs and trees
•       Spanning trees/forests
•       Traversal strategies
Algorithms and Complexity – basic analysis
•       Asymptotic analysis of upper and average complexity bounds
•       Identifying differences among best, average, and worst case behaviours
•       Big O, little o, omega, and theta notation
•       Standard complexity classes
•       Empirical measurements of performance
•       Time and space tradeoffs in algorithms
•       Using recurrence relations to analyze recursive algorithms
Algorithms and Complexity – algorithmic strategies
•       Brute-force algorithms
•       Greedy algorithms
•       Divide-and-conquer
•       Backtracking
•       Branch-and-bound
•       Heuristics
•       Pattern matching and string/text algorithms
•       Numerical approximation algorithms
Algorithms and Complexity – fundamental algorithms
•       Simple numerical algorithms
•       Sequential and binary search algorithms
•       Quadratic sorting algorithms (selection, insertion)
•       O(N log N) sorting algorithms (Quicksort, heapsort, mergesort)
•       Hash tables, including collision-avoidance strategies
•       Binary search trees
•       Representations of graphs (adjacency list, adjacency matrix)
•       Depth- and breadth-first traversals
•       Shortest-path algorithms (Dijkstra’s and Floyd’s algorithms)
•       Transitive closure (Floyd’s algorithm)
•       Minimum spanning tree (Prim’s and Kruskal’s algorithms)
Algorithms and Complexity – geometric algorithms
•       Closest pair
•       Convex hull finding algorithms
Algorithms and Complexity – advanced analysis
•       Online and offline algorithms
Algorithms and Complexity – P versus NP
•       Standard NP-complete problems

Teaching Rationale And Relationship

Techniques, theory and examples are presented in lectures. Examples and practice exercises are undertaken in the tutorial. Further exercise work takes place during the private study hours.

Assessment Rationale And Relationship

Each examination will cover the material taught in lectures.
An important objective of the course is to develop students' practical abilities in designing, analysing and implementing algorithms. This will be assessed by coursework that cover these key aspects.

Study abroad students considering this module should contact the School to discuss its availability and assessment.

N.B. This module has both “Exam Assessment” and “Other Assessment” (e.g. coursework). If the total mark for either assessment falls below 35%, the maximum mark returned for the module will normally be 35%.