Midterm Topics
++++++++++++++++++++++++++++++++++++++++++++

Algorithmic Analysis (Chapters 2 & 3)
=================================
Big-Oh Notation
Properties of Growth-rate Functions
Common Growth Rates


Divide and Conquer (Chapter 4)
=================================
Major components
Recursion


Priority Queues & Heaps (Chapter 6)
=================================
Advantages
Definition for validity
Operations and their run times


Sorting Exercises (execution and run times) (Chapters 2, 6, 7, 8 & 9)
=================================
Insertion sort (Chapter 2)
Heapsort (Chapter 6)
Mergesort
Quicksort (Chapter 7)
Bucket sort
Radix sort


Dynamic Data Structures (Chapters 10 & 12)
=================================
Stacks and Queues (Chapter 10)
+ Operations
Linked Lists (Chapter 10)
Binary Search Trees (Chapter 12)
+ Operations and their run times


Hashing (Chapter 11)
=================================
Basics of hashing
+ Hash table
+ Hash function
+ Separate Chaining      
+ Collision
+ Uniform hash function
+ Open addressing
+ Primary clustering
+ Secondary clustering
+ Load factor alpha
When to use a hash table (and when not to)
Average case efficiency for hash table operations:
Properties of an ideal hash function
Need to be careful about the constants in hash functions (to avoid various issues like collisions, not cycling through all of the slots for open addressing, etc)
Which strategy to use when (separate chaining, double hashing)
Worst case efficiency for hash table operations


Dynamic Programming (Chapter 15)
=================================
Definition & necessary conditions
Elements of dynamic programming
+ Optimal substructure
+ Overlapping subproblems
Applications
+ Rod Cutting
+ Knapsack


Greedy Algorithms (Chapter 16)
=================================
Elements of a greedy strategy
+ Greed-choice property
+ Optimal substructure
Applications
+ Activity-selection problem
+ Huffman codes
+ Knapsack


Elementary Graph Algorithms (Chapter 20)
=================================
Terminology
Sparse vs dense
Graph Implementation Options (including advantages and disadvantages)
1) Adjacency list
2) Adjacency matrix
Two common operations on graphs
Run-times for basic operations on each graph implementation
Graph Traversals
Depth-First Search (DFS)
Breadth-First Search (BFS)
Topological Sorting