TOL203F: Algorithms, Logic and Complexity, Spring 2017

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, divide-and-conquer algorithms and dynamic programming. The complexity classes P and NP, NP-complete problems, reductions, integer programming and the P vs NP question. Universal computation, Turing machines, lambda calculus and recursive functions. Diagonalization, the halting problem and undecidability. Space complexity and the complexity of games. Randomized algorithms. Private and public key cryptography, trapdoor functions.

Syllabus (tentative)

Week Subject
1 - 3 Basics, algorithm review (chapters 2 and 3)
4 - 7 NP-Completeness (chapters 4 – 6)
8 - 9 Theory of computation (chapter 7)
10 - 11 Memory (chapter 8)
12 - 13 Randomization and cryptography (chapter 10)
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).

Evaluation

There will be 12 problem sets posted on the course web (see below) during the semester and the best 10 solutions count towards the final grade. Each student will also give a short (approx. 25 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"). 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/spring2017/tol203f and select "Join as Student". Click on "Join Classes" and provide your email account.