TWiki> CS301 Web>WebHome (revision 6)EditAttach

# CS 301—Languages and Automata

Please see the Syllabus for initial course details, prerequisites, etc.

I will be setting up a Piazza site for the course for Q&A, etc., shortly. I anticipate using UIC's Blackboard system for its GradeBook, but for nothing else.

Remember: Class meets Monday, Wednesday, Friday 1:00 to 1:50, and you are expected to also attend a weekly discussion devoted primarily to homework problems.

## Syllabus: CS 301, Languages and Automata (Fall 2012)

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.

## Overview: Key learning objectives

At the completion of the course, all students should have the ability to:
• 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.

## Prerequisites

A grade of C or better in CS 201 is required. You must also have either completed or be currently registered in CS 202.

## Course Topics (subject to change without notice)

• 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) and its proof
• More NP-complete problems: 3-SAT, CLIQUE, SUBSET-SUM, HAMPATH
• By popular demand: Introduction to quantum computing
• Basic mathematical theory and motivation
• Quantum teleportation
• Independent learning via course project: Space complexity
• PSPACE and NPSPACE
• Savitch's theorem (PSPACE = NPSPACE)
• TQBF is PSPACE-complete

## Evaluation

This policy is subject to change at any time for any reason.

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.
Course Project: I am tentatively planning to have a small course project, due on Friday, December 7. It will likely involve picking a small section of the text we have not covered in class of your choice (from among a suitable set of advanced sections I will provide), reading through it on your own and completing a relevant problem set.
• ### Weight of course components for grades

• Problems sets: 40%
• Project: 10%
• Midterm: 20%
• Final: 30%
You must pass the final in order to pass the course.

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.

### Incompletes

The UIC Undergraduate Catalog states that in addition to needing excellent justification for an incomplete, a student must also have been “making satisfactory progress in the course.”

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.

You may discuss the homework problems with other students—in fact, I encourage you to do so—but you are expected to write up your solutions by yourself. If you do work on the problem sets with other students, please put the names of your group at the top of your problem set. If you consult any web page while working on an assignment, put the URL for the page on the homework. If your homework is highly similar to another students’ homework or to a web page and you have not put that name or URL on your paper, then we will consider you to be guilty of cheating.

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.

### Keeping documents private

You must keep private and not email, post on the web, or share in any way:
• 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.