"CS 374" — About This Course

CS 498 section BL1 (unofficially "CS 374") covers fundamental tools and techniques from theoretical computer science, including design and analysis of algorithms, formal languages and automata, computability, and complexity. Specific topics include regular and context-free languages, finite-state automata, recursive algorithms (including divide and conquer, backtracking, dynamic programming, and greedy algorithms), fundamental graph algorithms (including depth- and breadth-first search, topological sorting, minimum spanning trees, and shortest paths), undecidability, and NP-completeness. The course also has a strong focus on clear technical communication.

Enrollment: This is the fourth offering of "CS 374", and the second one "at scale" (400 students). Some bugs are still to be expected. Your patience and feedback is appreciated.
Prerequisites: 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!
Postrequisites: CS 374 is a prerequisite for CS 421 (programming languages, required for all CS majors), the soon-to-be revised CS 473, and possibly for other 400-level courses.
Coursework: Grades will be based on online quizzes (4% total), weekly written homeworks (24% total), two midterms (22% each), and a final exam (28%). See the grading policies for more details.
Difficulty: This is a hard course. Many CS majors considered CS 473 the single most challenging course in the entire undergraduate curriculum; CS 374 covers more material than CS 473 did, at a faster pace. On the other hand, many alumni and employers consider CS 473 the most useful course in the undergraduate computer science curriculum (after CS 225), in no small part because it was so challenging. It is our sincere hope that CS 374 develops a similar reputation. CS and CE majors are some of the brightest students on campus; an easier course would be an insulting waste of your time.

Class Resources

Web site

Almost everything—course policies, detailed schedule, lecture notes, lecture videos, homeworks, homework solutions, head-banging problems, etc.—can be found here. Hey, look! You found it!

Lecture notes

There is no required textbook for this class. Lecture notes and presentation slides will be posted to the course web site as the semester progresses. Some older lecture notes are already available:

Jeff's algorithms notes for CS 473 and CS 573. The site also contains homeworks, lab handouts, and exams from Jeff's past algorithms classes. Jeff is revising these notes to include new material from CS 374; eventually this will become a single cohesive reference.
Margaret Fleck's discrete mathematics textbook for CS 173 (review material)
Mahesh Viswanathan's automata and formal languages notes for CS 373
Margaret Fleck and Sariel Har-Peled's automata and formal languages notes for CS 373

Videos

In Spring 2015 there were technical difficulties in the room that prevented the lectures from video-taped. This semester they should be available (see the link on the main page) although we strongly encourage students to attend the lectures in person to get the most out of them.

Moodle

We will use Moodle for weekly online quizzes, for homework turn-in and grading, and to record and distribute grades. Registered students should already have access. If you've recently registered, it may take until the next day to gain access. Contact the course staff if this does not occur in a timely manner.

Piazza

We will use Piazza for online discussions. Anyone can sign up for access to the CS 374 Piazza site. 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. Furthermore, all questions to course staff should be posted as a private note via Piazza.

Etc.

There are a long list of other useful resources on a separate page.

What happened with CS x73 courses?

For students familiar with the existing/old CS curriculum: CS 374 includes about half of the material in CS 373 (which has now been retired) and about two-thirds of the material from CS 473 (which is being revised), combined into a single four-credit 300-level course. The move from two required theory courses (373 and 473) to one (374) is part of a larger revision of the undergrad CS currculum. This particular change was motivated by several factors.

Smaller CS core: The CS department is shrinking the core of required undergraduate courses, which is shared by all undergraduate computer science programs. (The CS department currently offers seven majors: CS Engineering, CS+Anthropology, CS+Astronomy, CS+Chemistry, CS+Linguistics, Math/CS, and Stat/CS. Several 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: In particular, the earlier course frees the CS department to offer a broader range of 400-level elective theory courses.
Computer engineers: The ECE department has wisely decided that all computer engineering majors need an algorithms course, but did not want to force students to take both CS 373 and CS 473.

Covering every important topic from CS 373 and CS 473 in a single course is simply impossible; we have had to make some difficult choices. Topics from CS 473 that we could not include will survive in a new revision of CS 473, which has launced in Spring 2015 and will be taught every semester including this one.