Document Actions
20 CS 332: Design and Analysis of Algorithms
Syllabus:
Learning Objectives:
| Course Number | 20 CS 332 |
| Credit Hours | 3 Undergraduate |
| Prerequisites |
20 CS 228 |
| Catalog Data | Students learn about algorithm complexity analysis, algorithm design techniques (e.g., branch and bound, divide and conquer, greedy methods), advanced data structures, and sorting techniques. Polynomial (P) and non-polynomial (NP) classes of problems are discussed. |
| Textbooks |
R. Sedgewick, Algorithms in C, Addison Wesley, 1990. |
| References | None |
| Prerequisites by Topic | 20-CS-228, Data Structures. |
| Goals | The goal of this course is to introduce methods of algorithm complexity analysis, algorithm design techniques, advanced data structures, sorting techniques, polynomial and nonpolynomial classes of problems. |
| Topics | 1. Fundamentals: Elementary data structures, Trees, Recursion, Analysis of algorithms, implementation of algorithms (4 classes). 2. Sorting Algorithms: Basic sorting techniques, Quicksort, Heapsort, Mergesort (7 classes). 3. Searching Algorithms: Basic searching methods, Balanced trees, and Hashing (7 classes). 4. String Processing: String searching, and pattern matching (2 classes). 5. Graph Algorithms: Elementary notions, Connectivity etc. (6 classes). 6. Brief exposure to NP-completeness etc. (2 classes). 7. Test (1 class). |
| Computer Usage | Students will design, code document, and test programs to explore the algorithms and techniques covered in class. |
| Labs | See Computer Usage |
| Estimated ABET | Engineering science: 3 credits or 100% |
| Prepared By | Ravi Kothari, Ph.D. on 2000/08/01 |
UC's PlanetLab Contribution Upgraded Thanks to Major Equipment Donation from HP