CSE 548/AMS 542
Analysis of Algorithms

• Anouncements
• Course Information
• Homework Assignments

Announcements

• When you send email to me, please put "cse 548" at the subject line.
• Homework 2 is out! Due Oct 20. Please email me in case you find any typos - Abhishek.
• Oct 13: Slides on Dynamic programming updated.
• Oct 14: MIDTERM will be on November 10, 2009 in class.
• Oct 14: Assignment 2 has been updated, specifically problem 4. Please check the link for the update.
• Oct 17: Slides on Dynamic Programming are now complete.
• Oct 17: Slides on Greedy algorithms uploaded.
• Oct 21: Homework 3 is out! Due Oct 29 (extended to Nov 3). Please email me in case of typos. - Abhishek
• Oct 22: We apologize that there was a severe misprint in the description of the second question in Homework 1. Further announcement will be made to deal with everyone's grade - Kota
• Oct 23: Slides on Matroids, Background of Randomized Algorithms posted.
• Oct 24: We have a google group for CSE 548: "sunysb-cs-548-fall09". Please consider joining it for discussions and urgent announcements.
• Oct 24: UPDATE on 2nd Q in HW1: Everyone will get 5pts automatically if marked incorrect - Kota
• Oct 24: Assignment 3 submission POSTPONED - Now due in class on tuesday, NOV 3 2009.
• Oct 27: Slides on Randomized Algorithms posted.
• Nov 4: Homework 4 is out ! Due Nov 12. As always, please email me in case of typos - Abhishek
• Nov 5: Homework 4 is now complete with all the four problems - Enjoy!
• Nov 7: Slides on order statistics lecture are now up.

Course Information

Time:

3:50-5:10pm, Tue, Thu

Place:

Light. Eng. Rm 102

Professor:

Radu Grosu
1425 CS Building; 632-9801
e-mail: grosu @ cs. sunysb. edu  (Please write "cse 548" in the subject line.)
office hours: 1:30-3:30pm, Tue, Thu

Teaching Assistants:

Abhishek Murthy
e-mail: amurthy @ cs.sunysb.edu
Office hours: 10am-12noon, Mon, Wed (Rm. TA Room, CS Building)

Kota Yamaguchi
e-mail: kyamagu @ cs.sunysb.edu
Office hours: 5:20pm-7:20pm, Tue, Thu (Rm. TA Room, CS Building)

Prerequisites:

CSE373 Analysis of Algorithms

Textbook:

T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 3rd Edition, MIT Press, 2009; ISBN 978-0-262-03384-8.

Syllabus

1. Mathematics background; Divide and Conquer (Chapters 3, 4; 3 classes)
2. Dynamic Programming (Chapter 15; 4 classes)
3. Greedy Algorithms (Chapter 16; 2 classes)
   • Matroids
4. Randomized Algorithms (Chapters 5, 7, 9; 4 classes)
   • Background
   • Order statistics
5. Data Structures and Graph Algorithms (Chapters 22-25; 5 classes)
6. NP-Completeness (Chapter 34; 3 classes);
7. Approximation Algorithms (Chapter 35; 4 classes);

Grading

• Homeworks: 35%. (Six homework sets. All homeworks are mathematical problems; there will be no programming homeworks.)
• Midterm exam: 30%; tentative date: TBA.
• Final exam: 35%; date: TBA.

1. If you have a physical, psychological, mental, or learning disability that may impact your course work, please contact Disability Support Services at (631)632-6748 or at Disability Support Service. They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential.

2. Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and Disability Support Services. For procedures and information go to the following webcite: Disability Support Service.

3. Because one of the main goals of this course is to teach professionalism, any academic dishonesty will be viewed as the evidence that this goal has not been achieved and will be grounds for receiving a grade of F. (See CEAS Procedures and Guidelines Governing Academic Dishonesty, 1/81)

Homework Policy

You are encouraged, but not required, to form two-person homework teams to solve the homework questions together. Each team will submit only one copy of the homeworks and the two members of the team will receive the same grade for the homework. Homework team does not have to be the same for all homeworks.

Discussion of homeworks are encouraged but copying homeworks is not allowed. Severe penalty will be imposed to both parties of the cheating case, including, at least, receiving zero point for the homework.

Solutions (or hints to solutions) are usually posted here the day after the due date of the homework. No homeworks will be accepted after the post of solutions.

Homework Assignments

Homework 1

• Due Sep. 29, Tue
• Problems (pdf)

Homework 2

• Due Oct. 20, Tue
• Problems (pdf)

Homework 3

• Due Oct 29, Thu
• Problems (pdf)

Homework 4

• Due Nov 12, Thu
• Problems (pdf)