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
4th ed., Addison-Wesley
-
Computer algorithms : introduction to design and analysis
3rd ed., Addison-Wesley
-
Algorithms
-
Introduction to algorithms [electronic resource]
Fourth edition., The MIT Press
-
Algorithms
Boston : McGraw-Hill Higher Education
-
The golden ticket [electronic resource] : P, NP, and the search for the impossible
Princeton University Press
-
Mathematical structures for computer science
7th ed., W. H. Freeman
-
Algorithms unlocked [electronic resource]
MIT Press
-
Algorithms illuminated : omnibus edition
Cambridge University Press