CS 473 Algorithms, Spring 2018

Lectures: Tue & Thu 5:00 pm to 6:15 pm in 0216 Siebel Center

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

• Practice Homework. Not to be submitted, but the material covered is relevant for the final exam.

• Homework 11 (tex) is due on Wednesday, May 2nd on Gradescope by 8pm.

• Homework 10 (tex) is due on Wednesday, April 25th on Gradescope by 8pm.

• Homework 9 (tex) is due on Wednesday, April 18th on Gradescope by 8pm.

• Homework 8 (tex) is due on Wednesday, April 4th on Gradescope by 8pm. This is the last homework before Midterm 2.

• 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.

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

• 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.

  • A rubric for dynamic programming problems is available.
  • The solutions to this homework have been uploaded on Moodle.

• Homework 0 is due on Wednesday, January 24th on Gradescope by 8pm.

  • Please read the course policies on homework, grading, and especially academic integrity.
  • You may find Jeff Erickson's notes on induction and solving recurrences useful.
  • Here you can find a LaTeX template for your solutions to the homeworks.
  • The solutions to this homework have been uploaded on Moodle.

• 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.