Data Structures

3 Credits · Level: Undergraduate

This course is designed as a second-year course for majors and minors. The main goals of the course are to present a variety of schemes for structuring data so that computer programs can efficiently insert, retrieve, modify, and remove information, to understand and express these operations as formal algorithms, and to analyze these algorithms formally. Using asymptotic analysis, the focus is on the analysis of worst-case running times of algorithms, although the course also covers the analysis of the average-case, amortized, and expected running times for selected algorithms. The data structures that the course surveys include unordered maps, hash tables, general trees, binary trees, ordered maps, search trees, self-balancing trees, multi-way trees, priority queues, heaps, sets, and graphs. Finally, the course reviews elementary sorting algorithms, presents heap-sort, and covers the formal analysis of their running times.