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 or Math 213 (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.

The CS department strictly enforces the CS 173 (or Math 213) and CS 225 prerequisite requirements. Students must have already 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 Science (in any of our seventeen degree programs) or Computer Engineering at Illinois.

Postrequisites

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

Sections

CS/ECE 374 is consistently offered in two independent sections. To first approximation, Section A is restricted to computer science majors, and Section B is restricted to ECE majors, although each section admits some students from the other department to accommodate scheduling conficts. Section B is also available to students in the City Scholars program. This is the web site for Section A; Section B has a separate site.

Coursework

Grades are based on weekly guided problem sets on PrairieLearn, weekly written homeworks, two midterm exams, and a final exam. Guided problem sets are auto-graded warmup exercises, intended to reinforce a design/solution process that can be used to solve similar homework an exam problems. Homework and exam problems are more open-ended design and proof exercises, designed to be answered on paper and graded manually. See the grading policies for more information about how each type of coursework contributes to the final course grade.

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.

We know that this material can be challenging and frustrating, but trust us—you'll get better with practice. The learning goals in this course are practical skills, just like writing or singing or cooking or programming or teaching. The only way to learn to do the thing is to consciously do the thing; the more you do, and the more you pay attention to how you do, the better you get.

In particular, you should not expect to succeed in this class merely on the basis of your intellect. Being smart can certainly help, but it is far more important to be careful and systematic, and to think about what you're doing as you're doing it. Approach every problem as an opportunity to practice solving that kind of problem, and to get feedback on that practice.

Whenever you start something new, it's completely normal to occasionally feel overwhelmed by the task at hand and/or intimidated by others who seem to be doing better than you. We have all been there. (Jeff earned a C– in his first algorithms class.) No matter how it may seem, a lot of other students in 374 also find the material challenging. And even if you are working harder than some other students, that only means you are learning more than they are.

Class Resources

Web site: Almost everything—course policies, detailed schedules, 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. The course will closely follow Jeff's models of computation lecture notes and Algorithms textbook, all of which you can download for free. The topic schedule page contains links to the relevant notes/chapters for each lecture, along with additional material written by others. Several other useful references and resources are listed on a separate page.
Videos: Recordings of all lectures will appear on MediaSpace shortly after each lecture. We are also tentatively planning to post walkthrough videos for a few of each week's lab and solved homework problems. Lecture and walkthrough videos should be publicly accessible forever. Lectures videos from past semesters of CS 374 are linked from a separate page.
PrairieLearn: We are using PrairieLearn for guided problem sets that count toward your final course grade, as well as optional exercises that are only for practice. The official PrairieLearn resources for the course are restricted to registered students, but a separate practice instance is open to the general public.
Gradescope: We are using Gradescope for submission and grading of both homeworks and exams. Everyone who registered for CS 374 before the semester started should already have access to the CS/ECE 374A Gradescope site. Students who add the course later can enroll themselves using the self-enrollment code Y76PYE.
Ed Discussion: We are using Ed Discussion for online questions and announcements. Anyone can join the Ed site with any name and any email address; no access code is necessary. Please post questions on any course-related topic to Ed rather than emailing the course staff. You can even post your questions and answers anonymously.
Discord: We are also using Discord for more reactive online discussions, especially during lectures and labs. In particular, someone on the course staff will monitor Discord during each lecture for questions, will answer most questions immediately, but will pass on common questions to the lecturer. (We also encourage students to answer on Discord directly.) Anyone can join the Fall 2023 374A Discord server; no access code is required.
Caveats: The university does not have a contract with either Ed or Discord; we cannot enroll students automatically, and we must allow you to enroll anonymously (using pseudonyms and non-university email addresses). Campus administration strongly encourage instructors to use CampusWire for online discussion and Canvas for everything else, but we prefer to use tools that actually work.
As a matter of course policy, course staff will wait a minimum of three hours before answering any online question about the course material—except for questions about lecture material on the day of the the lecture—so that other students have an opportunity to answer first. (We will answer administrative questions as quickly as we can.)
Etc.: We've collected a long list of other useful resources on a separate page.