Data Structures
Prerequisites
Students must have completed CMSC 202 with a ‘B’ or better AND CMSC 203 with a ‘C’ or better.
Description
An examination of a range of advanced data structures, with an emphasis on an object-oriented approach. Topics include asymptotic analysis; various binary search trees, including red-black and splay trees; skip lists as alternatives to binary search trees; data structures for multidimensional data such as K-D trees; heaps and priority queues, including binary heaps, binomial heaps, leftist heaps (and/or other mergeable heaps); B-trees for external storage; other commonly used data structures, such as hash tables and disjoint sets. Programming projects in this course will focus on implementation issues for data structures and on empirical analysis of their asymptotic performance.
Course Outcomes
Each student will:
- Demonstrate understanding and appropriate use of standard data structures including: linked lists, stacks, binary heaps, balanced binary trees and hash tables in C++.
- Implement data structures in the context of complex programming assignments, including the use of recursive solutions.
- Analyze the performance of data structure operations using asymptotic analysis.
- Assess competing data structures and choose the most appropriate for a given application.
- Effectively use software development tools to improve memory management, security, and debugging.
Student Outcomes
| Level of Emphasis | |||
| ABET Outcome | Low | Medium | High |
| Analyze a complex computing problem and to apply principles of computing and other relevant disciplines to identify solutions. | x | ||
| Design, implement, and evaluate a computing-based solution to meet a given set of computing requirements in the context of the program’s discipline. | x | ||
| Communicate effectively in a variety of professional contexts. | x | ||
| Recognize professional responsibilities and make informed judgments in computing practice based on legal and ethical principles. | x | ||
| Function effectively as a member or leader of a team engaged in activities appropriate to the program’s discipline. | x | ||
| Apply computer science theory and software development fundamentals to produce computing-based solutions. | x | ||
Text
Goodrich, M., Tamassia, R., and Mount, D. (2011). Data Structures and Algorithms in C++, Second Edition. John Wiley & Sons (ISBN-13: 978-0470383278, ISBN-10: 0470383275).
Topics
- Asymptotic Analysis
- Lists, stacks and queues
- General Trees including k-ary trees
- Binary Search Trees
- Splay Trees
- Red-Black Trees
- Priority Queues using binary and leftist heaps
- Hash Tables
- Graphs
Optional Topics
- Skiplists, Disjoint Sets, K-d trees, B-Trees, or Treaps
Grading
| 10-20% | 5 – 6 Homework Assignments |
| 30-40% | 5 Programming Projects |
| 40-50% | Exams (1 or 2 Midterm Exams and a Comprehensive Final Exam) |
| 0-10% | Other (participation, in-class, group activities) |