CSE 332: Data Abstractions

Covers abstract data types and structures including dictionaries, balanced trees, hash tables, priority queues, and graphs; sorting; asymptotic analysis; fundamental graph algorithms including graph search, shortest path, and minimum spanning trees; concurrency and synchronization; and parallelism. Not available for credit for students who have completed CSE 373.

either CSE 311 or CSE 321.

communicate the representation and organization of data in terms of ubiquitious computing abstractions such as stacks, queues, trees, hashtables, and graphs
analyze algorithms for correctness and efficiency, including the use of asymptotic analysis
design parallel programs that use extra computational resources to complete a task more quickly
recognize software errors related to concurrent execution of tasks such as race conditions
create software that implements classic data structures and algorithms and uses such algorithms appropriately

(a) an ability to apply knowledge of mathematics, science, and engineering
(b) an ability to design and conduct experiments, as well as to analyze and interpret data
(c) an ability to design a system, component, or process to meet desired needs within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability
(e) an ability to identify, formulate, and solve engineering problems
(k) an ability to use the techniques, skills, and modern engineering tools necessary for engineering practice
(m) knowledge of discrete mathematics

Review of simple abstract datatypes (2 lecture hours)
- Stacks
- Queues
- Binary Search Trees
Algorithm Analysis (1 lecture hour)
- Simple cost model of operations
- Recurrence relations
Asymptotic Analysis (2 lecture hours)
- Formal definition and informal understanding of big-O, big-Omega, big-Theta
- Running time and space
- Best vs. worst vs. expected case
- Amortized analysis (optional)
Priority Queues (2 lecture hours)
- Binary heaps
- Applications of priority queues, including heapsort
Dictionaries (5 lecture hours)
- Balanced trees, such as AVL Trees, B Trees, Splay Trees, or Red-Black Trees (usually two of these)
- Hashtables
  - Properties of good hashing functions
  - Collision-avoidance strategies (optional: universal hashing)
Sorting (3 lecture hours)
- Comparison-sorting algorithms: Insertion sort, selection sort, merge sort, quick sort, heap sort
- Relative strengths of different sorting algorithms
- Big-Omega nlog n lower-bound for comparison sorting
- Non-comparison sorts such as radix sort
Graphs (4 lecture hours)
- Graph terminology (nodes, edges, paths, cycles, weights, etc.)
- Graph representations: adjacency-matrix and adjacency list
- Graph traversal strategies
- Topological sort
- Algorithms for shortest paths
- Algorithms for minimum spanning trees
Parallel Programming (4 lecture hours)
- Shared-memory programming model with explicit threads
- Divide-and-conquer parallelism for map and reduce operations
- Example of a non-trivial parallel algorithm, such as parallel prefix
- Asymptotic analysis of parallel algorithms
- Amdahl's law
Concurrent Programming (3 lecture hours)
- Need for synchronization to control access to shared resources
- Race conditions
- Deadlock
- Passive waiting e.g., with condition variables (optional)