CS/ECE 374 A (Spring 2024)
Introduction to Algorithms & Models of Computation
Course Staff
Instructors 
Teaching Assistants 
Course Assistants 
Timothy Chan (tmc)
Ruta Mehta (rutameht) 
Alex Desjardins (aed6)
Ahsan Gilani (ahsang2)
Zhengcheng Huang (zh3)
Rhea Jain (rheaj3) (head TA)
Sonali Merchia (merchia2)
Haoxiang (Tommy) Sun (hs23)
Yuancheng Yu (yyu51)
Shiliang Zuo (szuo3) 
Abhi Annaluru (abhia2)
Rahul Bansal (rahulb4)
Brendan Biernacki (bab8)
Sushruth Booma (sbooma2)
Alex Broihier (adb12)
Tianyue Cao (tc37)
Tue Do (tuedo2)
David Fu (jiahaof4)
Aniket Gargya (agargya2)
Sebastian Gluszak (sglus2)
Sambhav Gupta (sambhav4)

Jacob Levine (jlevine4)
Sean Liu (zxliu2)
Meghan Lu (meghan7)
Shashwat Mundra (mundra3)
Ashay Parikh (ashayp2)
Pranav Pullabhotla (pranav19)
Sam Shi (mshi17)
Kaushik Varadharajan (kv22)
Allison Ye (ay14)
Maxwell You (myou6)
Ryan Ziegler (ryanjz2)


We are also grateful to the TheorieLearn team for developing
materials on PrairieLearn for our guided problem sets (GPSs).
Meeting Time/Place
There are two lectures per week, and two lab/discussion sessions per week.
Lectures will be recorded and made available in mediaspace to registered students.
AL1 Lecture 
TR 11:00am12:15pm 
THEAT Lincoln Hall 
Timothy Chan / Ruta Mehta 
AYJ Discussion 
WF 9:00am9:50am 
Siebel 1304 
Haoxiang Sun 
AYK Discussion 
WF 10:00am10:50am 
Siebel 1304 
Haoxiang Sun 
AYA Discussion 
WF 11:00am11:50am 
Siebel 1304 
Rhea Jain 
AYB Discussion 
WF 12:00pm12:50pm 
Siebel 1304 
Alex Desjardins 
AYC Discussion 
WF 1:00pm1:50pm 
Siebel 1304 
Yuancheng Yu 
AYD Discussion 
WF 2:00pm2:50pm 
Siebel 1304 
Ahsan Gilani 
AYE Discussion 
WF 3:00pm3:50pm 
Siebel 1304 
Shiliang Zuo 
AYF Discussion 
WF 4:00pm4:50pm 
Siebel 1304 
Zhengcheng Huang 
AYG Discussion 
WF 5:00pm5:50pm 
Siebel 1304 
Sonali Merchia 
AYH Discussion 
WF 6:00pm6:50pm 
Siebel 1304 
Sonali Merchia 
Office Hours
See calendar below
for the time and location of office hours.
Most office hours (except for Wednesdays and Saturdays) will be held in the open lounge area on the 3rd floor of Siebel (outside of 3240).
Wednesday office hours from 12:002:50 will be in Siebel 0218.
Saturday sessions are meant to be "homework parties", where students can work together
and help each other, with course staff present to answer questions.
Timothy/Ruta will also hold a "conceptual" office hour on most Thursdays.
All guided problem sets ("GPSs") on PrairieLearn are due Tuesdays at 10:00am. All written homeworks are due Thursdays at 10:00am. We will post each week's homework about one week before the due date; we will post solutions here within a couple of days after the due date. Please carefully read the homework policies and academic integrity page!
 GPS1 (due Jan 23), HW1 [.tex] (due Jan 25)
[solutions]
 GPS2 (due Jan 30), HW2 [.tex] (due Feb 1)
(1/26: hints changed in 2.2(a) and (b); 1/27: further change in hint for 2.2(a))
[solutions]
(last updated 2/9)
 GPS3 (due Feb 6), HW3 [.tex] (due Feb 8)
(2/1: extra parenthesis removed in 3.1(a))
[solutions]
 GPS4 (due Feb 13), HW4 [.tex] (due Feb 15)
[solutions]
 GPS5 (due Feb 27), HW5 [.tex] (due Feb 29)
 GPS6 (due Mar 5), HW6 (due Mar 7)
 GPS7 (due Mar 19), HW7 (due Mar 21)
 GPS8 (due Mar 26), HW8 (due Mar 28)
 GPS9 (due Apr 2), HW9 (due Apr 4)
 GPS10 (due Apr 16), HW10 (due Apr 18)
 GPS11 (due Apr 23), HW11 (due Apr 25)
Here are some selected past HW problems with solutions that you may find useful (both as extra practice problems, and as examples on how to write solutions):
 Date and time: Feb 19 Monday 7:00pm9:00pm
 Location:
 for students with last names starting with AG: Natural History Building 2079
 for students with last names starting with HR: Campus Instructional Facility 0027/1025
 for students with last names starting with SZ: Noyes Laboratory 100
 Instructions: Please read the midterm 1 cover page.
Except for the cheat sheets (see below), exams are closedeverything. In particular: No medically unnecessarily electronic devices are allowed in exams, including smart watches and headphones/earbuds.
 Cheat sheets: You may bring one doublesided 8.5" x 11" sheet of paper with anything you like written on both sides, with your name and NetID written on the upper right corner. (Two singlesided sheets are okay.) You must write your own cheat sheets by hand on paper, unless you have a documented writing disability. No printing or photocopying. We may not return or scan the cheat sheets, so if you want to keep a copy, you should photocopy or scan your cheat sheet before the exam.
 All exams are strictly confidential for at least 24 hours, until all conflict exams have been taken. Do not discuss your exam with anyone, either in person or online. (We may deactivate this class's Ed and discord during this period.)
 Coverage:
Lectures (and labs) from week 14; see
midterm 1 skillset for more details.
 Practice problems:
 Conflict midterm 1: Feb 20 Tuesday 7pm9pm.
This will be a different exam.
Conflict exams will be offered only to those with a valid reason. To get permission, you must fill in this form by Feb 14 Tuesday 5pm.
 DRES accommodations:
If you have sent us your DRES accommodation letter at the beginning of the semester,
you should have already been contacted by us about
scheduling your exam at the DRES TAC. If not, please email Timothy ASAP.
Midterm 2
 Date and time: Apr 8 Monday 7:00pm9:00pm
Final Exam
About This Course
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 contextfree languages, finitestate automata, recursive algorithms (including divide and conquer, backtracking, dynamic programming, and greedy algorithms), fundamental graph algorithms (including depth and breadthfirst search, topological sorting, minimum spanning trees, and shortest paths), undecidability, and NPcompleteness.
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); see stuff you already know.
There is no required textbook, but Jeff Erickson's book is highly recommended. Notes/scribbles can be found in the lecture schedule page. Other useful resources
(see also here):
 some past offerings of CS/ECE 374: Fall 2023 (Jeff Erickson), Spring 2023 (Chandra Chekuri), Fall 2022 (Sariel HarPeled), Spring 2022 (Timothy Chan and Ruta Mehta), ...
 other textbooks on algorithms, e.g., by Cormen, Leiserson, Rivest, and Stein, and DasGupta, Papadimitriou, and Vazirani, and Kleinberg and Tardos
 other textbooks on automata and NPcompleteness, e.g., by Hopcroft, Motwani, and Ullman and Sipser
Website generously borrowed from those of previous semesters.