CS/ECE 374 A (Spring 2022):
Introduction to Algorithms & Models of Computation

Important links

• Lecture and lab schedule
• Homeworks
• Exams
• Policies: HW policies, Academic integrity, Grading, Culture
• Gradescope (entry code ERKJXG)
• Piazza (for Q&A and all announcements, and for contacting course staff (via private notes))
• These are the web pages for Section A of the course taught by Timothy Chan and Ruta Mehta. (Section B is independently taught by Nickvash Kani and has a separate web site.)

Course staff

Meeting time/place/zoom links

There are two lectures per week, and two lab/discussion sessions per week. The first week of lectures and labs was entirely online via zoom. Afterwards (from Jan 25 onward), we will have lectures given in-person in ECE Building 1002 and live-streamed on zoom (see below for the zoom link). For the labs, two sections will be online (see below for the zoom links) and the rest are in-person in Siebel 1105.

Lectures will be recorded and made available on the "CS/ECE 374 A Spring 2022" channel in mediaspace to registered students. Some of the lab recordings can be found on the "CS/ECE 374 A Labs Spring 2022" channel in mediaspace.

AL1 Lecture	TR 11:00am-12:15pm	ECE 1002	Ruta Mehta	zoom link
AYA Discussion	WF 9:00am-9:50am	online	Stav Ashur	zoom link
AYB Discussion	WF 10:00am-10:50am	SC 1105	Rhea Jain
AYD Discussion	WF 11:00am-11:50am	SC 1105	Vasilis Livanos / Rucha Kulkarni	zoom link
AYE Discussion	WF 12:00pm-12:50pm	SC 1105	David Zheng
AYF Discussion	WF 1:00pm-1:50pm	SC 1105	James Hulett
AYC Discussion	WF 2:00pm-2:50pm	SC 1105	James Hulett
AYG Discussion	WF 3:00pm-3:50pm	SC 1105	Eliot Robson
AYH Discussion	WF 4:00pm-4:50pm	online	Qizheng He	zoom link
AYJ Discussion	WF 5:00pm-5:50pm	SC 1105	Daniel Christl

Office hours

Office hours will be held entirely online, using zoom (this is the zoom link for all office hours), Discord (invite link), and Queue@illinois.edu.

Monday	Tuesday	Wednesday	Thursday	Friday
Stav: 1:00-2:00 Daniel: 4:00-5:00	Eliot: 3:00-4:00 Qizheng: 4:00-5:00	James: 10:00-11:00 Rhea: 11:00-12:00 Ruta: 2:30-3:30 Timothy: 3:30-4:30	Ruta: 1:00-2:00 (**)	David: 2:00-3:00

New (**): starting after spring break, Ruta will hold "conceptual" office hours on Thursdays 1:00-2:00 (these are for questions about lectures and/or notes and other references, but not about HWs).

Homeworks

All guided problem sets ("GPS") 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 read the homework policies and academic integrity page!

• GPS1 (due Jan 25), HW1 [.tex] (due Jan 27) [solutions]
• GPS2 (due Feb 1), HW2 [.tex] (due Feb 3) [solutions]
• GPS3 (due Feb 8), HW3 [.tex] (footnote added 2/7) (due Feb 10) [solutions]
• GPS4 (due Feb 15), HW4 [.tex] (due Feb 17) [solutions]
• GPS5 (due Mar 1), HW5 [.tex] (footnote added 2/24) (due Mar 3) [solutions]
• GPS6 (due Mar 8), HW6 [.tex] (footnote added 3/6) (due Mar 10) [solutions]
• GPS7 (due Mar 22), HW7 [.tex] (footnotes added 3/21) (due Mar 24) [solutions]
• GPS8 (due Mar 29), HW8 [.tex] (due Mar 31) [solutions]
• GPS9 (due Apr 5), HW9 [.tex] (due Apr 7) [solutions]
• HW10 [.tex] (due Apr 21) (note: this HW has 3 problems, since there is no GPS this week; footnotes added on 4/19) [solutions]
• GPS10 (due Apr 26 May 3), HW11 [.tex] (due Apr 28) [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, Past HW8, Past HW9, Past HW10, Past HW11, Past HW12

Midterm 1

• exam and solutions (conflict exam and solutions)
• Date and time: Feb 21 Monday 7:00pm-9:30pm Central Time (exams will be held online with zoom proctoring)
• Instructions: Please read Midterm 1 Logistics carefully for all the details (zoom links)
• Dry run: as announced on piazza, remember to try out the "Dry Run" before Sunday 10pm, to make sure that you have your scanning app set up prior to the exam and are comfortable submitting to Gradescope.
• Coverage of material: Lectures (and labs) from week 1-4; see midterm 1 skillset
• Practice problems:
  • a (long) list of study problems (we don't distribute solutions, but will go over selected problems during the review sessions in class and the labs)
  • Past midterm 1 from Spring 2019, with solutions
  • Other past midterms from Fall 2021, Spring 2021 (with solutions), Fall 2019, Fall 2018, Fall 2017, etc. (we don't distribute official solutions to these)
• Conflict midterm 1: Feb 22 Tuesday 7:00pm-9:30pm Central Time. Conflict exams will be offered only if you have a valid reason. To get permission, you must fill in this form to request for conflict midterm 1 no later than Feb 16 Wednesday.
• DRES accommodations: if you have sent us your DRES accommodation letter at the beginning of the semester, you should already have been contacted by us about your exam arrangement. If not, please email Timothy (tmc) no later than Feb 16.

Midterm 2

• exam and solutions (conflict exam and solutions)
• Date and time: Apr 11 Monday 7:00pm-9:30pm Central Time (exams will be held online with zoom proctoring)
• Instructions: Please read Midterm 2 Logistics carefully for all the details (they are similar to Midterm 1) [here are midterm 2's zoom links]
• Coverage of material: Lectures (and labs) from week 6-10; see midterm 2 skillset (greedy will not be covered)
• Practice problems:
  • a list of study problems (we don't distribute solutions, but will go over selected problems during the review sessions in class and the labs)
  • Past midterm 2 from Spring 2019, with solutions
  • Other past midterms from Fall 2021, Fall 2019, Fall 2017, etc. (we don't distribute official solutions to these)
• Conflict midterm 2: Apr 12 Tuesday 7:00pm-9:30pm Central Time. Conflict exams will be offered only if you have a valid reason. To get permission, you must fill in this form to request for conflict midterm 2 no later than Apr 6 Wednesday (the form has been activated now).
• DRES accommodations: if you have sent us your DRES accommodation letter at the beginning of the semester, you should already have been contacted by us about your exam arrangement. If not, please email Timothy (tmc) no later than Apr 6.

Final exam

• exam and solutions (conflict exam and solutions)
• Date and time: May 12 Thursday 8:00am-11:00am Central Time (exams will be held online with zoom proctoring)
• Instructions: Please read Final Exam Logistics carefully for all the details (they are similar to the midterms, except that the length is 2 hrs and 30 mins, plus 30 mins for scanning/uploading; and two double-sided cheat sheets are allowed) [here are the final exam's zoom links]
• Coverage of material: everything! (it's a cumulative exam); see final exam skillset for more details
• Practice problems:
  • a list of practice problems (from Fall 2019)
  • Past final from Spring 2019, with solutions
  • Other past finals from Fall 2021, Fall 2019, Spring 2018, Fall 2016, etc. (we don't distribute official solutions to these)
• 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 24-hour 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 by Apr 29 Friday. The date/time of the conflict exam 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 have already been contacted by us about your exam arrangement. If not, please email Timothy (tmc).

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 context-free languages, finite-state automata, recursive algorithms (including divide and conquer, backtracking, dynamic programming, and greedy algorithms), fundamental graph algorithms (including depth- and breadth-first search, topological sorting, minimum spanning trees, and shortest paths), undecidability, and NP-completeness.

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. Here are some other useful resources (also see here for more):

• some past offerings of CS/ECE 374: Fall 2021 (Dakshita Khurana and Jeff Erickson), Spring 2021 (Chandra Chekuri, Patrick Lin, Nickvash Kani, and Yi Lu), Fall 2020 (Sariel Har-Peled, Andrew Miller, and Nickvash Kani), Spring 2020 (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 NP-completeness, e.g., by Hopcroft, Motwani, and Ullman and Sipser

Website generously borrowed from those of previous semesters.