X
Home Computer Science Santosh Kumar Comp 7/8313

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.
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 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