Foundations of Computing Theory, 4003-700

Foundations of Computing Theory, 4003-700, Winter 2012-2013

Course Description

This course provides an introduction to the theory of computation, including formal languages, grammars, automata theory, computability, and complexity.

Course Outcomes

Students should demonstrate an understanding of basic concepts in formal language theory, grammars, automata theory, computability theory, and complexity theory.
Students should be able to relate practical problems to languages, automata, computability, and complexity.
Students should demonstrate an increased level of mathematical sophistication.
Students should demonstrate an understanding of and be able to apply mathematical and formal techniques for solving problems in computer science.

Course Web Page

http://www.cs.rit.edu/~eh/700.html

Instructor

Edith Hemaspaandra
bldg. 70, room 3625
Email: eh at cs.rit.edu
http://www.cs.rit.edu/~eh

Office hours (weeks 1-10; tentative)

Monday 11-12;
Monday 6pm (I will leave if nobody shows up at 8pm; part-time students have priority);
Tuesday 11-12;
Tuesday 2-3;
and, if you can't make any of the above times, by appointment.

Asking questions via email seems to work well for many people.

Lectures

Monday/Wednesday, 2:00-3:50, GOL-3560.

Required Book

Michael Sipser, Introduction to the Theory of Computation, third edition, Course Technology, June 2012.

Other Materials

I will distribute copies of the slides that I use at the start of class and/or I will post them. Information about reading and homework assignments, quizzes, exams, etc. will be linked from the course web page.

Prerequisites

Algorithms and data structures at the level of an introductory programming sequence.
Discrete Mathematics. You should have taken a course in discrete mathematics covering
- fundamentals of logic
- sets
- relations
- equivalence relations
- functions
- simple combinatorics
You should be competent in constructing proofs involving sets, relations, and functions, using various techniques such as mathematical induction.

To refresh your memory on discrete math, read (and do some of the exercises/problems of) Chapter 0.

The Work

Homework Assignments

There are eight homework assignments, one per week except for weeks 1 and 6. Homeworks are due on Wednesday at 2:00pm, and are usually posted at least six days before they are due. The actual assignments will be available on the homework, quizzes, and reading page.

Unless it is specifically stated otherwise, you may may choose to do the homeworks individually or in pairs. If you are working as a pair, both partners should contribute significantly to the solution for every question. You should submit only one copy of the homework with both your names on it. All authors have to be able to explain all solutions.

Whether you submit on your own or with a partner, discussing homework with your classmates is encouraged. However, after such discussions, you have to discard all notes, cell phone pictures, and other materials you have created before you write up your solutions on your own (or with your partner, if working as a pair) without further consultations with your classmates or any written material other than your class notes, materials handed out in class, the textbook, and materials linked from this page. You are not allowed to discuss the homework with people other than your classmates, the theory tutors, and me. You are not allowed to look up the answers to your homeworks.

Your homework submissions must be submitted by Wednesday, 2:00pm sharp. You have the following submission options:

Give it to me before the start of class or during office hours.
Upload it to myCourses (as a single well-readable pdf file). Do not wait until the last moment to upload.

Clearly state your name(s) and staple your homework. I will not accept late assignments for any reason. I will drop the two lowest homework grades. However, a zero for cheating will not be dropped.

I will not answer homework questions after 5pm on Tuesday.

Quizzes

There will be a short quiz at the start of almost every class. Information about the quizzes will be available on the homework, quizzes, and reading page.

If you can not take a quiz because of religious reasons, please let me now as soon as possible. Quizzes can not be made up for any other reason. However, I will drop the three lowest quiz grades.

Midterm Exam

The midterm exam will take place on Wednesday, January 16, 2:00-3:50, in our regular classroom. Reda, Rohan, and Vaibhav will take the midterm in break-out room 3 (70-3576).

Final Exam

The semi-cumulative final exam is scheduled for Tuesday, February 19, 8:00am-10:00am, in GOL-2590.

Exams can not be made up except for real emergencies in which case proper documentation (like a doctor's note) will be required or if you can not take an exam because of religious reasons. If at all possible, you should contact me prior to the exam. Oversleeping, cars that don't start etc. do not constitute a valid excuse.

Evaluation

20% Homeworks
30% Quizzes
25% Midterm
25% Final Exam

Numerical grades will be converted to letter grades according to the following scale:
> 88%: A; 77%-88%: B; 66%-77%: C; 55%-66%: D; < 55%: F.
Keep in mind that you need a grade of B or better to pass a bridge course.

Tutoring

In addition to all of the usual support services RIT and the CS department offer, the CS theory faculty are offering their own tutoring service, featuring very qualified CS students. The tutoring takes place in the CS student center (70-3660). For hours, see the theory tutoring page.

One rule about tutors: They will not do your homework for you.

Disputing Your Grade

If you feel that an error was made in grading your homework, quiz, or exam, you have one week from the moment the graded work was handed back to dispute your grade. All grading issues should be taken up with me; do not discuss grading issues with graders or tutors!
All grades will be posted on myCourses.

Students with Disabilities

RIT is committed to providing reasonable accommodations to students with disabilities. If you would like to request accommodations such as special seating or testing modifications due to a disability, please contact the Disability Services Office. It is located in the Student Alumni Union, Room 1150; the Web site is http://www.rit.edu/dso. After you receive accommodation approval, it is imperative that you see me during office hours so that we can work out whatever arrangement is necessary.

Academic Honesty

The DCS Policy on Academic Honesty will be enforced.

You should only submit work that is completely your own. Failure to do so counts as academic dishonesty and so does being the source of such work. Submitting work that is in large part not completely your own work is a flagrant violation of basic ethical behavior and will minimally be punished with failing the course.

Electronic Devices in Class

Professional and respectful behavior is expected. If behavior is disruptive, the policy on electronic devices in class will change accordingly. You are not allowed to record the lectures.