Spring 2020 - 3040 - Foundations of Computer Science

Instructor: Matteo Cimini (email: matteo_cimini [A_T] uml [DOT] edu)
Instructor's office hours: Tuesday and Thursday 9:20AM - 10:50AM
Exception: The week that starts on 20th January, instructor is away.
Where we meet: Olsen Hall 408 - NC
When: Tuesday & Thursday 11:00AM - 12:15PM

Description of the Course

An 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 Jan. 21st Matteo is away, class canceled. Self-study: ITC 0.1
Jan. 23rd Introduction & Preliminaries ITC 0
2 Jan. 28th Finite Automata ITC 1.1
Jan. 30th Finite Automata ITC 1.1 | additional notes
3 Feb. 4th Finite Automata ITC 1.1 | additional notes
Feb. 6th Nondeterministic Finite Automata ITC 1.2 | additional notes
4 Feb. 11th Nondeterministic Finite Automata ITC 1.2
Feb. 13th Project Description
5 Feb. 18th Monday Schedule
Feb. 20th Nonregular Languages ITC 1.4
6 Feb. 25th Midterm Review
Feb. 27th Midterm at Olsen Hall 408. Time: 11:00AM - 12:15PM
7 Mar. 3rd Context-Free Grammars ITC 2.1 | additional notes
Mar. 5th Pushdown Automata ITC 2.2
8 Mar. 10th
Mar. 12th
9 Mar. 17th Pushdown Automata ITC 2.2 | additional notes
Mar. 19th Pushdown Automata vs Context-Free Grammars ITC 2.2
10 Mar. 24th Non-Context-free Languages ITC 2.3
Mar. 26th Turing Machines ITC 3.1
11 Mar. 31st Turing Machines ITC 3.1 | additional notes
Apr. 2nd Variants of Turing Machines & Church-Turing Thesis  ITC 3.2, 3.3
12 Apr. 7th Variants of Turing Machines & Church-Turing Thesis  ITC 3.2, 3.3
Apr. 9th Variants of Turing Machines & Church-Turing Thesis  ITC 3.2, 3.3
13 Apr. 14th Regular Expressions ITC 2
Apr. 16th Decidable Problems ITC 4.1
14 Apr. 21st Undecidable Problems ITC 4.2
Apr. 23rd Undecidable Problems ITC 4.2
15 Apr. 28th Reducibility ITC 5.1, 5.2
Apr. 30th Reducibility ITC 5.1, 5.2
16 May 5th Final Review
May 7th Final Review
Final Exam: Thursday 5/7/2020 at 11:30AM - 2:30PM. Where: REMOTE
Due to the pandemic disruption, the timeline of the schedule does not reflect the actual lectures that have taken place.
Topics that have been covered and reference to material are correct.
Topics that were planned and have not been covered (and are not part of the final exam) have been crossed off.

Evaluation and Grade Calculation

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

    Midterm 37.5% score x 0.375 +
    Programming Project 25% score x 0.25 +
    Final 37.5% score x 0.375 +
    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

    Thursday 27th February 11:00AM - 12:15PM, Room: Olsen Hall 408 - NC
    The midterm will cover the following topics:
    Introduction & Preliminaries - Finite Automata - Nondeterministic Finite Automata - Nonregular Languages

    Final Exam

    Final Exam: Thursday 5/7/2020 at 11:30AM - 2:30PM. Where: REMOTE
    The final exam will cover the following topics:
    Context-free Grammars - Pushdown Automata - Non-Context-free Languages - Turing Machines - Variants of Turing Machines & Church-Turing Thesis - Undecidable Problems

    Instructions for the Final Exam.

    Download the file exam.txt
    Rename it so that its name is your first name and last name, keep the .txt extension.
    The file contains 4 questions. Edit the file by inserting your answer after each question.
    The .txt file can only use plain characters, and not, for example, unicode.
    Send me an email with the file .txt that you have edited with your answers by 2:30PM included. The timestamp of the email will be valid evidence that you have submitted on time.

    Programming Project

    Allowed Programming Languages: Java, C/C++, Python.
    Implement an interpreter for DFAs that takes their 5-tuple representation and a string, then returns whether the string is accepted or not.
    Extend your implementation with a compiler from NFAs to DFAs.
    Provide a large set of meaningful examples.
    Provide a clear documentation on how to run your examples and how someone else can write new example tests.
    Programming Projects must be sent to the instructor by email by the 27th March.

    Acknowledgments

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