Computability (G53COM)
General Information:
The information here corresponds to the Spring Semester 2007.
See the Module Specification.
Timetable for Spring Semester 2007: Monday 12:00-13:00 in C1-JBCEXGE and Tuesday 10:00-11:00 in A24-JBCSOUTH.
See the Module Reading List.
See the Module Feedback for 2006-2007, 2005-2006, 1999-2000.
Schedule for the Spring Semester 2007:
| LECTURE |
TOPIC |
RESOURCES |
| Lecture 1 (29-Jan) |
Introduction |
Lecture Notes |
| Lecture 2 (30-Jan) |
Problems and Algorithms |
Lecture Notes |
| Lecture 3 (05-Feb) |
Mathematical Preliminaries Part 1 |
Lecture Notes |
| Lecture 4 (06-Feb) |
Mathematical Preliminaries Part 2 |
Lecture Notes |
| Lecture 5 (13-Feb) |
Turing Machines Part 1 |
Lecture Notes |
| Lecture 6 (19-Feb,20-Feb) |
Turing Machines Part 2 |
Lecture Notes |
| Lecture 7 (26-Feb) |
Special Turing Machines |
Lecture Notes |
| Lecture 8 (27-Feb) |
Solvability and Unsolvability |
Lecture Notes |
| Lecture 9 (12-Mar) |
Algorithm Analysis and Complexity Classes |
Lecture Notes |
| Lecture 10 (19-Mar) |
Polynomial Reducibility |
Lecture Notes |
| Lecture 11 (20-Mar) |
Reductions and Completeness |
Lecture Notes |
| Easter Break |
| Lecture 12 (23-Apr) |
The NP-Complete Class Part 1 |
Lecture Notes |
| Lecture 13 (24-Apr) |
The NP-Complete Class Part 2 |
Lecture Notes |
| Lecture 14 (30-Apr) |
Tackling NP-Complete Problems |
Lecture Notes |
| Lecture 15 (01-May) |
Summary and Revision |
Lecture Notes |
| Examination: 31-May-2007 16:30-18:30 Portland Building Dining Room |
Assessment:
Examination (100%) - The exam is a reasoning
questions style, more details will be given in the Summary and Revision Lectures.
|
