# 2019/20 Undergraduate Module Catalogue

## COMP3940 Graph Algorithms and Complexity Theory

### 10 creditsClass Size: 130

**Module manager:** Dr Haiko Muller**Email:** H.Muller@leeds.ac.uk

**Taught:** Semester 1 View Timetable

**Year running** 2019/20

### Pre-requisite qualifications

Students must have studied one of the below two Pre-requisite modules### Pre-requisites

COMP2941 | Algorithms II |

MATH2230 | Discrete Mathematics |

MATH2231 | Discrete Mathematics with Computation |

Module replaces

COMP3930 Complexity and Approximation**This module is not approved as a discovery module**

### Module summary

A graph is a mathematical object defined by a set of vertices and a set of edges that connect these vertices. Many problems arising in diverse areas such as transportation, telecommunication, molecular biology, industrial engineering, etc. can be modeled by graphs. These problems then reduce to optimizing some graph parameter. Since the objects we are dealing with are finite, we can envision an algorithm that would list all the possibilities and go through them to find the desired optima. The problem with such an algorithm is its complexity, it grows exponentially with the input size. Even with relatively small input graph it would take the computer centuries to find the answer. The graphs used to model problems in say bioinformatics, or the problems related to the internet, are enormous in size, stressing the importance for the algorithms to be extremely efficient. To construct efficient algorithms one needs to exploit the mathematical understanding of the underlying objects.In this module we introduce a wide range of graph problems, classify them with respect to their computational complexity, and demonstrate how these methods extend to other computational problems.### Objectives

On completion of this module students should be able to:- recognise real-world problems that can be modelled by graph problems considered in this module;

- understand and be able to use these algorithms;

- demonstrate how such algorithms are analysed;

- construct reductions to prove NP-hardness;

**Learning outcomes**

On completion of the year/programme students should have provided evidence of being able to:

-understand and demonstrate coherent and detailed subject knowledge and professional competencies some of which will be informed by recent research/scholarship in the discipline;

-deploy accurately standard techniques of analysis and enquiry within the discipline;

-demonstrate a conceptual understanding which enables the development and sustaining of an argument;

-appreciate the uncertainty, ambiguity and limitations of knowledge in the discipline

### Syllabus

Network flows (Ford-Fulkerson Labelling Algorithm, Max Flow Min Cut Theorem)

Matchings (matchings in bipartite graphs, matchings in general graphs, Edmonds’ Blossom Algorithm, matchings and coverings, Hall’s Theorem, König-Egervary Theorem)

Complexity Theory (the classes P and NP, NP-completeness, polynomial-time many-one reductions, proofs of NP-completeness of independent set, vertex cover and clique problems)

### Teaching methods

Delivery type | Number | Length hours | Student hours |

Example Class | 10 | 1.00 | 10.00 |

Lectures | 22 | 1.00 | 22.00 |

Class tests, exams and assessment | 1 | 2.00 | 2.00 |

Private study hours | 66.00 | ||

Total Contact hours | 34.00 | ||

Total hours (100hr per 10 credits) | 100.00 |

### Private study

Taught session preparation: 18 hoursTaught session follow-up: 18 hours

Self-directed study: 7 hours

assessment activities: 23 hours

### Opportunities for Formative Feedback

Attendance and formative assessment.### Methods of assessment

**Coursework**

Assessment type | Notes | % of formal assessment |

Problem Sheet | Problem Sheet 2 | 5.00 |

Problem Sheet | Problem Sheet 3 | 5.00 |

Problem Sheet | Problem Sheet 1 | 5.00 |

Problem Sheet | Problem Sheet 4 | 5.00 |

Total percentage (Assessment Coursework) | 20.00 |

This module is re-assessed by exam only.

**Exams**

Exam type | Exam duration | % of formal assessment |

Standard exam (closed essays, MCQs etc) | 2 hr 00 mins | 80.00 |

Total percentage (Assessment Exams) | 80.00 |

This module is re-assessed by exam only.

### Reading list

The reading list is available from the Library websiteLast updated: 05/11/2019 08:50:00

## Browse Other Catalogues

- Undergraduate module catalogue
- Taught Postgraduate module catalogue
- Undergraduate programme catalogue
- Taught Postgraduate programme catalogue

Errors, omissions, failed links etc should be notified to the Catalogue Team.PROD