CS 515: Data Structures
(Coordinator: Karen Jin)
Catalog description
This class has a number of goals: to provide an introduction to the C++ programming language; to provide an introduction to address and dynamic memory manipulation; to provide an introduction to the analysis of algorithms; to introduce a number of sorting algorithms; to introduce more advanced data structures; and to provide an insight as to how the basic and advanced data structures may be implemented. Prereq: CS 416.
Attributes
 This course is one of the required courses for CS majors.
Outcomes
 methodologies of software development: Objectoriented programming; software testing and debugging.
 principles of data structures: implementation of basic to more advanced data structures; use appropriate data structures and Abstract Data Types (ADTs) under a given set of constraints.
 fundamental computer science algorithms: Understand and apply algorithms to solve moderately complex problems; understand algorithm classes such as backtracking, divideandconquer, dynamic programming, randomized algorithms and greedy algorithms.
 concepts of programming languages: C++ programming language.
 think abstractly and reason logically about computer science problems: Determine the efficiency category of algorithms (including sorts and searches), data structure operations, and code segments using big O notation. Evaluate tradeoffs in data structure and algorithm selection.
Evaluation
Weekly programming assignments (40%), weekly labs (25%), midterm exam (15%) and final exam (20%).
Topics

C++ fundamentals and language features:
 basic C++, memory model, pointers and reference types, file I/O
 functions and parameter passing; object and class;
 class and function template; standard template library
 operator overloading;
 inheritance and polymorphism

Abstract Data Types (ADTs) and concrete data structures:
 basic data structures: linkedlist, stack, queue, binary search tree
 introduction to amortized analysis.
 skiplists and introduction to randomized algorithms.

map and set ADTs:
 implementation with balanced search tree
 AVL tree, redblack tree, 2–3–4 tree, Btree

hashing:
 hash function, collision resolution, closed hashing and open addressing
 Cuckoo hashing
 map ADT and set ADT using hash tables, performance analysis and comparison.

priority queue ADT:
 binary heap, Floyd algorithm
 implement priority queue using a binary heap

trie:
 map ADT and set ADT using tries, performance analysis and comparison.
 Hoffman encoding and introduction to greedy algorithms

sorting algorithms:
 tree sort, heap sort, merge sort and quicksort
 lower bound of comparison based sorting algorithms
 bucket sort and radix sort

graph algorithms:
 graph representations, depthfirst and breadthfirst graph traversals
 minimal spanning tree algorithms: Kruskal’s algorithm, Prim’s algorithm
 shortest path algorithms: Dijkstra’s algorithm, FolydWarshall’s algorithm, BellmanFord’s algorithm
 introduction to dynamic programming algorithms.
Textbooks
Recommended:
 Mark Allen Weiss. Data Structures and Algorithm Analysis in C++, 4th edition, 2013.
 Stanley Lippman et al. C++ Primer, fifth edition, 2012.