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 and for the latest updates.
Most office hours, except those with prebooked rooms, will be held in the open lounge area on the 3rd floor of Siebel (outside of 3240) the open area in the Siebel basement outside of 0218 (the change will hopefully alleviate issues with overcrowding).
Wednesday office hours from 12:002:50 will be in Siebel 0218.
Saturday sessions, in DCL 1320, 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 (these are for questions about lecture material and other things, but not about HWs).
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)
[solutions]
 GPS6 (due Mar 5), HW6 [.tex] (due Mar 7)
(3/1: corrections in the example in 6.1)
[solutions]
 GPS7 (due Mar 19), HW7 [.tex] (due Mar 21)
[solutions]
 GPS8 (due Mar 26), HW8 [.tex] (due Mar 28)
(3/21: added footnote for clarification; 3/25: added a bonus problem 8.1(c)))
[solutions]
 GPS9 (due Apr 2), HW9 [.tex] (due Apr 4)
[solutions]
 GPS10 (due Apr 17), HW10 [.tex] (due Apr 18)
(4/13: fixed typo "T" to "Q" in 10.2)
[solutions]
 GPS11 (due Apr 23), HW11 [.tex] (due Apr 25)
[solutions]
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):

Past HW1,
Past HW2,
Past HW3,
Past HW4,
Past HW5,
Past HW6,
Past HW7,
some tips on dynamic programming,
Past HW8,
Past HW9,
Past HW10,
some tips on NPcompleteness proofs and Past HW11 (and a list of useful known NPcomplete problems)
 exam and solutions (conflict exam and solutions)
 Date and time: Feb 19 Monday 7:00pm9:00pm
 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
 exam and solutions (conflict exam and solutions)
 Date and time: Apr 9 Tuesday 7:00pm9:00pm
 Location:
 for students with last names starting with AJ: Noyes Laboratory 100
 for students with last names starting with KQ: Materials Science & Engineering Building 100
 for students with last names starting with RZ: Loomis Laboratory of Physics 141
 Conflict midterm 2: Apr 8 Monday 7:00pm9:00pm (location TBA)
 Note that we have swapped the dates of the regular and midterm exam, because of students' preferences.
If you want to take the exam at the original Monday time slot, just fill in
conflict midterm 2 request form before Apr 2 Tuesday 1pm,
and we will automatically give you permission (you don't need to provide any reason, though you must fill in the form).
Note that the two versions of the exam will be different.
 DRES accommodations:
If you have sent us your DRES accommodation letter at the beginning of the semester,
you should schedule your exam at the DRES TAC (like you have done before for midterm 1) about
a week in advance, and you should pick a time on Apr 9 Tuesday. Let Timothy know if there are issues.
 Instructions: Similar to midterm 1.
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, until all versions of the exams have been completed. 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 of material: Lectures (and labs) from week 610; see midterm 2 skillset (greedy will not be covered)
 Practice problems:
Final Exam
 exam solutions (and conflict exam solutions)
 Date and time:: May 9 Thursday 7:00pm10:00pm
 Location: Foellinger Auditorium
 Instructions:
Similar to the midterms (except for the longer 3hour length, and for two doublesided cheat sheets instead of one).
Except for the cheat sheets, the exams are closedeverything.
Please read the final exam cover page (or the conflict cover page or the DRES cover page).
 Cheat sheets: you may bring two doublesided 8.5" x 11" sheets of paper with anything you like written on both sides, with your name and NetID written on the upper right corner. (Four 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 sheets before the exam. (Note: We will provide this list of useful known NPcomplete problems in the exam, as you can see in the above cover page.)
 All exams are strictly confidential for at least 24 hours, until all conflict exams have been completed. 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 of material: everything (it's a cumulative exam!); see final exam skillset for more details
 Practice problems:
 Conflict final: Conflict final exams will be offered only for one of the official reasons stated in the student code (namely, (i) another final exam scheduled at the same time, (ii) three consecutive final exams in a 24hour period, (iii) national or state professional examinations, (iv) illness or other extenuating circumstances, or (v) religious accommodations). To get permission, you must fill in this form before Apr 29 Monday 2pm. The date of the conflict exam will be May 10 Friday, and the time will be decided after the forms are received.
 DRES accommodations: if you have sent us your DRES accommodation letter at the beginning of the semester, you should schedule your exam at the DRES TAC (like you have done before for the midterms), and you must pick a time on
May 10 Friday. Let Timothy know if there are issues. The TAC requires you to schedule your final exam at least a week in advance.
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.