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

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

  (*) indicates optional materials most likely 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 (*)