Computer Science (3 Years) [BSc]
Advanced Algorithms 2
|Unit level:||Level 3|
|Teaching period(s):||Semester 2|
|Offered by||School of Computer Science|
|Available as a free choice unit?:||Y
Additional RequirementsCOMP36212 - Enrolment restricted to students who have taken COMP11120 or are registered on the CS and Maths programme.
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.
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.
Teaching and learning methods
24 (2 hours/week)
Learning outcomes are detailed on the COMP36212 course unit syllabus page on the School of Computer Science's website for current students.
- Analytical skills
- Group/team working
- Oral communication
- Problem solving
- Written exam - 70%
- Written assignment (inc essay) - 30%
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.
COMP36212 reading list can be found on the School of Computer Science website for current students.
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 - 2 hours
- Lectures - 24 hours
- Independent study hours - 74 hours