CSCI 570 Analysis of Algorithms
Spring 2007

Instructor: ***Dr. Shawn Shamsian***
Class Meeting Time:	F 5:00PM - 7:40PM	Class Location:	OHE 132;
Instr. Phone:		Instr. Office:	SAL 236
Email:	sshamsia@usc.edu	Office Hours:	F 12:50PM-1:50PM

**Teaching Assistant : Qing Luo**
TA Phone:	(213) 740-4521	TA Office:	SAL 229
Email:	qingluo@ usc.edu	Office Hours:	M 2:30PM-4:30PM

**Teaching Assistant : Bo Mi Song**
TA Phone:	213-740-4514	TA Office:	SAL 219
Email:	bsong@usc.edu	Office Hours:	T 9:30AM-11:30PM

**Teaching Assistant : Po-An Chen**
TA Phone:	(213)740-6747	TA Office:	SAL 237
Email:	poanchen@usc.edu	Office Hours:	W 3:00PM-5:00PM

**Teaching Assistant : Jae Cha**
TA Phone:	213-740-2354	TA Office:	EEB 332
Email:	jaecha@usc.edu	Office Hours:	Th 1:30PM-3:30PM

**Teaching Assistant : Ilya Eckstein**
TA Phone:	213-740-4177	TA Office:	PHE 108
Email:	ilyaeck@usc.edu	Office Hours:	F 10:00AM-12:00AM

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.

Text:
The textbook is
* 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 about 7 homework assignments.
Exams: There will be two in-class midterm exam 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.

* Introduction and overview
* Complexity of algorithms--review
* Basic graph algorithms--review
* Greedy Algorithms
* Data structures
* Graph algorithms
* Dynamic Programming
* Divide-and-Conquer
* Amortized analysis
* Max-Flow/Min-Cut and its applications
* P, NP, and NP-Completeness
* Approximation methods, linear programming

Exam Schedule

Exam	Date	Time	Location	Covered Materials	Weight
Midterm I	Feb 23	5:00PM-7:00PM	THH101 and THH212	Lecture Covered	30%
Midterm II	March 30	5:00PM-7:00PM	SGM123	Lecture Covered	30%
Final	May 4(5 O'clock Section )	4:30PM-6:30PM	THH101	Comprehensive	40%
	May 7(2 O'clock Section )	2:00PM-4:00PM	SLH102	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.

Homework is due at the start of class on the due date. There will be roughly 7 homework assignments.

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.

The University of Southern California does not screen or control the content on this website and thus does not guarantee the accuracy, integrity, or quality of such content. All content on this website is provided by and is the sole responsibility of the person from which such content originated, and such content does not necessarily reflect the opinions of the University administration or the Board of Trustees

CSCI 570 Analysis of Algorithms Spring 2007

CSCI 570 Analysis of Algorithms
Spring 2007