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

COMP36212 Advanced Algorithms 2 syllabus 2017-2018

COMP36212 materials

COMP36212 Advanced Algorithms 2

Level 3
Credits: 10
Enrolled students: 25

Course leader: Eva Navarro-Lopez


Additional staff: view all staff

Requisites

  • Pre-Requisite (Compulsory): COMP11120

Additional requirements

  • COMP36212 - Enrolment restricted to students who have taken COMP11120 or are registered on the CS and Maths programme.

Assessment methods

  • 70% Written exam
  • 30% Coursework
Timetable
SemesterEventLocationDayTimeGroup
Sem 2 Lecture 1.4 Thu 09:00 - 10:00 -
Sem 2 Lecture 1.4 Mon 15:00 - 16:00 -
Themes to which this unit belongs
  • Programming and Algorithms
  • Programming and Algorithms

Overview

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.

Aims

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.

Syllabus

PART 1: NUMERICAL STABILITY AND ACCURACY OF COMPUTATIONS (4 hours)

  1. Introduction to finite precision computation;
  2. Floating point arithmetic (examples involving precision, error propagation through a computational process, condition of a problem, stability of numerical algorithms);
  3. .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)

  1. Numerical solution of initial value problems (explicit/implicit methods, linear multistep methods, consistency, stability, convergence);
  2. 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.

Teaching methods

Lectures

24 (2 hours/week)

Feedback methods

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.

Study hours

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

Employability skills

  • Analytical skills
  • Group/team working
  • Innovation/creativity
  • Oral communication
  • Problem solving
  • 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.
  • Examination
  • Lab assessment
  • Individual coursework
A2 B1 B2 B3 C5 D6Develop numerically stable and accurate algorithms.
  • Examination
  • Lab assessment
  • Individual coursework

Reading list

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

Additional notes

Course unit materials

Links to course unit teaching materials can be found on the School of Computer Science website for current students.