CS 473 Algorithms, Fall 2016

Lectures: Wed & Fri 9:30am to 10:45am in 1310 DCL

Office Hours:

All office hours will be held in 3201 Siebel (the open area near the stairs).

• Mon 11.15-12.15: Shalmoli
• Mon 15.00-16.00: Ruta
• Tues 14.00-15.00: Patrick
• Fri 15.30-16.30: Chandra

Schedule, lecture notes, and lecture videos

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
• Matchings
• Basics of linear and convex programming
• NP-Completeness and reductions
• Basics of approximation and online algorithms

Announcements

• Homework 11 is NOT due, but material covered by this homework may appear on the final exam. Solutions will be released on Tuesday, December 6th. The LaTeX source.

• Homework 10 is due on Wednesday, November 30th. The LaTeX source.

• Homework 9 is due on Tuesday, November 15th. The LaTeX source.

• Homework 8 is due on Tuesday, November 1st. The LaTeX source, and file for the figure: monotone-paths.pdf. This is the last homework before Midterm 2.

• Homework 7 is due on Tuesday, October 25th. The LaTeX source.

• Homework 6 is due on Tuesday, October 18th. The LaTeX source.

• Homework 5 is due on Tuesday, October 11th. The LaTeX source, and necessary style file for compilation: algo.sty.

• Homework 4 is due on Tuesday, September 27th. The LaTeX source. This is the last homework before Midterm 1.

• Homework 3 is due on Tuesday, September 20th. The LaTeX source.

• Brush up on basics of randomization before the next lecture (September 14th). Here are relevant slides.

• Homework 2 is due on Tuesday, September 13th. The LaTeX source.

• Homework 1 is due on Tuesday, September 6th. The LaTeX source. A rubric for dynamic programming problems is available.

• Homework 0 is due on Tuesday, August 30th on Gradescope by 8pm.
  • Please read the course policies on homework, grading, and especially academic integrity.
  • LaTeX source
  • You may find Jeff Erickson's notes on induction and solving recurrences useful.

• 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 9E2PZM. 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. You are also not required to be registered for the class (or even a student at Illinois) before you sign up.

  To give you credit for the homework, we need to know who Gradescope thinks you are. There is 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.