Title: Advanced Data Structures and Algorithm Analysis

Catalog Data:
Description and utilization of formal ADT representations, especially those on lists, sets, and graphics; time and space analysis of recursive and nonrecursive algorithms, including graph and sorting algorithms; algorithm design techniques.

(3 hrs. credit)

Textbook: Fundamentals of Data Structured by Horowitz

Software: Microsoft Visual C++ on Lab PCs or GNU C++ on UNIX systems

Goals:
To acquaint students with basic classical science and their underlying principles. To explore algorithm analysis and data structures so that students can make appropriate choices when designing programs.

Prereqs:

1. Credit in CSC 2290 or CSC 1254
2. Credit or registration in CSC 2259

Course Topics:

1. Software Engineering
2. ADTS and Data Structures
3. Queues and Stacks
4. Sparse Matrix
5. O-notion
6. String and KMP searching
7. General Trees
8. Priority Queues
9. Sets
10. Binary Search Trees
11. Hashing
12. AVL Trees
13. 2-3 trees
14. Graphs
15. Dijkstra's Algorithm
16. Floyd's Algorithm
17. Depth First/Breadth First searches
18. Topological Sort/Strong Components
19. Longest Path/Weighted Graphs
20. Spanning Trees
21. Prim's Algorithm
22. Kruskal's Algorithm
23. Tries
24. Huffman Code
25. Game Trees
26. N-P Complete Problem
27. Sorting
28. External Sorting
29. Proof by Induction

The homework list for this course will appear here.

The list of old tests for this course will appear here.