Skip to navigation | Skip to main content | Skip to footer
Menu
Menu

COMP36212: Advanced Algorithms II (2012-2013)

This is an archived syllabus from 2012-2013

Advanced Algorithms II
Level: 3
Credit rating: 10
Pre-requisites: No Pre-requisites
Co-requisites: No Co-requisites
Duration: 12 weeks
Lectures: 24 (2 hours/week)
Course Leader: Pedro Mendes
Additional Lecturers: Milan Mihajlovic, Eva Navarro-Lopez
Course leader: Pedro Mendes

Additional staff: view all staff
Timetable
SemesterEventLocationDayTimeGroup
Sem 2 Lecture 1.5 Fri 11:00 - 12:00 -
Sem 2 Lecture 1.5 Thu 11:00 - 12:00 -
Assessment Breakdown
Exam: 75%
Coursework: 25%
Lab: 0%

Themes to which this unit belongs
  • Programming and Algorithms

Introduction

This course will explore certain classes of algorithms for modelling and analysing complex systems, as arising in nature and engineering. These examples include: flocking algorithms - e.g., how schools of fish or flocks of birds synchronised; optimisation algorithms; stability and accuracy in numerical algorithms.

Aims

By the end of the course, students should:

- appreaciate the role of using nature-inspired algorithms in computationally hard problems,

- be able to apply what they learnt across different disciplines,

- appreciate the emergence of complex behaviours in networks not present in the individual network elements.

Programme outcomeUnit learning outcomesAssessment
A2 B1 B2 B3 C5 D6Apply basic concepts to describe representative network models.
  • Lab assessment
  • Individual coursework
  • Examination
A2 B1 B2 B3 C5 D6Understand the dynamical properties implications of the structure of a network on individual elements and vice versa.
  • Individual coursework
  • Lab assessment
  • Examination
A2 B1 B2 B3 C5 D6Develop numerically stable and accurate algorithms.
  • Examination
  • Individual coursework
  • Lab assessment

Syllabus

PART 1: OPTIMISATION AND NATURE-INSPIRED ALGORITHMS (8 hours)

1. Introduction to optimisation algorithms (2 hours)

1.1 - applications for optimisation algorithms
1.2 - local and global optimisation
1.3 - methods based on derivatives
1.4 - direct search methods

2. Stochastic optimisation (2 hours)

1.1 - grid search, random searches, multistart
1.2 - Simulated annealing
1.3 - particle swarm

3. Evolutionary algorithms (4 hours)

1.1 - basics of genetics and evolution
1.2 - evolutionary programming
1.3 - genetic algorithms
1.4 - evolution strategies
1.5 - genetic programming


PART 2: COMPLEX NETWORKS AND COLLECTIVE BEHAVIOUR (8 hours)

Complex networks are groups of systems (normally, a big number of them) interconnected in a non-trivial and non-regular way

1. Introduction to complex networks (2 hours)

1.1. Where are the networks and the complexity?
1.2. Characterisation of complex networks
1.3. Basic network properties and terminology. Topological analysis

2. Complex network models. The structure of the network (2 hours)

2.1. Regular networks
2.2. Random-graph networks
2.3. Small-world networks
2.4. Scale-free networks

3. Network dynamics and collective behaviour (3 hours)

3.1. Distributed/local versus centralised/global
3.2. The concept of self-organisation
3.3. Synchronisation in complex dynamical networks
3.4. Consensus over complex networks
- Swarm dynamics
- Consensus protocols
- Flocking algorithms


PART 3: NUMERICAL STABILITY AND ACCURACY OF COMPUTATIONS (8 hours)

1. Introduction to finite precision computation (2 hours)

2. Floating point arithmetic (examples that include error analysis in
summation, evaluation of polynomials, recurrences, and basic linear algebra)
(3 hours)

3. Mixed precision algorithms (basic concept of iterative refinement,
different speed of execution on different architectures, linear algebra
examples) (1 hour)

4. Numerical solution of initial value problems (explicit/implicit methods,
multistep methods, consistency, stability, convergence) (2 hours)

Reading List

Title: Networks: an introduction
Author: Newman, M.E.J.
ISBN: 9780199206650
Publisher: Oxford University Press
Edition:
Year: 2010


Title: Lectures on complex networks
Author: Dorogovtsev, Sergey N.
ISBN: 9780199548934
Publisher: Oxford University Press
Edition:
Year: 2010


Title: Stochastic optimization
Author: Schneider, J.J. and S. Kirkpatrick
ISBN: 9783540345596
Publisher: Springer
Edition:
Year: 2006


Title: Small worlds: the dynamics of networks between order and randomness
Author: Watts, Duncan J.
ISBN: 9780691117041
Publisher: Princeton University Press
Edition:
Year: 2003


Title: Introduction to genetic algorithms
Author: Mitchell, Melanie
ISBN: 0262133164
Publisher: MIT Press
Edition:
Year: 1996


Title: Self-organization of complex structures: from individual to collective dynamics
Author: Schweitzer, Frank (ed.).
ISBN: 9789056990275
Publisher: CRC Press
Edition:
Year: 1997


Title: Practical methods of optimization (2nd edition)
Author: Fletcher, R.
ISBN: 9780471494638
Publisher: Wiley
Edition: 2nd
Year: 2000


Title: Accuracy and stability of numerical algorithms (2nd edition)
Author: Higham, Nicholas J.
ISBN: 9780898715217
Publisher: SIAM (Society for Industrial and Applied Mathematics)
Edition: 2nd
Year: 2002


Title: Introduction to numerical analysis
Author: Suli, Endre and David Mayers
ISBN: 9780521007948
Publisher: Cambridge University Press
Edition:
Year: 2003


Title: Dynamical processes on complex networks
Author: Barrat, Alain and Marc Barthelemy and Alessandro Vespignani
ISBN: 9780521879507
Publisher: Cambridge University Press
Edition:
Year: 2008


Title: Structure and dynamics of networks
Author: Newman, Mark and Albert-Laszlo Barabasi and Duncan J. Watts (eds.).
ISBN: 9780691113579
Publisher: Princeton University Press
Edition:
Year: 2006


Title: Self-organization in biological systems
Author: Camazine, Scott et al.
ISBN: 9780691116242
Publisher: Princeton University Press (Princeton Studies in Complexity)
Edition:
Year: 2001


Title: Sync: the emerging science of spontaneous order
Author: Strogatz, Steven
ISBN: 9780141007632
Publisher: Penguin
Edition:
Year: 2004