|
||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||
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. NP-Completeness. |
||||||||||||||||||||||||||||||||||||||||
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
tenure-track 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: Matrix-chain multiplication, optimal binary-search trees, longest common subsequence. GREEDY ALGORITHMS: Huffman codes. ALGORITHMS FOR ELEMENTARY GRAPH PROBLEMS: Graph traversal techniques and their applications (breadth-first search, depth-first search), Minimum spanning trees (Kruskal's and Prim's algorithms), Shortest paths (Dijkstra's algorithm and Bellman-Ford algorithm), Warshall's algorithm for transitive closure. Algorithms for Maximum-flow and bipartite matching. STRING MATCHING: Knuth-Morris-Pratt algorithm. ALGEBRAIC ALGORITHMS: Fast-Fourier Transform. NUMBER-THEORETIC ALGORITHMS: Greatest-Common Divisors, Chinese Remainder theorem, and basic Cryptographic algorithms. \item BASIC RANDOMIZED ALGORITHMS. NP-COMPLETENESS: Basic notions such as reducibility and completeness. Examples of NP-Complete problems. |
Suggested Texts | T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, McGraw-Hill. |