CS/ECE 374 A (Spring 2024) (2024)

Introduction to Algorithms & Models of Computation

• Lecture and Lab Schedule
• Homeworks
• Exams
• Policies: HW Policies, Academic Integrity, Grading, Culture
• Gradescope (entry code: NPNDP5)
• Ed (for Q&A and all announcements, and for contacting course staff)
• Discord
• These are the web pages for Section A of the course taught by Timothy Chan and Ruta Mehta.

Course Staff

We are also grateful to the TheorieLearn team for developingmaterials 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.

Office Hours

Most office hours, except those with pre-booked rooms, will be held in the open lounge area on the 3rd floor of Siebel (outside of 3240) the open area in the Siebel basem*nt outside of 0218 (the change will hopefully alleviate issues with overcrowding). Wednesday office hours from 12:00-2:50 will be in Siebel 0218.Saturday sessions, in DCL 1320, are meant to be "homework parties", where students can work togetherand 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).

Homeworks

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 NP-completeness proofs and Past HW11 (and a list of useful known NP-complete problems)

Midterm 1

• exam and solutions (conflict exam and solutions)
• Date and time: Feb 19 Monday 7:00pm-9:00pm
• Instructions: Please read the midterm 1 cover page.Except for the cheat sheets (see below), exams are closed-everything. In particular: No medically unnecessarily electronic devices are allowed in exams, including smart watches and headphones/earbuds.
• Cheat sheets: You may bring one double-sided 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 single-sided 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 1-4; seemidterm 1 skillset for more details.
• 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 lab)
  • Old midterm 1 from Spring 2019, with solutions (note: we don't allow IDKs this semester)
  • Other past midterms fromFall 2023,Fall 2022, Fall 2018,etc.(we don't distribute official solutions to these)
• Conflict midterm 1: Feb 20 Tuesday 7pm-9pm. 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 aboutscheduling 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:00pm-9:00pm
• Location:
  • for students with last names starting with A-J: Noyes Laboratory 100
  • for students with last names starting with K-Q: Materials Science & Engineering Building 100
  • for students with last names starting with R-Z: Loomis Laboratory of Physics 141
• Conflict midterm 2: Apr 8 Monday 7:00pm-9: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) abouta 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 closed-everything. In particular: No medically unnecessarily electronic devices are allowed in exams, including smart watches and headphones/earbuds.
• Cheat sheets: You may bring one double-sided 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 single-sided 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 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 2023, Fall 2022, Fall 2021, Fall 2019, Fall 2017, etc. (we don't distribute official solutions to these)

Final Exam

• exam solutions (and conflict exam solutions)
• Date and time:: May 9 Thursday 7:00pm-10:00pm
• Location: Foellinger Auditorium
• Instructions: Similar to the midterms (except for the longer 3-hour length, and for two double-sided cheat sheets instead of one). Except for the cheat sheets, the exams are closed-everything.Please read the final exam cover page (or the conflict cover page or the DRES cover page).
• Cheat sheets: you may bring two double-sided 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 single-sided 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 NP-complete 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:
  • a list of practice problems
  • Past final from Spring 2022, with solutions
  • Past final from Spring 2019, with solutions
  • Other past finals from Fall 2023,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 circ*mstances, 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 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. Other useful resources (see also here):

• some past offerings of CS/ECE 374: Fall 2023 (Jeff Erickson), Spring 2023 (Chandra Chekuri), Fall 2022 (Sariel Har-Peled), 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 NP-completeness, e.g., by Hopcroft, Motwani, and Ullman and Sipser

Website generously borrowed from those of previous semesters.