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

Important links

• Links to zoom meetings for lectures, labs, and office hours (we are moving to online instruction after spring break!)
• Lecture and lab schedule (and lecture videos)
• Homeworks
• Exams
• Policies: HW policies; Academic integrity; Grading
• Gradescope (entry code M6722X)
• 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 Andrew Miller and Haitham Hassanieh and has a separate web site.)

Course staff

Meeting time/place

There are two lectures per week, and two lab (discussion) sessions per week. The students are strongly encouraged to attend all sessions of their assigned lab sections.

AL1 Lecture	TR 11:00am-12:15pm	ECE 1002	Ruta Mehta
AYA Discussion	TR 12:30-1:20pm	SC 1105	Vasilis Livanos
AYB Discussion	TR 1:30-2:20pm	SC 1105	Vasilis Livanos
AYC Discussion	WF 2:00-2:50pm	SC 1105	Aditya Shankar Narayanan
AYD Discussion	TR 2:30-3:20pm	SC 1105	Zhiqian Zhou
AYE Discussion	TR 3:30-4:20pm	SC 1105	Ching-Hua Yu
AYF Discussion	TR 4:30-5:20pm	SC 1105	Ching-Hua Yu
AYG Discussion	TR 5:30-6:20pm	SC 1105	Shiliang Zuo
AYH Discussion	TR 6:30-7:20pm	SC 1105	Iris Sun
AYJ Discussion	WF 10:00-10:50am	SC 1105	Rucha Kulkarni
AYK Discussion	WF 11:00-11:50am	SC 1105	Pooja Kulkarni

Office hours

All office hours except the Wednesday ones will be in the open area on the 3rd floor of Siebel (outside of 3240). Wednesday office hours will be in Siebel 0216. (Occasional changes will be announced on piazza.)

Monday	Tuesday	Wednesday	Thursday	Friday
Pooja: 1-2pm Rucha: 2-3pm	Zhiqian: 1-2pm Vasilis: 3-4pm Shiliang: 4:30-5:30pm Ching-Hua: 5:30-6:30pm	Aditya: 12:30-1:30pm (Siebel 0216) Ruta: 3:30-4:30pm (Siebel 0216) Timothy: 4:30-5:30 pm (Siebel 0216)	none	Iris: 2-3pm

Homeworks

All homeworks are due Thursday at 10:00am. We will post each week's homework at least 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!

• HW1 [.tex] (due Jan 30) [solutions]
• HW2 [.tex] (due Feb 6) [solutions]
• HW3 [.tex] (due Feb 13) [solutions]
• HW4 [.tex] (due Feb 20) [solutions]
• HW5 [.tex] (due Mar 5) [solutions (revised 3/14)]
• HW6 [.tex] (due Mar 12) [solutions]
• HW7 [.tex] (due Mar 26) [solutions]
• HW8 [.tex] (due Apr 2) [solutions]
• HW9 [.tex] (due Apr 9) (revised 4/3 and 4/4) [solutions]
• HW10 [.tex] (corrected 4/20) (due Apr 23) [solutions]
• HW11 [.tex] (due Apr 30) [solutions]

Here are some selected old HW problems with solutions that you may find useful (both as extra practice problems, and as examples on how to write solutions):

• Old HW1, Old HW2, Old HW3, Old HW4, Old HW5, Old HW6, Old HW7, Old HW8, Old HW9, Old HW10, Old HW11

Midterm 1

• solutions
• Time and place: Feb 24 Monday 7pm-9pm, at Foellinger Auditorium
• Coverage of material: Lectures (and labs) from week 1-4; see midterm 1 skillset for more details
• Instructions: please read the midterm 1 cover page; in particular, note the following:
  • You may bring one double-sided 8.5" x 11" cheat sheet, with your name and NetID written on the upper right corner. The sheet should be handwritten by you (not photocopied or printed). We will 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.
  • Unlike homeworks (and some past exams), "I don't know" (IDK) will NOT receive any credit in exams.
• 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
  • Other past midterms from Fall 2019, Fall 2018, Fall 2017, etc. (we don't distribute official solutions to these)
• Conflict midterm 1: Feb 26 Wednesday 7pm-9pm, at DCL 1310. This will be a different exam. Conflict exams will be offered only if you have a valid excuse (scheduling a job interview is normally not a valid excuse). To get permission, you must fill in this form to request for conflict midterm 1 no later than Feb 19 Wednesday.
• DRES accommodations: Students requiring such accommodations should first discuss their needs with DRES, and then give the instructor the DRES accommodation letter at least one week before the first midterm. We strongly prefer that students who require accommodations schedule their exams at DRES. Please do not attempt to schedule exams at DRES at the last minute; they normally require reservations one week in advance for midterms, and two weeks in advance for final exams. The scheduled time should be within a day or so from the regular exam time and should be after the regular exam time (not before).

Midterm 2

• solutions (revised 4/20)
• Time: Apr 13 Monday 7pm-10pm (Central Time)
• Coverage of material: Lectures (and labs) from week 6-10; see midterm 2 skillset for more details
• Instructions:
  • The exam will be open-book.
  • We will send you by email (using your official university email address) a link to the PDF of the exam at Apr 13 Monday 7:00pm Central Time. In the same email, you will also receive a link to a Google doc where you can read announcements (if there are any) during the exam.
  • You will write your solutions on paper (so, bring blank papers before the exam). At the completion of the exam, scan or take pictures of your solutions and upload your PDF to Gradescope (so you will need access to a scanner or a smartphone that can take decent-quality photos), and submit before Apr 13 Monday 10:00pm Central Time. (You do not need to submit scratch papers.) Note that the exam duration has already been extended from 2 hours to 3 hours to account for the time for scanning, uploading, and computer-related issues. So, don't scan and upload at the last minute! We will not accept submissions after 10:00pm unless there are truly extraordinary circumstances (and even so, we may apply a penalty however we deem appropriate). With Gradescope, you may resubmit multiple times before the 10:00pm deadline.
  • If you want to write on your tablet or type your solution in LaTeX instead of writing on paper, this is still acceptable, provided that the submitted file is a PDF and can be read clearly. However, we are not responsible if you accidentally lose your file due to computer problems during the exam (so save it often!).
  • If you have questions during the exam, you may post a "private note" on piazza and the course staff will try to respond in a timely fashion. Do not post public messages on piazza during the exam! Some time after the exam is over, we will close piazza and reopen on Tuesday evening (we may reopen during the conflict exam, again just for "private note").
  • If you believe the statement of an exam problem is incomplete or has errors, regardless of whether you are able to get clarification on piazza or from the Google doc during the exam, we recommend that you state your assumptions clearly and solve the problem accordingly. In case of a genuine error, grading rubrics will be adjusted appropriately.
  • You are reminded about the course's, the college's, and the university's academic integrity policies.
  • Do not communicate with other students during the exam. Do not communicate with other people about the content of the exam. Never copy from other people's work or show your work to other students. (We may look for similarities to check for plagiarism.) Give proper citation if you have used other sources (e.g., from the internet) outside of the course slides/notes and Jeff's book. (Although the exam is open-book, we think that it would be a waste to search the internet.)
  • Unlike homeworks, "I don't know" (IDK) will NOT receive any credit in exams. (Reasonable progress toward a correct solution will receive partial credit, so you should attempt to solve all problems if you can.)
  • Avoid the deadly sins. Write complete solutions, not examples. Declare all your variables. Write concisely and precisely.
  • We will set up a "dry run" on gradescope a few days before the exam, so that you can practice scanning and submitting the exam, if you want. But the process is basically the same as submitting a homework.
• Conflict midterm 2: Apr 14 Tuesday 7am-10am (Central Time). This will be a different exam. Conflict exams will be offered only if you have a valid excuse (for example, if you are residing in a place with a large time zone difference). To get permission, you must fill in this form to request for conflict midterm 2 no later than Apr 8 Wednesday.
• 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 lab)
  • Old midterm 2 from Spring 2019, with solutions
  • Other past midterms from Fall 2019, Fall 2017, etc.
• DRES accommodations: please email one of the instructors (tmc) no later than Apr 8 Wednesday.

Final exam

• solutions
• Time: May 8 Friday 7pm-11pm (Central Time)
• Coverage of material: everything! (it's a cumulative exam); see final exam skillset for more details
• All students are required to take the final exam, if you don't want to receive an "ABS", according to the university policies (see paragraph b2 of student code 3-201).
• Instructions:
  • (These are similar to midterm 2, but there are some differences, e.g., no Google doc this time and a stricter late penalty policy...)
  • The exam will be open-book.
  • We will send you by email (using your official university email address) a link to the PDF of the exam at May 8 Friday 7:00pm Central Time.
  • You will write your solutions on paper, scan or take pictures of your solutions (so you will need access to a scanner or a smartphone that can take decent-quality photos), and submit your PDF to Gradescope under an assignment named "Final Exam", before May 8 Friday 11:00pm Central Time. (You do not need to submit scratch papers.)
  • Note that the exam duration has already been extended from 3 hours to 4 hours to account for the time for scanning, uploading, and computer-related issues. With Gradescope, you may submit your solutions to different problems at different times during the exam, and you may resubmit multiple times before the 11:00pm deadline. So, don't wait till the last minute to scan and upload! We highly encourage you to submit a complete version at least 20 minutes before the deadline, to avoid potential computer-related issues near the deadline.
  • We will apply the following late penalty: -1 point per minute. (E.g., if your submission is received at 11:08pm, you will lose 8/100.) We will grade your last submitted file, and apply the penalty based on the time of this last submission (we will not grant request to "revert" to an earlier version). Gradescope will stop accepting submissions at 11:15pm.
  • If you want to write on your tablet or type your solution in LaTeX instead of writing on paper, this is still acceptable, provided that the submitted file is a PDF and can be read clearly. However, we are not responsible if you accidentally lose your files due to computer problems during the exam (so save often!).
  • If there are any major announcements during the exam, e.g., about errors and corrections (which will be rare), we will send you a message by email. So, please check your email once in a while.
  • If you have questions during the exam, you may post a "private note" on piazza and the course staff will try to respond in a timely fashion. Do not post public messages on piazza during the exam! We will only answer technical questions during the first one and a half hour of the exam (from 7:00pm to 8:30pm). Some time after the exam, we will temporarily close piazza (and reopen after the conflict exam).
  • If you believe the statement of an exam problem is incomplete or has errors, regardless of whether you are able to get clarification on piazza during the exam, we recommend that you state your assumptions clearly and solve the problem accordingly. In case of a genuine error, grading rubrics will be adjusted appropriately.
  • You are reminded about the course's, the college's, and the university's academic integrity policies.
  • Do not communicate with other students during the exam. Do not communicate with other people about the content of the exam. Never copy from other people's work or show your work to other students. (We may look for similarities to check for plagiarism.) Give proper citation if you have used other sources (e.g., from the internet) outside of the course slides/notes and Jeff's book. (Although the exam is open-book, we think that it would be a waste to search the internet.)
  • Unlike homeworks, "I don't know" (IDK) will NOT receive any credit in exams. (Reasonable progress toward a correct solution will receive partial credit, so you should attempt to solve all problems if you can.)
  • Avoid the deadly sins. Write complete solutions, not examples. Declare all your variables. Write concisely and precisely.
• Practice problems:
  • a list of study problems (from Fall 2019)
  • Old final exam from Spring 2019, with solutions
  • Other past final exams from Fall 2019, Spring 2018, Fall 2016, etc. (we don't distribute official solutions to these)
• Conflict exam: May 9 Saturday 9am-1pm (Central Time). This will be a different exam. Conflict exams will be offered only if you have a valid excuse (for example, if you are residing in a place with a large time zone difference). To get permission, you must fill in this form to request for conflict final exam no later than May 5 Tuesday.
• DRES accommodations: We will contact those students who have previously requested DRES accommodations with the details.

About this course

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. Slides can be found in the lecture schedule page. Here are some other useful resources (also see here for more):

• past offerings of CS/ECE 374: Fall 2018 (Chandra Chekuri and Nikita Borisov), Spring 2019 (Timothy Chan, Sariel Har-Peled, and Haitham Hassanieh), Fall 2019 (Jeff Erickson and Nikita Borisov)
• 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