COMP 7/8313: Network Design and Performance Analysis

Instructor Information	Course Information
Instructor: Prof. Santosh Kumar	Meeting Date/Time/Location: MW 2:20-3:45 in FIT 227
Office: DH 376	Latest semester of offering: Fall 2008
Phone: 901 678 2487	Next semester of offering: Fall 2009
Email: santosh (dot) kumar (at) memphis (dot)edu	Prior Semester Syllabus: Fall 2007
Office Hours: MW 3:45-5:00, and by appointment	Grader: TBD

Course Focus: How do we build computing systems with predictable performance? How do we prove the properties of a new system? These are the driving questions for this course. The focus of this course is to introduce analytical tools that students can use in designing sound theory and theoretically sound systems. We will learn how to build optimal algorithms and prove their optimality. Several algorithmic problems do not have efficient optimal solutions. Consequently, we will spend significant portion of the course on learning how to design (distributed) approximation algorithms and how to prove bounds on their performance with respect to optimal. Finally, we will learn few useful probabilistic results that are useful in proving probabilistic bounds on the performance of algorithms where the input data is probabilistic in nature.

The analytical tools learned in this course will strengthen students' research strength, irrespective of their areas of interest.

Books:

Required Text: [T1] Vijay Vazirani, “Approximation Algorithms,” 2nd Edition, Academic Press, 2004.
Reference Books: Selected portions from the following books will be used in the course
- [R1] Raj Jain, “The Art of Computer System Performance Analysis,” Wiley, 1991.
- [R2] Wayne L. Winston, “Operations Research: Applications and Algorithms,” 4^th Edition, Duxbury Press, 2004.
- [R3] Michael R. Garey and Davis S. Johnson, "Computers and Intractability: A Guide to the Theory of Incompleteness", 1979.
- [R4] Sheldon M. Ross, "Introduction to Probability Models," 8th Edition, Academic Press, 2003.
- [R5] Noga Alon and Joel H. Spencer, "The Probabilistic Method," 2nd Edition, John Wiley & Sons, 2000.

For details of topics, grading criteria, class format, and policies, see the detailed syllabus.

Lecture Slides:

8/25/2008:   Introduction to the Course
8/25/2008:   Systematic Approcah to Performance Evaluation;
9/8/2008:   Linear Algebra Review;
9/10/2008:     Review of Linear Programing (LP), Integer Programming (IP), and Duality;
9/15/2008:    Review of NP Completeness
9/24/2008:    Designing Optimal Algorithms (e.g., coverage level optimization and lifetime optimization for barrier coverage)

Back to my Homepage