TOL203F: Algorithms, Logic and Complexity, Spring 2015

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, lambda-calculus, recursive functions, diagonalization, the halting problem and undecidability. Space complexity and the complexity of games. Randomness 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 Memory (chapter 8)
11 - 12 Optimization and approximation (chapter 9)
13 - 14 Randomized algorithms (chapter 10)

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).

Evaluation

There will be weekly homework assignments with the 10 best assignments (out of 13) counting towards the final grade. Each student will 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 final exam will be closed book but the students will be allowed to bring a single page of handwritten notes ("cheat sheet") to the exam. The student must obtain a pass mark of 5 on the examination itself and a pass mark of 6 for 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/spring2015/tol203f and select "Join as Student". Click on "Join Classes" and provide your email account.