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

This is an archived syllabus from 2015-2016

COMP36212 Advanced Algorithms 2 syllabus 2015-2016

COMP36212 Advanced Algorithms 2

Level 3
Credits: 10
Enrolled students: 43

Course leader: Eva Navarro-Lopez


Additional staff: view all staff

Additional requirements

  • COMP36212 - Enrolment restricted to Computer Science students

Assessment methods

  • 75% Written exam
  • 25% Coursework
Timetable
SemesterEventLocationDayTimeGroup
Sem 2 Lecture LF15 Thu 11:00 - 12:00 -
Sem 2 Lecture LF15 Fri 11:00 - 12: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

Oral and written feedback

Study hours

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

Employability skills

  • Analytical skills
  • Group/team working
  • Research

Learning outcomes

Programme outcomeUnit learning outcomesAssessment
A2 B1 B2 B3 C5 D6Apply basic concepts to describe representative network models.
  • Individual coursework
  • Examination
  • Lab assessment
A2 B1 B2 B3 C5 D6Understand the dynamical properties implications of the structure of a network on individual elements and vice versa.
  • Individual coursework
  • Lab assessment
  • Examination
A2 B1 B2 B3 C5 D6Develop numerically stable and accurate algorithms.
  • Examination
  • Individual coursework
  • Lab assessment

Reading list

TitleAuthorISBNPublisherYearCore
Self-organization in biological systemsCamazine, Scott et al.9780691116242Princeton University Press (Princeton Studies in Complexity)2001
Structure and dynamics of networksNewman, Mark and Albert-Laszlo Barabasi and Duncan J. Watts (eds.).9780691113579Princeton University Press2006
Stochastic optimizationSchneider, J.J. and S. Kirkpatrick9783540345596Springer2006
Practical methods of optimization (2nd edition)Fletcher, R.9780471494638Wiley2000
Sync: the emerging science of spontaneous orderStrogatz, Steven9780141007632Penguin2004
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
Introduction to genetic algorithmsMitchell, Melanie0262133164MIT Press1996
Introduction to numerical analysisSuli, Endre and David Mayers9780521007948Cambridge University Press2003
Self-organization of complex structures: from individual to collective dynamicsSchweitzer, Frank (ed.).9789056990275CRC Press1997
Dynamical processes on complex networksBarrat, Alain and Marc Barthelemy and Alessandro Vespignani9780521879507Cambridge University Press2008
Lectures on complex networksDorogovtsev, Sergey N.9780199548934Oxford University Press2010
Networks: an introductionNewman, M.E.J.9780199206650Oxford University Press2010

Additional notes

Course unit materials

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