Introduction to Computer Science Theory, 4003-380-01, 20112

Course Description

Course Outcomes

1. Students will be able to explain basic concepts in formal language theory, grammars, automata theory, computability theory, and complexity theory.
2. Students will be able to relate practical problems to languages, automata, computability, and complexity.
3. Students will be able to demonstrate an increased level of mathematical sophistication.
4. Students will be able to describe and apply mathematical and formal techniques for solving problems in computer science.

Class Schedule

Instructor

Required Book

Other Materials

I will try to keep useful items on an auxiliary directory of 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
  • existential and universal quantifiers
  You should be competent in constructing proofs involving sets, relations, and functions, using various techniques such as contradiction, counterexample, and mathematical induction.

The Work

Discrete Math Quiz

Homework Assignments

There are eight homework assignments (not counting the discrete math quiz), one per week except for the weeks 1 and 6. Homeworks are due on Wednesday at 4pm, and are posted at least 6 days before they are due. The actual assignments will be available on the homework page. Homework grades have two parts.

• Was anything handed in (10%)
• How good are the answers (90%)
  

Unless it is specifically stated otherwise, you must work on and submit your homework individually. Discussing homework with your fellow students is encouraged.

You may use discussion forums set up for each homework assignment. I will use them as well to get answers disseminated as quickly as possible to everyone.

You may talk verbally with each other, and share notes on a whiteboard (for example, in a CS breakout room or the mentoring center). However, after such discussions, all notes must be discarded, boards erased, and every student must write up his/her solutions in private without further consultations with your classmates or any written material other than your class notes, materials handed out in class, the textbook or the course web sites. For every problem discussed with other students, please state their names on your paper. This in itself will have no impact on your grade.

Of course, you are not allowed to look up the answers to your homeworks.

Your homework submissions must be submitted by Wednesday, 4pm sharp (start of class). You have the following submission options:

• Upload it to mycourses.
• Give it to me in person.
• Other methods are by prior approval only.
  

• A zero for cheating will not be dropped;
• a zero for the 10% of the grade for handing something in does not get dropped if you hand nothing in.

I will stop answering homework questions at 10am the day it is due. (This means that you can post a homework question on the discussion forums by Wednesday 10am and I will answer it as soon as possible.)

Midterm Exam

Final Exam

Exams cannot be made up except for real emergencies in which case proper documentation (like a doctor's note) will be required. 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

• 50% Homeworks
• 25% Midterm
• 25% Final Exam

However, your final grade will never be more than one letter grade higher than the average of your midterm and final.

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.

All grades will be posted on myCourses.