40008

Graphs and Algorithms

Module aims

In this module you will have the opportunity to:

• prove mathematical properties of graphs
• explore classical algorithms associated with graphs and trees
• design algorithms for sorting and searching
• apply various methods for determining the time complexity of algorithm
• study the complexity classes P and NP and the concept of NP-completeness
   

Learning outcomes

Upon successful completion of this module you will be able to:

• Prove basic properties of graphs
• Describe, and establish the correctness of, some of the fundamental algorithms in computing
• Analyse the time complexity of an algorithm
• Explain the complexity classes P and NP and the P=NP problem
• Determine to which complexity class a computational problem belongs

Module syllabus

• Graphs and graph representations
• Algorithms for graph traversal
• Minimum spanning trees
• Shortest paths
• Dynamic programming
• Divide and conquer
• Searching and sorting
• Algorithm analysis (time complexity, recurrence relations, Master Theorem)
• Decision trees
• The complexity classes P and NP, NP-completeness               

Teaching methods

The material will be taught through traditional lectures, backed up by formative exercises designed to reinforce the material as it is taught. Approximately half of these exercises will be covered in small-group tutorials, Personal Maths Tutorials (PMTs), which are weekly one-hour tutorials run by academic tutors and Undergraduate Teaching Assistants (UTAs). These tutorials encourage group discussions and group problem solving designed to reinforce your understanding of key topics in logic, discrete mathematics, algorithm design and program reasoning. The remaining exercises are intended for you to use for self-study.   

An online service will be used as a discussion forum for the module.          

Assessments

There will be one assessed coursework that contributes 20% of the mark for the module. There will be a final written exam, which counts for the remaining 80% of the marks. The formative exercises selected for the PMT tutorials will be assessed by your academic tutor and UTA. This assessment does not count to your final degree mark, but is intended to give you an indication of how well you are assimilating the material taught and how effectively you are applying that material to solving previously unseen problems. 
   
Detailed feedback, both written and verbal, will be given on the exercises covered in the PMT tutorials. These exercises will be issued approximately every two weeks and written feedback will be returned the week after submission. You will receive written feedback on the assessed coursework exercise, which counts for 20% of the module mark.

Reading list

Supplementary

• Algorithms

  Sedgewick, Robert, 1946-

  4th ed., Addison-Wesley

• Computer algorithms : introduction to design and analysis

  Baase, Sara.

  3rd ed., Addison-Wesley

• Algorithms

  Dasgupta, Sanjoy

• Introduction to algorithms [electronic resource]

  Cormen, Thomas H.,

  Fourth edition., The MIT Press

• Algorithms

  Dasgupta, Sanjoy, author.

  Boston : McGraw-Hill Higher Education

• The golden ticket [electronic resource] : P, NP, and the search for the impossible

  Fortnow, Lance,

  Princeton University Press

• Mathematical structures for computer science

  Gersting, Judith L.

  7th ed., W. H. Freeman

• Algorithms unlocked [electronic resource]

  Cormen, Thomas H.

  MIT Press

• Algorithms illuminated : omnibus edition

  Roughgarden, Tim (Columbia University, New York)

  Cambridge University Press

Module leaders

Dr Iain Phillips