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

COMP36212: Advanced Algorithms II (2011-2012)

This is an archived syllabus from 2011-2012

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.4 Wed 10:00 - 11:00 -
Sem 2 Lecture 1.4 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.
  • Examination
  • Lab assessment
  • 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
  • Lab assessment
  • Examination
A2 B1 B2 B3 C5 D6Develop numerically stable and accurate algorithms.
  • Lab assessment
  • Examination
  • Individual coursework

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: 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)

PART 3: 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

Reading List



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


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


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: 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: Practical methods of optimization (2nd edition)
Author: Fletcher, R.
ISBN: 9780471494638
Publisher: Wiley
Edition: 2nd
Year: 2000


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


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


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


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


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: Dynamical processes on complex networks
Author: Barrat, Alain and Marc Barthelemy and Alessandro Vespignani
ISBN: 9780521879507
Publisher: Cambridge University Press
Edition:
Year: 2008


Title: Networks (2nd edition)
Author: Newman, Mark
ISBN: 9780198805090
Publisher: Oxford University Press
Edition: 2nd
Year: 2018


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