Data Structures and Algorithms

Notes from Steven Skiena’s The Algorithm Design Manual and AlgoMonster.

The Algorithm Design Manual

Algorithmic Analysis

• Algorithmic Correctness
• RAM Model of Computation
• Algorithmic Complexity
• Big O Notation
  • Operations with Big O
• Logarithmic Algorithms

Data Structures

Basic Data Structures

• Contiguous vs Linked Data Structures
• Array
  • Dynamic Array
• Pointers
• Linked List
• Stacks and Queues
• Dictionary
  • Dictionary Implementations
• Priority Queue
  • Priority Queue Implementations
• Heap

Trees

• Trees
• Binary Tree
• Binary Search Tree
  • Balanced Binary Tree
    • Red-black trees
    • AVL trees
• Tree Traversal

Hashing

• Hashing
  • Hash Table Example
• Hash Collision
  • Separate Chaining
  • Open Addressing
• Duplicate Detection via Hashing
• Canonicalization
• Compaction

Sorting

• Sorting Algorithms
• Comparison Function
• Selection Sort
• Insertion Sort
• Heapsort
  • Heaps
• Mergesort
• Quicksort
• Bucketsort
• Sorting Algorithm Lower Bounds

Divide and Conquer

Basic Divide and Conquer Algorithms

• Divide and Conquer Algorithms
• Binary Search
• Occurrence Counting
• One-sided Binary Search
• Square Root with Binary Search
• Fast Exponentiation Algorithm

Recurrence Relations

• Recurrence Relations
• Divide and Conquer Recurrences

Other Divide and Conquer

• Fast Multiplication Algorithms
• Largest Subrange and Closest Pair
• Parallel Algorithms
• Convolution Algorithm
  • Applications of Convolution

Hashing & Randomized Algorithms

• Randomized Algorithms

Graph Traversal

Depth First Search

• Depth First Search
  • Depth First Search on Trees

Breadth First Search

• Breadth First Search

Weighted Graph Algorithms

Combinatorial Search

• Backtracking
• Tree Pruning
• Backtracking Aggregation
• Memoization

Dynamic Programming

NP-Completeness

Dealing with Hard Problems

Miscellaneous