CSC 250
Theory of Computation
(Spring 2017)

Joseph O'Rourke


Last Updated: 

Syllabus Link


This course is one of the four Core requirements of the Computer Science Major. It covers grammars, and in particular, context-free grammars, which are used to define and parse all modern programming languages, and regular expressions, which are used to search for specific strings. Grammars are associated with finite automata, a powerful formalism to guide the coding of parsing and searching programs. The course also explores the limits of computation, through Turing Machines. TMs allow a proof that a universal debugging program is impossible via the undecidability of the halting problem.

Prerequisites: There are two prerequisites for this course: CSC111 or equivalent knowledge of Python, and MTH153 Discrete Mathematics. It is possible to take MTH153 and CSC250 in the same semester. It is also possible to waive the MTH153 requirement by permission of the instructor, if the student has a sufficiently strong mathematics background.


Class Times: Lectures: MWF 9:00-9:50. (No lab)

Location: Seelye 110

Enrollments: The course has no enrollment limit.

Office Hours: FH256, Mon & Tue & Thu afternoons: Office Hours & Calendar, or by appointment

Textbooks: I will use two free textbooks: Critchlow&Eck: Foundations of Computation, and Maheshewari&Smid: Introduction to Theory of Computation. Both can be downloaded from those links as PDFs. The first book has a printed, bound version, sold by lulu.com for about $10. The second book has no printed version, but I took the PDF to Paradise Copies and they printed and bound it for me for $20. The first book is strong on the first half of the course, on grammars and automata, and the second book is strong on the second half of the course, on Turing machines and decidability. Finally, I will sometimes be guided by a more advanced text that I am not asking students to purchase (but is well worth owning eventually): Sipser: Introduction to the Theory of Computation (International Edition).

Course Structure:  We meet three times a week; there is no lab, although we will often have "minilabs" during class time.  There will be one assignment per week, due each Tuesday at midnight. Ideally you get started over the weekend and are prepared to ask questions in class Monday. Collaboration is permitted—even encouraged—on assignments. Use name=250, pass=250 for web access-restricted files.

Submitting Assignments: Via the Moodle page for this course, by Tuesday at midnight. . (If you are registered for the course you should be automatically enrolled to access Moodle.)

Collaboration: Collaboration is encouraged on all aspects of the course except for the three take-home exam-assignments. You may collaborate in groups of 2 or 3 (but not larger groups). You need only submit one copy of the homework for the group. All members of the group get the same grade. I will treat individual submissions and group submissions identically.

Exams:  Three of the assignments will be one-week take-home "exams," which are very much like assignments except that (a) they focus more on understanding rather than "doing," they may have an associated (untimed) Moodle quiz, and (c) unlike assignments, there is no collaboration permitted. You can view the assignment-exams as more comprehensive assignments. They count about the same as a normal assignment.

Project: There is a final project, due on the last day of the exam period. (Here collaboration permitted.) Students must give a brief presentation on their projects toward the end of the course. A typical project would be a series of web pages that explains a particular topic or algorithm professionaly and thoroughly, something like an excellent Wikipedia entry.

Tutors: Zoe Kendall: Currently Sun & Wed evenings.

Grading:

n Assignments (n~=6)
55%
Class participation
(±0,1,2%)
3 Assignment-exams (take-home)
30%
Project
15%
100%
See also: Grading Numerology.

Late Policy