CS 251: Data Structures

Revised June 13, 2016

Prerequisite:

CS 18200 (Foundations of Computer Science)
CS 24000 (Programming in C)

Detailed Syllabus:

1. Running time analysis of algorithms and their implementations
   1. Review of proof methods and mathematics concepts
   2. Mathematical induction and recursion
   3. Experimental running time analysis
      • Benchmarking, counting instructions
      • Importance of constants
   4. Asymptotic running time analysis
      • Big-O and Theta notations
      • Best, expected, worst case running times.
      • Comparison of log n vs. constants, linear vs. quadratic vs. exponential running times.
2. Review of basic data structures
   1. Abstract data types (ADTs) and common operations
      • 1- and 2-dimensional arrays; dynamic arrays
      • Linked lists
      • Stacks, queues
   2. Comparison of different implementations of stacks and queues
3. Trees
   1. Trees
      • Definitions, ADTs
      • Pointer-based implementations
      • Different traversals and tree explorations
   2. Binary trees
      • Properties of binary trees, ADTs
      • Traversals
      • Representing and manipulating arithmetic expressions
4. Searching and Sorting
   1. Binary search
   2. Basic sorting algorithms: Bubble sort, Selection sort, Insertion sort
   3. Sorting Algorithms with a good performance: Mergesort, Qucksort
   4. Sorting algorithms not based on comparisons: Bucket and Counting sort, Radix sort
5. Heaps
   1. Definition, properties, ADTs
   2. Array implementation of heaps
   3. Priority queue operations: Insertion and min/max extraction
   4. Building a heap (insertions versus bottom-up heap construction)
   5. Heapsort
6. Binary search trees
   1. Binary search trees
      • Properties, performance, ADTs
      • Basic operations: search, insert, delete
   2. Balanced search trees
      • Properties, performance, ADTs
      • Red-black trees, 2-3 trees
      • Keeping a search tree balanced under insertions and deletions
7. Hashing
   1. ADTs and implementations
   2. Hash functions
   3. Collision handling schemas (open hashing, linear probing, double hashing)
   4. Impact of hash table size and load factors on performance
8. Other data structures
   1. Data structures for Union-Find operations
   2. Spatial data structures and spatial queries
9. Strings
   1. Tries
      • Representations, operations
      • Variations: ternary and suffix tries
   2. Data compression, generating Huffman codes
   3. Substring searches and other operations on string
      • Simple algorithms
      • Boyer-Moore, Knuth-Morris-Pratt
10. Introduction to graphs
    1. Definitions, terminology, properties, ADTs
    2. Implementations: Edge list, Adjacency list, Adjacency matrix
11. Undirected graphs
    1. Depth-first search
    2. Breadth-first search
    3. Finding connected components
12. Directed graphs
    1. Depth- and breadth-first search revisited
    2. Topological sorting and its applications
    3. Strongly-connected components (optional)
13. Selected graph algorithms
    1. Shortest paths (Dijkstra and Bellman Ford)
    2. Minimum-cost spanning trees (Prim and Kruskal)