CS 330-3
Advanced Data Structures and Algorithms
Catalog Description
An advanced course in data structures including a detailed treatment of the design, analysis, and complexity of algorithms. Covers B-trees, hash tables, heaps, and advanced sorting algorithms. Explores fundamental algorithm design techniques and basic graph algorithms.
Prerequisite:
CS 220 with a grade of C or better.
Objectives
This course is designed to give students a good understanding of advance data structures and a basic understanding of the concepts of algorithm design. These objectives are pursued by implementing the data structures and algorithms discussed.
Organization
The course consists of four contact hours, two lecture and two lab hours, per week. The target audience is students with little or no background in programming.
Course Outline
| Lectures | ||
| 1. | Mathematical Foundation
Formal treatment of analysis and design of algorithms, growth of functions, summations, recurrences, recursive vs. iterative algorithms, worst cast and average case analysis of algorithms, lower bounds |
6 |
| 2. | Files Basic file processing, seeking and indexing |
3 |
| 3. | Trees
B-Trees and other balanced trees |
8 |
| 4. | Hashing
Hash functions, collisions and resolutions |
6 |
| 5. | Heaps
Implementations, applications, and variations |
3 |
| 6. | Sorting
Variations of Quicksort, merge sort, heapsort |
4 |
| 7. | Graph Algorighms
DFS, BFS, topological sort, minimum spanning trees algorithm, shortest path algorithm |
3 |
| 8. | Advanced Algorithm Design Techniques
Divide and conquer, greedy and backtracking |
3 |
| 9. | Introduction to Parallel Algorithms | 4 |
| Total | 40 | |