EECS 4115/5115, Fall 2020

EECS 4115/5115
Computational Complexity
Fall 2020

Web page contents:

General Information
Announcements
Important Dates
Resources
Reading
Course Handouts

General Information

Instructor: Eric Ruppert
Email: [my last name] @eecs.yorku.ca
Lectures: Tuesdays and Thursdays from 11:30 to 13:00 via Zoom meetings. See course eclass page for meeting details.
Office Hours: Mondays at 2pm and Thursdays at 3pm via Zoom meetings. See course eclass page for meeting details.

When emailing, please use your cs account when sending me email, and start your subject line with "[4115]" for faster attention.

Course Overview

This course is intended to introduce students to the fundamentals of complexity theory, which is an important part of the foundations of the entire field of computer science.

We'll look at models of computers (e.g. Turing machines) and see how they are used to measure the resources (time, space and others) required to solve problems. If we pick a model and a bound on one or more resources, we can define a complexity class (e.g. P, NP, NC) to be the set of problems that can be solved in that model with the given resources. These classes give us a systematic way of understanding how efficiently problems can be solved.

In studying complexity theory, we learn about techniques that can be used to design efficient algorithms. We also learn how to identify those problems for which efficient solutions do not exist or are unlikely to exist. Such information is useful, because it often suggests how to modify our approach when faced with an intractable problem: for example, we might look for approximate solutions instead of exact solutions, or try to solve a special case of the problem that is sufficient for our needs.

This course assumes knowledge of the material in CSE2001 and CSE3101, and you should be comfortable reading and writing mathematical proofs.

Here is a tentative list of topics:

Marking scheme

Component EECS4115 EECS5115
Homework exercises 25% 25%
Test 1 10% 10%
Test 2 15% 10%
Oral test 10% 10%
Participation 10% 10%
Project (EECS5115 only) 0% 10%
Final exam 30% 25%

Academic Honesty

It is important that you look at the departmental guidelines on academic honesty.

Although you may discuss the general approach to solving a problem on a homework assignment with other people, you should not discuss the solution in detail. You must not take any written notes away from such a discussion. Also, you must list on the cover page of your solutions any people with whom you have discussed the problems. The solutions you hand in should be your own work. While writing them, you may look at the course textbook and your own lecture notes but no other outside sources.

If you get stuck while working on one of the assignments, I encourage you to discuss it with me during an office hour.

Announcements

Important Dates

(Information will be added to this table thoughout the term.)

First class September 10
Test 1 October 1
Reading Week (no classes) October 10-16
Test 2 November 3
Drop deadline November 6
Oral test Various dates, mid-Nov
Bonus Quiz December 2, 10:00-11:00
Last class December 8
Exam period December 9-23

References

Course Textbook

[Sip] Michael Sipser. Introduction to the Theory of Computation, 3rd edition. Cengage Learning, 2013.
We will be focusing on Part III of the book.
The textbook website has lists of errata.

Other Books

Original Articles

Resources for Special Topics

Blogs

More advanced complexity resources

Reading

DateSectionSuggested Exercises
Sep 10Review chapter 0 and 30.1-0.8, 3.1-3.2, 3.7, 3.8, 3.10-3.13
Sep 157.1, review 3.17.1, 7.2, 3.8
Sep 17review 3.23.12, 3.13
Sep 17notes on PalindromesShow every single-tape TM that decides {0x1y2x : x,y ≥ 0} takes Ω(n log n) steps
Sep 227.27.3-7.6, 7.8, 7.9, 7.13, 7.14, 7.15
Sep 247.37.7, 7.12, 7.16
Oct 67.47.18, 7.20-7.27
Oct 207.57.17, 7.28, 7.30-7.33, 7.35, 7.38, 7.40-7.41
Oct 27Optional: The Status of the P Versus NP Problem (from CACM, Sep 2009) and/or
P vs. NP survey results (from SIGACT News, Mar 2019; starts on p.4)
Nov 510.1
Nov 108.0-8.1, 8.48.1, 8.4, 8.7, 8.9, 8.17, 8.20, 8.22
Nov 128.5, 8.68.25,8.29,8.32
Nov 198.2, 8.38.3,8.4,8.6,8.11,8.15
Nov 249.1 (to page 371)9.1-9.3,9.12,9.13
Dec 1p.396-398, Defn 10.1010.7, 10.11, 10.19, 10.20, 10.22
NOTE: Exercise numbers are from the third edition of the textbook.

Course Handouts

Updated December 3, 2020