Fall 2017 - 5020 - Foundations of Computer Science

Instructor: Matteo Cimini (email: matteo_cimini [A_T] uml [DOT] edu)
Instructor's office hours: Tue and Wed at 1:00-2:30PM. (Notice that Mon changed to Wed)
Where we meet: Olsen Hall 103
When: Wednesday 5:30PM - 8:15PM.
First class: 6th Sept.
Midterm: Wednesday 25th Oct. 6:00PM - 9:00PM, Room: Olsen Hall 103
Final Exam: Wednesday 20th Dec. 6:30PM - 9:30PM, Room: TBD

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 Languages & Midterm Review ITC 2.3
8 Oct. 25th Midterm. Time: 6:00PM - 9:00PM, Room: Olsen 103
9 Nov. 1st Turing Machines ITC 3.1
10 Nov. 8th Variants of Turing Machines & Church-Turing 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
Dec. 20th Final Exam. Time: 6:30PM - 9:30PM, Room: TBD
(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


    Wednesday 25th Oct. 6:00PM - 9:00PM, Room: Olsen Hall 103
    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


    Wednesday 20th Dec. 6:30PM - 9:30PM, Room: TBD
    The final exam will cover the following topics:
    Non-Context-free Languages - Turing Machines - Variants of Turing Machines & Church-Turing 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.)
    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 feature to produce the DFA for the union, intersection and complement of DFAs. (If you implement the feature for combining only DFAs that have a same alphabet is fine).
      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 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.)
    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 that of similar courses by Jay Maccharty.