TOL203F: Algorithms, Logic and Complexity, Spring 2016

Overview

This course provides an introduction to some of the central ideas in theoretical computer science. The topics include strategies for designing efficient algorithms (recursive, greedy, and divide-and-conquer algorithms, dynamic programming). The complexity classes P and NP, NP-complete problems, reductions and the P vs NP question. Universal computation, Turing machines, recursive functions, diagonalization, the halting problem and undecidability. Space complexity and the complexity of games. Optimization and approximation.

Syllabus (tentative)

Week Subject
1 - 2 Basics, algorithm review (chapters 2 and 3)
3 - 6 NP-Completeness (chapters 4 – 6)
7 - 9 Theory of computation (chapter 7)
10 - 11 Memory (chapter 8)
12 - 13 Optimization and approximation (chapter 9)
14 Wrapup

Textbook: The Nature of Computation by Christopher Moore and Stephan Mertens. Oxford University Press, 2011. The book is available from The University Bookstore.

Course information

Lectures: Teacher: Steinn Guðmundsson (steinng@hi.is). Office: Tæknigarður, room 212 (tel. 525 4738). Office hours: Fridays 10 - 12.

Evaluation

There will be 6 problem sets posted on the course web (see below) during the semester. They will be due approximately every 2 weeks and the best 5 solutions count towards the final grade. Each student will also give a short (approx. 20 minutes) presentation on a selected topic in theoretical computer science. The presentation along with a brief written summary will count for 10% of the final grade. The midterm and final exams will be closed book but the students will be allowed to bring a single page of handwritten notes ("cheat sheet"). The student must obtain a pass mark of 6 on the total grade.

Course web

Announcements, homework assignments and supplementary material will be posted on Piazza. Piazza also provides an online forum to ask questions relating to the course, e.g. clarification of homework problems. To sign up, go to https://piazza.com/hi.is/spring2016/tol203f and select "Join as Student". Click on "Join Classes" and provide your email account.