Data Structures

Notes:

Because several sections of this important core course are offered each semester, a course “coordinator” is assigned to develop the syllabus, course schedule and programming project descriptions. The course coordinator will consult with the other instructors regarding the schedule and programming assignments before and during the semester.

All instructors are will follow the schedule developed by the coordinator. Individual instructors are responsible for creating their exams.

The instructor for the “honors” section may choose to modify the programming assignments or offer different programming projects as appropriate.

Prerequisites

B or better in CMSC 202 (generic classes, interfaces, recursion)

C or better in CMSC 203 (counting, formal mathematical proof techniques)

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

The student will be able to

1. Analyze common operations performed on a variety of data structures using asymptotic and amortized analysis as appropriate.
2. Perform common operations on a variety of data structures using the appropriate algorithms.
3. Prove theorems regarding the performance of common operations on a variety of data structures.
4. Effectively use software development tools such as Eclipse, CVS and ant.
5. Use and/or modify and/or implement data structures in a complex application including recursive solutions as appropriate
6. Choose an appropriate implementation of a data structure based on application requirements.

Program Outcomes

CMSC 341 supports the CMSC program outcomes:

• (O1) and (O3) through development of large programming assignments in Java
• (O5) through analyzing various algorithms for operations on a variety of data structures.

Text

Data Structures and Algorithm Analysis in Java 2nd Edition, by Mark Alan Weiss, Addison-Wesley, ISBN 0-321-37013-9 (required)

Topics

• CVS and ant
• 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
• K-d trees
• B-Trees
• Treaps
• Skiplists
• Hash Tables
• Union-Find for disjoint sets
• Graphs
• 1-2 weeks of additional topics

Grading

Updated December 5, 2011