CSCI 570 Analysis of Algorithms
Fall 2007

Instructor: Dr. Shawn Shamsian
Class Meeting Time:	F 5-7:40PM, M 6-8:50PM	Class Location:	OHE 136
Instr. Phone:		Instr. Office:	SAL 236
Email:	sshamsia@usc.edu	Office Hours:	M 2~3PM, F 1~2PM

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

Teaching Assistant : Marcos Vieira
TA Phone:	(213) 821-1240	TA Office:	SAL 103
Email:	mvieira@usc.edu	Office Hours:	F 9:00 – 11:00AM

Teaching Assistant : Majed Alresaini
TA Phone:	(213) 821-1240	TA Office:	SAL 103
Email:	alresain@usc.edu	Office Hours:	TH 2:00 – 4:00PM

Teaching Assistant : Dilip Iyer

TA Phone:	(213) 821-1240	TA Office:	SAL 103
Email:	dilipiye@usc.edu	Office Hours:	T 10:00-12:00PM

Graders : Manish Khanna <manishkh@usc.edu> and Rutuja Joshi <rutujajo@usc.edu>

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	Oct 5th	5:00 to 7:00	THH 101 and 201	Lecture Covered	30%
Midterm II	Nov 9th	5:00 to 7:00	SGM 123	Lecture Covered	30%
Final	Dec 14th	4:30 to 6:30	SGM 123	Comprehensive	40%
Final	Dec 17th	7:00 to 9:00	SGM 124	Comprehensive	40%

Reading Schedule

	Subject	Chapter(s)
	Introduction	Algorithm Design: Chapter 1
	Complexity Analysis	Algorithm Design: Chapter 2
	Graphs	Algorithm Design: Chapter 3
	Memorial Day	No Class
	Greedy technique	Chapter 4
	Greedy technique Heaps from supplemental textbook	Chapter 4 & Supplement textbook
	Shortest path and minimum spanning tree	Chapter 4
	Dynamic programming	Chapter 6
	Dynamic programming	Chapter 6
	Midterm I
	Divide and conquer	Chapter 5
	Network flow	Chapter 7
	Network flow	Chapter 7
	Holiday	No Class
	Circulation	Chapter 7
	Mid-term II;
	NP-Completeness	Chapter 8
	NP-Completeness	Chapter 8
	NP completeness TSP	Supplement textbook
	Approximation algorithms	Chapter 11
	Linear programming
	Review
	Final

Grading

There will be two midterms and one final exam in this course. Each midterm worths 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 DEN site regularly. Homework set will be available on DEN.

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 Fall 2007

CSCI 570 Analysis of Algorithms
Fall 2007