>>PRINT
| Algorithms and Complexity | |||
| ALG COMP | |||
| CLASS CODE: | CS 306 | CREDITS: 3 | |
| DIVISION: | PHYSICAL SCIENCE & ENGINEERING | ||
| DEPARTMENT: | ELECTRICAL & COMPUTER ENGINEERING | ||
| GENERAL EDUCATION: | This course does not fulfill a General Education requirement. | ||
| DESCRIPTION: | Introduces formal techniques to support the design and analysis of algorithms, focusing on both the underlying mathematical theory and practical considerations of efficiency. Topics include asymptotic complexity bounds, techniques of analysis, and algorithmic strategies. | ||
| TAUGHT: | Summer, Fall | ||
| CONTENT AND TOPICS: | Basic algorithmis analysis: Asymptotic analysis of upper and average complexity bounds; best, average, and worst case behaviors; big-O, little-O, omega, and theta notation; standard complexity classes; emirical measurements of performance; time and space tradeoffs in algorithms; using recurrence relations to analyze recursive algorithms; fundamental algorithmic strategies: Brute-force; greedy; divide and conquer; backtracking; brand-and-bound; pattern matching and strin/text algorithms; graph and tree algorithms: depth-and-breadth-frist traversals; shortest-path algorithms (Dijkstra's and Floyd's algorithms); minimum spanning tree (Prim's and Kruskal's algorithms); topological sort | ||
| GOALS AND OBJECTIVES: | 1. Analyze adn compare computer algorithms using: Big-Oh, Big-Omega, Big-Theta, and Recurrence Relations. 2. Describe and implement in a high level language the following algorithmic techniques: Divide and Conquer, Greedy, Dynamic Programming, Backtracking, and Branch and Bound. |
||
| REQUIREMENTS: | Access to computers in the Linux computer lab is required to complete homework assignments. Class attendance is required but is not necessarily part of the grade. Each student is required to read assigned portions of the textbook(s). | ||
| PREREQUISITES: | CS 235 and CS 236 | ||
| OTHER: | |||
| EFFECTIVE DATE: | August 2002 | ||