CS/ECE 374A fa22: About This Course

CS/ECE 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”. If you got a C+ or worse in CS 173, we strongly recommend retaking 173 before taking 374.

Requirements

This course is required for all undergraduates majoring in Computer Science majors (in both Engineering and LAS) and Computer Engineering.

Postrequisites

CS/ECE 374 is a prerequisite for at least the following classes:

Coursework

Grades will be based on weekly written homeworks, and weekly done problems on Prairie Learn, two midterms, and a final exam. See the grading policies for more details.

Difficulty

Many students consider 374 to be a challenging course in the undergraduate CS/CE curriculum. On the other hand, we believe (and employers and alumni seem to agree) that 374 is also a very useful course in the undergraduate CS/CE curriculum.

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. Lecture notes will be posted to the course web site as the semester progresses. You should also look at a wide variety of additional resources (see the link at the bottom of this page). Some older lecture notes and/or slides are already available:

Fall 2016 offering of CS 374 by Alexandra Kolla and Jeff Erickson
Jeff's lecture notes (January 2015 revision). This site also contains homeworks, lab handouts, and exams (but no solutions) from Jeff's past theory classes.
Margaret Fleck's discrete mathematics textbook for CS 173 (review material)
Mahesh Viswanathan's automata and formal languages notes for CS 373 (Spring 2013)
Margaret Fleck and Sariel Har-Peled's automata and formal languages notes for CS 373 (Spring 2008 and Spring 2009)

Videos

All lectures will be recorded, and links to lecture videos will be added to the schedule web page as the semester progresses. However, we strongly encourage students to attend the lectures in person to get the most out of them. Videos from several past semesters are available:

Spring 2016: Mahesh Viswanathan
Fall 2015: Chandra Chekuri and Manoj Prabhakaran
Fall 2014: Jeff Erickson

Gradescope

We will use Gradescope for homework submission and grading. Anyone can sign up for access to the site with their favorite alias and email address. Go here for access.

EdStem

We will use EdStem for online discussions. Go here for access. 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. (However, we can only give you extra credit for helpful posts if you post them using your real name.)

Etc.

You can find a long list of other useful resources on a separate page.

Last modified: Mon 2022-08-22 18:10:21 UTC 2022 by Sariel Har-Peled