COT5405 - Homework/Reading Assignments
Fall 2005
- Class 1 : Aug 29
- Read the slides for the first lecture.
- Read chapter 1 of the text book.
You should be familiar with the stuff in chapter 2, 3 of the text book
from the prerequisites of the course.
- Homework 1: Chapter 1 ( Ex 1,2,7 ), Chapter 2 ( Ex 4,6,8 ), Chapter 3 ( Ex 1,2,8,9 ) ,
Chapter 7 ( Ex 9, 10 ): Due 12th Sep (Before class begins)
- Programming Assignment 1 is coming up, get started.
- Class 2 : Aug 31
- Read the slides for the second lecture.
- Read chapter 7 of the text book. (Sections 7.1, 7.2, 7.3, 7.5)
- Class 3 : Sep 7
- Read the slides for the third lecture.
- Continue reading chapter 7 of the text book. (Section 7.4)
- Look at the project list and send me your preferences (Top 5)
- Class 4 : Sep 14
- Read the slides for the fourth lecture.
- Continue reading chapter 7 of the text book. (Section 7.5, 7.6, 7.10)
- Start preparing your project proposal
- Class 5 : Sep 19
- Read the slides for the fifth lecture.
- Continue reading chapter 7 of the text book. (Section 7.13)
- Try the solved exercises yourself.
- Homework 2: Chapter 7 ( Ex 5,7 )
- Class 6 : Sep 21
- Read the slides.
- Complete reading chapter 7 of the text book.
Start reading chapter 8 (8.1-8.3)
- Homework 2: Chapter 7 ( Ex 12 )
- Class 7 : Sep 26
- Read the slides.
- Continue reading chapter 8 (8.4-8.5)
- Homework 2: 7.25, 8.5, 8.20 (Hint: Try reduction from k-coloring), 8.29
- Class 8 : Sep 28
- Read the slides.
- Complete reading chapter 8.
Start reading chapter 11 (Section 11.2)
- Homework 2: Vertex Cover approximation, Factor of greedy?
[Solution]
- Class 9 : Oct 3rd
- Read more on Vertex Cover
approximation/Inapproximability of TSP/k-center clustering.
- Homework 2: Due Oct 12th.
- Weighted Matching assignment: Due Oct 10th.
- MidTerm is here: Oct 17th
- Second part of programming assignment 1, Lec notes 5, slide 22/23.
- Class 10-11 : Oct 5th
- Read section 11.2
- Read Lecture slides on linear programming.
- Read chapter 12 of Vazirani's approximation algorithms book
- Think about why 1-center approximation improves if you do a simple
furthest walk twice (Extra Credit question: HW 2).
- Class 12 : Oct 17th: Midterm
- Class 13 : Oct 19th
- Class 14-15 : Oct 24th and 26th
- Read Huffman Coding and Clustering using MSTs from the book and the slides.
- Get preliminary results on your project and submit
a new version of your project report by Nov 4th.
- Schedule a project demo to be done by Nov 7th.
- Midterm scores: Min: 23. Max: 84. Av.: 59
- You can calculate your midterm rank using this.
- HW1 scores: Min: 0. Max: 119. Av: 84.
- HW2 scores: Min: 0. Max: 80. Av. 56.
- Programming Assn 1: Min: 88. Max: 110. Av. 98.
- Programming Assn 2: Min: 0. Max: 100. Av. 91.5
- Class 16 : Oct 31st
- Read Data Compression chapter by Guy Blelloch
- Read Section 4.8 from the book.
- Project writeup due: 4th Nov (Midnight).
Preliminary Milestone check meeting (Schedule an appointment by Nov 4th).
The preliminary presentation and the writeup, will count 8% towards the final project.
- Class 17-23: Nov 16th
- Final Homework: Chapter 4: 2,4,5,11,21
- Chapter 5: 4,5
- Chapter 6: 1,6
- Final Week:
- Some sample midterms/finals. Most of this material is what I have taught previously in undergraduate classes. This is just to give you a feeling of what kind of question paper you can expect. Of course the syllabus of the graduate course is radically different than the undergraduate one.
- Project Presentation Schedule.
- Surprise In-class Tests: 1 2
- Final Statistics:
- Average Score = 53/105.
- Min = 11
- Max = 84
- Std. Deviation = 17
Back to course homepage
Piyush Kumar (piyush at acm. dot. org)