Skip to main content
MyCourses MyCourses
  • Schools
    School of Arts, Design, and Architecture (ARTS) School of Business (BIZ) School of Chemical Engineering (CHEM) –sGuides for students (CHEM) – Instructions for report writing (CHEM) School of Electrical Engineering (ELEC) School of Engineering (ENG) School of Science (SCI) Language Centre Open University Library Aalto university pedagogical training program UNI (exams) Sandbox
  • CORONAVIRUS INFO
    Koronavirus - tietoa opiskelijalle Coronavirus - information for students Coronavirus - information för studerande Koronaviruksen vaikutus opiskeluun: kysymyksiä ja vastauksia Effects of the coronavirus on studies: questions and answers Coronaviruset och studierna: frågor och svar Corona help for teachers
  • Service Links
    MyCourses - Instructions for Teachers - Teacher book your online session with a specialist - Digital tools for teaching - Personal data protection instructions for teachers - Instructions for Students - Workspace for thesis supervision WebOodi Into portal for students Courses.aalto.fi Library Services - Resourcesguides - Imagoa / Open science and images IT Services Campus maps - Search spaces and see opening hours Restaurants in Otaniemi ASU Aalto Student Union Aalto Marketplace
  • ALLWELL?
    Study Skills Support for Studying Starting Point of Wellbeing About AllWell? study well-being questionnaire
  •   ‎(en)‎
      ‎(en)‎   ‎(fi)‎   ‎(sv)‎
  • Toggle Search menu
  • Hi guest! (Log in)

close

CS-E4530 - Computational Complexity Theory, 03.01.2018-03.04.2018

  1. Home
  2. Courses
  3. School of Science
  4. department of...
  5. cs-e4530 - co...
Syllabus

General

  • General

    General

    OVERVIEW. CS-E4530 Computational complexity theory is a master's level course introducing the basic mathematical theory of analysing the hardness of computational problems, i.e., the basic toolset for understanding what makes some computational problems difficult to solve.

    • Second midterm Tuesday April 3 at 13:00-16:00 (Room T1)
    • Lectures Monday 10-12, Wednesday 10-12 (Room T3).
    • Exercise sessions Tuesday 10-12 (B337).

    The course is worth 5 credits. The language of instruction is English.

    The lectures are given by Janne H. Korhonen. Teaching assistants are Tuomo Lempiäinen and Abdulmelik Mohammed.

    PREREQUISITES. Automata and formal languages. Deterministic and nondeterministic Turing machines. Decidable and undecidable problems (e.g. CS-C2150 / ICS-C2000 Theoretical Computer Science). Basics of discrete mathematics.

    CONTENT. Basic concepts of complexity theory: models of computation, complexity measures including time and space, reductions, complexity classes and completeness. Complexity classes: P, NP and coNP; PSPACE, LOGSPACE, EXPTIME. Advanced topics such as the polynomial hierarchy, approximation, randomised computation, circuits and parallel computation, fine-grained complexity, and relativisations.

    MATERIAL. Lecture slides and exercise sets will be posted online. The main reference text is the textbook Computational Complexity: A Modern Approach by Arora and Barak. A draft version is available freely online (http://theory.cs.princeton.edu/complexity/).

    EXERCISES AND GRADING. The course has two midterm exams, graded pass/fail. You are required to pass both exams to pass the course.

    In addition to the midterms, there are 10 sets of weekly exercises. Each exercise set except the first is worth 8 points (the first is 14 points), for a maximum of 86 points. The number of points from the exercises will determine your final grade:

    • 1/5: pass midterms
    • 2/5: pass midterms + at least 16 points
    • 3/5: pass midterms + at least 32 points
    • 4/5: pass midterms + at least 48 points
    • 5/5: pass midterms + at least 64 points

    DOING THE EXERCISES. You are allowed and encouraged to work together with your fellow students on exercises, and you can get help from the teaching assistants during the weekly exercise session. However, you must write up your final solutions by yourself, completely in your own words.

    You should return your answers to the exercises via MyCourses. The deadline for each weeks' exercises is on midnight on Friday. Answers must be submitted as a easily readable, single pdf file. Your answers should be self-contained and written with sufficient detail so it is easy to follow your reasoning.

    BONUS EXERCISES. In addition to the weekly exercises, there will be some more challenging bonus exercises. These can be completed at any point before the second midterm, and can give extra points on top of the weekly exercises. Practical instructions can be found on the bonus exercise sheets.

    DISCUSSION FORUM. The course has a Slack workspace that you can use for discussions and getting help with the exercises. The workspace is available at https://aalto-cct.slack.com.

    Sign up at https://aalto-cct.slack.com/signup with your aalto.fi email account.

    LEARNING OUTCOMES. Once you have taken the course, you master the central concepts of computational complexity theory and are able to use these concepts to analyse the complexity of computational problems. You can formulate a concrete real-world computational task as a formal computational problem and formally reason about its computational complexity in comparison with well-known problems and complexity classes. You can use reductions and other complexity-theoretic concepts to identify which algorithmic tools — such as randomisation, approximation, parameterisation and parallelism – can and cannot help with the efficient solution of a given problem.



    • icon for activity Announcements Forum
    • icon for activity General discussion Forum

Course home

Course home

Next section

Materials►
Skip Upcoming events
Upcoming events
Loading There are no upcoming events
Go to calendar...
  • CS-E4530 - Computational Complexity Theory, 03.01.2018-03.04.2018
  • Sections
  • General
  • Materials
  • Home

Aalto logo

Tuki / Support
  • MyCourses help
  • mycourses(at)aalto.fi
Palvelusta
  • MyCourses rekisteriseloste
  • Tietosuojailmoitus
  • Palvelukuvaus
About service
  • MyCourses protection of privacy
  • Privacy notice
  • Service description
Service
  • MyCourses registerbeskrivining
  • Dataskyddsmeddelande
  • Beskrivining av tjänsten

Hi guest! (Log in)
  • Schools
    • School of Arts, Design, and Architecture (ARTS)
    • School of Business (BIZ)
    • School of Chemical Engineering (CHEM)
    • –sGuides for students (CHEM)
    • – Instructions for report writing (CHEM)
    • School of Electrical Engineering (ELEC)
    • School of Engineering (ENG)
    • School of Science (SCI)
    • Language Centre
    • Open University
    • Library
    • Aalto university pedagogical training program
    • UNI (exams)
    • Sandbox
  • CORONAVIRUS INFO
    • Koronavirus - tietoa opiskelijalle
    • Coronavirus - information for students
    • Coronavirus - information för studerande
    • Koronaviruksen vaikutus opiskeluun: kysymyksiä ja vastauksia
    • Effects of the coronavirus on studies: questions and answers
    • Coronaviruset och studierna: frågor och svar
    • Corona help for teachers
  • Service Links
    • MyCourses
    • - Instructions for Teachers
    • - Teacher book your online session with a specialist
    • - Digital tools for teaching
    • - Personal data protection instructions for teachers
    • - Instructions for Students
    • - Workspace for thesis supervision
    • WebOodi
    • Into portal for students
    • Courses.aalto.fi
    • Library Services
    • - Resourcesguides
    • - Imagoa / Open science and images
    • IT Services
    • Campus maps
    • - Search spaces and see opening hours
    • Restaurants in Otaniemi
    • ASU Aalto Student Union
    • Aalto Marketplace
  • ALLWELL?
    • Study Skills
    • Support for Studying
    • Starting Point of Wellbeing
    • About AllWell? study well-being questionnaire
  •   ‎(en)‎
    •   ‎(en)‎
    •   ‎(fi)‎
    •   ‎(sv)‎