This repository follows Princeton's class, Algorithms, part I and part II on coursera.
This part introduced two basic data structures, queues and stacks. Detailed description of the two data structures and their implementations can be found here.
- Queue
- Stack
-
Problem description:
Given a set of numbers, implement at least two features: union() and find(). Union() method connects two numbers in the set while find() tells if two numbers in the set are connected or not.
- Quick find algorithm
- Quick union algorithm
- Weighted quick union algorithm
- Weighted quick union algorithm with path compression The codes can be found here.
- Detailed description of the algorithms needs to be added. Here I only summarize the complexity of the algorithms.
| Algorithm | Constructor | union() | find() |
|---|---|---|---|
| quick find | O(N) | O(N) | O(1) |
| union find | O(N) | tree height | tree height |
| Weighted quick union | O(N) | O(lgN) | O(lgN) |
| Weighted quick union with path compression | O(N) | ~O(1) | ~O(1) |
-
Elementary sorting algorithms:
- Bubble sort
- Selection sort
- Insertion sort
- Shell sort
-
Advanced sorting algorithms:
- Merge sort
- Quick sort
- Heapsort ( Introduced later in chapter III )
You might want to read my article on these methods here: Sorting Algorithms.
- Binary tree
- 2-3-4 tree
- Red-black tree
- Hash table
- Chaining
- Linear probing
-
Graph representation
- Sparse matrix
- Adjacency list
-
Undirected graph
- Depth-first search (DFS)
- Broadth-first search (BFS)
- Applications:
- Connected components
-
Directed graph (aka Digraph)
- BFS & DFS
- Applications:
- Topological graph
- Strong connected components
- DAG & How to check DAG
-
Edge Weighted Graphs & Minimum spanning tree
- Kruskal algorithm
- Prim algorithm
- Lazy implementation
- Eager implementation
-
Edge Weighted Digraph & Shortest Path
- Dijkstra algorithm
- SP in positive-weight DAG
- Bellman-Ford algorithm
- Negative cycle & how to check negative cycle
- Longest path
-
String Algorithms
- To be added