# COMP36212 Advanced Algorithms 2 syllabus 2014-2015

Level 3
Credits: 10
Enrolled students: 34

Assessment methods

• 75% Written exam
• 25% Coursework
Timetable
SemesterEventLocationDayTimeGroup
Sem 2 Lecture Hum Bridge St G6 Thu 11:00 - 12:00 -
Sem 2 Lecture 1.4 Fri 11:00 - 12:00 -
Themes to which this unit belongs
• Programming and Algorithms

## Overview

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.

## Syllabus

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

1. Introduction to optimisation algorithms (2 hours)
• applications for optimisation algorithms
• local and global optimisation
• methods based on derivatives
• 1.4 - direct search methods
2. Stochastic optimisation (2 hours)
• grid search, random searches, multistart
• Simulated annealing
• particle swarm
3. Evolutionary algorithms (4 hours)
• 3.1 - basics of genetics and evolution
• 3.2 - evolutionary programming
• 3.3 - genetic algorithms
• 3.4 - evolution strategies
• 3.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)
• Where are the networks and the complexity?
• Characterisation of complex networks
• Basic network properties and terminology. Topological analysis
2. Complex network models. The structure of the network (2 hours)
• Regular networks
• Random-graph networks
• Small-world networks
• Scale-free networks
3. Network dynamics and collective behaviour (3 hours)
• Distributed/local versus centralised/global
• The concept of self-organisation
• Synchronisation in complex dynamical networks
• 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 insummation, 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 algebraexamples) (1 hour)
4. Numerical solution of initial value problems (explicit/implicit methods,multistep methods, consistency, stability, convergence) (2 hours)

## Teaching methods

Lectures

24 (2 hours/week)

## Feedback methods

Oral and written feedback

## Study hours

• Assessment written exam (2 hours)
• Lectures (24 hours)

## Employability skills

• Analytical skills
• Group/team working
• Research

## Learning outcomes

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.
• Lab assessment
• Examination
• Individual coursework
A2 B1 B2 B3 C5 D6Develop numerically stable and accurate algorithms.
• Examination
• Individual coursework
• Lab assessment

TitleAuthorISBNPublisherYearCore
Introduction to genetic algorithmsMitchell, Melanie0262133164MIT Press1996
Structure and dynamics of networksNewman, Mark and Albert-Laszlo Barabasi and Duncan J. Watts (eds.).9780691113579Princeton University Press2006
Networks: an introductionNewman, M.E.J.9780199206650Oxford University Press2010
Dynamical processes on complex networksBarrat, Alain and Marc Barthelemy and Alessandro Vespignani9780521879507Cambridge University Press2008
Stochastic optimizationSchneider, J.J. and S. Kirkpatrick9783540345596Springer2006
Self-organization of complex structures: from individual to collective dynamicsSchweitzer, Frank (ed.).9789056990275CRC Press1997
Lectures on complex networksDorogovtsev, Sergey N.9780199548934Oxford University Press2010
Small worlds: the dynamics of networks between order and randomnessWatts, Duncan J.9780691117041Princeton University Press2003
Practical methods of optimization (2nd edition)Fletcher, R.9780471494638Wiley2000
Sync: the emerging science of spontaneous orderStrogatz, Steven9780141007632Penguin2004
Introduction to numerical analysisSuli, Endre and David Mayers9780521007948Cambridge University Press2003
Self-organization in biological systemsCamazine, Scott et al.9780691116242Princeton University Press (Princeton Studies in Complexity)2001
Accuracy and stability of numerical algorithms (2nd edition)Higham, Nicholas J.9780898715217SIAM (Society for Industrial and Applied Mathematics)2002