Introduction to Computer Science Theory, 4003-380, 20104
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://cs.rochester.edu/~menton/380/index.html
Instructor
Curtis Menton
Email: last name at cs.rochester.edu
Office: 70-3575
Office hours:
- Monday 2:00-4:00PM
- Wednesday 2:00-4:00PM
- Also by appointment.
Lectures
Monday/Wednesday, 4:00PM-5:50PM, 70-3445.
Required Book
Michael Sipser,
Introduction to the Theory of Computation, (Second Edition),
Thomson Course Technology, 431 pages, 2005, ISBN:0534950973.
Other Materials
Slides
and information about reading and homework assignments,
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.
The Work
There
are eight homework assignments, one per week except for weeks 1 and
6. Homeworks will usually be due on Wednesdays at 4pm at the start of class, and
are posted at least 6 days before they are due. The actual
assignments will be available on
the homework, reading, and slides
page.
Unless it is specifically stated otherwise,
you may work on and submit your homework in groups of 1 or 2.
If you choose to work as a group of 2, both of you
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 fellow students is encouraged. However, after such
discussions, all notes must be discarded, blackboards erased, and
every group must write up their 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 this
webpage. For every problem discussed with other students, state their
names and briefly sketch the extent of your discussions (e.g. "solved
together", or "clarified problem statement"). You are not allowed to
look up the answers to your homeworks.
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.
Midterm Exam
The midterm exam will take place in week 5 or 6 during our usual class
period.
The midterm is closed book and notes but you may bring one sheet
of letter-sized paper with your own hand-written notes.
Final Exam
The final is
semi-cumulative. It is closed book and notes but you may bring one
sheet of letter-sized paper with your own hand-written notes.
Exams can not 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
- 40% Homeworks and the best of
- 30% Midterm and 30% Final Exam or
- 25% Midterm and 35% 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.
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.
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.