Algorithms

Learning Outcomes

Knowledge and Understanding

Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:

• Understand the concept of NP-completeness and its implications
• Understand why algorithms for a range of problems including sorting, shortest path, network flow, matchings, produce the correct solution, and apply these algorithms to given instances
• Analyse the worst-case running time of an algorithm

Subject Specific Intellectual and Research Skills

Having successfully completed this module you will be able to:

• Derive worst-case performance bounds for some simple algorithms

Subject Specific Practical Skills

Having successfully completed this module you will be able to:

• Design an algorithm for certain types of problem

Basic concepts.

Introduction to algorithms. Recap on computational complexity and asymptotic estimates of running times and on sorting algorithms.

Divide and conquer algorithms.

Examples on sorting, scalar multiplication, and matrix multiplication.

Graphs and networks.

Basic graph theory definitions. Algorithms for the reachability problem in a graph.

Spanning trees.

Algorithms for finding a minimum-cost spanning tree in a graph.

Shortest paths.

Algorithms for finding one or more shortest paths in graph with nonnegative arc or general arc lengths but not negative length circuits.

Network flow algorithms.

Flows in capacitated networks, algorithms to find a maximum flow in a network and max-flow min-cut theorems.

Matchings.

Elements of matching theory, including algorithms to find an optimal weighted and unweighted matching in bipartite graphs, the Koenig-Egervary theorem and the relationship with the vertex cover problem.

Computational complexity theory.

The P and NP classes. Polynomial reductions. NP-completeness and NP-hardness.

Elements of exponential-time algorithms.

Elements of branch and bound.

Elements of dynamic programming

Lectures, problems class, private study

Summative

This is how we’ll formally assess what you have learned in this module.

Referral

This is how we’ll assess you if you don’t meet the criteria to pass this module.