BU CS 332 – Theory of Computation Lecture 9: • Midterm I review Reading: Sipser Ch 0-2.3 Mark Bun February 19, 2020 Midterm I Topics 2/18/2020 CS332 – Theory of Computation 2 Deterministic FAs (1.1) • Given an English or formal description of a language 𝐿, draw the state diagram of a DFA recognizing 𝐿 […]
CS代考计算机代写 algorithm compiler BU CS 332 – Theory of Computation Read More »
BU CS 332 – Theory of Computation Lecture 21: • NP-Completeness • Cook-Levin Theorem • Reductions Mark Bun April 15, 2020 Reading: Sipser Ch 7.3-7.5 Last time: Two equivalent definitions of NP 1) NP is the class of languages decidable in polynomial time on a nondeterministic TM NP = ⋃∞ NTIME(𝑛𝑛𝑘𝑘) 𝑘𝑘=1 2) A polynomial-time
CS代考计算机代写 AI algorithm BU CS 332 – Theory of Computation Read More »
BU CS 332 – Theory of Computation Lecture 23: • Savitch’s Theorem • PSPACE-Completeness • Unconditional Hardness • Course Evaluations Mark Bun April 27, 2020 Reading: Sipser Ch 8.1-8.3, 9.1 Space analysis Space complexity of a TM (algorithm) = maximum number of tape cell it uses on a worst-case input Formally: Let 𝑓𝑓 ∶ N
CS代考计算机代写 algorithm BU CS 332 – Theory of Computation Read More »
Foundations and Trends⃝R in Theoretical Computer Science Vol. 4, Nos. 1–2 (2008) 1–155 ⃝c 2009 S. V. Lokam DOI: 10.1561/0400000011 Complexity Lower Bounds using Linear Algebra By Satyanarayana V. Lokam Contents 1 Introduction 2 1.1 Scope 2 1.2 Matrix Rigidity 3 1.3 Spectral Techniques 4 1.4 Sign-Rank 5 1.5 Communication Complexity 6 1.6 Graph Complexity
CS 535: Complexity Theory, Fall 2020 Homework 2 Due: 8:00PM, Friday, September 18, 2020. Reminder. Homework must be typeset with LATEX preferred. Make sure you understand the course collaboration and honesty policy before beginning this assignment. Collaboration is permitted, but you must write the solutions by yourself without assistance. You must also identify your collaborators.
CS代考计算机代写 algorithm CS 535: Complexity Theory, Fall 2020 Homework 2 Read More »
BU CS 332 – Theory of Computation Lecture 16: • Mapping Reducibility Reading: Sipser Ch 5.3 Mark Bun March 25, 2020 Problems in language theory 3/30/2020 CS332 ‐ Theory of Computation 2 𝐃𝐅𝐀 𝐂𝐅𝐆 𝐓𝐌 decidable decidable undecidable 𝐓𝐌 𝐃𝐅𝐀 𝐂𝐅𝐆 decidable decidable undecidable 𝐓𝐌 decidable ? ? 𝐃𝐅𝐀 𝐂𝐅𝐆 Reductions A reduction from problem
CS代考计算机代写 algorithm BU CS 332 – Theory of Computation Read More »
BU CS 332 – Theory of Computation Lecture 22: • NP-Completeness Example • Space Complexity • Savitch’s Theorem Mark Bun April 22, 2020 Reading: Sipser Ch 8.1-8.2 NP-completeness Definition: A language 𝐵𝐵 is NP-complete if 1) 𝐵𝐵 ∈ NP, and 2) Every language 𝐴𝐴 ∈ NP is poly-time reducible to 𝐵𝐵, i.e., 𝐴𝐴 ≤p 𝐵𝐵
CS代考计算机代写 algorithm BU CS 332 – Theory of Computation Read More »
BU CS 332 – Theory of Computation Lecture 13: • Mid-Semester Feedback • Enumerators • Decidable Languages • Countability Reading: Sipser Ch 4.1 Mark Bun March 16, 2020 What aspects of the course help you learn best? • Examples in class • Reviewing past homeworks/exams in class • Textbook • Posting materials online • Lecture,
CS代考计算机代写 Java Context Free Languages python algorithm BU CS 332 – Theory of Computation Read More »
BU CS 332 – Theory of Computation Lecture 7: • More on CFGs • Pushdown Automata Reading: Sipser Ch 2.1-2.3 Mark Bun February 12, 2020 Context-Free Grammar (Formal) A CFG is a 4-tuple 𝐺 = 𝑉,Σ,𝑅,𝑆 • 𝑉 is a finite set of variables • Σ is a finite set of terminal symbols (disjoint from
CS代考计算机代写 algorithm BU CS 332 – Theory of Computation Read More »
BU CS 332 – Theory of Computation Lecture 13: • Mid‐Semester Feedback • Enumerators • Decidable Languages Reading: Sipser Ch 4.1 Mark Bun March 16, 2020 What aspects of the course help you learn best? • Examples in class • Reviewing past homeworks/exams in class • Textbook • Posting materials online • Lecture, generally •
CS代考计算机代写 Java Context Free Languages python algorithm BU CS 332 – Theory of Computation Read More »