CSE 202 Winter 2012: Design and Analysis of Algorithms

Time and Venue:

TTh 5-6:20pm, Center Hall 212

Instructor:

Kamalika Chaudhuri
Email: kamalika at cs dot ucsd dot edu
Office Hours: TTh 6:30-7:30pm, CSE 4110

Teaching Assistant:

Alex Tsiatas
Email: atsiatas at cs dot ucsd dot edu
Office Hours: M4-5, W11-12, CSE 260A

Announcements

• The average for the final is 25/40, standard deviation 6.
• There's a correction to Problem 3 in the final. Problem 3(b) should say: Show that Pr(N_{t+1} (greater than or equal to) 9N_t/10 | N_t) (less than or equal to) 5/6, instead of: Show that Pr(N_{t+1} (greater than or equal to) 2 (1 - 1/e) N_t | N_t) (less than or equal to) 1/2.
• There's a correction to Problem 2 in the final. Problem 2(a) should ask you to find a consistent reconciliation where at most n checks are written (instead of simply a consistent reconciliation).
• Extra TA Office Hours on Mon 3/19, 10-11am, B260A.
• The Final will go out on March 15th at the end of class. It will be due March 20th in my mailbox or TA Office (CSE 4232) by 5pm. The final should be taken individually, no collaboration . You are permitted to discuss the final only with me and the TA, and no other person inside or outside the class.
• Material covered in the Final is Max Flow and Randomized Algorithms.
• No class on Mar 8. Please drop off HW4 either in the instructors mailbox or TA Office (CSE 4232) by 5pm Mar 8.
• Homework 4 will be posted on Mar 1. It will be due Mar 8 by 5pm.
• No instructor office hours on Tuesday Feb 28. Extra instructor office hours on Wednesday Feb 29, 4:30-5:30.
• Homework 3 will be posted on Tuesday Feb 21. It will be due on Tuesday Feb 28.
• There will be no lecture on Tuesday, Feb 21. Instead, there will be TA office hours from 5-6:20 in the classroom (Center Hall 212).
• The average for the midterm is 40. The standard deviation is 11.
• The midterm will be closed book, closed notes. You are allowed one 8.5 x 11.5 sheet of paper with printed or hand-written notes on it; the paper can be printed one sided or two sided.
• Material covered in Midterm is Greedy algorithms, Divide and Conquer, Dynamic Programming, and Network Flows (upto Ford-Fulkerson style algorithms, not including Preflow-Push.)
• Homework 2 solutions are up!
• A clarification on HW2. For Problem 2, if there are multiple smallest elements, the second smallest element is the smallest one. For example, if the input is [1, 1, 1, 2], then the second smallest element is 1.
• Homework 2 is now posted, it's due Feb 2 in class.
• Homework 1 solutions are up!
• Instructor Office Hours on Tuesday, Jan 24 are cancelled. Extra office hours Wednesday, Jan 25, from 12:15-1:15pm.
• The midterm is on February 14, in class.
• Homework 2 will be posted on January 26.
• Homework 1 is posted. It is due January 24 in class.