HW6 Problem 4d

While writing up the solutions to HW6, it occurred to me that Problem 4 part d might be a little ambiguous, since we never discussed approximation algorithms with randomization. For the purposes of this problem, let's allow a small failure probability: your algorithm should in polynomial time return a valid set cover with high probability (say, at least 1 - 1/n) and in expectation the cost of the solution it returns should be at most O(log n) more than the cost of the optimum solution. Once you have this it's pretty simple to get to other versions (e.g. algorithms that always return a valid set cover but only run in polynomial time in expectation), so it's fine if you end with a statement of this form (again: in polynomial time, with high probability we return a set cover and in expectation it does not cost much more than the optimum solution).

Upcoming office hours

Since this Friday is Carnival I am not planning on having office hours. I will also be out of the country all next week, and so will not be available for office hours. I'll do my best to respond to email, but it's not clear that I'll have reasonable internet access.

Midterm II

Midterm II has been graded. Some stats: Mean = 71.23, Stddev = 21.13, Median = 71. Max = 100. See histogram below for more info.

Friday office hours

I will once again be out of town this Friday, so I need to cancel my office hours. As always, feel free to email me with any questions you might have (or come to my Wednesday office hours).

Midterm II Review Session

Here are some tidbits from the review session we had in class on Friday:

Exam Format: 80 minutes, open books, notes, handouts, etc -- no laptop. 3 - 4 questions: design algorithms, write proofs, analyze running time, etc.

Topics: (everything since Midterm I).

• Graph Algorithms: Depth-first Search, Strongly Connected Components
  
  
• FFT, String Matching, String Matching using FFT, Wildcard
  
  
• Resistive Model of Graphs, Random Walks (Hitting Time, Commute
  Time, etc.)
  
  
• Linear Solvers: Direct Methods (pivoting strategy, fill, work, nested dissection), Iterative Linear Solvers.
  

Practice Midterm Solutions: We also went over the practice midterm. You can download the solutions here.

Problem 2, Homework 5

In part a) of problem 2, $C_{uv} \leq |E|$ is not achievable; you might want to prove $C_{uv} \leq 2|E|$ instead. Consequently, your upper-bound in part b) should be $2|V||E|$ (we don't mind if you show us a $4|V||E|$ bound), and hence the probability in part c) will be something like 3/4 (instead of 7/8). Thanks Yiming for pointing this out.


If you are going to use the theorem $C_{uv} = R_{uv}\times C$ (where $R_{uv}$ is the effective resistance between $u$ and $v$), keep in mind that in this case $C = \sum_{i} C_i = 2\times \sum_{e} C_e$.

Practice Midterm and Homework Solutions

We have posted a practice midterm in light of Midterm 2 (link here). Your Midterm 2 will be in class on Monday, April 6. To include more questions for you to play with, the practice midterm is significantly longer than what your real midterm will be. Solutions will be up later.


We have also posted solutions to Homework 2 and 3.