CS6413 Theory of Computation

6413-001

J-131

Tue, Thu

7:40-10:10pm

Juan Carlos Guzmán
Office hours:
	Tue, Thu	3:00-4:45pm 10:10-10:30pm
	Also by appointment
e-mail: jguzman@spsu.edu
web: http://cse.spsu.edu/jguzman
Office: J-360 (2π)
Phone: (678) 915-7430

Introduction to Automata Theory, Languages, and Computation, 3rd Edition
John E. Hopcroft, Rajeev Motwani & Jeffrey D. Ullman
Addison Wesley, 2006
ISBN 0321455363

Catalog Description

A study of topics from theoretical computer science that includes automata and languages, computability theory, and complexity theory. [Academic Catalog 2008-2009]

Objective

The purpose of this course is to provide a foundation of theoretical aspects of Computer Science. We study in detail the languages classes in the Chomsky hierarchy, and, for each family of languages, we present how these languages can be described (using a grammar), and how it can be recognized (using a machine). If time permits, the student will also study undecidability as well as intractable problems (NP-complete problems).

Course Outcome

Assignments

There are a series of homework sets and three exams. The homework sets correspond to each major topic (chapter in the book), and will be given after each topic is covered. Students may solve these assignments individually or in groups of up to 2 persons (no, there are no groups of 3 or more people). They are due within a week. The exams are in-class examinations, and are individual evaluations.

You should keep a copy of all your submitted material, as well as all graded material until your final grade is posted (to access the electronic version of these assignments, please click "Assignments", to your left).

Late Policy

Home Assignments are due on the posted day, at the beginning of the class. Assignments not turned-in in class must be submitted in person or electronically. Assignments will be accepted after the due date with substantial penalty. In asking for an extension, it will definitely help that you show that you have been working on the assignment. Under no circumstance you will be allowed to have two past-due assignments at any given time.

Grading

Cumulative Grade	Letter Grade
90% and above	A
80%-90%	B
70%-80%	C
below 70%	F

Academic Dishonesty

All individual assignments are meant to be done individually. All group assignments are meant to be solved by each individual group. Collaboration is permitted in areas like installing the programming environment, and even in sharing references with others. However, it is not permitted that you share your own code (your group's code) or your own written documents (your group's written documents). Studying in groups is permitted, acknowledged and encouraged. However, group study is not an excuse for identical submissions.

The penalty for academic dishonesty will be zero in the assignment, lowering the final grade up to two letters (in addition to not getting credit for the assignment), and reporting this incident to the CS Dept., which may take additional actions. The following sources may give you background information on the subject: http://www.spsu.edu/cs/faculty/bbrown/papers/conduct.html (academic conduct), and http://www.spsu.edu/cs/faculty/bbrown/papers/gshpla.html (plagiarism and references).

Students with Disabilities

Students with disabilities who believe that they may need accommodations in this class are encouraged to contact the counselor working with disabilities at (678) 915-7244 as soon as possible to better ensure that such accommodations are implemented in a timely fashion. For more information, visit http://www.spsu.edu/attic/Dis_Svcs.html.

Registration Problems

If you are majoring in Computer Science, Software Engineering or Information Technology and have questions about your schedule or you are having registration problems, please contact Ms. Beth Haynie, Academic Advisor for CS, IT and SwE, at J-375 or call (678) 915-4292 and ask for an appointment.

Class Attendance

You are expected to attend classes regularly. You will be responsible for all announcements made in class, even if you have not attended. The professor will keep a record of your attendance. Class attendance does not count towards your final grade, however, class interaction will count 10% towards your grade.

The class schedule given below is a tentative plan of the classes. You should read the material related to the class before the corresponding class. Sometimes, the exams might contain up to 25% of topics covered in the book, but not in class.

Policy on Electronic Devices

The students must turn off set their electronic devices such as cell phones, blackberries, pagers, etc. Otherwise, they must be put in either silent or vibrating mode so that class is not interrupted in the event of a call.

Calendar

Class Period: Mon, 18/May--Thu, 09/Jul
Withdrawal Deadline: Thu, 18/Jun
Final Exam Period: n/a
Holidays: Memorial Day (Mon, 25/May), Independence Day (Sat, 04/Jul)
Graduation: Sat, 01/Aug
Final grades posted: Mon, 20/Jul

We will follow the topics of the text. There will be an exam on 04/Jun, another on 23/Jun and the final exam will be on 09/Jul.

Topics Covered

We will cover up to Chapter 10 from the textbook. The topics are as follows (table of contents):