Algorithm算法代写代考

CS 332: Elements of Theory of Computation Prof. Mark Bun Boston University February 18, 2021 Test 1 � Read all the instructions on this page before beginning the exam. � Your solutions must be scanned and uploaded to Gradescope by 11:59PM Eastern Standard Time, Thursday February 25, 2020. � We are flexible with the format […]

Microsoft PowerPoint – CS332-Lec17-ann BU CS 332 – Theory of Computation Lecture 17: • Mapping Reductions Reading: Sipser Ch 5.3 Mark Bun March 21, 2021 Reductions A reduction from problem  to problem  is an algorithm  for problem  which uses an algorithm for problem  as a  subroutine If such a reduction exists, we say “ reduces to  ” 3/22/2021 CS332 ‐ Theory of Computation 2 Positive uses: If  reduces to  and  is decidable, then  is also decidable Ex.  is decidable  is decidable Negative uses: If  reduces to  and  is undecidable,  then  is also undecidable Ex.  is undecidable  is undecidable  What’s wrong with the following “proof”? Bogus “Theorem”:  is not Turing‐recognizable Bogus “Proof”: Suppose for contradiction that there exists a recognizer  for  . We construct a recognizer for 

CS 332: Theory of Computation Prof. Mark Bun Boston University February 15, 2021 Homework 3 – Due Thursday, February 18, 2021 at 11:59 PM Reminder Collaboration is permitted, but you must write the solutions by yourself without as- sistance, and be ready to explain them orally to the course staff if asked. You must also

PowerPoint Presentation BU CS 332 – Theory of Computation Lecture 13: • Decidable Languages • Universal TM • Countability and Diagonalization Reading: Sipser Ch 4.1, 4.2 Mark Bun March 8, 2021 A “universal” algorithm for recognizing regular languages 𝐴𝐴DFA = 𝐷𝐷,𝑤𝑤 DFA 𝐷𝐷 accepts 𝑤𝑤} Theorem: 𝐴𝐴DFA is decidable Proof: Define a 3-tape TM 𝑀𝑀

Microsoft PowerPoint – CS332-Lec25-ann BU CS 332 – Theory of Computation Lecture 25: • Final review Reading: Sipser Ch 7.1‐8.2, 9.1 Mark Bun April 28, 2021 Final Topics 4/28/2021 CS332 ‐ Theory of Computation 2 Everything from Midterms 1 and 2 • Midterm 1 topics: DFAs, NFAs, regular expressions,  distinguishing set method (more detail in lecture 8 notes) • Midterm 2 topics: Turing machines, TM variants, Church‐ Turing thesis, decidable languages, countable and  uncountable sets, undecidability, reductions,  unrecognizability  (more detail in lecture 16 notes) 4/28/2021 CS332 ‐ Theory of Computation 3 Mapping Reducibility (5.3) • Understand the definition of a computable function • Understand the definition of a mapping reduction • Know how to use mapping reductions to prove  decidability, undecidability, recognizability, and  unrecognizability 4/28/2021 CS332 ‐ Theory of Computation 4 Time and Space Complexity (7.1) • Asymptotic notation: Big‐Oh, little‐oh • Know the definition of running time and space for a TM  and of time and space complexity classes (TIME / NTIME  / SPACE / NSPACE)

CS 332: Theory of Computation Prof. Mark Bun Boston University January 24, 2021 Math and Algorithms Review A firm background in discrete math, algorithms, and mathematical problem-solving / proof-writing will set you up for success in CS 332. You should be comfortable with almost all of the topics listed below and know how to complete

PowerPoint Presentation BU CS 332 – Theory of Computation Lecture 11: • TM Variants and Closure Properties • Church-Turing Thesis Reading: Sipser Ch 3.2 Mark Bun March 1, 2021 TM Variants 2/28/2021 CS332 – Theory of Computation 2 TMs are equivalent to… • TMs with “stay put” • TMs with 2-way infinite tapes • Multi-tape