About CS/ECE 374

Course Description:

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 (30% total), two midterms (20% each), and a final exam (30%). 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.

Website:

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!

Videos:

Recordings of all lectures will automatically appear on Echo360 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.

Gradescope:

We will use Gradescope for homework submission and grading. Anyone can sign up for access to the CS/ECE 374 Section B Gradescope site using the self-enrollment code MGZY84. Please sign up using your @illinois.edu email. Otherwise, it will be hard to correctly map your grades to your Gradescope identity.

Piazza:

We will use Piazza for online discussions and announcements. Anyone can sign up for access to the CS/ECE 374 Section B Piazza site with any name and any email address; no access code is required. We strongly encourage posting questions on any course-related topic to Piazza rather than emailing the course staff. We are unlikely to respond quickly to email. You can even post your questions anonymously to your classmates and you can post private questions to instructors.

The goal of Piazza is to generate discussion among students. The staff will monitor Piazza regularly. However, we cannot guarantee a response to every question as we have a small staff. This is especially true for last minute questions before assignment deadlines and exams. Please use the following etiquette:

  • Post your question significantly before the deadline if you want a response.
  • Monitor Piazza for answers to your classmates' questions and other clarifications and announcements. Many students will have similar questions.
  • Before asking a question check if it has already been answered on the class webpage, the slides, or on Piazza itself. It takes 1 min for you to check before asking. By asking questions that have already been answered, you create a lot of spam for everyone that distracts from new questions.
  • Help answer each other's questions. We will try to approve non-staff answers if they are correct and we have time. We reserve the right to bump up grades of students who were really helpful in answering questions on Piazza.
  • Please be courteous to the staff and your classmates. We reserve the right to deduct grades due to rudeness.

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:

Additional Rescources:

We've collected a long list of other useful resources on a separate page.