This course requires registration in both Lecture and Class Problem Session sections, shown below:

**Lectures: **Monday, Wednesday, Friday, 11:00 am – 11:50 am in 2BSB 381. Call Number 10647.

**Class Problem Session: **Friday, 12:00 pm - 12:50 pm 2BSB 381. Call Number 10645.

**Instructor: **Dr. Sevag Gharibian**Email:** sggharib at uic dot edu **Webpage:** http://www.cs.uic.edu/bin/view/Main/Sggharib

**Book: **Sipser, *Introduction to the Theory of Computation, *3rd edition. (Note: If you prefer to use the 2nd edition of the text instead, it should probably be OK.)

Office: 1218 SEO.

Office Hours: Mondays and Wednesdays, 12:00 pm - 1:00 pm.

**TA: **Behpour, Sima, email: sbehpo2 at uic dot edu

TA Office: 1310 SEO (the elevator only goes to the 12th floor; you'll need to take the stairs to go from 12 to 13), phone number: 312-413-3432.

TA Office Hours: 10:00am - 12:00pm Thursdays.

- Determine a language’s location in the hierarchy: regular languages, context- free languages, and recursively enumerable languages.
- Prove that a language is in a specified class.
- Convert among DFAs, NFAs, and regular expressions.
- Explain the Church-Turing Thesis and its significance.
- For certain languages, prove that they are not recursively enumerable.

- Introduction
- Review of Discrete Mathematics (Logic, sets, functions, relations, etc.)
- Alphabets, strings, formal languages, language classes

- Finite Automata
- Deterministic Finite Automata
- Nondeterministic Finite Automata
- Regular expressions
- The Pumping Lemma and non-regular languages

- Context-Free Languages
- Context-Free Grammars
- Pushdown Automata

- Turing machines and computability theory
- Turing machines (deterministic, non-deterministic, multi-tape, enumerators)
- Universal Turing machines and the Church-Turing Thesis
- Detour: Countable versus uncountable sets, uncountability of the real numbers
- Basic undecidability (halting problem)
- More undecidability: Mapping and Turing reductions
- Rice’s Theorem (Problem 5.28 in the text)
- The Recursion theorem

- Introduction to complexity theory
- P, NP, and the importance of the P vs NP question
- Polynomial-time reductions
- The Cook-Levin theorem (SAT is NP-complete)
- More NP-complete problems: 3-SAT, CLIQUE, VERTEX COVER, HAMPATH
- As time allows: An introduction to the PCP theorem

**Exams**:

- Midterm exam: 11:00-11:50 am, Wednesday, October 17, 2012 (tentative). In class.
- Final exam: 10:30am-12:30pm. Thursday, December 13, 2012. In BSB 381. The final exam will be comprehensive.

*If you do not work on all the problem sets, then do not expect to pass the course. *(Not only are the problem sets weighted heavily, but students who don't do the problem sets flunk the midterm and the final.)

**Homework: **Homework will generally be given each week and will generally be due at the Friday discussion section. (Some weeks may not have homework, e.g. the week the project is due.)

Late homework will not be accepted, because homework will generally be due at the problems session, and solutions will normally be given then and there.

Late homework will receive a grade of 0. (Of course, a missing homework may be excused altogether if, for example, you are seriously ill.)

**Attendance:** I do not plan to associate grades with whether or not you attend class, unless a serious problem with attendance develops.

Therefore, no matter how good your excuse, I will not grant you an incomplete if you have less than a C average at the time you ask for an incomplete.

The minimum penalty for any cheating will be a grade of zero for the homework, project, or exam in question, along with a warning. The minimum penalty for cheating after a warning has been given will be an F for the course. In both cases, the maximum penalty is expulsion from the University.

See http://www.uic.edu/depts/dos/studentconduct.html for more details.

• Any solutions to homework problem sets of tests that we give you,

• Any lecture notes posted to Blackboard (unless they say that they are 100% by Dr. Gharibian).

There are two different reasons for this: First because some of these materials are provided by the textbook’s author who insists on this arrangement. Second, because some problems from the book will be assigned to other students elsewhere, and they lose their value if solutions are distributed.

Statement about disability services

List of registration and records policies

UIC 2011-2013 Undergraduate Catalog

Topic revision: r23 - 2012-11-21 - 01:22:16 - Main.sggharib

Copyright 2016 The Board of Trustees of the University of Illinois.webmaster@cs.uic.edu |
WISEST Helping Women Faculty Advance Funded by NSF |