ECE374B: Fall 2026

CS374B: Introduction to Algorithms & Models of Computation

Introduction

Welcome to CS/ECE 374, a foundational course in theoretical computer science jointly offered by the Siebel School of Computing and Data Science – SSCDS – and the Department of Electrical and Computer Engineering – ECE – at the University of Illinois, Urbana-Champaign.

How to find this page again? Press Ctrl+D (Windows) or Cmd+D (Mac) to bookmark it. Or memorize: courses.ece.uiuc.edu/ece374bl1

This is Section B of the course – this semester the two sections will run completely independently, with different instructors, office hours, and discussion sections.

This course delves into the essential tools and techniques for understanding formal languages and automata, designing and analyzing algorithms, and exploring the limits of computation.

Key Topics: The key topics covered in this course are:

  • Formal Models of Computation: Understand formal definitions of languages, finite automata, Turing machines, and the Church-Turing thesis.
  • Algorithm Design: Learn various paradigms such as recursive algorithms, divide-and-conquer, dynamic programming, and greedy algorithms.
  • Graph Algorithms: Study fundamental graph algorithms, including reachability, breadth-first search, depth-first search, shortest paths, and minimum spanning trees.
  • Complexity Theory: Explore the concepts of NP-completeness, polynomial-time reductions, and undecidability.

Prerequisites: One of CS 173 (Discrete Structures) or MATH 213 (Basic Discrete Mathematics), and CS 225 (Data Structures).

Learning Outcomes: By the end of this course, students will be able to:

  • Understand formal models of computation and their limitations.
  • Design efficient algorithms for a variety of computational problems.
  • Analyze the asymptotic running time of algorithms.
  • Model computational problems using graphs and apply appropriate graph algorithms.
  • Prove the correctness of algorithms and understand their limitations.
  • Demonstrate an understanding of NP-hardness and undecidability through reductions.

Course Structure: The course includes lectures, discussion sessions, and hands-on assignments to reinforce the theoretical concepts covered. Active participation in all sessions is strongly encouraged to maximize learning outcomes.

Course Platforms: The course platforms are:

  • Website is the primary platform for everything you need.
  • Canvas to formally maintain grades.
  • Gradescope to submit homework, view grades, and submit regrade requests.
  • Campuswire to have class-related discussions.
  • PrairieLearn to submit Guided Problem Sets (GPS).

Grading

The course grade will be based on homework, quizzes and exams. The weights of the various items are as follows:

  • GPS: 14%. There will be 12 Guided Problem Sets (GPS) released via PrarieLearn. We will drop the lowest scoring two sets. Thus each GPS counts towards 1.4% of the course grade.
  • Exams: 66%. There will be a total of 4 exams. Three non-cumulative exams, called midterms, will be taken during class time. An optional cumulative final exam will be held according to the final exam schedule determined by the registrar. Each counted exam (midterm or final) will carry 22% of the final grade.
  • Quizzes: 20%. There will be twelve short quizzes held during the lab sections, with the lowest scoring two quizzes dropped. Each counted quiz will carry 2.0% of the final grade.
  • Homework: This semester we will not have traditional graded homework sets. Instead, a collection of past homeworks will be released for practice.

The final letter grades will be assigned as follows, based on your course score:

[0, 60) [60, 70) [70, 80) [80, 90) [90, 100]
F D-, D, D+ C-, C, C+ B-, B, B+ A-, A, A+

Note that \([x, y)\) means the interval that includes \(x\) but not \(y\). The grades may be curved using one, both, or neither of these methods:

  • Adjusting the cutoffs so that the final grade is better than it would be based on the initial cutoffs, but never worse.
  • Increasing the raw exam scores based on the overall class performance.

By design, you can miss, perform poorly, or fail on a midterm and still make up for it on the final exam. But if you miss two or more exams, which realistically means you miss the final exam in addition to a midterm, you will not get a passing grade unless you secure an incomplete from the College (which is not under my control).

Textbooks and References

The course textbooks are:

  • [SITC] Michael Sipser, Introduction to the Theory of Computation, 3rd Edition.
  • [JEAL] Jeff Erickson, Algorithms, 1st Edition, June 2019. Free ebook.
  • [JEMC] Jeff Erickson, Models of Computation, December 2018. Online notes.

Additional references are:

  • [ATLC] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, Automata Theory, Languages, and Computation, 3rd Edition.
  • [CLRS] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 3rd Edition.
  • [KTAD] Jon Kleinberg and Éva Tardos, Algorithm Design, 1st Edition.
  • [TACP] Donald E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd Edition.

Absence Policy

One of the great aspects of the college experience is that it is truly what you make of it. Attendance will not be enforced in this class. However, attending lectures is crucial as exams will cover both lecture content and assigned readings. You are responsible for all lecture materials and any announcements made in class, regardless of your attendance.

Weekly quizzes will be held during the Friday lab sections; so attending these are necessary to keep your grade up. If you miss a quiz, you will receive a zero for that quiz. There will be no make-up quizzes. See the quiz policy.

Please communicate with the instructor and/or the teaching assistant if you become ill, or emergencies arise, so that we will be aware of your circumstances. Article 1, Part 5 of the Student Code outlines those circumstances in which a student may be eligible to obtain a letter from the Office of the Dean of Students for absences.

Academic Honesty

The usual academic integrity policies apply. Students are expected to behave in a professional & ethical manner, and your work should be your own. At minimum, plagiarism or cheating will result in a zero for the relevant assignment/exam and a grade reduction (see quiz and exam policies). Repeat offenses may result in a failing grade for the course.

Please refer to Article 1, Part 4 – Academic Integrity Policy and Procedure of the Student Code of the University of Illinois Urbana-Champaign for relevant definitions and policies.

Generative AI Policy

Generative AI tools can provide plausible text or code, but they do not replace your learning. This course seeks to impart and measure a solid understanding of course material rather than your knack in prompting a model.

Improper use of AI tools can:

  1. Mask gaps in your understanding
  2. Lead to incorrect or unverified solutions
  3. Cause poor performance in unplugged exams and interviews
WarningWARNING

AI usage is not allowed in individual assessments (i.e., quizzes and exams). Any use of AI tools in these assements is a breach of class policy.

That said, we recognize that generative AI tools can be useful for brainstorming, ideation and additional learning. You may sparingly use generative AI tools (e.g., ChatGPT, Gemini, Claude, GitHub Copilot, Bard) to assist your learning and problem solving.

We strongly recommend a maximal attempt to solving problems yourself before resorting to LLM use.

Your AI usage in this class is subject to the following guidelines:

  • You must re-write: all solutions, code, explanations based solely on your understanding without help after AI usage.
    • Simply copying text or code from an AI tool into your submission (even with attribution) is NOT acceptable.
    • Simply reading the AI generated solution is NOT learning.
    • Simply paraphrasing the AI solution while having it open is NOT based on your understanding. Go for a run, have a meal – come back and then redo the problem by yourself. 

    While we won’t enforce this guideline any deviation from it will naturally become obvious (see point 3 above).

Like Prof. Erickson writes, “…Understanding is a seductive lie, a warm feeling of satisfaction that your brain uses as a defense mechanism against doing real work. The only way to know when when you truly understand the concepts (is) when you can do the work.”

So, if after using AI, you cannot solve a problem of the same pattern on your own, you have not learned the material.

  • You must clearly document usage of the tool: On any submitted work where AI usage is allowed, include a short statement at the top or bottom of your submission. For example:

    Used ChatGPT (GPT-4) to help interpret problem prompt and brainstorm
approaches; final solution written entirely in my own words."

  • Treat AI assistance like any other external source: Use it to inform your work instead of generating it. Always validate it independently. Then, cite any usage, and describe/reflect on how you used it to inform your work or better your understanding.

The days of being able to pass AI work off as your own could soon be over. See Anthropic’s announcement about watermarking AI generated text.

As engineers and computer scientists, you are expected to be responsible for all documentation and code you submit, and to ensure that it is correct & complete – you will hardly be able to blame AI for a failure at your future workplace.

Accessibility and Disability Accommodations

To obtain disability-related academic adjustments and/or auxiliary aids, students with disabilities must contact the course instructor as soon as possible and provide the instructor with a Letter of Accommodations (LOA) from Disability Resources and Educational Services (DRES). Please refer to Disability Resources and Educational Services (DRES) at the University of Illinois Urbana-Champaign for further details.

To streamline the process for a class this size please upload your LOA using the LOA Upload Link and read about policy on exams and quizzes.

Community of Care

As members of the Illinois community, we each have a responsibility to express care and concern for one another. If you come across a classmate whose behavior concerns you, whether regarding their well-being or yours, we encourage you to refer this behavior to the Connie Frank CARE Center (formerly the Student Assistance Center) in the Office of the Dean of Students. You may do so by calling 217-333-0050 or by submitting an online referral. Based on your report, staff in the Student Assistance Center will reach out to offer support and assistance

Disruptive Behavior

Behavior that persistently or grossly interferes with classroom activities is considered disruptive behavior and may be subject to disciplinary action. Such behavior inhibits other students’ ability to learn and an instructor’s ability to teach. A student responsible for disruptive behavior may be required to leave class pending discussion and resolution of the problem, and may be reported to the Office for Student Conflict Resolution for disciplinary action.

Emergency Responses

In the event of a major campus emergency, course requirements, deadlines, and grading percentages are subject to changes that may be necessitated by a revised semester calendar or other circumstances.

Please review the run, hide, fight handout and video provided on campus for information from the U of I Police Department.

Emergencies can happen anywhere and at any time, so it’s important that we take a minute to prepare for a situation in which our safety could depend on our ability to react quickly.

  • Take a moment to learn the different ways to leave the class building. If there’s ever a fire alarm or something like that, you’ll know how to get out and you’ll be able to help others get out.
  • Next, figure out the best place to go in case of severe weather – we’ll need to go to a low-level in the middle of the building, away from windows.
  • If there’s ever someone trying to hurt us, our best option is to run out of the building. If we cannot do that safely, we’ll want to hide somewhere we can’t be seen, and we’ll have to lock or barricade the door if possible and be as quiet as we can. We will not leave that safe area until we get an Illini-Alert confirming that it’s safe to do so. If we can’t run or hide, we’ll fight back with whatever we can get our hands on.

If you want to better prepare yourself for any of these situations, visit police.illinois.edu/safe.


Emergency response recommendations and campus building floor plans can be found at the following website: https://police.illinois.edu/em/run-hide-fight/. We encourage you to review this website within the first 10 days of classes.

Religious Observances

It is the policy of the University of Illinois Urbana-Champaign to reasonably accommodate its students’ religious beliefs, observances, and practices that conflict with a student’s class attendance or participation in a scheduled examination or work requirement, consistent with state and federal law.

You should review the course website, and any due dates therein to make requests for accommodation two weeks before any conflict to allow time for both consideration of the request and alternate procedures to be prepared. Requests should be directed to the instructor. The Office of the Dean of Students provides a resource on its website to assist students in making such requests by generating a Letter of Accomodation (LOA) for submission to the instructor.

To streamline the process for a class this size please upload your LOA using the LOA Upload Link.

Other Policies

The Grainger College of Engineering at Illinois is committed to the creation of an anti-racist, inclusive community that welcomes diversity along several dimensions. The effectiveness of this course is dependent upon each of us to create a safe and encouraging learning environment that allows for the open exchange of ideas while also ensuring equitable opportunities and respect for all of us. Everyone is expected to help establish and maintain an environment where students, staff, and faculty can contribute without fear of personal ridicule, or intolerant or offensive language.

We in the Illinois ECE community are committed to understanding, empathizing with, and respecting each other, embracing the many differences among us.

If you witness or experience racism, discrimination, micro-aggressions, or other offensive behavior, you are encouraged to bring this to the attention of the course director if you feel comfortable. You can also report these behaviors to Campus Belonging Resources.