My coding exercise when studying algorithms, data structures, solving games and puzzles.

Algorithms

Sorting

Comparison-based sorting: these models must take at least Ω(nlogn) steps

• Bubble sort
• Selection sort
• Insertion sort
• Merge sort
• Quick sort
• Heap sort

Linear-time sorting:

• Counting sort
• Radix sort
• Bucket sort
• Linear select

Divdide and Conquer

• An algorithm which is faster than the quadratic "grade school" by turning original problem into smaller problems (karatsuba-multiplication)
• Find the maximum profit of 1 time buying and selling stock, given the stock price (maximum-subarray)
• Find a lowest altitude that a ball can roll into compared to its neighbors(local-minimum)
• Measure the similarity between users about ranking favorite movies - collaborative filtering technique (counting-inversions)
• (closest-pair)
• An algorithm with faster running time comparing to normal matrix multiplication we take from linear algebra course (strassen-matrix-multiplication)

Backtracking

• N-Queens
• Knapsack
• Maze
• Color graph

Dynamic Programming

• Cut Rod
• Fibonacci
• Knapsack
• Longest common sequence

Data Structures

Trees

• Binary search trees
• Red-black trees
• B-tree
• Heap
• Hash tables

Graphs

• Undirected and directed graph class (graph_hash.py vs graph_linked_list.py)
• DFS and typological sorting - Sort clothing when getting dressed or scheduling classes' order based on its prequeresite (graph_hash.py vs graph_linked_list.py)
• DFS and simple path - How many ways get to B from A? (graph_hash.py vs graph_linked_list.py)
• DFS and strongly connected components - Used in detecting network failure, data visualization and clustering (graph_hash.py vs graph_linked_list.py)
• BFS and shortest path - Find a Bacon number, which is the number of degrees of separation from an actor to Kevin Bacon (graph_hash.py vs graph_linked_list.py)
• BFS and bipartiteness testing - Seperate objects into two so that it will not conflict with the other (graph_hash.py vs graph_linked_list.py)
• Dijkstra's - Find the shortest path in non-negative weighted graph (graph_weight.py)
• Bellman Ford - Find the shortest path in graph which has negative weights (graph_weight.py)
• DAG shortest paths - An algorithm of PERT application, which helps arrange and performs tasks more efficiently (graph_weighted.py)
• Floyd Warshall - Find all pairs shortest path (graph_weighted.py)
• Johnson - Find all pairs shortest path (graph_weighted.py)
• Transitive Closure - Check if there is a path from one destination to another detination (graph_weighted.py)