Skip to content

Personal implementation of algorithms in Algorithm Design and some other useful algorithms and data structures

License

Notifications You must be signed in to change notification settings

yinengy/Algorithm-Implementation

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

75 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

Dynamic Programming

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

About

Personal implementation of algorithms in Algorithm Design and some other useful algorithms and data structures

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published