About CS273
This course will focus on fundamental mathematical models of computation. We will be interested in both the inherent capabilities and limitations of these computational models as well as their relationships with formal languages. Rigorous arguments and proofs of correctness will be emphasized. Particular topics to be covered include:
- Finite automata, regular languages, and regular grammars.
- Determinism and nondeterminism.
- Context-free grammars, languages, and pushdown automata
- Turing machines, Church-Turing thesis, and undecidable problems
Prerequisites
The prerequisites for this course are CS125 (or ECE190), CS173 (or MATH213), and CS225.To test the mathematical side of your background, skim through Chapter 0 of the Sipser textbook. You might not be able to produce all the details from memory, but almost all of it should look like something you used to know.
Other experience (e.g. advanced math courses) may be able to serve in lieu of these prerequisites, especially CS225. If you aren't sure of your background, please speak to one of the instructors.
Meeting Times
Lectures will be held Monday through Thursday, followed by a recitation on Friday. Recitation section will provide a chance to ask questions, clarify concepts from the week's lectures, and work on practice problems in small groups.Course Material and References
Textbook
The course textbook is Introduction to the Theory of Computation, second edition, by Michael Sipser.Course Website
Given the fast summer schedule, you should check (and refresh!) the course website at least once each day. Important announcements will be posted as well as lecture notes, problem sets, and solutions. These announcements will usually also be posted on the course newsgroup (see below).Newsgroup
The class newsgroup is class.cs273 on the department's news server (news.cs.uiuc.edu). You must sign up for access if you have not already done so.We highly recommend you use the newsgroup to communicate with the course staff and your classmates about course material related questions. It's also a great resource for getting clarifications on homework problems. However, do not post your solutions to the homework on the newsgroup where others could copy it; remember that this is a breach of academic integrity.
Homework
Homework will be assigned every Monday and will be due the following Monday at 3:00pm. You may submit homework at Monday's lecture or after lecture by sliding homework underneath the door to 3303 Siebel Center (Theory Lab). Graded homeworks will be returned the following Wednesday.Homework Revision
After receiving feedback on your homework submission, you still have an opportunity to improve your homework grade by submitting revised homework solutions. Homework revisions are due on the Friday following the homework's regular due date, at 3:00pm.If your first submission scores x points and your revised submission scores y points, then your recorded grade for that homework is max(x, average(x, y)) points. In other words, submitting revised solutions can only improve your score, but you can only gain back a maximum of half of the missed points.
Late Policy
Late submissions are not accepted and will earn zero points. If you miss a homework's original due date, you still have until the following Friday to submit a homework "revision" that will earn half credit.General Homework Policies
Your writing must be both clear and legible. You'll receive zero points for any answers we cannot decipher. We do not recommend using a standard word processing program (e.g., Microsoft Word, Google Documents) to type your assignment because it's relatively difficult to typeset mathematics well in these programs. However, if you're feeling ambitious, you may want to look into learning LaTeX.Each student must turn in his or her own homework assignments. You are allowed to discuss the problems with other students enrolled in the course, but you must write up your own solutions. Your solutions should reflect your own understanding of the homework problems. You are required to explain your answers to the homework assignment if called upon. Verbatim copying and other offenses will be handled according to the Cheating Policy. Remember, upholding your academic integrity involves two things: you should neither copy your solutions from others, nor should you allow your solutions to be copied.
Exams
There will be two midterm exams and a final exam. See the schedule for exam dates.
We will follow university policy with regards to offering a conflict final. Since our midterms will be held in class, you will need to have a very good reason to be excused from a midterm. Requests to be excused from a midterm must be made at least one week before the exam date or as soon as you become aware of your need to be excused, whichever is later. Requests to be excused for medical reasons must be accompanied by written documentation from a doctor or other appropriate authority. In the event that you are excused from a midterm, we will use your score on the final for your midterm grade. Emergencies will be handled as necessary.
Honors Section
Homework assignments will include honors problems. Students signed up for the honors section must do these problems. Students not enrolled in the honors section are welcome to do the honors problems for extra credit.
Grading Policies
The "I Don't Know" Policy
A responsible professional understands the limits of his/her competence: you should too! Therefore, if you don't know the answer to a homework or exam question, simply say so. Writing "I don't know" (and nothing else) as a response to a question will earn you 20% of that question's points. (The "I Don't Know" policy does not apply to honors problems.)Cheating Policy
Copying solutions from ANY source (including, but not limited to, books, people, old class notes or handouts) is cheating and a violation of academic integrity. At a minimum, cheating will result in a zero on the homework or exam in question. The UIUC student code also allows for more severe penalties. See the UIUC student code for more information regarding academic integrity; if you are aware of any breach of academic integrity, it is your responsibility to report it to the instructors.Regrades
If you believe that a problem was graded incorrectly on any homework or exam -- the course staff is only human, and mistakes can happen! -- then you may bring it to a course staff member within at most one week of when it was handed back in class. Attach a slip of paper briefly describing what you feel is in error. The grader will adjust your score as necessary.Grading Rubric
Your course grade is composed of four parts, as detailed in the following grading rubric:
Participation 10 % Homework 30 % Two Midterm Exams 30 % (15 % each) Final Exam 30 % The 10% of your grade for participation should be very easy to obtain. We will note when you participate in recitation. (Participation means more than mere attendance.) Your "participation" grade will be calculated as the maximum of your participation in recitation and your weighted average of all other course grades (i.e. (homework * 0.3 + midterm1 * 0.15 + midterm2 * 0.15 + final * 0.3) / 0.9). This is to say, your participation grade can't hurt your course average.
Letter Grades
Your course average will be rounded to the nearest integer percent and converted to a letter grade as follows:
A+ 97+ C+ 77-79 A 92-96 C 72-76 A- 90-91 C- 70-71 B+ 87-89 D 60-69 B 82-86 F 59- B- 80-81 If you achieve the listed percentage, then you are guaranteed the corresponding letter grade. We reserve the right to lower the grade cutoffs at the end of the semester if necessary.