CS 515: Data Structures
(Coordinator: Karen Jin)
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.
- This course is one of the required courses for CS majors.
- methodologies of software development: Object-oriented 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, divide-and-conquer, 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 trade-offs in data structure and algorithm selection.
Weekly programming assignments (40%), weekly labs (25%), midterm exam (15%) and final exam (20%).
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: linked-list, 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, red-black tree, 2–3–4 tree, B-tree
- 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
- map ADT and set ADT using tries, performance analysis and comparison.
- Hoffman encoding and introduction to greedy algorithms
- tree sort, heap sort, merge sort and quicksort
- lower bound of comparison based sorting algorithms
- bucket sort and radix sort
- graph representations, depth-first and breadth-first graph traversals
- minimal spanning tree algorithms: Kruskal’s algorithm, Prim’s algorithm
- shortest path algorithms: Dijkstra’s algorithm, Folyd-Warshall’s algorithm, Bellman-Ford’s algorithm
- introduction to dynamic programming algorithms.
- Mark Allen Weiss. Data Structures and Algorithm Analysis in C++, 4th edition, 2013.
- Stanley Lippman et al. C++ Primer, fifth edition, 2012.