# COMP36111: Advanced Algorithms 1 (2010-2011)

## This is an archived syllabus from 2010-2011

Level: 3
Credit rating: 10
Pre-requisites: COMP20012 or INFO20006
Co-requisites: No Co-requisites
Duration: 11 weeks in second semester
Lectures: 22 lecture course but some lectures will be cancelled to provide time for assessed exercises.
Lecturers: Howard Barringer, Dave Lester, David Rydeheard
Course lecturers: Howard Barringer

Dave Lester

David Rydeheard

Timetable
SemesterEventLocationDayTimeGroup
Sem 1 Lecture 1.5 Tue 13:00 - 14:00 -
Sem 1 Lecture 1.5 Fri 15:00 - 16:00 -
Assessment Breakdown
Exam: 75%
Coursework: 25%
Lab: 0%

Themes to which this unit belongs
• Programming and Algorithms

## Aims

This unit provides an advanced course in algorithms, assuming the student already knows algorithms for common computational tasks, and can reason about the correctness of algorithms and understand the basics of computing the complexity of algorithms and comparing algorithmic performance.

The course focuses on the range of algorithms available for computational tasks, considering the fundamental division of tractable tasks, with linear or polynomial-time algorithms, and tasks that appear to be intractable, in that the only algorithms available are exponential-time in the worst case.

To examine the range of algorithmic behaviour and this fundamental divide, three topics are covered:

Examining a range of common computational tasks and algorithms available: We shall consider linear and polynomial-time algorithms for string matching tasks and problems that may be interpreted in terms of graphs. For the latter we shall consider the divide between tractable and intractable tasks, showing that it is difficult to determine what range of algorithms is available for any given task.
Complexity measures and complexity classes: How to compute complexity measures of algorithms, and comparing tasks according to their complexity. Complexity classes of computational tasks, reduction techniques. Deterministic and non-deterministic computation. Polynomial-time classes and non-deterministic polynomial-time classes. Completeness and hardness. The fundamental classes P and NP-complete. NP-complete tasks.
Intractable problems: Techniques for efficient computation: What to do in the case of intractable computational tasks? A range of possible approaches will be considered, including approximation techniques and randomised/probabilistic algorithms.

Advanced Algorithms (II): In the second semester a follow-up course unit is available. This course will explore classes of algorithms for modelling and analysing complex systems, as arising in nature and engineering. These examples include: flocking algorithms; optimisation algorithms; stability and accuracy in numerical algorithms.

Programme outcomeUnit learning outcomesAssessment
A2 B1 B2 B3 D6Be able to develop, and reason about the correctness and performance of, algorithms for string searching and for calculating over graphs.
• Lab assessment
• Examination
A2 B1 B2 B3 C5 D6Understand the distinction between linear and polynomial-time tasks, and those with exponential-time algorithms; tractable and intractable tasks.
• Lab assessment
• Examination
A2 B1 B2 B3 C5 D6Understand the general notion of complexity classes, P and NP, completeness and hardness, and the relationships between classes by reduction.
• Examination
• Lab assessment
A2 B1 B2 B3 C5 D6You will also have seen how to show tasks are NP-complete and know a range of NP-complete problems.
• Lab assessment
• Examination
A2 B1 B2 B3 C5 D6Have studied a range of techniques for approaching intractable tasks, including approximation methods and randomised/probabilistic algorithms, understand the key issues involved, and be able to use these techniques to develop algorithms.
• Lab assessment
• Examination

## Syllabus

Lecture sessions per topic are estimates.

Part 1: Introduction to algorithmic diversity

Introduction (1 lecture)

Overview, organisation, background, the key ideas of the course and their importance.

String searching: Linear and polynomial-time algorithms (1 lecture)

Introduction to string searching
Preconditioning techniques: Boyer-Moore and Knuth-Morris-Pratt algorithms
Survey of other techniques for string searching

Graphs and graph algorithms: Polynomial-time and exponential-time algorithms (3 lectures)

Review of graphs: basic ideas, terminology and basic concepts including paths,
connectivity and components, graph representation
Traversal techniques for trees and graphs, analysis and use in algorithms
Linear and polynomial-time graph algorithms
Exponential-time graph algorithms: the landscape and examples of tasks and algorithms.

Part 2: Algorithmic complexity and complexity classes (5-6 lectures)

Introduction to complexity
Polynomial Time and Space
NP Time and Space
Completeness and Hardness
SAT and Cook's Theorem
Proofs of NP-Completeness and examples of NP-complete problems

Part 3: Intractable problems: Techniques for efficient computation (3-4 lectures)

What to do in the case of intractable computational tasks?
Approximation techniques
Randomised/probabilistic algorithms. Examples of randomisation in use and performance issues

Title: Algorithms in Java (3rd edition): parts 1-4: fundamentals, data structures, sorting, searching
Author: Sedgewick, Robert (with Schidlowsky, Michael)
ISBN: 0201361205
Edition: 3rd
Year: 2003
Part 5 (graph algorithms) is separate volume: ISBN 0201361213

Title: Graph algorithms
Author: Even, Shimon
ISBN: 0914894218
Publisher: Computer Science Press
Edition:
Year: 1979

Title: Introduction to the theory of complexity
Author: Bovet, Daniel Pierre and Pierluigi Crescenzi
ISBN: 0139153802
Publisher: Prentice Hall
Edition:
Year: 1993

Title: Computer algorithms: introduction to design and analysis (3rd edition)
Author: Baase, Sara and Allen van Gelder
ISBN: 0201612445
Edition: 3rd
Year: 2000

Title: Algorithmic graph theory
Author: McHugh, James A.
ISBN: 0130236152
Publisher: Prentice-Hall
Edition:
Year: 1990

Title: Model checking
Author: Clarke, Edmund M., Orna Grumberg, and Doron A.Peled
ISBN: 0262032708
Publisher: MIT Press
Edition:
Year: 2000

Title: Randomized algorithms
Author: Motwani, Rajeev and Prabhakar Raghavan
ISBN: 0521474655
Publisher: Cambridge University Press
Edition:
Year: 1995

Title: String searching algorithms
Author: Stephen, Graham A.
ISBN: 9810237030
Publisher: World Scientific
Edition:
Year: 1994

Title: Fundamentals of algorithmics
Author: Brassard, Gilles and Paul Bratley
ISBN: 0133350681
Publisher: Prentice Hall
Edition:
Year: 1996

Title: Algorithms in Java (3rd edition): part 5: graph algorithms
Author: Sedgewick, Robert (with Schidlowsky, Michael)
ISBN: 0201361213
Edition: 3rd
Year: 2004
Parts 1-4 (fundamentals, data structures, sorting, searching) are one separate volume: ISBN 0201361205

Title: Introduction to automata theory, languages, and computation (3rd edition)
Author: Hopcroft, John E., Rajeev Motwani, and Jeffrey D.Ullman
ISBN: 9781292039053
Publisher: Pearson Education
Edition: 3rd
Year: 2014

Title: Graphs, networks and algorithms (3rd edition)
Author: Jungnickel, Dieter
ISBN: 9783540727798
Publisher: Springer
Edition:
Year: 2007

Title: Combinatorial optimization: algorithms and complexity
Author: Papadimitriou, Christos H. and Kenneth Steiglitz
ISBN: 9780486402581
Publisher: Dover
Edition:
Year: 2000