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
 NPhardness 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 undergraduatelevel 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 proofbased 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 500level 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 500level credits. It's a 400level 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 builtin 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 courserelated 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 juniorlevel class on formal languages and machine models, required for all undergraduate computer science majors.
 CS 473: A seniorlevel algorithms class, required for all undergraduate computer science majors.
 CS 573: A graduatelevel algorithms class, designed for computer science PhD students.
The new regular theory currculum has just two courses:

CS 374: A new juniorlevel 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 twothirds 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 400level classes.
 More flexibility later: The earlier course frees the CS department to offer a broader range of 400level elective theory courses. CS 473 is the only such course so far, but we hope to offer a 400level complexitytheory 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 graduatelevel 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 graduatestudent 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 500level algorithms courses.