New Course Proposal

 Graduate: Level I ______ Undergraduate: ___X___ Level II ______ Unit: College of Computing Date: 1/27/03

 1. Course Number Program Number: CS3xxx
 2. Hours: Lecture Lab Recitation Total Semester Credit ___3___ ___ ________ _____3___
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______
 8. Prerequisites: CS 1050, CS 1322, and MATH 3012* Corequisites:
 10. Expected Mode of Presentation: MODE % OF COURSE Lecture ____100______ Laboratory (Supervised) _______________ Laboratory (Unsupervised) _______________ Discussion _______________ Seminar _______________ Independent Study _______________ Library Work _______________ Demonstration _______________ Other (Specify) _______________
11. Planned Frequency of Offering: TERM TO BE OFFERED EXPECTED ENROLLMENT
 Fall ___x___ Spring ___x___ Summer ___x___
 ______150_________ ______150________ _______50________
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 Description and Topical Outline 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.