xiaonanln/study-algorithm-design

Write code to study Algorithm Design

study-the-algorithm-design-manual

Write python code to study 《The Algorithm Design Manual》

Data Structures & Algorithms

Sorting

• Insertion Sort
• Selection Sort
• Heap Sort
• Merge Sort
• Quick Sort
• 3-Way Quick Sort
• Radix Sort
• Shell Sort

Heap

• Heap
• Priority Queue

Tree

• Binary Tree
• B-Tree
• Trie
• Binary Indexed Tree

Graph

• DFS

• BFS

• Connected Components

• Two Color (bipartite)

• Finding Cycles (graph & digraph)

• Articulation Vertices

• Digraph DFS Orders (pre & post & reversePost)

• Topological Sorting

• Strongly Connected Components

• Minimal Spanning Tree

  • Prim's Algorithm
  • Prim's Algorithm using Priority Queue
  • Kruskal's Algorithm

• (All-Pairs) Shortest Path

  • Dijkstra's Algorithm
  • Floyd's Algorithm

• Union Find

  • My Stupid Union Find Algorithm
  • Union Find with Path Compression and Union by Rank

• Network Flows (not understand yet)

Backtracking

• Construct All Subsets
• Construct All Permutations
• Construct All Paths in a Graph (from s to t)
• Solve Sudoku (find one in leetcode)

Dynamic Programming

• Floyd's Algorithm

• Binomial Coefficients

• Edit Distance

• Maximum Monotone Subsequence

• Longest Increasing Subsequence

• Integer Partition problem (P.294 not read yet)

• 背包九讲V2

• Tushar Roy's Playlist On Dynamic Programming

  • 0-1 Knapsack Problem
  • Longest Common Subsequence
  • Matrix Chain Multiplication
  • Subset Sum Problem
  • Optimal Binary Search Tree
  • Coin Changing Minimum Coins
  • Longest Increasing Subsequence
  • Minimum Edit Distance
  • Longest Palindromic Subsequence
  • Coin Changing Number of ways to get total
  • Weighted Job Scheduling
  • Egg Dropping
  • Cutting Rod

Algorith Design by Jon Kleinberg, Eva Trados

• 1.1 Gale-Shapley
• 4.1 Internal Scheduling
• 4.8 Huffman Codes (Greedy Algorithm)
• 4.9 Minimum-Cost Arborescences (Greedy Algorithm)
• 5.3 Counting Inversions (Divide and Conquer)
• 5.4 Finding the Closest Pair of Points (Divide and Conquer)

Data Structures

• B-Tree (P.370)
• Skip List (P.371)
• Suffix Tree (P.377)
• Bloom Filter (P.386)
• Kd-Trees (P.389)
  • Quadtree or Octtree
  • BSP-tree
  • R-tree

Classic Leetcode Problems

• 33. Search in Rotated Sorted Array
• 677. Map Sum Pairs (Trie)