Michael sipser introduction to the theory of computation

Cengage Learning, 27-Jun-2012 - Computers - 504 pages

5 Reviews

Reviews aren't verified, but Google checks for and removes fake content when it's identified

Now you can clearly present even the most complex computational theory topics to your students with Sipser's distinct, market-leading INTRODUCTION TO THE THEORY OF COMPUTATION, 3E. The number one choice for today's computational theory course, this highly anticipated revision retains the unmatched clarity and thorough coverage that make it a leading text for upper-level undergraduate and introductory graduate students. This edition continues author Michael Sipser's well-known, approachable style with timely revisions, additional exercises, and more memorable examples in key areas. A new first-of-its-kind theoretical treatment of deterministic context-free languages is ideal for a better understanding of parsing and LR(k) grammars. This edition's refined presentation ensures a trusted accuracy and clarity that make the challenging study of computational theory accessible and intuitive to students while maintaining the subject's rigor and formalism. Readers gain a solid understanding of the fundamental mathematical properties of computer hardware, software, and applications with a blend of practical and philosophical coverage and mathematical treatments, including advanced theorems and proofs. INTRODUCTION TO THE THEORY OF COMPUTATION, 3E's comprehensive coverage makes this an ideal ongoing reference tool for those studying theoretical computing.
Important Notice: Media content referenced within the product description or the product text may not be available in the ebook version.

Registered Office Address:

Flipkart Internet Private Limited,

Buildings Alyssa, Begonia &

Clove Embassy Tech Village,

Outer Ring Road, Devarabeesanahalli Village,

Bengaluru, 560103,

Karnataka, India

CIN : U51109KA2012PTC066107

Telephone: 044-45614700

Required background. To succeed in this class, you need experience and skill with mathematical concepts, theorems, and proofs. If you did reasonably well in 18.062, 18.200, or any other substantial, proof-oriented mathematics class, you should be fine. The class moves quickly, covering about 90% of the textbook. The homework assignments generally require proving some statement, and creativity in finding proofs will be necessary.

Resources

Canvas
Piazza - discussion forum
Gradescope - log in to Canvas first if you have trouble accessing Gradescope
Pset Partners - for finding study groups
Math Learning Center - free tutoring in math subjects including 18.404
Slides and nearly all recorded lectures from 2020 are available - 2022 lectures will not be recorded.
Textbook - Introduction to the Theory of Computation, 3rd edition. It has an errata web site. You may use the 2nd edition but it is missing some additional practice problems, or the International Edition but it numbers a few of the problems differently.

Information, Problem Sets, and Study Materials

Course Information
Problem Set 1 - source - solutions**
Problem Set 2 - source

** Access requires MIT certificates.

Homework submission instructions. Upload a single file with all problems to Gradescope before the due date. Handwritten is ok as long as we can read it easily, otherwise use latex. When Gradescope prompts you, mark the pages containing each problem.

Late homework submission. You may submit any individual problems after the due date, before 11:59pm the following day, for a 1 point per problem late penalty deduction. In each pset, you may submit some problems or problem parts on time and others late. (Note the change in policy, now allowing late problem parts. The penalty will be 10% of the part's point value.) At 2:30pm on the due date, the regular Gradescope assignment will close and a new "late submission" assignment will appear. Please upload only those problems you wish to be counted as late. You may resubmit problems you submitted previously if you wish to change your answer, but these will be marked late and get the 1 point penalty. DO NOT RESUBMIT UNCHANGED PROBLEMS you submitted previously. The late submissions will override earlier submissions. Note: We cannot accept unexcused (see "Student Support" below) homework after the late submission deadline.

Regrade requests. If you feel that your work was incorrectly graded, you may submit a regrade request through gradescope. Please review your graded papers promptly; regrade requests are accepted only for two weeks from the original pset due date. Please do not abuse the regrade system by making lots of frivolous requests; we have limited grader capacity.

Course Staff

Lecturer: Michael Sipser,
Head TA: Zhezheng Luo,
Head TA: Rene Reyes,
TA: Lara Booth,
TA: Jason Chen,
TA: Haimoshri Das,
TA: MingYang Deng,
TA: Jocelin Su,
TA: Jett Wang,

Office Hours

Mondays 2-4pm, 38-166, Jocelin
Mondays 4-6pm, 36-144, Jett
Mondays 5-6pm, Zoom (MIT Certificate required), Mike
Tuesdays 11am-noon, Zoom (MIT Certificate required), Lara
Tuesdays 4:15-5pm, 2-438 (or down the hall), Mike
Tuesdays 5-7pm, 36-112, MingYang
Wednesdays 2-4pm, 26-142, Jason and Rene
Fridays 4-5pm, 36-112, Lara

Lectures and Recitation Sections

Lectures are held in room 34-101 on Tuesdays and Thursdays from 2:30 to 4pm.
The one-hour recitations meet Fridays at the following times and rooms:

10:00am, 2-135, Lara
11:00am, 2-135, Jason
12:00pm, 2-147, Jocelin
1:00pm, 2-147, Rene
2:00pm, 2-139, Jett
3:00pm, 2-139, MingYang

Recitation Notes

September 9 - Jett's notes
September 16 - Jocelin's notes

Exam Schedule

Midterm exam: Thursday, October 27, 2:30 - 4pm, Walker (Building 50), top floor.
Final exam: Tuesday, December 20, 1:30 - 4:30, Johnson Track.

Student Support

If you are dealing with a personal or medical issue that may affect your participation in any MIT class, please discuss it with Student Support Services (S3) at 617-253-4861. They have a Dean on Call 24x7 at 617-253-1212. Graduate students may contact GradSupport. We cannot excuse you from coursework without support from S3 or GradSupport.

If you may require disability accommodations, please speak early in the semester with Associate Dean Kathleen Monagle then let me know so that we can work together to get your accommodation logistics in place.

Course Schedule

9/8 Introduction, finite automata, regular expressions §1.1
9/13 Nondeterminism, closure properties, Reg Exprs → FA §1.2-1.3
9/15 Reg Exprs ← FA, Proving non-regularity via pumping lemma, CFGs §1.4-2.1
9/20 Context free languages, Pushdown Automata, CFG ⇆ PDA §2.2
9/22 Context-free pumping lemma, Turing machines §2.3,3.1 Pset 1 DUE
9/27 TM variants, Church-Turing thesis §3.2-3.3
9/29 Decision problems for automata and grammars §4.1
10/4 Undecidability §4.2
10/6 Reducibility §5.1,5.3 Pset 2 DUE
10/11 NO CLASS --- Student Holiday
10/13 Computation history method §5.2
10/18 Recursion theorem, Logic §6.1-6.2
10/20 Time complexity §7.1 Pset 3 DUE
10/25 P and NP, SAT, Poly-time reducibility §7.2-7.3
10/27 Midterm Exam
11/1 NP-completeness §7.5
11/3 Cook-Levin theorem §7.4
11/8 Space complexity, PSPACE §8.1-8.2
11/10 Savitch's theorem, PSPACE-completeness §8.3 Pset 4 DUE
11/15 Games, Generalized geography, L and NL §8.3-8.4
11/17 NL-completeness, NL = coNL §8.4
11/22 Hierarchy theorems §9.1
11/24 NO CLASS --- Thanksgiving
11/29 Provably intractable problems, oracles §9.2 Pset 5 DUE
12/1 Probabilistic computation, BPP §10.2
12/6 An interesting language in BPP, Arithmetization §10.2
12/8 Interactive proof systems, IP §10.4 Pset 6 DUE
12/13 coNP ⊆ IP §10.4

2020 Lectures

Slides
Videos OCW, YouTube

Accessibility

What is computation theory?

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., approximate solutions versus precise ones).

Is theory of Computing useful?

Theory of Computation is very important as it helps in writing efficient algorithms that operate on computer devices, research and development of programming languages and in compiler design and construction that is efficient.

What is automata theory in computer science?

Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word automata comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving".