BBM 402 - Theory of Computation (Fall 2020)

Lecture: Thursday 14-14:40, 14:50-15:30, 15:45-16:25

Instructor:

Lale Özkahya

ozkahya-at-cs.hacettepe.edu.tr
218
+90 312 297 7500

Preferred Prerequisite

Foundations of Computer Science , a free textbook written by A. Aho and J. Ullman

Grading

25% Midterm Exam
35% Reading&Project
40% Final Exam

Resources

Introduction to the Theory of Computation, by Michael Sipser, 2006.
Introduction to Automata Theory, Languages, and Computation (3rd Edition) by John E. Hopfcroft, Rajeev Motwani, Jeffrey D. Ullman.
Algorithms text book by Dasgupta, Papadimitriou and Vazirani. (available online)
Algorithm Design by Kleinberg and Tardos.
Margaret Fleck and Sariel Har-Peled's automata and formal languages notes, 2008 (available online)
Jeff Erickson's Algorithm Notes (available online)
Course Notes for "CS15-251: Great Theoretical Ideas in Computer Science" at CMU (available online)

Similar Courses

MIT Open Courseware: Automata, Computability, and Complexity
CS125: Algorithms and Complexity at Harvard Uni.
15-251: Great Theoretical Ideas in Computer Science at Carnegie Mellon Uni.
COS423: Theory of Algorithms at Princeton Uni.
CS170: Efficient Algorithms and Intractable Problems at EECS, Berkeley Uni.
15-451: Algorithms at Carnegie Mellon Uni.
CS374: Algorithms and Models of Computation at Uni. of Illinois
CS473: Algorithms at Uni. of Illinois

Sample Exams and Questions

Office Hours (Virtual)

Use Piazza for quick course related questions. Please enroll by following the link https://piazza.com/hacettepe.edu.tr/fall2020/bbm402

Schedule (Tentative)

Date	Topic	Jeff Erickson's Notes and Kevin Wayne's Slides on Kleinberg-Tardos' book
Oct. 5 - 9	Review of Algorithms: Recursion: linear-time selection, Karatsuba multiplication slides Backtracking: n queens, subset sum, NFA acceptance, longest increasing subsequence slides	Recursion, Backtracking Divide and Conquer: 1, 2
Oct 12 - 16	Review of Algorithms: Dynamic programming: Fibonacci, longest increasing subsequence, subset sum, NFA acceptance slides Greedy algorithms: tape sorting, scheduling, exchange arguments slides	Dynamic Programming: 1, 2, 3 Edit Distance, Sequence Alignment, Longest Common Subsequence Problem, Maximum Weighted Independent Set in Trees, Greedy Algorithms: 1, 2
Oct 19 - 23	Turing machines: history, formal definitions, examples slides	Turing machine variations: multiple tracks, heads, and tapes; doubly-infinite tape; subroutines; random-access memory Nondeterministic Turing machines Paper to study for the project: due October, 23
Oct. 26 - Oct. 30	Undecidability: halting problem, diagonalization, reductions slides Polynomial time Reductions slides	Undecidability
Nov. 2 - Nov. 6	NP-hardness: Definitions, examples, Cook-Levin Theorem slides NP-hardness: 3SAT, Max Independent Set, Vertex cover, 3-Color, Hamiltonian cycle slides	NP, NP-completeness
Nov. 9 - Nov. 13	Ford-Fulkerson algorithm, Max-flow min-cut theorem [Slides] Applications of Network Flow on bipartite matching, disjoint path finding problems [Slides]	Maximum Flows and Minimum Cuts Chapter 7 in KT slides Applications of Maximum Flow Randomized Minimum Cut
Nov. 16 - Nov. 20	The midterm exam
Nov. 23 - Nov. 27	PSPACE: A Class of Problems beyond NP [Slides_Wayne] [Slides]	Chapter 9 in KT
Nov. 30 - Dec. 4	Limits of Tractability [Slides]	Chapter 10 in KT
Dec. 7 - Dec. 11	Approximation Algorithms [Slides]	Chapter 11 in KT Approximation Algorithms
Dec. 14 - Dec. 18	Local Search [Slides]	Chapter 12 in KT
Dec. 21 - Dec. 25	Randomized Algorithms [Slides]	Chapter 13 in KT Randomized Algorithms
Dec. 28 - Jan. 1	Review for the Final Exam
Jan. 4 - Jan. 8	Project Presentations