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.