|
Catalog Description : |
This
Algorithm Analysis, Asymptotic Notation, Hashing, Hash Tables, and Scatter
Tables AVL and B-Trees, Brute-Force and Greedy Algorithms,
Divide-and-Conquer Algorithms, Dynamic Programming, Randomized Algorithms,
Graphs and Graph Algorithms, Distributed Algorithms |
|
Prerequisite: |
CMPS 223 |
|
Units: |
5 |
|
Coordinator: |
|
|
Goals/Objectives: |
- To determine the time and space complexity of given
algorithms.
- To implement brute force, greedy, divide-and-conquer,
backtracking, branch-and-bound, heuristic and dynamic programming
algorithms to solve an appropriate problem.
- To design and implement hash tables for an appropriate
problem.
- To solve problems using the graph algorithms.
- To solve problems using the randomized algorithms.
|
|
Current Texts: |
- Anany Levitin The Design and Analysis of Algorithms , ISBN
xxxxxxxxxxx
|
|
Topics: |
- (AL1)Basic algorithmic analysis:Asymptotic
analysis of upper and average complexity bounds, Identifying
differences among best, average, and worst case behaviors, Big O,
little o, big omega, and big theta notation , Standard complexity
classes, Empirical measurements of performance, Time and space
tradeoffs in algorithms, Using recurrence relations to analyze
recursive algorithms.
- (AL2) Algorithmic strategies: Brute-force
algorithms, Greedy algorithms, Divide-and-conquer, Backtracking,
Branch-and-bound, Heuristics, Randomized algorithms, Dynamic
programming.
- (AL3) Fundamental computing algorithms: Hash
tables, including collision-avoidance strategies, Search trees (AVL
and B-trees), Representations of graphs (adjacency list, adjacency
matrix), Depth- and breadth-first traversals, Shortest-path algorithms
(Dijkstra's and Floyd's algorithms), Transitive closure (Floyd's
algorithm), Minimum spanning tree (Prim's and Kruskal's algorithms),
Topological sort, Pattern matching and string/text algorithms.
- (AL4) Distributed algorithms: Consensus and
election, Termination detection, Fault tolerance, Stabilization.
|
|
ACM Sub Areas or Units Covered:: |
ACM Sub Areas or Units covered
in this course:
| (AL1) Basic algorithmic analysis |
1.5 |
| (AL2) Algorithmic strategies |
1.5 |
| (AL3) Fundamental computing algorithms |
1.5 |
| (AL4) Distributed Algorithms |
0.5 |
AL: Algorithms and Complexity |
|
Laboratory: |
The laboratory work involves
implementing various types of algorithms in C++ |
|
Oral and Written Communication: |
|
|
Social and Ethical Issues: |
|
|
Problem Analysis: |
|
|
Solution Design: |
|
|
Version & Date |
Version 1, 5/6/2003 |
|
Comments |
The first draft based on ACM
curricula 2001 in the format of ABET sample course description.
|