



4. Descriptive Title: Design and Anaysis of Algorithms  
5. Recommended Abbreviation for Transcript (24 characters including
spaces):
Algorithms 

6. Catalog Description (25 words or less):
Basic techniques of design and anaysis of efficient algorithms for standard compuattional problems. NPCompleteness. 

7. Basis: L/G ____X_____ P/F ____X______ Audit ____X______  






12. Are you requesting this course satisfy: Humanities ________ Social Science ________ (Must be 1000 or 2000 level)  
13. Probable instructor(s) (Please mark with an asterix any non
tenuretrack individuals):
Yan Ding, Milena Mihail, Dana Randall, V. Vazirani, H. Venkateswaran 

15. Required _____x_______ Elective ___________  
16. Please attach a topical outline of the course. 


Course Outline and Syllabus 
INTRODUCTORY CONCEPTS: computational problems, models of computation, order notation, recurrences. DIVIDE and CONQUER: Strassen's matrix multiplication merge sort, divide and conquer recurrences. SORTING: heap sort, quick sort, lower bound for comparison sorting counting sort. MEDIANS and ORDER STATISTICS: linear time selection algorithm. SEARCHING: Balanced binary search trees. DYNAMIC PROGRAMMING: Matrixchain multiplication, optimal binarysearch trees, longest common subsequence. GREEDY ALGORITHMS: Huffman codes. ALGORITHMS FOR ELEMENTARY GRAPH PROBLEMS: Graph traversal techniques and their applications (breadthfirst search, depthfirst search), Minimum spanning trees (Kruskal's and Prim's algorithms), Shortest paths (Dijkstra's algorithm and BellmanFord algorithm), Warshall's algorithm for transitive closure. Algorithms for Maximumflow and bipartite matching. STRING MATCHING: KnuthMorrisPratt algorithm. ALGEBRAIC ALGORITHMS: FastFourier Transform. NUMBERTHEORETIC ALGORITHMS: GreatestCommon Divisors, Chinese Remainder theorem, and basic Cryptographic algorithms. \item BASIC RANDOMIZED ALGORITHMS. NPCOMPLETENESS: Basic notions such as reducibility and completeness. Examples of NPComplete problems. 
Suggested Texts  T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, McGrawHill. 