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.
The CS department strictly enforces the CS 173 (or Math 213) and CS 225 prerequisite requiremens. 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.
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. These are strict prerequisites; students must already have credit for both CS 163/Math 213 and CS 225 in order to register.
This course is required for all undergraduates majoring in Computer Science majors (of all fifteen species) and all Computer Engineering majors at Illinois.
CS/ECE 374 is a prerequisite for at least the following classes:
Grades will be based on weekly preflights, weekly homeworks, two midterm exams, and a final exam. Preflights are auto-graded warmup exercises, often (but not always) involving small snippets of Python. Homeworks 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 these contribute to the final course grade.
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 do the thing; the more you do, the better you get.
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.
- 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. The course will closely follow Jeff's models of computation lecture notes and Algorithms textbook, all of which you can download for free. The 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.
- All lectures and labs will be held simultaneously in person and on Zoom; links are available [SOMEWHERE] on the main course web page. Access to these Zoom sessions requires University login credentials. We will also use Zomo for proctoring online exams; stay tuned for details.
Recordings of all lectures and labs will appear on MediaSpace shortly after each lecture. We also plan to post walkthrough videos for a few of each week's lab and solved homework problems. Lecture and walthrough videos should be publicly accessible forever; lab videos are restricted to registered students (because they may include students' names, faces, and voices). Lectures videos from past semesters of CS 374 are linked from a separate page.
- We are using PrairieLearn for guided problems that count as part of the homework, as well as optional exercises that are only for practice. Pracice exercises should be open to the genreal public, but problems that count toward the course grade are restricted to registered students.
- We are using Gradescope for submission and grading of both homeworks and exams. Anyone can sign up for access to the CS/ECE 374A Gradescope site with any name and any email address, using the self-enrollment code
N84GEX. We will separately ask you for your Gradescope identity, so that we can map your homework grades to you.
- We are using Piazza for online questions and announcements. Anyone can joint the CS/ECE 374A Piazza site with any name and any email address, using the access code
374A. Please post questions on any course-related topic to Piazza rather than emailing the course staff. You can even post your questions and answers anonymously.
As a matter of course policy, course staff will wait a minimum of three hours before answering any Piazza question about the course material, so that other students have an opportunity to answer first. (We will answer administrative questions as quickly as we can.)
The university no longer has a contract with Piazza; as a result, Piazza asks for voluntary donations and/or serves advertisements to support its business. Campus administration strongly encourage instructors to use either CampusWire or Canvas for online discussion, but CampusWire has well-documented accessibility issues, and Canvas does not support anonymous posting.
- We are also using Discord for more reactive online discussions, especially during lectures and labs. In particular, one of the instructors or TAs will monitor Discord during each lecture for common questions and will pass on those questions to the lecturer. (However, we also encourage students to answer on Discord directly.) Anyone can join the 374A Discord server; no enrollment code is required.
The same three-hour delay applies to Discord, except for questions about lectures on the day of the lecture.
Using both Piazza and Discord is a bit of an experiment; each platform seems better for a different type of discussion. If traffic on one of the two platforms seriously
- We've collected a long list of other useful resources on a separate page.