Design of Algorithms

Summary

This course is concerned with issues that arise in the design of algorithms for solving computational problems. In the first part methods a number of standard algorithm design paradigms are presented and example applications of these examined. In the second part of the course some theoretical issues in algorithm design are examined: the concepts of computability and computational tractability are introduced and some examples of computational problems with no feasible algorithmic solution are presented.

Detailed Syllabus

1. Introduction: Algorithm design paradigms - motivation; concepts of algorithmic efficiency; run-time analysis of algorithms; the Landau notation;
2. Divide-and-Conquer: Structure of divide-and-conquer algorithms; example applications from Binary Search, Integer Multiplication, Nearest Neighbour. Analysis of divide-and-conquer run-time recurrence relations.
3. Dynamic Programming: Form of dynamic programming algorithms; differences between dynamic programming and Divide-and-Conquer; example applications from: shortest path in graphs; ordering of matrix multiplications; longest common subsequence.
4. Greedy Methods: Overall view of greedy paradigm. Example of exact optimisation solution (Minimum spanning tree) and approximation solution (Integer Knapsack).
5. Graph Searching and traversal: Pervasiveness of graph models in applications and notion of search; combinatorial search (e.g. Knight's Tour); graph traversal methods: depth-first and breadth-first search;
6. Foundations of algorithms: Fundamental questions in the design of algorithms: does an algorithmic solution exist? does an efficient algorithmic solution exist? Models of algorithmic process and their universality: Church-Turing hypothesis.
7. Introduction to Computability: The existence of problems with no algorithmic solution; an example and proof that a specific computational problem has no algorithmic solution.
8. Computational Complexity: Quantification of resources used by algorithms: Time and Space; Complexity measures and Classes; Polynomial versus Non-Polynomial time complexity; the class P and motivation for viewing this as the set of tractable computational problems.
9. NP-completeness: Combinatorial search and optimisation problems; informal view of the case NP as problems with efficient checking algorithms; approaches to tackling the question of P = NP - informal review of NP-completeness, Cook's Theorem (without proof).

Recommended Texts:

1. M.A. Weiss; Data Structures and Algorithm Analysis in ADA; Benjamin Cummings Publishing; 1993
2. P.E. Dunne; Computability Theory - concepts and applications; Ellis Horwood; 1991

PED Home Page