This is an archived syllabus from 2013-2014

• View 2022-2023 syllabus.

COMP36212 Advanced Algorithms II

Level 3
Credits: 10
Enrolled students: 48

Course leader: Pedro Mendes

Additional staff: view all staff

Assessment methods

• 75% Written exam
• 25% Coursework

Timetable

Semester	Event	Location	Day	Time	Group
Sem 2	Lecture	1.3	Thu	11:00 - 11:00	-
Sem 2	Lecture	1.4	Fri	11:00 - 11: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

Study hours

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

Employability skills

• Analytical skills
• Group/team working
• Research

Learning outcomes

On successful completion of this unit, a student will be able to:

Learning outcomes are detailed on the COMP36212 course unit syllabus page on the School of Computer Science's website for current students.

Reading list

Additional notes

Course unit materials

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