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.
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."
CS 374 is a prerequisite for CS 421 (programming languages, required for all CS majors), and CS 473, and possibly for other 400-level courses.
Grades will be based on online quizzes (6% total), weekly written homeworks (24% total), two midterms (20% each), and a final exam (30%). See the grading policies for more details.
This is a hard course.
Many students consider 374 the single most challenging course in the entire undergraduate curriculum. On the other hand, many alumni and employers consider CS 374 the most useful course in the undergraduate computer science curriculum (after CS 225), in no small part because it was so challenging. CS and CE majors are some of the brightest students on campus; an easier course would be an insulting waste of your time.
- Web site
- Course policies, detailed schedule, lecture notes, and lecture videos can be found here.
- Lecture notes
Lecture notes will be posted on the course website as the semester progresses. Other lecture notes are already available:
- Video recording of the lectures will be available on a separate page. However, we strongly encourage students to attend
the lectures in person to get the most out of them.
- We will use Moodle to post weekly online quizzes, post homework assignments and solutions, 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.
- We will use Piazza for online discussions. Anyone can sign up
for access to the CS 374 B 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.
- There are a long list of other useful resources on a separate page.