Skip to content

CS374A

CS374A is one of two independent sections of CS374/ECE374 (Introduction to Algorithms and Models of Computation). It is a 4-credit hour course that is specifically required for CS majors and CEs and qualifies as a technical elective for EEs. It is offered in both the fall and spring. The A section is unofficially the 'CS' version of 374. Notes on the differences between the two sections can be found on the CS374A vs ECE374B page.

Content Covered

First Third (Languages)

  • Induction, with a focus on application to strings
  • Regular languages
  • Regular expressions
  • Deterministic finite autoamta (DFAs)
  • Nondeterminstic finite automata (NFAs)
  • Regular language transformation via DFA and NFA manipulations
  • Myhill-Nerode theorem and proving irregularity with fooling sets
  • Context free languages and context free grammars (CFGs)
  • Turing machines (only some semesters)

Middle Third (Algorithms)

  • Divide and conquer algorithms
  • Backtracking algorithms
  • Dynamic programming algorithms
  • Graph search algorithms
  • Greedy algorithms
  • Minimum spanning trees

Final Third (Complexity)

  • NP-Completeness and NP-hardness reductions
  • Undecidable languages
  • Undecidability of the halting problem
  • Undecidability reduction proofs

Prerequisites

CS374A studies algorithms using theoretical tools covered in CS173 and data structures covered in CS225. For the first third, students should be comfortable with induction and finite state machines (FSMs) from CS173; for the second third, students should be comfortable with data structures from CS225; for the final third, students should be comfortable with proof by contradiction from CS173.

When to Take it

CS374A is a required course for Computer Science and Computer Engineering majors. It serves as a prerequisite for CS421 (Programming Languages and Compilers), a required course for Computer Science majors, and students should complete it by their second-to-last semester. Algorithmic topics covered in CS374, especially dynamic programming, are useful for internship and full-time job interviews, so taking the course earlier may be beneficial.

Many students find CS374A to be a challenging course, so use caution when scheduling it in a semester with many other difficult courses.

Course Structure

Lecture

CS374A has lecture on Tuesday and Thursday for 75 mintues. Attendance is optional and lectures are recorded. Some students prefer to watch Professor Jeff Erickson's CS374 lecture videos instead, which are listed in Resources.

Discussion

CS374A has discussion sections on Wednesday and Friday, where students work with each other and a TA to solve practice questions. While optional, these discussions reinforce content covered in lectures and provide a way to get comfortable with content before homework and exams. Sometimes, discussions also introduce new material that can be helpful for homework assignments.

Homework and Guided Problem Sets

CS374A has a homework assignment during each non-exam week, which students may complete in groups of up to three people. Assignments consist of 2-3 problems and can be difficult, so it is beneficial to start early.

During each non-exam week, students are assigned a Guided Problem Set (GPS) on PrairieLearn to complete individually. GPSes offer instant feedback and focus on building intuition necessary to complete homework assignments, so it's recommended to complete the GPS before the homework assignment.

Exams and Grading

CS374A has two midterms and one final, and typically does not curve exam scores. Each midterm is worth 21% and the final is worth 30%. The remainder comes from homework scores (one GPS is equal to one homework problem). The lowest 4-6 homework problem scores over the semester are not included in grade calculation. The cutoffs for the letter grade are slightly lower than standard(>=90 for A, >=85 for A-, >=80 for B+, etc), and the final letter grade is curved based on the mean and standard deviation.

Instructors

The instructors for CS374A rotate between CS theory staff:

  • Sariel Har-Peled: considered to be the most difficult CS374A professor, but usually writes interesting problems and can be a fun lecturer
  • Jeff Erickson: author of the CS374 textbook and an engaging lecturer, some students wait for him to be teaching before taking the course
  • Chandra Chekuri: an engaging lecturer that cares about students and writes reasonable exams
  • Ruta Mehta and Timothy Chan: usually co-teaching with Professor Mehta lecturing, strong lectures but homework and exam questions may be difficult

Course Tips

It is important to work on homework assignments as a group, with others you work well with. Some groups prefer to solve problems together, while others prefer to break up the problems between members. Whichever approach you take, make sure to understand the solutions to every homework problem, because they may contain techniques that will be useful on exams.

You can save several hours on homework assignments by attending discussion sections for two hours per week. Since discussion attendance is optional, you can go to a different discussion section you are registered if there's space. Discussion sections are also a good place to meet potential groupmates for homework assignments.

It is important to show your work on all assignments, and if you handwrite, write legibly. Graders are generous with partial credit.

Office hours are very helpful. TAs will usually go over the general idea of the homework problems and provide useful hints. Q/A platform(Ed, discord) is also important since course staff will answer questions and make annoucements related to the course.

Life After

CS374 (or ECE374) is a prerequisite for CS421 (Programming Languages), a required course for Computer Science majors. Students who enjoyed the middle third of the course will enjoy CS473 (Algorithms). Students who enjoyed the first and last thirds of the course will enjoy CS475 (Formal Models of Computation).

While CS374A is considered a challenging course, it leaves students with a better ability to logically break down problems, consider multiple approaches, and find a solution, which is an important skill for engineering.

Infamous Topics

  • Language transformations: there is usually a language transformations question on the first midterm, and this is an unintuitive topic. TAs and CAs are good resources to ask for help, and Professor Erickson's textbook contains several examples.
  • Dynamic programming: dynamic programming solutions rely on recursion, which can be unfamiliar. The best way to improve is practice.
  • NP-completeness reductions: it is easy to prove the wrong direction, so you should draw diagrams and examples before starting your proof.

Resources