"CS/ECE 374" — About This Course

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.

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."
Postrequisites: 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.
Coursework: 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.
Difficulty: 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.

Class Resources

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:

Fall 2017 offering of CS 374 by Sariel Har Peled.
Fall 2015 offering of CS 374 by Chandra Chekuri and Manoj Prabhakaran.
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.
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

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.

Moodle

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.

Piazza

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.

Etc.

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