Fall 2017 - 5020 - Foundations of Computer Science

Instructor: Matteo Cimini (email: matteo_cimini [A_T] uml [DOT] edu)
Instructor's office hours: Mon and Tue at 1:00-2:30PM.
Only for the first week of class: Office hours are on Friday 8th September 10AM-1PM.
Where we meet: Olsen Hall 103
When: Wednesday 5:30PM - 8:15PM.
First class: 6th Sept.

Description of the Course


An advanced introduction to theoretical computer science. This course will cover the fundamentals of automata, formal languages, and computability theory.

Readings


Textbook: Introduction to the Theory of Computation (3rd Edition), by Michael Sipser.
Below, I refer to the textbook as ITC.

Lectures


Week Date Topic Notes
1 Sept. 6th Introduction & Preliminaries ITC 0
2 Sept. 13th Finite Automata ITC 1.1
3 Sept. 20th Nondeterministic Finite Automata ITC 1.2
4 Sept. 27th Regular Expressions ITC 1.3
5 Oct. 4th Nonregular Languages & Context-free Grammars ITC 1.4, 2.1
6 Oct. 11th Pushdown Automata ITC 2.2
7 Oct. 18th Non-Context-free Grammars & Midterm Review ITC 2.3
8 Oct. 25th Midterm
9 Nov. 1st Turing Machines ITC 3.1
10 Nov. 8th Variants of Turing Machines & Church Thesis ITC 3.2, 3.3
11 Nov. 15th Decidable Problems ITC 4.1
12 Nov. 22th No class
13 Nov. 29th Undecidable Problems ITC 4.2
14 Dec. 6th Reducibility ITC 5.1, 5.2
15 Dec. 13th Final Review
TBD Final Exam
(This schedule may be subject to small changes)

Evaluation and Grade Calculation


There are four evaluations:
  • Project & Presentation #1 will receive a grade between 0 and 1.
  • Midterm will receive a grade between 0 and 1.25.
  • Project & Presentation #2 will receive a grade between 0 and 1.
  • Final Exam will receive a grade between 0 and 1.25.

    Project & Presentation #1  20% score x 0.2 +
    Midterm 30% score x 0.3 +
    Project & Presentation #2 20% score x 0.2 +
    Final 30% score x 0.3 =
    Your numeric grade

    Letter Grades are computed as follows:

    Your numeric grade >= 0.94 A
    Your numeric grade >= 0.9 A-
    Your numeric grade >= 0.86 B+
    Your numeric grade >= 0.82 B
    Your numeric grade >= 0.8 B-
    Your numeric grade >= 0.76 C+
    Your numeric grade >= 0.72 C
    Your numeric grade >= 0.7 C-
    Your numeric grade >= 0.66 D+
    Your numeric grade >= 0.6 D
    Your numeric grade  <  0.6 F


    Midterm


    The midterm will cover the following topics:
    Introduction & Preliminaries - Finite Automata - Nondeterministic Finite Automata - Regular Expressions - Nonregular Languages & Context-free Grammars - Pushdown Automata.

    Final Exam


    The final exam will cover the following topics:
    Non-Context-free Grammars - Turing Machines - Variants of Turing Machines & Church Thesis - Decidable Problems - Undecidable Problems - Reducibility

    Project & Presentation #1


    Implement an interpreter for DFAs that takes their 5-tuple representation and a string, then returns whether the string is accepted or not.
    Also, extend your implementation with a compiler from NFAs to DFAs.

    Schedule an appointment with me, where you will show your implementation.
    You are responsible for showing meaningful running examples.
    I will ask you to test your implementation against additional examples. (You will not be asked to solve exercises at this time.)
    The presentation will last approx. 15 minutes.
    Deadline: Presentations must be done before the 25th October. Make plans to meet me in advance.

    Project & Presentation #2


    Build your own Automata Tool Kit: Extend Project & Presentation #1 with at least 3 features among:
      Implement a compiler from regular expressions to NFAs.
      Implement a direct interpreter for NFAs.
      Implement an interpreter for CFGs that takes their tuple representation and can generate all strings from the language up to some depth.
      Implement a compiler from general CFGs to CFGs in Chomsky normal form.
      Implement a compiler from CFGs to PDAs.
      Implement an interpreter for PDAs that takes their tuple representation and a string, and returns whether the string is accepted or not.
      Implement a compiler from PDAs to CFGs.
      Implement an interpreter for Turing machines.
      Implement an interpreter for multitape Turing machines.
      Implement an interpreter for nondeterministic Turing machines.
      Implement a compiler from multitape Turing machines to standard Turing machines.
      Implement a compiler from nondeterministic Turing machines to multitape Turing machines.
      You can propose your own extension but I have to agree with that.

    Schedule an appointment with me, where you will present your software tool.
    You are responsible for showing meaningful running examples.
    I will ask you to test your implementation against additional examples. (You will not be asked to solve exercises at this time.)
    The presentation will last approx. 30 minutes.
    Deadline: Presentations must be done before the 6th December. Make plans to meet me in advance.

    Acknowledgments


    The design of this course borrows in part from similar courses by Jay Maccharty.