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,” 4th 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.
Lecture Slides:
8/25/2008: Introduction to the Course
8/25/2008: Systematic Approach to Performance Evaluation;
9/8/2008: Linear Algebra Review;
9/10/2008: Review of Linear Programming (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