Lecture Course
MAST31213, 10 cr, Åsa Hirvonen, 04.09.2017 - 13.12.2017Master's Programme in Mathematics and StatisticsEnglish
Subscribe this course activityRSS

Kaisa_2012_3_photo by Veikko Somerpuro
Enrol
14.8.2017 at 09:00 - 13.12.2017 at 23:59
Moodle
Log in to view the registration key for Moodle.

Messages

Åsa Hirvonen

Published, 9.12.2017 at 17:37

I added a 14th set of exercises as practice for the exam. They are not supposed to be a preview of the exam, but going through them will probably help in preparing for the exam. Choose which ones you want to look at in class on Wednesday, as we won't have time for all.
Also, these exercises are not counted for the exercise points for the course (i.e. completely voluntary to do).

Åsa Hirvonen

Published, 1.9.2017 at 19:27

Due to the lecturer's sick leave, the lectures will only start on week 37 (i.e., Mon 11.9.). However, exercises start already on Wed 6.9. - assignments will appear shortly. In the meantime, read the introduction and chapter 0 of the book (intro + chapter 1.1 of web draft).

Timetable

Here is the course’s teaching schedule. Check the description for possible other schedules.

DateTimeLocation
Mon 4.9.2017
10:15 - 12:00
Mon 11.9.2017
10:15 - 12:00
Tue 12.9.2017
10:15 - 12:00
Mon 18.9.2017
10:15 - 12:00
Tue 19.9.2017
10:15 - 12:00
Mon 25.9.2017
10:15 - 12:00
Tue 26.9.2017
10:15 - 12:00
Mon 2.10.2017
10:15 - 12:00
Tue 3.10.2017
10:15 - 12:00
Mon 9.10.2017
10:15 - 12:00
Tue 10.10.2017
10:15 - 12:00
Mon 16.10.2017
10:15 - 12:00
Tue 17.10.2017
10:15 - 12:00
Mon 30.10.2017
10:15 - 12:00
Tue 31.10.2017
10:15 - 12:00
Mon 6.11.2017
10:15 - 12:00
Tue 7.11.2017
10:15 - 12:00
Mon 13.11.2017
10:15 - 12:00
Tue 14.11.2017
10:15 - 12:00
Mon 20.11.2017
10:15 - 12:00
Tue 21.11.2017
10:15 - 12:00
Mon 27.11.2017
10:15 - 12:00
Tue 28.11.2017
10:15 - 12:00
Mon 4.12.2017
10:15 - 12:00
Tue 5.12.2017
10:15 - 12:00
Mon 11.12.2017
10:15 - 12:00
Tue 12.12.2017
10:15 - 12:00

Learn more about the classrooms accessibility and facilities (in Finnish)

Other teaching

Ryhmä 1
06.09. - 18.10.2017 Wed 10.15-12.00
01.11. - 29.11.2017 Wed 10.15-12.00
13.12.2017 Wed 10.15-12.00
Lauri Ylinen
Teaching language: English

Material

We follow approximately chapters 1-5 of the book Arora, S., Barak, B. Computational Complexity: A Modern Approach. A draft of the book is available on the authors' page http://theory.cs.princeton.edu/complexity/

Other recommended texts are
C. H. Papadimitriou: Computational complexity (1994)
J. Paris: Computational Complexity (lecture notes, 2007-08), available at http://www.maths.manchester.ac.uk/~jeff/lecture-notes/MATH63011.ps

Tasks

Exercises

PDF icon Exercise set 1
PDF icon Exercise set 2
PDF icon Exercise set 3
PDF icon Exercise set 4
PDF icon Exercise set 5
PDF icon Exercise set 6
PDF icon Exercise set 7
PDF icon Exercise set 8
PDF icon Exercise set 9
PDF icon Exercise set 10
PDF icon Exercise set 11
PDF icon Exercise set 12
PDF icon Exercise set 13 (for 11.12.)
PDF icon Practice exercises for 13.12.

Conduct of the course

The course is evaluated based on a final exam and the exercises the student solved during the course.
The course exam will be organized in the December general exam of the department (13.12. at 16-20). A second possibility is offered in the January general exam.

Description

Optional course.

Master's Programme in Mathematics and Statistics is responsible for the course.

The course belongs to the Mathematics and Applied mathematics module.

The course is available to students from other degree programmes.

Routine in mathematics

Master studies

The course is an introductory course to computational complexity theory.

Recommended time/stage of studies for completion: 1. or 2. year

Term/teaching period when the course will be offered: varying

Turing machines, basic complexity classes, hierarchy theorems, reductions and completeness

C. H. Papadimitriou: Computational complexity (1994); S. Arora and B. Barak: Computational complexity: a modern approach (2009)

Lectures and exercise classes

Exam and excercises, Course will be graded with grades 1-5

Exam, other methods will be described later