|Instr. Phone:||213-740-5972||Office Hours:
12:00 to 5:00 PM|
Wednesday: 12:00 to 5:00 PM
Thursday: 1:20 to 3:20 PM
|Instr. Office:||SAL 236|
|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
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.
This syllabus is meant as an outline. Depending on progress, material may be
added or removed. Also, there will often be interesting tangents to
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 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%|
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.
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
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.