>>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