CS 473: About This Course
About This Course
- What is this?
-
CS 473 (officially "CS 498 DL1") is an algorithms course aimed at advanced undergraduates and graduate students in computer science and related disciplines.
- Syllabus
- The course will cover a wide range of algorithm design and analysis techniques including the following:
- Advanced dynamic programming
- Randomized algorithms
- Hashing, filtering, and streaming algorithms
- Maximum flows and minimum cuts
- Linear programming
- NP-hardness and related lower bounds
- Approximation algorithms
- Coursework
-
Grades will be based on regualr written homeworks (30% total), two midterms (20% each), and a final exam (30%). See the grading policies for more details.
- Prerequisites
-
CS 374 or equivalent, or graduate standing. In particular, we assume that students have mastered the material taught in CS 173 (discrete mathematics, especially induction) and CS 225 (basic algorithms and data structures). Note that "mastery" is not the same as "exposure" or even "a good grade"; hence, Homework Zero!
- Am I in the right place?
-
Well, that depends.
- If you are an undergraduate who has taken CS 374, you are in the right place! Welcome!
- If you are an undergraduate who has not taken CS 374 or an equivalent course, you are in the wrong place. You really do need to take CS 374 first.
- If you are a graduate student in computer science or a related discipline, you are in the right place! Welcome! In particular:
- If you are a CS PhD student whose program of study includes "CS 573", you are in the right place.
- Yes, even if you've already taken an undergraduate-level algorithms class.
- If you are a graduate student without an undergraduate background in computer science, you might still be in the right place. Welcome! Past experience suggests that a strong background in proof-based mathematics is more important for success in this class than programming experience. If you have any concerns, please talk to Jeff as soon as possible.
- Finally, if you want an easy A, you are probably in the wrong place.
- Postrequisites
-
This course replaces CS 573 as a prerequisite for all 500-level algorithms courses, in particular:
- Degree Requirements
-
This course is not specifically required for any program on campus, but it has been approved to satisfy requirements in each of the following programs:
However, this course does not count toward the requirement in all graduate programs for 500-level credits. It's a 400-level course.
Class Resources
- Web site
- All course materials—announcements, course policies, detailed schedule, lecture notes, lecture videos, homeworks, homework and exam solutions—can be found here. Hey, look! You found it!
- Lecture notes
-
Jeff's algorithms lecture notes will be the primary reference for this class. We will post revisions and new notes to the lecture page as the semester progresses. The lecture note site also contains homeworks and exams from Jeff's past algorithms classes.
-
The lecture notes have bugs. We will award extra credit to any student who identifies a mistake and offers a suitable correction on Piazza. Yes, typos and spellign mistaks count.
- Videos
-
We plan to record all lectures, as in past semesters. However, because the classroom does not have the same built-in recording equipment as the classroms in Siebel and DCL, we will have to record everything ourselves. We anticipate some technical difficulties, especially early in the semester. Lecture videos should appear automatically on a separate page (TBD); links to lecture videos will be added to the schedule web page as the semester progresses. Videos of Jeff's lectures from several past semesters are also available; Jeff has asked the college to maintain these videos permanently.
- Moodle
- We will use Moodle for electronic homework submission and to record homework and exam grades. If you were registered for the course at the start of the semester, you should already have access to our Moodle site; if not, you can enroll yourself with the code
CS473. (Sorry, Illinois students only.)
- Piazza
- We will use Piazza for online discussions. Anyone can sign up for access with their favorite email address and the access code
CS473. We strongly encourage posting questions on any course-related topic to Piazza rather than emailing the course staff. You can even post your questions anonymously. (However, we can only give you extra credit for helpful posts if you post them using your real name.)
- Etc.
- I've collected a long list of other useful resources on a separate page.
What's happening to CS *73?
As part of a larger curriculum revision, the CS department recently revised its theoretical computer science course offerings. Before the revision, we offered three regular theory courses:
- CS 373: A junior-level class on formal languages and machine models, required for all undergraduate computer science majors.
- CS 473: A senior-level algorithms class, required for all undergraduate computer science majors.
- CS 573: A graduate-level algorithms class, designed for computer science PhD students.
The new regular theory currculum has just two courses:
-
CS 374: A new junior-level class on automata and algorithms, required for all undergraduate computer science and computer engineering majors. (This class contains about half of the material from CS 373 and about two-thirds of the material from the old CS 473.) This course is offered under the rubric CS 498 BL1 while we await its official approval.
-
CS 473: A more advanced elective algorithms class, aimed at undergraduates who have taken CS 374 and graduate students in computer science and related fields. This revision of CS 473 is officially offered under the rubric CS 498 DL1 while we await its official approval.
This revision was motivated by several factors.
- Smaller CS core: The CS department is shrinking the core curriculum shared by all undergraduate computer science majors. (The CS department currently offers seven majors: CS Engineering, CS+Anthropology, CS+Astronomy, CS+Chemistry, CS+Linguistics, Math/CS, and Stat/CS. More CS+X majors are in development.)
- Earlier algorithms: The new course moves algorithms earlier in the curriculum, so that the material can be exploited in 400-level classes.
- More flexibility later: The earlier course frees the CS department to offer a broader range of 400-level elective theory courses. CS 473 is the only such course so far, but we hope to offer a 400-level complexity-theory course in the near future.
- Computer engineers: The ECE department has wisely decided that all computer engineering majors need an algorithms course, but they did not want to force students to take both CS 373 and CS 473.
- Graduate students: There has been increasing demand from other departments, especially ECE, for graduate-level algorithms instruction.
- Calibration: To our intense frustration, the number of computer science graduate students taking CS 573 has significnatly declined over the last several years. (Our graduate programs do not require any particular classes.) By recalibrating the course, we are hoping to reinvigorate graduate-student interest in algorithms. We have no plans to offer a separate CS 573 in the near future, although we do regularly teach several other specialized 500-level algorithms courses.