"CS 374" — About This Course
CS 498 section 374 (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 contextfree languages, finitestate automata, recursive algorithms (including divide and conquer, backtracking, dynamic programming, and greedy algorithms), fundamental graph algorithms (including depth and breadthfirst search, topological sorting, minimum spanning trees, and shortest paths), undecidability, and NPcompleteness. The course also has a strong focus on clear technical communication.
 Enrollment

This is the second pilot offering of "CS 374"; many aspects of the course are still experimental. Registration is limited to 100 CS and CE majors, chosen by lottery from the students who filled out an interest survey in April.
 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 soontobe revised CS 473, and possibly for other 400level courses.
 Coursework

Grades will be based on online quizzes (5% total), weekly written homeworks (25% total), two midterms (20% each), and a final exam (30%). 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 my 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, headbanging problems, etc.—can be found here. Hey, look! You found it!
 Lecture notes

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

All lectures will be recorded, and links to lecture videos will be added to the schedule web page as the semester progresses. Jeff has asked the college to maintain these videos permanently. Videos of Jeff's CS 473 lectures from Fall 2013 are also available. Lecture videos are accessible without a password from any oncampus computer; unfortunately, after the first two weeks of the semester, offcampus access requires a university NetID and password.
 Canvas
 We will use Canvas for weekly online quizzes and to record and distribute grades. (If you've used Moodle, you basically know how to use Canvas.) Please stay tuned for further details.
 CrowdGrader
 We will use CrowdGrader for peer evaluation of some homework problems, on an experimental basis. Please stay tuned for further details.
 Piazza
 We will use Piazza for online discussions. Anyone can sign up for access to the CS 374 Piazza site with your favorite email address and the access code
CS374
. 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 with CS x73?
For students familiar with the existing CS curriculum: CS 374 includes about half of the material in CS 373 (which has now been retired) and about twothirds of the material from CS 473 (which will be revised starting next semester), combined into a single fourcredit 300level 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 400level classes.
 More flexibility later: In particular, the earlier course frees the CS department to offer a broader range of 400level 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 will launch next semester; other 400level elective CS theory courses are also in development. Here is our current timeline for the transition:

Spring 2014
 CS 373 (last offering)
CS 374 (first pilot, limited enrollment)
CS 473

Fall 2014
 CS 374 (second pilot, limited enrollment)
CS 473
CS 573 (last offering)

Spring 2015
 CS 374 (first offering at scale: 400 students)
CS 473 (last offering)
CS 473++ (first offering, limited enrollment)

Every semester thereafter
 CS 374
CS 473++
Other 400 and 500level theory courses in development