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.
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! 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.

Requirements
This course is required for all undergraduates majoring in Computer Engineering or any species of Computer Science.
Postrequisites
CS/ECE 374 is a formal prerequisite for at least the following classes:
Coursework
Course grades are based on weekly written homeworks, two midterms, and a final exam. See the grading policies for more details.
Difficulty
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!
Reading
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:

Videos
Recordings of all lectures automatically appear (LINK GOES HERE) at most a few hours after each lecture. Streamable and downloadable lecture videos are also available on the schedule page at most a day 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.

PrairieLearn
Quizzes will be found on PrairieLearn.
Gradescope
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 KYK557.
Piazza
We will use Piazza for online discussions. Anyone can sign up for access to the CS/ECE 374 Piazza site with with any name and any email address using the access code KYK557. 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.
We've collected a long list of other useful resources on a separate page.