Office: Dunn Hall 307

Phone: (901) 678-3135

Home page : http://www.cs.memphis.edu/~nkumar/

Office hours : TBA

Date | Item | Relevant link |

W Jan 20th | Introduction to the course and Approximation algorithms. - 2 approx. Minimum Makespan sched. | Sec 11.1 KT |

M Jan 25th | Approximation algorithms - MMS contd. (1.5 approx), k-center clustering | Sec 11.1, Sec 11.2 KT |

W Jan 27th | Approximation algorithms - k-center clustering contd. | Sec 11.2 KT |

M Feb 1st | Approximation algorithms - Set Cover | Sec 11.3 KT |

W Feb 3rd | Approximation algorithms - Pricing Method (Vertex Cover) | Sec 11.4 KT |

M Feb 8th | Approximation algorithms - Pricing method contd. (Disjoint paths) | Sec 11.5 KT |

W Feb 10th | Approximation algorithms - LP and rounding (Vertex cover again) | Sec 11.6 KT |

M Feb 15th | LECTURE CANCELLED - SNOW STORM | |

W Feb 17th | LECTURE CANCELLED - SNOW STORM | |

M Feb 22nd | LECTURE CANCELLED - CAMPUS WATER PROBLEM , HW1 | HW1 |

W Feb 24th | LP rounding : Generalized Load Balancing | Sec 11.7 KT |

M Mar 1st | LP rounding wrap up and Local Search | Sec 11.7 KT and Sec 12.1 KT |

W Mar 3rd | Local Search contd. and HW1 due | Sec 12.2 KT and Sec 12.3 KT |

M Mar 8th | No Lecture | |

W Mar 10th | Randomized algorithms | Sec 13.1 |

M Mar 15th | Randomized algorithms | Sec 13.2 |

W Mar 17th | Randomized algorithms | Sec 13.3 |

M Mar 22nd | Randomized algorithms and HW2 | Sec 13.4, 13.9, and HW2 |

W Mar 24th | Randomized algorithms | Sec 13.10 and Sec 13.11 |

M Mar 29th | Randomized algorithms | Sec 13.11 wrap up |

W Mar 31st | FPT | Sec 10.1 and Sec 10.2 |

M Apr 5th | FPT and HW2 due and HW3 | Sec 10.2 contd. and Sec 10.3, HW3 |

W Apr 7th | FPT | Sec 10.3 wrap up |

M Apr 12th | Lecture postponed | |

W Apr 14th | Lecture postponed | |

F Apr 16th | Special lecture cancelled HW3 due and HW4 | HW4 |

M Apr 19th | Tree decomposition | Sec 10.4 |

W Apr 21st | Tree decomposition contd. | Sec 10.4 wrap up |

M Apr 26th | Tree decomposition contd. | Sec 10.5 |

F Apr 30th | 10 - 11:30 AM: Student presentations, and HW4 due |