COMP36212 Advanced Algorithms 2 syllabus 2019-2020
This course consists of three interconnected parts. In the first part, the notion of finite precision computation will be introduced, including the details on precision and accuracy, error propagation through a computational process and accuracy and stability of numerical algorithms. In the second part, a class of algorithms for numerical solution of initial value problems which are modelling continuous-time dynamical systems are studied, followed by the techniques for examining stability of continuous-time linear dynamical systems. In the final part of the course, a class of algorithms will be introduced for modelling and analysing complex systems from nature and engineering. The examples include: generation of complex networks, flocking and swarming algorithms (which explain, for example, how schools of fish or flocks of birds synchronise). Adaptation and dynamical processes in complex networks –including synchronisation and self-organisation– will be also considered.
Upon successful completion of the course, the students should:
- Appreciate the issues associated with the finite precision computation with floating point numbers;
- Be able to apply simple algorithms for numerical solution of initial value problems;
- Be aware of the stability issues in continuous-time dynamical systems, and the methods for examining stability;
- Appreciate the importance of studying dynamical processes and properties in complex systems;
- Appreciate the emergence of complex behaviours in networks not present in the individual network elements;
- Be able to apply interdisciplinary knowledge.
PART 1: NUMERICAL STABILITY AND ACCURACY OF COMPUTATIONS (4 hours)
- Introduction to finite precision computation;
- Floating point arithmetic (examples involving precision, error propagation through a computational process, condition of a problem, stability of numerical algorithms);
- .Mixed precision algorithms (basic concept of iterative refinement, different speed of execution on different architectures).
PART 2: NUMERICAL SOLUTION OF INITIAL VALUE PROBLEMS AND STABILITY OF CONTINUOUS-TIME LINEAR DYNAMICAL SYSTEMS (8 hours)
- Numerical solution of initial value problems (explicit/implicit methods, linear multistep methods, consistency, stability, convergence);
- Methods based on the eigenvalues for examining stability of continuous-time dynamical systems.
PART 3: COMPLEX NETWORKS AND COLLECTIVE BEHAVIOUR (12 hours)
A synchronised school of fish; the evolution of a flock of birds; the controlled distributed motion of swarm satellites; the cooperation of several robotic systems; social networks; the spreading of diseases; the development and regeneration of multicellular biological organisms: these are examples of complex networks and collective behaviour. That is, a group of systems (normally, a big number of them) interconnected in a non-trivial and non-regular way. The key aspect of these networks is the complex nature of their interconnection topology, which defines the behaviour of the overall structure and entails the onset of dynamical phenomena and patterns not present in the individual systems. This module will provide the students with the basic terminology and analysis tools in order to understand the structure and dynamics of complex networks. It consists of the following sections.
1. Introduction to complex networks
- 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
- Regular networks;
- Random-graph networks;
- Small-world networks;
- Scale-free networks.
3. Network dynamics and collective behaviour
- 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).
4. Adaptive networks and self-organisation
- What are adaptive networks?
- Adaptive feedback loop between dynamical processes on the network and the evolving topology;
- Emergent dynamical phenomena in adaptive networks
5. Real-world networks and big data: giving structure to the data
- Neuronal networks;
- Social networks;
- The internet;
- Other examples.
24 (2 hours/week)
We will maintain a continuous feedback with students through active participation in the classroom. There will be feedback for the group coursework which will be face-to-face feedback in the classroom when course works are presented to all the class and the lecturers. This will happen twice, at the end of each part of the course. At the end of the course, there will be general feedback on the exam results.
- Assessment written exam (1 hours)
- Lectures (24 hours)
- Analytical skills
- Group/team working
- Oral communication
- Problem solving
|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.|
|Small worlds: the dynamics of networks between order and randomness||Watts, Duncan J.||9780691117041||Princeton University Press||2003||✖|
|Structure and dynamics of networks||Newman, Mark and Albert-Laszlo Barabasi and Duncan J. Watts (eds.).||9780691113579||Princeton University Press||2006||✖|
|Sync: the emerging science of spontaneous order||Strogatz, Steven||9780141007632||Penguin||2004||✖|
|Self-organization of complex structures: from individual to collective dynamics||Schweitzer, Frank (ed.).||9789056990275||CRC Press||1997||✖|
|Self-organization in biological systems||Camazine, Scott et al.||9780691116242||Princeton University Press (Princeton Studies in Complexity)||2015||✖|
|Dynamical processes on complex networks||Barrat, Alain and Marc Barthelemy and Alessandro Vespignani||9780521879507||Cambridge University Press||2008||✖|
|Introduction to numerical analysis||Suli, Endre and David Mayers||9780521007948||Cambridge University Press||2003||✖|
|Networks (2nd edition)||Newman, Mark||9780198805090||Oxford University Press||2018||✖|
|Lectures on complex networks||Dorogovtsev, Sergey N.||9780199548934||Oxford University Press||2010||✖|
|Accuracy and stability of numerical algorithms (2nd edition)||Higham, Nicholas J.||9780898715217||SIAM (Society for Industrial and Applied Mathematics)||2002||✖|
Course unit materials
Links to course unit teaching materials can be found on the School of Computer Science website for current students.