CPSC 421 & 501: Introduction to Theory of Computing

2018-19 Winter Term 1

General Information

Course Website: http://www.cs.ubc.ca/~nickhar/F18-421

Lecture Time: Monday, Wednesday, Friday, 3:00pm-4:00pm

Lecture Room: DMP 110

Instructor: Prof. Nicholas Harvey, X851, nickhar@cs.ubc.ca

·        Office Hours: Thursday 2-3pm in ICCS x851

TAs:

·        Sikander Randhawa, sikander_94@alumni.ubc.ca

o   Office Hours: Tuesday 10-11am, Table 6 in DLC (ICCS x150)

·        Curtis Fox, curtis.fox@alumni.ubc.ca

o   Office Hours: Monday 1-2pm, Table 6 in DLC (ICCS x150)

·        Substituted On November 8th:

o   Chris Liaw, cvliaw@cs.ubc.ca

o   Office Hours: Friday 10-11am, Table 5 in DLC (ICCS x150)

·        Substituted Off November 8th:

o   Shane Sims, ssims@cs.ubc.ca

o   Office Hours: Friday 10-11am, Table 5 in DLC (ICCS x150)

 

Syllabus

 

Assignments

Here is the assignment policy.

Here is the latex template as tex file, and as an Overleaf project.

 

Handout

Due

Handback

Link

TA Grader

0

W 9/5

M 9/10

F 9/14

PDF

Shane

1

W 9/12

W 9/19

M 9/24

PDF

Curtis

2

Th 9/20

F 9/28

F 10/5

PDF

Sikander

3

F 9/28

F 10/5

F 10/12

PDF

Shane

4

F 10/19

F 10/26

Su 11/04

PDF

Curtis

5

F 10/26

F 11/2

Mo 11/12

PDF

Sikander

6

Su 11/04

M 11/12

?

PDF

Chris

7

F 11/09

M 11/19

Th 11/28

PDF

Curtis

8

W 11/21

F 11/30

 

PDF

Sikander

 

Practice Problems

 

Link

Topics

P0

PDF

Basic set theory

P1

PDF

Regular languages

P2

PDF

Context-free languages

P3

PDF

Turing machines and Decidability

P4

PDF

P, NP, NP-completeness

P5

PDF

coNP

P6

PDF

RP, BPP

 

Project for 501 students

 

Lectures (may be slightly revised as the term unfolds)

 

Date

Topics

Readings

Review

Sets, functions, graphs, strings, logic, proofs, induction

Chapter 0

1

W 9/5

What is computation? Start of finite automata

Section 1.1

2

F 9/7

Definition of finite automata

Section 1.1

3

M 9/10

Nondeterministic finite automata

Section 1.2

4

W 9/12

Converting NFA-DFA, Operations on regular languages

Section 1.2, 1.3

5

F 9/14

Regular expressions, Non-regular languages

Section 1.3, 1.4

6

M 9/17

Pumping lemma: Proving languages are not regular

Section 1.4

7

W 9/19

Push down automata          

Section 2.2

8

F 9/21

Context free grammars

Section 2.1

9

M 9/24

Parse trees, Converting CFGs to PDAs

Section 2.1 & 2.2

10

W 9/26

Intro to computability

Section 3.1 & 3.3

11

F 9/28

Turing machines

Section 3.1 & 3.3

12

M 10/1

Decidable & Recognizable Languages, Configurations, Variants of Turing machines

Section 3.2

13

W 10/3

Examples of Multitape and Nondeterministic TMs

Section 3.2

14

F 10/5

Converting NTM to DTM

Section 3.2

M 10/8

No class: Thanksgiving

15

W 10/10

Encodings, Universal Turing Machine, Countable Sets

Section 4.2

16

F 10/12

Undecidability of A_TM

Section 4.2

M 10/15

Midterm Exam

17

W 10/17

Reductions

Section 5.1

18

F 10/19

More reductions

Section 5.1

19

M 10/22

Definition of P, EXP

Section 7.1, 7.2

20

W 10/24

Time hierarchy theorem, Definition of NP

Section 9.1, 7.3

21

F 10/26

Polytime Reductions, 2 Definitions of NP, SAT

Section 7.3

22

M 10/29

NP-hardness and NP-completeness

Section 7.3

23

W 10/31

NP-completeness of Clique

Section 7.5

24

F 11/2

NP-completeness of Vertex Cover

Section 7.5

25

M 11/5

Cook-Levin Theorem

Section 7.4

26

W 11/7

coNP

Umans, Arora-Barak 2.6

27

F 11/9

RP, coRP, BPP

Section 10.2, Arora-Barak 7

 

M 11/12

No class: Remembrance Day

 

28

W 11/14

Communication complexity: definitions and examples

Sherstov 1

29

F 11/16

Protocol trees, Deterministic communication complexity,
Monochromatic rectangles

Sherstov 1

30

M 11/19

Tight analysis of EQ, Fooling sets

Sherstov 1, Sherstov 2

31

W 11/21

Disjointness, Reduction to Network Monitoring

Sherstov 2

32

F 11/23

Nondeterministic Communication Complexity

Sherstov 5

33

M 11/26

Reduction from Equality

34

W 11/28

Nondeterminism and Covers

Sherstov 4, Sherstov 5

35

F 11/30

A proof that “P != NP” and “P = NP intersect coNP”

 

 

Midterm Exam

In-class, Monday October 15th.

·        Material covered: Lectures 1-16.

·        Not covered: GNFAs, Mapping Reductions, Pumping Lemma for CFLs, …

 

 

Piazza­

Piazza signup link: https://piazza.com/ubc.ca/winterterm12018/cpsc421/home

I will use Piazza for all announcements, and you should use it for your own questions and answers about course material. Posting questions to Piazza is a better choice than sending email to the instructor or TAs individually, since all of us are monitoring the group – plus, your classmates may have useful answers! You may choose whether to post questions and answers anonymously or using your own name. If you are asking a question that would reveal too much of a homework solution, then please make sure to post it as a private question so that your classmates cannot see it, only the instructors.

 

Bonus marks: will be given to major contributors to Piazza discussions.

·        1% will be given to selected individuals based on the amount of contributions by asking questions, answering questions whether correct or not.

·        2% will be given to selected individuals based on the amount of quality contributions, endorsed questions and answers, etc.

 

Course Links

Previous versions of this course

·        Fall 2016, Prof. Harvey

·        Fall 2013, Prof. Harvey

·        Fall 2012, Prof. Harvey

·        Fall 2008, Prof. Greenstreet

Related courses at UBC

·        CPSC 506 “Complexity of Computation”, Fall 2016 (Prof. Condon)

Computability theory at other universities

·        Caltech’s “Decidability and Tractability” by Chris Umans

Communication complexity at other universities

·        UCLA's "Communication Complexity" by Alexander Sherstov

·        Aarhus University’s “Communication Complexity” by Joshua Brody

·        Toronto's "Foundations of Communication Complexity" by Toniann Pitassi