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

COMP36212: Advanced Algorithms II (2010-2011)

This is an archived syllabus from 2010-2011

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)
Lecturers: Pedro Mendes, Milan Mihajlovic, Eva Navarro-Lopez
Course lecturers: Pedro Mendes

Milan Mihajlovic

Eva Navarro-Lopez

Additional staff: view all staff
Timetable
SemesterEventLocationDayTimeGroup
Sem 2 Lecture 1.3 Wed 09:00 - 10:00 -
Sem 2 Lecture 1.3 Thu 12:00 - 13: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
  • Examination
  • Individual coursework
A2 B1 B2 B3 C5 D6Understand the dynamical properties implications of the structure of a network on individual elements and vice versa.
  • Individual coursework
  • Examination
  • Lab assessment
A2 B1 B2 B3 C5 D6Develop numerically stable and accurate algorithms.
  • Examination
  • Lab assessment
  • Individual coursework

Syllabus

PART 1: 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 2: 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 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

[1] A.-L. Barab?si. "Bursts: The Hidden Pattern behind Everything We Do". Dutton Adult, 2010.

[2] S. Camazine, J.-L. Deneubourg, N.R. Franks, J. Sneyd, G. Theraulaz, E. Bonabeau. "Self-organization in Biological Systems". Princeton Studies in Complexity, 2003.

[3] Z.P. Fan. "Complex Networks: From Topology to Dynamics". PhD Thesis. City University of Hong Kong. May, 2006.

[4] N.J. Higham. "Accuracy and Stability of Numerical Algorithms". Second Edition, SIAM, Philadelphia, 2002.

[5] M.E.J. Newman, A.-L. Barab?si, D.J. Watts. "The Structure and Dynamics of Networks". Princeton University Press, 2006.

[6] M.E.J. Newman. "Networks: An Introduction". Oxford University Press, 2010.

[7] F. Schweitzer (Editor). "Self-organization of Complex Structures. From Individual to Collective Dynamics". Gordon and Breach Publishers, 1997.

[8] E. Suli, D. Mayers. "An Introduction to Numerical Analysis". Cambridge University Press, Cambridge, 2003.

[9] D.J. Watts. "Small Worlds: The Dynamics of Networks between Order and Randomness". Princeton Studies in Complexity, 1999.

[10] R. Fletcher. "Practical Methods of Optimization" 2nd Edition, Wiley, 2000.

[11] J. Schneider, S. Kirkpatrick. "Stochastic Optimization" Springer, 2006.

[12] M. Mitchell. "An Introduction to Genetic Algorithms" MIT Press, 1995.