CSCI 570 Analysis of Algorithms
Spring   2011

Instructor: Dr. Shawn Shamsian
Instr. Phone: 213-740-5972 Office Hours:
Monday:        12:00 to 5:00 PM
Wednesday:   12:00 to 5:00 PM  
Thursday:       1:20 to 3:20 PM
Instr. Office: SAL 236

Class Meeting Time & Location

Section Day Time Location Final Exam Date, Time
048-30101D  Wednesday 06:40 - 09:20 PM OHE132 TBD
034-30099D Wednesday 06:40 - 09:20 PM OFF CAMPUS TBD

TA : Kai Song TA Office: SAL 235
Email: kaisong AT usc DOT edu Office Hours: Monday 09:00 - 11:00am
TA : Mohammad Chitgarha TA Office: EEB524
Email: chitgarh AT usc DOT edu Office Hours: Wednesday 3:00-5:00pm


Course Information

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


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 2/23/2011 6:40-8:40pm SGM 101 Lecture Covered 30%
Exam II 4/6/2011 6:40-8:40pm SGM 101 Lecture Covered 30%
Final 5/4/2011 7-9pm SGM 101 Comprehensive 40%


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

All homeworks must be solved and written independently, or you will be penalized for cheating. The USC Student Conduct Code prohibits plagiarism. All USC students are responsible for reading and following the Student Conduct Code, which appears on SCampus.

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.