Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Luca Trevisan & Prasad Raghavendra, Spring 2019

Lecture: Tu/Th 3:30-5:00 pm, 1 Pimentel

Week 9: Announcements

3/17 - 3/23 • piazza @557
  • Assignments
    • Homework 9 was released yesterday. It is due April 1st at 10:00pm (the Monday after spring break). It covers material from lectures 14 and 15.
      • Homework 9 is of normal length, as we do not expect you to have to work on it over break.
    • Homework 10 will be optional and will contain problems on midterm content. We recommend that you do it, but will not be grading the assignment this time.
      • It will be released as soon as we have it ready, but by Monday after spring break at the latest
    • Homework 8 scores will be released March 25th. Solutions will be posted on the website shortly
    • Homework 7 grades have been released. Distribution here. You have till April 1st to submit regrade requests.
    • Homework 5 regrade requests should have all been responded to
  • Midterm 2
    • Midterm 2 will take place on April 3rd from 8-10pm (note that this is a Wednesday and not a Tuesday)
      • There will be an exam logistics post with more details later this week
    • We will be holding two review sessions for this midterm
      • There will be one on April 1st, and one on April 2nd
      • More details will be released in a separate post
  • Project
    • The course project will start after the second midterm. Homework load will be adjusted accordingly for the duration of the project.
      • The project will involve groups of size 1-3 (though we strongly recommend you work in a group with at least one other person)
      • For now, you need not do anything else to prepare

Week 9: Course Materials

Lec 16

Linear Programming

Lec 17

Linear Programming