COMP36212: Advanced Algorithms II (2010-2011)
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.
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 outcome||Unit learning outcomes||Assessment|
|A2 B1 B2 B3 C5 D6||Apply basic concepts to describe representative network models.|
|A2 B1 B2 B3 C5 D6||Understand the dynamical properties implications of the structure of a network on individual elements and vice versa.|
|A2 B1 B2 B3 C5 D6||Develop numerically stable and accurate algorithms.|
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. 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)
 A.-L. Barab?si. "Bursts: The Hidden Pattern behind Everything We Do". Dutton Adult, 2010.
 S. Camazine, J.-L. Deneubourg, N.R. Franks, J. Sneyd, G. Theraulaz, E. Bonabeau. "Self-organization in Biological Systems". Princeton Studies in Complexity, 2003.
 Z.P. Fan. "Complex Networks: From Topology to Dynamics". PhD Thesis. City University of Hong Kong. May, 2006.
 N.J. Higham. "Accuracy and Stability of Numerical Algorithms". Second Edition, SIAM, Philadelphia, 2002.
 M.E.J. Newman, A.-L. Barab?si, D.J. Watts. "The Structure and Dynamics of Networks". Princeton University Press, 2006.
 M.E.J. Newman. "Networks: An Introduction". Oxford University Press, 2010.
 F. Schweitzer (Editor). "Self-organization of Complex Structures. From Individual to Collective Dynamics". Gordon and Breach Publishers, 1997.
 E. Suli, D. Mayers. "An Introduction to Numerical Analysis". Cambridge University Press, Cambridge, 2003.
 D.J. Watts. "Small Worlds: The Dynamics of Networks between Order and Randomness". Princeton Studies in Complexity, 1999.
 R. Fletcher. "Practical Methods of Optimization" 2nd Edition, Wiley, 2000.
 J. Schneider, S. Kirkpatrick. "Stochastic Optimization" Springer, 2006.
 M. Mitchell. "An Introduction to Genetic Algorithms" MIT Press, 1995.