Fall 2010

Instr. Phone: |
213-740-5972 | Office Hours: |
Monday:
2:25 to 3:25 PM Wednesday: 2:25 to 3:25 PM Friday: 12:55 to 1:55 PM |

Email: |
sshamsia@usc.edu | ||

Instr. Office: |
SAL 236 |

TA : |
Hikmet Dursun |
TA Office: |
SSC 326 |

Email: |
hdursun@usc.edu | Office Hours: |
Friday 08:00 - 10:00 AM |

TA : |
Hsing-Hau Chen |
TA Office: |
SAL 112 |

Email: |
hsinghac@usc.edu | Office Hours: |
Tuesday-Wednesday 08:00 - 10:00 AM |

__Course Information__

**Course Outline:**The course is intended as a first graduate course in the design and analysis of algorithms. The main focus is on developing an understanding for the major algorithm design techniques. At times, the practical side of algorithm design is also explored with interesting examples of their usage in solving industry problems.

**Textbook:***** Algorithm Design**

Jon Kleinberg/Eva Tardos

The class will be relying mostly on the textbook, but additional material will occasionally be drawn from the following:

* Introduction to Algorithms (second Edition)

Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest and Cliff Stein published by MIT Press and McGraw-Hill.

Students in the class are expected to have a reasonable degree of mathematical sophistication, and to be familiar with the basic notions of algorithms and data structures, discrete mathematics, and probability. Undergraduate classes in these subjects should be sufficient. If you have doubts about meeting these prerequisites, please contact the instructor.

__Class Structure__

**Homework:**There will be weekly homework assignments.**Exams:**There will be two in-class midterm exams and a final exam.

**Syllabus**

This syllabus is meant as an outline. Depending on progress, material may be
added or removed. Also, there will often be interesting tangents to
follow.

week 1 intro, stable matching chapter 1

week 2 Asymptotic notation, BFS, DFS, greedy algorithms chapter 2, 3, 4

week 3 Greedy algorithms, heaps chapter 4, suplemental text chapter 6,19

week 4 MST, shortest path, divide and conquer chapter 4, 5

week 5 divide and conquer chapter 5

week 6 review and exam I

week 7 dynamic programming chapter 6

week 8 dynamic programming chapter 6

week 9 network flow - max flow chapter 7

week 10 network flow - circulation chapter 7

week 11 review and exam II

week 12 NP-completeness chapter 8

week 13 NP-completeness chapter 8, supplemental text chapter 34

week 14 approximation algorithms chapter 11, supplemental text chapter 35

week 15 approximation algorithms, LP chapter 11, supplemental text chapter 29

**Exam Schedule**

Exam |
Date |
Time |
Location |
Covered Materials |
Weight |

Exam I |
10/01/2010 | TBD | TBD | Lecture Covered | 30% |

Exam II |
11/05/2010 | TBD | TBD | Lecture Covered | 30% |

Final |
12/10/2010 (30101D) 12/13/2010 (30105D) |
02:00 - 04:00 PM | TBD | Comprehensive | 40% |

**Grading**

There will be two midterm and one final exam in this course. Each midterm
exam worth 30% and the final 40%. There will be homework assigned from the
textbook roughly every 1-2 weeks. The homework will be collected and graded but
Will NOT be accounted in your grade; Solutions to the homework will become
available shortly after the deadline.

__Additional Policies__

- Academic
Integrity Policies of the University will be strictly enforced. You are
encouraged to review these policies, for example in
*SCampus*. - Please visit course homepage and check Announcements regularly.
- No late homework will be accepted unless approval is granted from the instructor in advance.

In this course we encourage students to study together. This includes discussing general strategies to be used on individual assignments. However, all work submitted for the class is to be done individually.

Some examples of what is not allowed by the conduct code: copying all or part of someone else's work (by hand or by looking at others' files, either secretly or if shown), and submitting it as your own; giving another student in the class a copy of your assignment solution; consulting with another student during an exam. If you have questions about what is allowed, please discuss it with the instructor.

Students who violate University standards of academic integrity are subject to disciplinary sanctions, including failure in the course and suspension from the University. Since dishonesty in any form harms the individual, other students, and the University, policies on academic integrity will be strictly enforced. We expect you to familiarize yourself with the Academic Integrity guidelines found in the current SCampus.

Violations of the Student Conduct Code will be filed with the Office of Student Conduct, and appropriate sanctions will be given.