COT 5310 Theory of Computation I
Spring 2021 Tuesday/Thursday 5:00PM - 6:15PM

Instructor:
Leonardo Bobadilla
Associate Professor
bobadillacs.fiu.edu
Office:CASE 212b
Phone: 305-348-7565
Office Hours:
Tuesday and Fridays 6:30pm-7:30 pm in Zoom or by appointment


Course Calendar and Assignments

Prerequisites

MAD 3512

Course Outline

  • Mathematical Preliminaries (Chapter 0). Overview, Notation, proof by induction, etc.
  • Regular Languages (Chapter 1). Deterministic and nondeterministic finite automata, regular expressions, the pumping lemma for regular languages, minimal DFAs and NFAs.
  • Context-Free Languages (Chapter 2). Context-free grammars, pushdown automata, the pumping lemma for context-free languages.
  • Turing Machines (Chapter 3). Definition of a Turing machine model, variants of Turing machines; Church's hypothesis; Turing machines as enumerators; restricted Turing machines equivalent to the basic model.
  • Decidability (Chapter 4). Decidable problems about regular languages and context-free languages. Languages that are not Turing recognizable. Undecidability of the halting problem.
  • Reducibility (Chapter 5). Undecidability of Halting Problem and PCP. Mapping reducibility
  • Other topics in Computability Theory (Chapter 6). The recursion theorem. First-order predicate logic review. Gödel's Incompleteness Theorem.
  • Time Complexity (Chapter 7). Measuring complexity. Complexity classes P and NP. Cook-Levin theorem.

Textbooks and Materials

Required Book:

  • Title: Introduction to the Theory of Computation
    Author: Michael Sipser
    ISBN#: 0534950973
    Edition: Second Edition
    Publisher: Cengage Learning;
Recommended Book
  • Title: Introduction to Automata Theory, Languages, and Computation
    Authors: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
    ISBN#: 0201441241
    Edition: Second Edition
    Publisher: Addison-Wesley

Grading

You should read the corresponding sections on the book and be able to actively participate in class discussions. There will two midterm exams and one final exam. You will be responsible for all material covered in lectures, homeworks, and assigned readings. The various components of the course will be weighted as follows:

Homework assignments 15%
First midterm 25%
Second midterm 25%
Final exam 30%
Quizzes and class participation 5%

Exams

The only excuse for missing an exam is verifiable cases of illness and emergencies and religious holidays. Please check the dates for exams and inform me at the earliest of any conflict due to the above-mentioned reasons.

Homeworks

Solving problems is a fundamental part of the course. Success in the class depend on the effort put in solving the homework problems. Try to think about the problems individually before discussing them with a group partner. Also, I would encourage you to think about all the problems in the text whether they are assigned or not.
There will be a homework assignments every other week during the semester. Homeworks are due at the start of the class . For the homeworks, you can work in pairs or individually. Please put your name and panther ID at the top of the homework. If you work in a pair, submit one copy with both names at the top.
Please cite all the sources (books, webpages, etc) that you use for solving your homework.

Attendance

I expect you to regularly attend class and participate in discussions.

Code of Academic Integrity:

University Policies:

For academic misconduct, sexual harassment, religious holidays, and information on services for students with disabilities, see :
  • Make-up Exam Policy. The midterms are an important component of the class. If for some grave circumstances you can not attend, you must contact me beforehand (email is OK) and later provide documentation of why you could not attend the exam. Only serious personal circumstances will be accepted as valid excuses. The make-up exam will be given on the final's week.

    • FIU STUDENTS AND FACULTY "STAYING SAFE AND HEALTHY"

    In collaboration with the Health, Safety, and Welfare Committee of the FIU Faculty Senate and the Healthy Panthers Council, the Provost encourages each faculty and student to take a proactive role in their safety, personal health, and well-being.

    Through viewing the "Staying Safe and Healthy" video series, you will learn:

    How to respond to an active shooter situation Care of an unconscious person Care of the bleeding person Panther's Care Initiative How to enhance your personal health and well being

    These 3-5 minute videos and related resources can be found for:

    On Campus Students in the Student Starter Kit in Canvas 2.0 Fully Online Students in Panther Den in Canvas Faculty in the Faculty Starter Kit in Canvas

    This video series and related resources can make a difference in promoting the safety and protecting the health of all members of the FIU community. These resources are available any time you have a few minutes to watch them and you can refresh your memory about their content at any point in time. STAYING SAFE AND HEALTHY requires the commitment of each of us as Panthers.