Algorithms, 4th Edition

Robert Sedgewick and Kevin Wayne
Princeton

Theory

• Big O notation
• Master Theorem

Data Structures

Algorithms

• Binary Search
  • Recursive, Iterative, and Deferred detection of equality [cpp]
  • Floor [cpp]
  • Search with duplicates [cpp]
• Sum Up To ZERO
  • TwoSum [cpp]
  • ThreeSum [cpp]
  • FourSum
• Pseudo Random Number Generators
• Suffling algorithm
  • An amusing anecdote for online poker
  • Recommended card shuffling approach for online casino
    1. get a cryptographically secure pseudo-random number generator
    2. assign a random 64-bit number to each card
    3. sort the cards according to their number
• Array
  • Maximum Subarray [cpp]
• Queue
  • Lock-free queue
  • Priority Queue
    • array
    • binary heap
    • Fibonacci heap
• Tree
  • Siddhartha Sen and Robert E. Tarjan. 2010. Deletion without rebalancing in balanced binary trees. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms (SODA '10). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1490-1499.
  • AVL (simulator 1, simulator 2)
• Hash Table
  • Collision resolution
    • Separate chaining: linked lists, list head cells, self-balancing tree, or dynamic array.
    • Open addressing (closed hashing, the location of the value is not determined by the key): linear probing, quadratic probing, or double hashing.
    • Cuckoo hashing
• Disjoint Set
• Karatsuba algorithm
• Geometric series
• Change of Base of Logarithm
• Streaming Algorithms