Before the annual leave, I set myself to complete more and more tasks, to do some meaningful things, reading, practicing, output some valuable words and notes is the realization of this idea, which will not only make my own experience more beautiful, but also help many others!
The JVM is a perennial test for Java programmers, and algorithms are a perennial test for all programmers. This should be a common understanding of many people, no matter who, on the way to study we often encounter confusion stage, grasp the most fundamental things you will never feel lost.
The Algorithm (4th edition) is an obscure book, especially the Chinese version! I would like to strongly ridicule the Chinese translation, because this book is highly rated in the industry, when I was interested to start to review, but was mouth wound Chinese reading out of breath, so I delayed for a long time finally in this year’s annual leave to slowly take out the English version of the translation!
Removal of basic data structure is introduced, in big ways, there are four large, sorting, searching, figure, strings, each chunk of basic content has 5 day, every day and there will be 4 ~ 5 kinds of algorithm implementation and interpretation, a total of more than 80 algorithm type, illustrated, is indeed a good book (except for translation).
In this way, I hope to motivate myself to finish the book, and also hope to help some students who are preparing for interviews and also preparing to review algorithms. I think the essence of the book is the illustrations, so I used almost all of the illustrations to help you understand this, you can see the 3-3-balanced search tree notes, and then the key code is posted for each one, So I can look at the code if I don’t understand it when I review it later. This note will be updated at any time after I review it repeatedly. It is expected that when I brush LeetCode in the future, I will also put the corresponding reminder in the corresponding chapter. If you have other suggestions, you are welcome to issue them.
Github: github.com/MeandNi/Alg…
Notes directory
- Chapter02-Sorting
- 2-1- Primary sorting algorithm
- 2 minus 2 minus merge sort
- 2-3- Quicksort
- 2-4- Priority queue
- 2-5- Sort applications
- Chapter03-Searching
- 3-1 – the symbol table
- 3-2- Binary search tree
- 3-3- Balance the search tree
- 3-4 – a hash table
- 3-5- Summary and application
- Chapter04-Graphs
- Chapter05-String
- 5-1- String sort
All the algorithms in the book
Sorting:
| ALGORITHM | CODE | IN PLACE | STABLE | BEST | AVERAGE | WORST | REMARKS |
|---|---|---|---|---|---|---|---|
| Selection sort | Selection.java | ✔ | 1/2 leveln 2 | 1/2 leveln 2 | 1/2 leveln 2 | n exchanges; quadratic in best case | |
| Insertion sort | Insertion.java | ✔ | ✔ | n | Quarter ofn 2 | 1/2 leveln 2 | use for small or partially-sorted arrays |
| Bubble sort | Bubble.java | ✔ | ✔ | n | 1/2 leveln 2 | 1/2 leveln 2 | rarely useful; use insertion sort instead |
| Hill sorting | Shell.java | ✔ | n log3 n | unknown | c n 3/2 | tight code; subquadratic | |
| Merge sort | Merge.java | ✔ | 1/2 leveln lg n | n lg n | n lg n | n log n guarantee; stable | |
| Quick sort | Quick.java | ✔ | n lg n | 2 n ln n | 1/2 leveln 2 | n log n probabilistic guarantee; fastest in practice | |
| Heap sort | Heap.java | ✔ | n † | 2 n lg n | 2 n lg n | n log n guarantee; in place |
Priority queue
| DATA STRUCTURE | CODE | INSERT | DEL-MIN | MIN | DEC-KEY | DELETE | MERGE |
|---|---|---|---|---|---|---|---|
| An array of | BruteIndexMinPQ.java | 1 | n | n | 1 | 1 | n |
| Binary heap | IndexMinPQ.java | log n | log n | 1 | log n | log n | n |
| d-way heap | IndexMultiwayMinPQ.java | logd n | d logd n | 1 | logd n | d logd n | n |
| The binomial heap | IndexBinomialMinPQ.java | 1 | log n | 1 | log n | log n | log n |
| Fibonacci heap | IndexFibonacciMinPQ.java | 1 | log n † | 1 | 1 † | log n † | log n |
To find the
| worst case | average case | ||||||
|---|---|---|---|---|---|---|---|
| DATA STRUCTURE | CODE | SEARCH | INSERT | DELETE | SEARCH | INSERT | DELETE |
| In order to find(Unordered list) | SequentialSearchST.java | n | n | n | n | n | n |
| Binary search(Ordered list) | BinarySearchST.java | log n | n | n | log n | n | n |
| Binary tree(Unbalanced) | BST.java | n | n | n | log n | log n | sqrt(n) |
| Red-black binary tree(left) | RedBlackBST.java | log n | log n | log n | log n | log n | log n |
| Hash table(Separated link method) | SeparateChainingHashST.java | n | n | n | 1 † | 1 † | 1 † |
| Hash table(Linear detection) | LinearProbingHashST.java | n | n | n | 1 † | 1 † | 1 † |
figure
| PROBLEM | ALGORITHM | CODE | TIME | SPACE |
|---|---|---|---|---|
| The path | DFS | DepthFirstPaths.java | E + V | V |
| Shortest path (least edge) | BFS | BreadthFirstPaths.java | E + V | V |
| ring | DFS | Cycle.java | E + V | V |
| Directed path | DFS | DepthFirstDirectedPaths.java | E + V | V |
| Shortest directed path (least edge) | BFS | BreadthFirstDirectedPaths.java | E + V | V |
| Have to ring | DFS | DirectedCycle.java | E + V | V |
| A topological sort | DFS | Topological.java | E + V | V |
| bipartiteness / odd cycle | DFS | Bipartite.java | E + V | V |
| Connected components | DFS | CC.java | E + V | V |
| Strongly connected component | Kosaraju – Sharir | KosarajuSharirSCC.java | E + V | V |
| Strongly connected component | Tarjan | TarjanSCC.java | E + V | V |
| Strongly connected component | Gabow | GabowSCC.java | E + V | V |
| Euler loop | DFS | EulerianCycle.java | E + V | E + V |
| Directed Euler cycle | DFS | DirectedEulerianCycle.java | E + V | V |
| Transitive closure | DFS | TransitiveClosure.java | V (E + V) | V 2 |
| Minimum spanning tree | Kruskal | KruskalMST.java | E log E | E + V |
| Minimum spanning tree | Prim | PrimMST.java | E log V | V |
| Minimum spanning tree | Boruvka | BoruvkaMST.java | E log V | V |
| Shortest path (non-negative weight) | Dijkstra | DijkstraSP.java | E log V | V |
| Shortest path (no negative cycle) | Bellman – Ford, | BellmanFordSP.java | V (V + E) | V |
| S shortest path (acyclic) | topological sort | AcyclicSP.java | V + E | V |
| Shortest between all node pairs | Floyd – Warshall | FloydWarshall.java | V 3 | V 2 |
| Maximum flow/minimum cut | Ford, Fulkerson | FordFulkerson.java | E V (E + V) | V |
| Bipartite graph matching | Karp Hopcroft – | HopcroftKarp.java | V1/2 level (E + V) | V |
| Task assignment problem | successive shortest paths | AssignmentProblem.java | n 3 log n | n 2 |