CS 374

CS 374 - Intro to Algorithms and Models of Computation

3

Credit Hours

Emily Fox

Instructor

Prerequisites
CS 173andCS 225

This is the primary theoretical computer science course for all CS/CS+X majors, comprising of in-person lectures, lab sections, weekly homeworks, and exams. There are two sections for this course, CS374A and CS374B, with the former being targeted to CS(+X) majors and the latter to ECE majors. The course structure and content taught between the two sections vary, with historic material indicating there is slightly more breadth in the B section and more depth in the A section.

As this is a wiki targeting CS and CS+X majors, the content of this page will primarily concern the CS374A. All future usage of CS374 refers to CS374A unless otherwise specified.

Topics Covered

  • Models of Computation
    • Induction
    • Languages
    • (Non-)Regularity of Languages (Fooling Sets)
    • Regular Expressions
    • Deterministic/Non-deterministic Finite Automata (DFA/NFAs)
    • Language Transformations
    • Context-Free Grammars
  • Algorithms
    • Recursion
    • Divide and Conquer
    • Backtracking
    • Dynamic Programming
    • Graphs and Graph Algorithms
      • Graph Traversal (BFS/DFS)
      • Shortest Path
      • Minimum Spanning Trees
      • Topological Sort
    • Greedy Algorithms
  • Complexity Theory
    • NP-Hardness
    • (Polynomial-time) Reductions
    • Turing Machines
    • Undecidability

Resources

Office hours are hosted as per the syllabus. Professor Jeff Erickson, who has previously taught this course, has a very well-written textbook covering all the content of the course. There are also some auxiliary notes on language transformations by staff of the course:

Developer’s Commentary

The Big, Bad Wolf

This class as a reputation of being extremely difficult and time consuming. This reputation is well-founded; on average, many students find the content and homeworks in this class difficult to understand. We attribute this largely because this classes forces you to think about problems in a novel way. More specifically, behind the language transformations, the memoisation, and turing machines, is the ability to problem-solve using only the foundational building blocks of a computer. This difficult, learned skill is much like how many students struggle when first tasked to write a program in C++ to solve a problem; a lot of the difficulty comes from expressing an idea in an unknown framework. That being said, we are very fortunate to be equipped with a brain capable a learning new things; with enough practice problems, office hours, and late-night tears, we assure you that you will make it through this course.

That being said, as this course is time-consuming, we suggest that students surround this course with lighter courses to allocate adequate time. This course is difficult as it is- no need to be miserable and overload yourself with other difficult courses. Specifically, we don’t recommend taking it with CS341, another core class that can be extremely time-consuming (or even ECE391), as the combined time-commitment can be quite strenuous. (If you happened to be wired such that this course comes naturally to you, or such that you can gracefully handle the increased workload, then more power to you! Otherwise, save yourself the headache. There is no trophy for the hardest semester or the most all-nighters.)

Application of Content

For those seeking careers in software engineering, the content in this class can be extremely useful for interviews and the job as a whole. Specifically, the techniques employed in many LeetCode Medium problems are covered in this class (Dynamic Programming, Graph Algorithms). In many LeetCode problems, you are tasked with framing a plain-text problem as a dynamic programming or graph problem. The algorithms portion of this course teaches you exactly this skill.

As a whole, the skill to take a real-life problem and solve it with a sensible data structure and algorithm is wildly applicable to the software engineering field.

CS374A vs. CS374B

There’s a lot of debate on whether the A section is harder than the B section. We’ll make no definitive statement on this debate, as the perceived difficulty of any given class is highly dependent on the student. Generally speaking, the historic grade cutoffs and overall grade distribution for the B section seem to be kinder than the A section. That being said, if you are a CS major, we highly recommend taking the A section as it is tailored the major and its academic goals.

Last updated: March 05, 2026