Algorithms in Algorithm Design

Summary

Personal implementation of Algorithm Design (Jon Kleinberg and Éva Tardos, 1st Edition, ISBN: 9780321295354) in Java.

Introduction

• Gale-Shapley - for Stable Matching Problem. Section 1.1, 9/6/2018

Graphs

• Adjacency List - a way to represent graph, support the implement of BFS and DFS. 9/22/2018
• Breadth-First Search - BFS for graph traversal. Section 3.3, 9/22/2018
• Depth-First Search - DFS for graph traversal. Section 3.3, 9/22/2018
• Find Topological Ordering - show the topological ordering of a DAG. Section 3.6, 9/24/2018
• Bipartite Graph - generate, label, and test a bipartite graph. To help the implementation of the Bipartite Matching Problem. Section 3.4, 11/14/2018

Greedy Algorithm

• Interval Scheduling - interval scheduling problem. Section 4.1, 10/5/2018
• Interval Partitioning - interval partitioning problem (interval coloring problem). Section 4.1, 10/5/2018
• Minimizing Lateness - scheduling to minimize lateness. Section 4.2, 10/5/2018
• Dijkstra's Algorithm - single-pair shortest path problem. Section 4.4, 10/7/2018
• Prim's Algorithm - minimum spanning tree problem. Section 4.5, 10/8/2018
• Union-Find Data Structure - help to implement Kruskal's Algorithm. Section 4.6, 10/8/2018
• Kruskal's Algorithm - another algorithm to solve minimum spanning tree problem. Section 4.6, 10/8/2018

Dynamic Programming

• Weighted Interval Scheduling - a version of interval scheduling problem with weight. Section 6.1, 11/3/2018
• Segmented Least Squares - segmented least squares problem. Section 6.3, 11/3/2018
• Knapsack Problem - a pseudo-polynomial time algorithm for Knapsack Problem. Section 6.4, 11/4/2018
• Sequence Alignment Problem - an algorithm for Sequence Alignment Problem. Section 6.6, 11/4/2018
• Bellman-Ford Algorithm - an algorithm for shortest path problem (with negative edges). Section 6.8, 11/10/2018

Network Flow

• Ford-Fulkerson Algorithm - find max flow in graph. Section 7.1, 11/11/2018.
  Update: two versions with improved time complexity by shortest augmenting path or capacity scaling. Section 7.3, 11/14/2018.
• Bipartite Matching - use max flow to find matching in a bipartite graph. Section 7.5, 11/15/2018.

Others

personal implementation of some useful algorithms and data structure.

• Trie Data Structure - use trie to speedup looking up word and finding prefixes. C++, 3/22/2019