W3136: Essential Data Structures in C/C++
==========================================

Tentative list of topics
-------------------------

  (*) indicates optional materials most likely not covered

  Coverage indicators for Spring 2013 class:
    '!' means that the topic was covered
    '/' means that the topic was kinda covered, but not completely
    '#' means that the topic was not covered

Getting started: C programming in UNIX environment I

  ! Basic UNIX commands
  ! Compiling and linking multiple source files
  ! Writing Makefiles
  ! Using source code version control system

C language I: fundamentals

  ! Data types
  ! Expressions and statements
  ! Using arrays
  ! Automatic vs. Static variables

Array-based data structures & algorithms I

  / List, stack, queue
  # Applications: ex) evaluating postfix expressions
  ! Recursion
  / Binary search
  ! Sorting: Insertion sort, Merge sort
  / Running time analysis & Big-O notation

Array-based data structures & algorithms II

  # Introduction to priority queues (*)
  # Introduction to quick sort (*)

C language II: memory management

  ! Pointers and arrays
  ! Call-by-reference using pointers
  ! Heap memory allocation
  ! Char array, aka strings
  ! Pointer to pointer
  ! Debugging memory errors using Valgrind

Abstract Data Types (ADT) in C

  ! Callbacks using pointer to function
  ! Linked list 
  ! Revisiting list, stack, queue 
  # Creating and using libraries (*)

C programming in UNIX environment II: I/O

  ! stdin, stdout and stderr
  ! I/O redirection and pipes in UNIX shell
  ! Formatted I/O
  ! File I/O (*)

Moving up to C++: fundamentals

  ! Object construction, destruction, and copy
  ! Stack v. Heap allocations
  ! Pointer v. Reference
  ! Implementing a string ADT

Object-oriented programming (OOP) in C++

  # Inheritance and polymorphism
  # Static members and methods
  # Design patterns in C++ (*)

Trees

  ! Binary tree: ex) expression tree
  ! Binary Search Tree (BST)
  / Analysis of BST (*)
  # Introduction to Red-Black Tree (*)

Graphs

  ! Graph data structures
  ! Graph traversals: DFS & BFS
  # Shortest paths: Dijkstra's algorithm
  # Minimum spanning tree (*)
  # Introduction to NP-Completeness (*)

Generic programming in C++

  ! Templates
  ! Containers in Standard Template Library (STL)
  # Implementing smart pointer using reference counting

Hash tables

  # Hashing functions and rehashing
  # Linked list revisited: wrapping legacy code with new interface
  # Implementing a generic hash table
  # Looking into STL's hash table implementation (*)