CS 473 Algorithms, Spring 2018
Lectures: Tue & Thu 5:00 pm to 6:15 pm in 0216 Siebel Center
- Teaching assistants:
- Office Hours:
- All office hours will be held in the theory lounge,
Siebel Center, 3rd floor (open lounge area
between Siebel 3304 and 3232).
- Mon 3pm - 4pm : Shant
- Wed 4pm - 5pm : Ruta
- Fri 11am - 12pm : Vasilis
- Piazza for announcements and discussion
- Gradescope for HW submissions
(self-enrollment code: 9747W2)
- Moodle for grades
- Important Dates
- Midterm 1: Feb 26, 2018, 7pm - 9pm. Venue: 1320 DCL
- Midterm 2: Apr 9, 2018, 7pm - 9pm. Venue: 1320 DCL
- Final Exam: May 11, 2018, 7pm - 10pm.
- Course topics:
- Below is a list of high-level topics that we hope to cover. This list is tentative.
- Divide and conquer, FFT
- (Advanced) Dynamic Programming
- Shortest path algorithms and negative cycle detection
- Randomization in algorithms and data structures
- Network flows and applications
- Basics of linear and convex programming
- NP-Completeness and reductions
- Basics of approximation and online algorithms
Homework 7 (tex) is due on Wednesday, March 28th on Gradescope by 8pm.
Homework 6 (tex, algo.sty) is due on Wednesday, March 14th on Gradescope by 8pm.
Homework 5 (tex) is due on Wednesday, March 7th on Gradescope by 8pm.
No Lecture on Tuesday, February 27, 2018.
Midterm 1 will be held next Monday, February 26, from 7pm to 9pm at 1320 DCL.
- The exam will cover everything covered in Homeworks 0 through 4, including prerequisite material. The best source of study materials are the slides, notes, and practice exam papers posted on Piazza. The exam will be significantly easier than the homework.
- You may state and use (without proof or justification) any results proved in class or in the homework unless we explicitly ask you for one.
- You are allowed to bring one hand-written double sided 8.5" x 5.5" (half letter size page) cheat sheet. Otherwise, the exam is closed-everything, e.g., books, calculator, phone, etc.
Homework 4 (tex) is due on Wednesday, February 21st on Gradescope by 8pm. This is the last homework before Midterm 1.
Homework 3 (tex) is due on Wednesday, February 14th on Gradescope by 8pm.
Homework 2 (tex) is due on Wednesday, February 7th on Gradescope by 8pm.
- The solutions to this homework have been uploaded on Moodle.
Homework 1 (tex) is due on Wednesday, January 31th on Gradescope by 8pm.
Homework 0 is due on Wednesday, January 24th on Gradescope by 8pm.
All homework will be submitted and graded electronically via Gradescope. Please enroll yourself on our Gradescope page as soon as possible, using the access code 9747W2. You are not required to sign up using your illinois.edu email address or even your real name; you may use any email address and alias you like.
To give you credit for the homework, we need to know who Gradescope thinks you are. There will be a web form to tell us your Gradescope identity on Moodle.
Welcome! We're working hard to get everything set up here before the semester begins. Meanwhile, you may notice a few broken links or references to previous courses. Stay tuned!
If you are graduate student in CS or a related area: You're in the right place. This class satisfies all degree requirements and program of study requirements for either CS 473 and CS 573.
Course webpages are borrowed extensively (with gratitude and permission) from Jeff Erickson's Fall 2010 version of CS 573 and Spring 2016 version of CS 473.