Fall 2018 - 5020 - Foundations of Computer Science

Instructor: Matteo Cimini (email: matteo_cimini [A_T] uml [DOT] edu)
Instructor's office hours: Wednesday 3:30-5:30PM, and Thursday 2:30-3:30PM
Exceptions:
  • Wednesday 12th Sept: 1:00-3:00PM
  • Wednesday 3rd Oct: 1:00-3:00PM
  • Wednesday 7th Nov: 1:00-3:00PM
  • Wednesday 13th Dec: 1:00-3:00PM

    Where we meet: Southwick Hall 401.
    When: Wednesday 6:30PM - 9:20PM.
    First class: 5th Sept.
    Midterm: Wednesday 24th October, 6:30PM - 9:20PM, Room: Southwick Hall 401.
    Final Exam: Wednesday 19th December, 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. 5th Introduction & Preliminaries ITC 0
    2 Sept. 12th Finite Automata ITC 1.1
    3 Sept. 19th Nondeterministic Finite Automata ITC 1.2 | additional notes
    4 Sept. 26th Regular Expressions ITC 1.3
    5 Oct. 3rd Nonregular Languages & Context-free Grammars ITC 1.4, 2.1
    6 Oct. 10th Pushdown Automata ITC 2.2 | additional notes
    7 Oct. 17th Non-Context-free Languages & Midterm Review Self-study week
    8 Oct. 24th Midterm. Time: 6:30PM - 9:20PM Room: Southwick Hall 401
    9 Oct. 31st Turing Machines ITC 3.1 | additional notes
    10 Nov. 7th Variants of Turing Machines & Church-Turing Thesis  ITC 3.2, 3.3
    11 Nov. 14th Non-Context-free Languages & Decidable Problems ITC 2.3, 4.1
    12 Nov. 21th No class
    13 Nov. 28th Undecidable Problems ITC 4.2
    14 Dec. 5th Reducibility ITC 5.1, 5.2
    15 Dec. 12th Final Review
    Dec. 19th 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 #1 will receive a grade between 0 and 1.
  • Midterm will receive a grade between 0 and 1.25.
  • Project #2 will receive a grade between 0 and 1.
  • Final Exam will receive a grade between 0 and 1.25.

    Project #1  20% score x 0.2 +
    Midterm 30% score x 0.3 +
    Project #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 6:30PM - 9:20PM, Room: Southwick Hall 401
    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


    Time: Wednesday 19th December, 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 #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: Appointments must be requested by Wednesday 10th October. Project presentations must be done by Friday 19th October.

    Project #2


    Build your own Automata Tool Kit: Extend Project #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: Appointments must be requested by Monday 26th November. Project presentations must be done by Wednesday 5th December.

    Acknowledgments


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