CS 473 Algorithms, Spring 2021

Lectures: Tue, Thu, 11am-12:15pm, on Zoom

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 (.tex source) is due on Wednesday, May 28th on Gradescope by 8pm.

• Homework 10 (.tex source) is due on Wednesday, May 5th on Gradescope by 8pm.

• Homework 9 (.tex source) is due on Wednesday, April 21st on Gradescope by 8pm.

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

• The Midterm 2 is on Monday, April 12th from 7-9pm online + 1 hour upload time. The logistics+instructions are the same as that for midterm 1. HW8 will be the last homework before midterm 2. HW9 will be released after the midterm.

• Homework 7 (.tex source) is due on Wednesday, March 31st on Gradescope by 8pm.

• Homework 6 (.tex source) is due on Thursday, March 25th on Gradescope by 8pm. The extension is because Wednesday, March 24th is a non instructional day. All further homeworks will be due on Wednesdays.

• The final exam will take place on Monday, May 10th, from 7pm til 10pm. More details will be given closer to the exam.

• Homework 5 (.tex source) is due on Thursday, March 18th on Gradescope by 8pm. Also, we will consider the best two out of three questions for HW 5 when calculating the final grade.

• No Lecture on Tuesday, March 9, 2021.

• Midterm 1 will be held next Monday, March 8, from 7pm to 10pm online.

  • The question paper will be emailed to your netid at 6:59pm, and you are expected to stop by 9pm. 9pm to 10pm is for scanning + uploading. We will answer questions through Piazza/email -- Piazza is preferable due to coordination issues. From 7pm to 9pm on March 8, only private posts will be allowed on Piazza to ask questions.
  • 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 use 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. If you choose to use one, then we expect you to upload it as well.

• Homework 4 (.tex source) is due on Wednesday, March 3rd on Gradescope by 8pm. This is the last homework before Midterm 1.

• Homework 3 (.tex source) is due on Wednesday, February 24th on Gradescope by 8pm.

• Homework 2 (.tex source) is due on Thursday, February 18th on Gradescope by 8pm. HW1 solutions have been posted.

• Homework 1 (.tex source) is due on Wednesday, February 10th on Gradescope by 8pm.

• Homework 0 solutions have been posted. All homework solutions will be in the password-protected homework-solutions page.

• Homework 0 (.tex source) is due on Wednesday, February 3rd 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.

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

• However, to give you credit for the homework, we need to know who Gradescope thinks you are. Please send an email to the course staff informing us of your Gradescope identity if you have not used your UIUC email, or if your name on Gradescope does not match the name we have for you on our records. 

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

Stressed?

Diminished mental health, including significant stress, mood changes, excessive worry, substance/alcohol abuse, or problems with eating and/or sleeping can interfere with optimal academic performance, social development, and emotional wellbeing. The University of Illinois offers a variety of confidential services including individual and group counseling, crisis intervention, psychiatric services, and specialized screenings at no additional cost. If you or someone you know experiences any of the above mental health concerns, it is strongly encouraged to contact or visit any of the University’s resources provided below. Getting help is a smart and courageous thing to do -- for yourself and for those who care about you.

Counseling Center: 217-333-3704, 610 East John Street Champaign, IL 61820

McKinley Health Center:217-333-2700, 1109 South Lincoln Avenue, Urbana, Illinois 61801

Course webpages are borrowed extensively (with gratitude and permission) from Jeff Erickson's Fall 2010 version of CS 573 and Spring 2016 and 2018 version of CS 473.