UIUC Computer Science Theory Course Revision 2005
Background
Recently, the Computer Science Department at UIUC deployed a
revised undergraduate program, comprising new/modified courses, requirements,
and paths to an undergraduate degree. The new curriculum was just approved
by the UIUC faculty senate. See the
recent news article on the CS Department web pages for more information.
As part of the revised curriculum, significant changes to existing CS theory
courses are planned to begin fall 2005. This page describes the changes in
content for the courses, and the transition strategy recommended for all
students.
Instructions for Students
If you are not interested in details, simply choose the row of the
following chart that applies to you, and follow the instructions.
| If CS 173 is completed in | and CS 273 is completed in |
Then to Complete the Theory
Requirement |
|---|
| summer 2005 or earlier (old version) |
fall 2005 or earlier (old version) |
take CS 473 or CS 475 |
| fall 2005 or later (new version) |
spring 2006 or later (new version) |
take CS 473 |
| summer 2005 or earlier (old version) |
spring 2006 or later (new version) |
take "transition" course (below) and CS 473 |
Transition course
A special one-credit-hour section of CS 199,
entitled "Counting and Recurrences"
will be made available in spring and fall 2006 only. The course
will cover elementary combinatorics, probability, and solutions
of recurrence equations.
Special note to Math/CS majors in LAS
While the theory course requirements do not change for you (i.e.,
you still take CS 173, 273, and one of CS 473, CS 475, or Math 414),
the course content is still changing, so you should be attentive
to the timing of CS 173, CS 273, and whether you should take the
transition course. Moreover, if you take the new 273, it is recommended
that you choose CS 473 (or Math 414) as opposed to the new CS 475, as
your third course.
Details of CS Theory Course Revisions
Theory topics are best categorized as "Discrete Mathematics",
"Automata and Formal Languages" (or "theory of computation"), and
"Algorithms". Most major CS departments have courses aligned with these
categories, and the new versions of CS 173, 273, and 473, all required
in the new curriculum, will correspond, respectively, to this content.
Currently, this content is spread out over four courses (old versions
of CS 173, 273, 473, 475), only three of which are required.
The main motivation for the revision is to eliminate duplication and
optional material, while at the same time all students leave with a basic
grounding in all core theory topics.
The OLD versions of the courses could be described as follows:
- CS 173: Covers two-thirds of a typical discrete math for CS course.
Missing only material on combinatorics and recurrence equations.
- CS 273: A hodge-podge of a class, containing the missing third of 173,
some material on graphs that is collectively covered by the current 173, 225,
and 473, some material on theory of computation covered by the current 475,
and some nice but not as central miscellaneous material (e.g., algebraic
structures).
- CS 473: Algorithms
- CS 475: Automata, formal languages, computability
("theory of computation")
To bring the above mess in line with the goal of three core theory courses,
the revision does the following:
- The missing third
(elementary combinatorics and recurrence relations) from CS 273 is
moved into CS 173, expanding the course to three hours from the current two.
This makes the course comparable to Math 213, though with a computational
focus.
- The content of CS 273 is replaced with that of CS 475,
after ensuring that all other core material from (the old) CS 273
is covered by CS 173, 225, and 473 collectively.
Thus, CS 273 becomes a standard
theory of computation course covering automata and formal languages.
- Minor adjustments are made to CS 473 as needed.
- The three course sequence 173, 273, 473 is now required.
- Ultimately, CS 475 will become an optional, advanced course on automata,
decidability, and complexity theory, suitable for graduate students and
undergraduates who have already had an initial course such as the new 273.
It will be offered one last time in its current form in fall 2006.
- A transition course is temporarily offered for students who took
the old CS 173 and the new CS 273. While not required, the course is
important preparation for CS 473. Study materials will be available online
for those students wishing to cover the material on their own.
Timeline for Revised Theory Course Introduction
| CS 173 | New version fall 2005 and beyond |
| CS 273 | New version spring 2006 and beyond |
| CS 199 transition | Offered spring and fall 2006 |
| CS 475 | Old version fall 2006 (not for students
who have taken CS 273 new version).
New version fall 2007 and beyond
|