Skip to main content
Search Context

CMSC 341 Syllabus

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)

 

Updated June 19, 2023 by JD and JK