Computational Complexity (CS5230)

Lecturer
The lecturer is Frank Stephan from the Departments of Mathematics and Computer Science of the National University of Singapore.

Frank Stephan's addresses are:

  (1) Department of Mathematics, National University of Singapore
      10 Lower Kent Ridge Road, Block S17, Singapore 119076
      Primary Office: S17#07-04

  (2) School of Computing, National University of Singpore
      Computing Drive, Computing 1 (COM1), Singapore 117590
      Secondary Office: COM1#03-11

When logged into and working at a computer, Frank Stephan is best reachable
under telephone +65 65164246.

The email address is fstephan@comp.nus.edu.sg

Time and Place
Mondayday 18:30 hrs - 20:30 hrs Lecture followed by Tutorial. The room is the Seminar Room next to LT 19.

Slides
Slides of all lectures are available here as ps-file and pdf-file. The slides are comprehensive and contain all information important for the lecture.

Assessment
The homeworks count 20 points, each single ones counts 2 points and the maximum points awarded is 20 (10 homeworks); the midterm examination counts 20 points and the final examination counts 60 points; in total a student can obtain up to 100 points.

The Midterm Examination is in Week 9, second half of Monday lecture. Please be there latest at 19:15 hrs. The date is 17 March 2024.

Tutorial
There will be a tutorial after the lecture each week from Week 2 onwards. The homeworks are listed in the slides. The homeworks with the number k.h should be presented in Week k, for example homework 3.4 should be presented in Week 3. Everyone should do per week one homework, write it up in the Discussion Forum and present it in the tutorial. Each student should choose an own homework and not do the same homework as a classmate; reserve a homework by putting a post with the homework number into the Discussion Forum and then work on the homework by editing this post until it is good; present the homework in the tutorial on black board or with slides in the week when it is due. The maximum points obtainable is 20, so one has to write up one homework per week scoring 2 points.
All homeworks should be the own work and using ChatGPT and other AI tools is not allowed. It is, however, allowed to write on a page of paper or produce with a text-programme a word file and to upload a scan or pdf-file of the homework. It is okay to consult textbooks or other sources, as long as you write the homework in your own words and do not copy and paste a source.