COMP202

Complexity of Algorithms

Aims

  • To demonstrate how the study of algorithmics has been applied in a number of different domains.
  • To introduce formal concepts of measures of complexity and algorithms analysis.
  • To introduce fundamental methods in data structures and algorithms design.
  • To make students aware of computationally hard problems and possible ways of coping with them.

Syllabus

A) Efficiency of Algorithms and Complexity Measures

  1. Examples of algorithmic problems and introduction of complexity measures in terms of various resources (time, space, power consumption, number of exchanged messages, etc).  (1 lecture)
  2.  Asymptotic complexity and notation in conjunction with a discussion on the worst-case versus the average-case complexity. Also recurrence equations and master method. (2 lectures).

 B)   Algorithms and Data Structures

  1.  Introduction and analysis of basic data structures with their efficient implementation, including: stack (array), queue (cyclic buffer), and priority queue (heap). (3 lectures)
  2. Rooted trees - efficient data structures with implementation, from: tree traversal, binary search trees, balanced trees – AVL and 2-3 trees, Graphs and their implementations. (4 lectures)
  3. Advanced graph algorithms, including: network flow algorithms and bipartite matchings. (5 lectures)
  4.  Elementary number theory, Euclid’s GCD algorithm, cryptography (from: symmetric encryption, public-key cryptosystem, RSA). (4 lectures)
  5. Greedy algorithms and divide-and-conquer algorithms, dynamic programming (8 lectures)
  6. Text processing, including pattern matching (from: Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp), longest common subsequence (dynamic programming). (3 lectures)

 C)   Computational Intractability and NP-Completeness

  1.   Introduction:  Comparison of two ‘similar’ problems (Euler and Hamiltonian cycle);  other example problems:  3-Colouring, Satisfiability, k-Clique, etc;  Common features of the problems. (1 lecture)
  2.  TheComplexity Class NP:  formulation of computational problems in terms of questions about witnesses to solutions; completeness; background to Cook’s Theorem and its significance, intuitions behind Cook’s Theorem (2 lectures)
  3. Selected standard reductions:  SAT to 3-SAT, SAT to Clique (1 lecture)

Recommended Texts

Handbook
Algorithm Design, Michael T. Goodrich and Roberto Tamassia (John Wiley & Sons, Inc. 2002).

Further reading
Introduction to ALGORITHMS, TH Cormen, CE Leiserson, and RL Rivest, MIT Press/McGraw-Hill, 1989.

Learning Outcomes

At the conclusion of the module students should:

  • Have an appreciation of the diversity of computational fields to which algorithmics has made significant contributions.
  • Have fluency in using basic data structures (queues, stacks, trees, graphs, etc) in conjunction with classical algorithmic problems (searching, sorting, graph algorithms, security issues) and be aware of basic number theory applications, etc.
  • Be familiar with formal theories providing evidence that many important computational problems are inherently intractable, e.g., NP-completeness.

Learning Strategy

Formal lectures reinforced by practical illustrations and exercises.  Practical work will be carried out through the medium of the Department’s integrated Year 2 practical classes.