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

The CS department is now strictly enforcing the CS 173 and CS 225 prerequisites. Students must have credit for both courses (either through taking the class, passing the proficiency exam, or transferring credit from an equivalent course taken elsewhere) before they can register for 374.

This course is required for all undergraduates majoring in Computer Engineering or any species of Computer Science.
CS/ECE 374 is a formal prerequisite for at least the following classes:
Course grades are based on weekly written homeworks, weekly guided problem sets (GPS) done on Prairie Learn, two midterms, and a final exam. See the grading policies for more details.
Many students consider 374 to be the most challenging course in the entire undergraduate CS/CE curriculum (perhaps after ECE 391). On the other hand, we believe (and employers and alumni seem to agree) that 374 is also the most useful course in the undergraduate CS/CE curriculum (perhaps after CS 225), in no small part because it is so challenging. CS and CE majors are among the brightest and hardest-working 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, lab problems, etc.—can be found here. Hey, look! You found it!
There is no required textbook. Lecture notes / book chapters for all lecture topics are available on the schedule page.

The algorithms portion of the class largely follows Jeff's Algorithms textbook, which is freely available online. The book web site also contains lots of additional lecture notes, along with homeworks, lab handouts, and exams (but no solutions) from his past theory classes.

You may also find resources from other Illinois instructors useful:

Recordings of all lectures automatically appear (LINK GOES HERE) at most a few hours after each lecture. However, we strongly encourage students to attend the lectures in person to get the most out of them.

Jeff's videos from Spring 2018 are also publicly available.

One problem from each homework will be a guided problem set on PrairieLearn.
We will use Gradescope for homework submission and grading (both homeworks and exams). Anyone can sign up for access to the CS/ECE 374 Gradescope site with any name and any email address, using the self-enrollment code G28NKB.
We will use EdStem for online discussions. We strongly encourage posting questions on any course-related topic to EdStem 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.)
We have a Discord server which you can use for real-time discussion of the course with your fellow students and the course staff.
We've collected a long list of other useful resources on a separate page.