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 4: Announcements

2/10 - 2/16 • piazza @274
  • Midterm 1 will be this Thursday, February 14th at 8-10pm.
    • You must take the exam in the room you been assigned to in this spreadsheet. Go to the room indicated based on the last 2 digits of your SID.
    • DSP students should have gotten an email a few minutes ago. If not, email cs170@berkeley.edu.
    • What you can/should bring to the exam:
      • You are allowed one cheat sheet. It can be at most two sides of one sheet of paper, and it can be handwritten or typed.
      • Student ID
      • Pencils and erasers
      • Water and your knawledge :)
    • All topics covered in lecture, discussion, homework, and the textbook chapters listed on the website up to and including Dijkstra’s are in scope for this exam
  • Review Sessions: We have two review sessions planned from 8-10pm in 2050 VLSB:
    • Review Session 1 (Feb 11): Asymptotics, Recurrences, Divide and Conquer, FFT. Piazza post here.
    • Review Session 2 (Feb 13): Graphs, BFS, DFS, Graph Decomposition, and Shortest Paths. Piazza post upcoming.
  • Discussions: Tarun’s section will be held in Soda 310 Wednesdays 12-1pm for the rest of the semester. Apologies for the confusion!
  • Assignments
    • Homework 4 has been released today. It is completely optional and is not worth any credit, but we strongly recommend you do it as practice for the midterm this week.
      • Solutions will be posted Wednesday to give you time to work on it.
      • We will even “grade” your homework on Gradescope to let you know what you did right (but again, the grade on Gradescope will not contain any points as the homework is not worth any credit).
        • This will only happen after the midterm, however
    • The next homework, Homework 5, will be graded and back to normal, and will cover material from lectures 5, 6, and 7.
    • Homework 3 grades will be released Monday, February 18.
    • Homework 2 grades have been released. A distribution has been included here.
      • You will have until Monday, Feb 18 to submit regrade requests
      • These requests will be processed a week after this deadline (Monday, Feb 25)
      • Please be sure to read solutions fully before submitting any regrade requests
  • Office Hours and Homework Party will be cancelled on Friday as we grade for the midterm.
  • Logistics: We have resolved most alternate exam requests and DSP accommodations by email. The exam conflict form and DSP accommodation forms are now closed. If anything comes up during the semester, please email cs170@berkeley.edu.
    • If you are still awaiting an email from us please bump us ASAP so we do not forget

Week 4: Course Materials

Lec 7

Greedy Algorithms, MST

Midterm 1

No lecture on 2/14

§ Up to Djikstra's Algorithm on 2/7