5.20. Theory of Computation (Mandatory)

5.20. Theory of Computation (Mandatory)

  • Semester: 4th Sem. Credits: 4
  • Hour of this course: Theory: 2 hours; Practice: 2 hours; Laboratory: 2 hours;
  • Syllabus:

    Español
    English
    - htmlonly
  • Prerrequisites:
    • CS1D1 Discrete Structures (2nd Sem) itemize
    Figure 5.20: Connection Map. CS211 Theory of Computation

    5.20.1. Justification ↑ Back to top

    Theory of Computation provides the mathematical foundations to understand what can be computed and how efficiently. It introduces formal languages, automata, and the limits of algorithmic solvability. This knowledge is fundamental for understanding compiler construction, formal verification, and the inherent complexity of computational problems.

    5.20.2. Generales Goals ↑ Back to top

    1. Master the concepts of finite automata and regular expressions.
    2. Analyze context-free grammars and pushdown automata.
    3. Understand the Universal Turing Machine as a model of computation.
    4. Comprehend the boundaries of computability and the Halting Problem.
    5. Differentiate between complexity classes like P and NP.

    5.20.3. Contribution to Outcomes ↑ Back to top

    AG-C08) Problem Analysis: Identifies, formulates, and analyzes complex computing problems. (Usage)
    AG-C12) Applies computer science theory and software development fundamentals to produce computer-based solutions. (Usage)

    5.20.4. Content ↑ Back to top

    5.20.4.1. Formal Languages and Automata (18 hours) [Skills AG-C08,AG-C12] ↑ Back to top

    Bibliography: (Sipser, 2012; Hopcroft et al., 2013)

    Topics

    1. Formal automata:
      1. Finite State
      2. Pushdown
      3. Linear Bounded
      4. Turing Machine enumerate
      5. Formal languages, grammars and Chomsky Hierarchy:
        1. Regular (Type-3):
          1. Regular Expressions enumerate
          2. Context-Free (Type-2)
          3. Context-Sensitive (Type-1)
          4. Recursively Enumerable (Type-0) enumerate )
          5. Deterministic and nondeterministic automata
          6. Pumping Lemma proofs:
            1. Proof of Finite State/Regular-Language limitation
            2. Pushdown Automata/Context-Free-Language limitation enumerate

            Learning Outcomes

            1. For each formal automaton in this unit:
              1. Explain its definition comparing its characteristics with this unit's other automata
              2. Using an example, explain step-by-step how the automaton operates on input including whether it accepts the associated input
              3. Explain an example of inputs that can and cannot be accepted by the automaton. enumerate [Explain]
              4. Given a problem, develop an appropriate automaton that addresses the problem [Create]
              5. Develop a regular expression for a given regular language expressed in natural language [Create]
              6. Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs [Apply]
              7. Apply pumping lemmas, or alternative means, to prove the limitations of Finite State and Pushdown automata [Apply]
              5.20.4.2. Formal Languages and Automata (16 hours) [Skills AG-C08,AG-C12] ↑ Back to top

              Bibliography: (Sipser, 2012; Hopcroft et al., 2013)

              Topics

              1. Formal automata:
                1. Finite State
                2. Pushdown
                3. Linear Bounded
                4. Turing Machine enumerate
                5. Formal languages, grammars and Chomsky Hierarchy:
                  1. Regular (Type-3):
                    1. Regular Expressions enumerate
                    2. Context-Free (Type-2)
                    3. Context-Sensitive (Type-1)
                    4. Recursively Enumerable (Type-0) enumerate
                    5. Normal Forms: Chomsky and Greibach
                    6. Pumping Lemma proofs:
                      1. Proof of Finite State/Regular-Language limitation
                      2. Pushdown Automata/Context-Free-Language limitation enumerate
                      3. Relations among formal automata, languages, and grammars

                      Learning Outcomes

                      1. For each formal automaton in this unit:
                        1. Explain its definition comparing its characteristics with this unit's other automata
                        2. Using an example, explain step-by-step how the automaton operates on input including whether it accepts the associated input
                        3. Explain an example of inputs that can and cannot be accepted by the automaton. enumerate [Explain]
                        4. Given a problem, develop an appropriate automaton that addresses the problem [Create]
                        5. Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs [Apply]
                        6. Apply pumping lemmas, or alternative means, to prove the limitations of Finite State and Pushdown automata [Apply]
                        7. Construct CFGs for formal language descriptions [Assessment]
                        5.20.4.3. Formal Languages and Automata (16 hours) [Skills AG-C08,AG-C12] ↑ Back to top

                        Bibliography: (Sipser, 2012; Kozen, 2006)

                        Topics

                        1. Formal automata:
                          1. Finite State
                          2. Pushdown
                          3. Linear Bounded
                          4. Turing Machine enumerate
                          5. Formal languages, grammars and Chomsky Hierarchy:
                            1. Regular (Type-3):
                              1. Regular Expressions enumerate
                              2. Context-Free (Type-2)
                              3. Context-Sensitive (Type-1)
                              4. Recursively Enumerable (Type-0) enumerate
                              5. Decidability, (un)computability, and halting
                              6. The Church-Turing thesis
                              7. Reducibility and reductions
                              8. Equivalent models of algorithmic computation:
                                1. Turing Machines and Variations (e.g., multi-tape, non-deterministic)
                                2. Lambda Calculus
                                3. Mu-Recursive Functions enumerate

                                Learning Outcomes

                                1. For each formal automaton in this unit:
                                  1. Explain its definition comparing its characteristics with this unit's other automata
                                  2. Using an example, explain step-by-step how the automaton operates on input including whether it accepts the associated input
                                  3. Explain an example of inputs that can and cannot be accepted by the automaton. enumerate [Explain]
                                  4. Explain a universal Turing Machine and its operation [Explain]
                                  5. Present to an audience of co-workers and managers the impossibility of providing them a program that checks all other programs, including some seemingly simple ones, for infinite loops including an explanation of the Halting problem, why it has no algorithmic solution, and its significance for real-world algorithmic computation [Explain]
                                  6. Explain the Church-Turing Thesis and its significance for algorithmic computation [Explain]
                                  7. Apply arithmetization and diagonalization to prove the Halting Problem for Turing Machines is Undecidability [Apply]
                                  8. Given a known undecidable language, apply a mapping reduction or computational history to prove that another language is undecidable [Apply]
                                  5.20.4.4. Formal Languages and Automata (12 hours) [Skills AG-C08,AG-C12] ↑ Back to top

                                  Bibliography: (Sipser, 2012; Kozen, 2006)

                                  Topics

                                  1. Formal languages, grammars and Chomsky Hierarchy:
                                    1. Regular (Type-3):
                                      1. Regular Expressions enumerate
                                      2. Context-Free (Type-2)
                                      3. Context-Sensitive (Type-1)
                                      4. Recursively Enumerable (Type-0) enumerate
                                      5. Relations among formal automata, languages, and grammars
                                      6. Equivalent models of algorithmic computation:
                                        1. Turing Machines and Variations (e.g., multi-tape, non-deterministic)
                                        2. Lambda Calculus
                                        3. Mu-Recursive Functions enumerate
                                        4. Context-Sensitive Languages (Type-1) and applications

                                        Learning Outcomes

                                        1. For each formal model in this unit:
                                          1. Explain its definition comparing its characteristics with the others in this unit
                                          2. Explain example inputs that are and cannot be accepted by the language/grammar. enumerate [Explain]
                                          3. Explain the Primitive and General Recursive functions (zero, successor, selection, primitive recursion, composition, and Mu), their significance, and Turing Machine implementations [Explain]
                                          4. Explain how computation is performed in Lambda Calculus (e.g., Alpha conversion and Beta reduction) [Explain]
                                          5. Explain Rice's theorem and its significance [Explain]
                                          5.20.4.5. Complexity Analysis Framework (3 hours) [Skills AG-C08,AG-C12] ↑ Back to top

                                          Bibliography: (Sipser, 2012; Cormen et al., 2022)

                                          Topics

                                          1. Complexity Analysis Framework:
                                            1. Best, average, and worst-case performance of an algorithm
                                            2. Empirical and relative (Order of Growth) measurements
                                            3. Input size and primitive operations
                                            4. Time and space efficiency enumerate

                                            Learning Outcomes

                                            1. Prepare a presentation that explains to first year students the basic concepts of algorithmic complexity including best, average, and worst-case algorithm behavior, Big-O, Omega, and Theta notations, complexity classes, time and space tradeoffs, empirical measurement, and impact on practical problems [Explain]
                                            2. Informally evaluate the foundational complexity class of simple algorithms [Evaluate]
                                            5.20.4.6. Asymptotic Notation and Complexity Classes (4 hours) [Skills AG-C08,AG-C12] ↑ Back to top

                                            Bibliography: (Sipser, 2012; Cormen et al., 2022)

                                            Topics

                                            1. Asymptotic complexity analysis (average and worst-case bounds):
                                              1. Big-O, Big-Omega, and Big-Theta formal notations
                                              2. Foundational Complexity Classes and Representative Examples/Problems:
                                                1. \(O(1)\) Constant (e.g., array access)
                                                2. \(O(\log_2 n)\) Logarithmic (e.g., binary search)
                                                3. \(O(n)\) Linear (e.g., linear search)
                                                4. \(O(n \log_2 n)\) Log Linear (e.g., mergesort)
                                                5. \(O(n^2)\) Quadratic (e.g., selection sort)
                                                6. \(O(n^c)\) Polynomial (e.g., \(O(n^3)\) Gaussian elimination)
                                                7. \(O(2^n)\) Exponential (e.g., Knapsack, Satisfiability (SAT), Traveling Sales-Person (TSP), all subsets)
                                                8. \(O(n!)\) Factorial (e.g., Hamiltonian circuit, all permutations) enumerate enumerate

                                                Learning Outcomes

                                                1. Using examples, explain each of the foundational complexity classes in this unit [Explain]
                                                2. Explain to a non-technical audience the significance of tractable versus intractable algorithms using an intuitive explanation of Big-O complexity [Explain]
                                                5.20.4.7. Complexity Analysis: Recursion, Amortization, and Tight Bounds (7 hours) [Skills AG-C08,AG-C12] ↑ Back to top

                                                Bibliography: (Sipser, 2012; Cormen et al., 2022)

                                                Topics

                                                1. Little-o, Little-Omega, and Little Theta notations
                                                2. Formal recursive analysis

                                                Learning Outcomes

                                                1. Use recurrence relations to evaluate the time complexity of recursively defined algorithms [Apply]
                                                2. Apply elementary recurrence relations using a form of the Master Theorem [Apply]
                                                5.20.4.8. Computational Complexity Theory (6 hours) [Skills ] ↑ Back to top

                                                Bibliography: (Sipser, 2012; Cormen et al., 2022)

                                                Topics

                                                1. Tractability and intractability:
                                                  1. P, NP, and NP-Complete Complexity Classes
                                                  2. NP-Complete Problems (e.g., SAT, Knapsack, TSP)
                                                  3. Reductions enumerate
                                                  4. Turing Machine-based models of complexity:
                                                    1. Time complexity:
                                                      1. P, NP, NP-C, and EXP classes
                                                      2. Cook-Levin theorem enumerate
                                                      3. Space Complexity:
                                                        1. NSpace and PSpace
                                                        2. Savitch's theorem enumerate enumerate

                                                        Learning Outcomes

                                                        1. Explain the significance of NP-Completeness [Explain]
                                                        2. Explain how NP-Hard is a lower bound and NP is an upper bound for NP-Completeness [Explain]
                                                        3. Explain examples of NP-complete problems [Explain]
                                                        4. Explain the Cook-Levin Theorem and the NP-Completeness of SAT [Explain]
                                                        5. Explain the classes P and NP [Explain]
                                                        6. Prove that a problem is NP-Complete by reducing a classic known NP-C problem to it (e.g., 3SAT and Clique) [Create]
                                                        7. Explain the P-space class and its relation to the EXP class [Explain]

                                                        5.20.5. Bibliography ↑ Back to top

                                                        Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning, 3rd edition.

                                                        Hopcroft, J. E., Motwani, R., and Ullman, J. D. (2013). Introduction to Automata Theory, Languages, and Computation. Pearson, 3rd edition.

                                                        Kozen, D. C. (2006). Theory of Computation. Springer.

                                                        Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2022). Introduction to Algorithms. MIT Press, 4th edition.

                                                        Spotted a typo, an outdated course, a broken link, or have a suggestion? Let us know.

                                                        Scan to open on your phone