CSE 303: Introduction to the Theory of Computation

2024-09-09 Admin 写评论

Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

CSE 303: Introduction to the Theory of Computation

Classes
Asynchronous
Instructor
Prof. Pramod Ganapathi
Office hours: Tuesday 07:30 am - 10:30 am via Zoom
TA's
Google Sheets link
Tutoring
CEAS Free Tutoring Service Schedule

Course Description
In this course, we will learn the mathematical theory of computation, computers, algorithms, and complexity. In this course, we will learn what can be computed (i.e., capabilities) and what cannot be computed at all (i.e., limitations) on a computer. We also learn, if something can be computed, how efficiently can it be computed (i.e., complexity). The topics covered include:
  • Computation models (finite automata, pushdown automata, and Turing machines)
  • Grammars accepted by different computation models (regular grammars, context-free grammars, and unrestricted grammars)
  • Languages accepted by different computation models (regular languages, context-free languages, and Turing-acceptable languages)
  • Turing-complete systems
  • Algorithmically unsolvable problems
  • Algorithmically hard problems
Prerequisites
C or higher: CSE 214 and 215 and CSE major.
Course Outcome
At the end of the course, the students should have the following knowledge and skills:
  • Understand the motivations behind and differences between various computation models
  • An ability to determine the algorithmic complexity or algorithmic impossibility of a given computational problem
  • An ability to determine the simplest computation model to solve a given computational problem
Textbook
  • [R] Automata, Computability and Complexity: Theory and Applications. Elaine Rich.
  • [LP] Elements of the Theory of Computation. Harry R. Lewis and Christos H. Papadimitriou. 2nd Edition.
  • [M] Introduction to Languages and the Theory of Computation. John Martin. 4th Edition.
Other Resources
  • Theory of Computation Lecture Notes
    • Margaret Fleck and Sariel Har-Peled's Notes.
    • Johan Hastad's Notes.
    • Jeff Erickson's Notes.
    • Michael Levet's Notes.
    • Jim Hefferson's Notes.
    • Peter Gacs and Laszlo Lovasz's Notes.
  • Theory of Computation
    • [S] Introduction to the Theory of Computation. Michael Sipser. 3rd Edition.
    • [K] Automata and Computability. Dexter C. Kozen.
    • [HMU] Introduction to Automata Theory, Languages, and Computation. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2nd Edition.
    • [MS] Introduction to Theory of Computation. Anil Maheshwari and Michiel Smid.
    • [FB] The Language of Machines. Robert W. Floyd and Richard Biegel.
    • [DK] Problem Solving in Automata, Languages, and Complexity. Ding-Zhu Du and Ker-I Ko.
  • Books for Generic Audience
    • Turing's Vision. Chris Bernhardt.
    • The Annotated Turing. Charles Petzold.
    • The Outer Limits of Reason. Noson S. Yanofsky.
  • Video Courses
    • Portland State University. Harry Potter.
    • IIT Kanpur. Raghunath Tewari.
    • ADUni. Shai Simonson.
  • JFLAP Software
    • Education tool to help experiment with DFA, regular expressions, NFA, grammars, and Turing machines.
    • Download.
    • Tutorial videos.
    • Book.
  • LaTeX
    • [OL] Learn LaTeX in 30 Minutes. Overleaf.
    • [WBL] Wikibook on LaTeX. Wikipeople.
    • [NSIL] The Not So Short Introduction to LaTeX. Tobias Oetiker.
    • [LCN] LaTeX for Complete Novices. Nicola L. C. Talbot (More Books).
    • [MML] More Math into LaTeX. George Gratzer. 4th Edition.
    • [LT] LATEX Tutorials. Indian Users Group.
    • [SIL] A Simplified Introduction to LaTeX. Harvey J. Greenberg.
    • More Books
  • Mathematical Writing
    • [SMW] Mathematical Writing. Donald E. Knuth, Tracy Larrabee, and Paul M. Roberts.
    • [HWMS] Handbook of Writing for the Mathematical Sciences. 2nd Edition. Nicholas J. Higham.
Grading
CSE 303 course requirements and grading are as follows:
  • Homeworks: 40%
  • Project: 10% (presentation: 5%, work and writing: 5%)
  • Midterm: 20%
  • Final: 30%
  • Bonus points: up to 5% depending on creativity
Homework
Homework assignments will be posted on Brightspace: https://it.stonybrook.edu/services/brightspace.

Academic calendar
Lectures
Class Schedule
Slides
Study
Optional Learning Materials
2 sessions Introduction (Course Info, Motivation, Course Overview) [PDF] [M, Ch. 1]
6 sessions Computation Model → Finite Automata
Grammars → Regular Grammars (or Type-3 Grammars)
Languages → Regular Languages 		[PDF] [M, Ch. 2, 3]
6 sessions Computation Model → Pushdown Automata
Grammars → Context-Free Grammars (or Type-2 Grammars)
Languages → Context-Free Languages 		[PDF] [M, Ch. 4, 5, 6]
1 session Midterm Exam Time: Thursday July 20, 6-7:30 pm, Venue: Office hours Zoom link
5 sessions Computation Model → Turing Machines
Grammars → Unrestricted Grammars (or Type-0 Grammars)
Languages → Turing-Semidecidable Languages 		[PDF] [PDF] [M, Ch. 7, 8] Morten Tyldum's The Imitation Game, Lambda Calculus
5 sessions Algorithmically Solvable/Unsolvable Problems [PDF] [M, Ch. 9, 10] Undecidability: (Part 1, Part 2, Part 3), Halting Problem, Busy Beaver Problem, Chomsky Hierarchy, Self-replicating program
1 session Algorithmically Hard Problems [PDF] [M, Ch. 11] Erik Demaine's Complexity I, Complexity II, Michael Sipser's P vs. NP Problem, Avi Wigderson's P vs. NP Problem, Complexity Zoo
1 session Final Exam Time: Thursday August 17, 6-8:30 pm, Venue: Office hours Zoom link

发表评论

电子邮件地址不会被公开。 必填项已用*标注