182 lines (144 loc) · 14.2 KB

Algorithms_Princeton_Java

This repository is used to store files generated during my learning process of the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. The official website of the book can be found here.

All .java source files are stored in directory src, and all data files used to test .java files are stored in directory data.

The .java files and their page numbers (that the corresponding topic first appears) on the textbook including:

Chapter 1: Fundamentals

1.1 Basic Programming Model

BinarySearch.java (Page 46)

1.2 Data Abstraction

Date.java (Page 78)
Transaction.java (Page 78)
Counter.java (Page 84)
Flips.java (Page 84)
Accumulator.java (Page 92)
VisualAccumulator.java (Page 94)
StaticSetOfInts.java (Page 98)
WhiteList.java (Page 98)

1.3 Bags, Queues and Stacks

Stats.java (Page 124)
ReadInts.java (Page 126)
Reverse.java (Page 127)
Evaluate.java (Page 128)
FixedCapacityStackOfStrings.java (Page 132)
FixedCapacityStack.java (Page 134)
ResizingArrayStack.java (Page 136)
LinkedStack.java (Page 147)
LinkedQueue.java (Page 150)
LinkedBag.java (Page 154)

1.4 Analysis of Algorithms

ThreeSum.java (Page 173)
StopWatch.java (Page 174)
DoublingTest.java (Page 176)
TwoSumFast.java (Page 189)
ThreeSumFast.java (Page 190)
DoublingRatio.java (Page 192)

1.5 Case Study: Union-Find

QuickFindUF.java (Page 222)
QuickUnionUF.java (Page 224)
WeightedQuickUnionUF.java (Page 228)
OptimalUF.java (Page 231)

Chapter 2: Sorting

2.1 Elementary Sorts

Selection.java (Page 248)
Insertion.java (Page 250)
InsertionX.java (Page 252)
SortCompare.java (Page 254)
Shell.java (Page 258)

2.2 Mergesort

Merge.java (Page 270)
MergeBU.java (Page 277)

2.3 QuickSort

Quick.java (Page 288)
Quick3way.java (Page 296)

2.4 Priority Queues

TopM.java (Page 310)
MaxPQ.java (Page 313)
MinPQ.java (Page 313)
Multiway.java (Page 319)
IndexMaxPQ.java (Page 320)
IndexMinPQ.java (Page 320)
Heap.java (Page 323)

Chapter 3: Searching

3.1 Symbol Tables

3.2 Binary Search Trees

BST.java (Page 397)

3.3 Balanced Search Trees

RedBlackBST.java (Page 432)

3.4 Hash Tables

SeparateChainingST.java (Page 464)
LinearProbingHashST.java (Page 469)

3.5 Applications

SET.java (Page 489)
DeDup.java (Page 490)
WhiteFilter.java (Page 491)
BlackFilter.java (Page 491)
LookupCSV.java (Page 492)
LookupIndex.java (Page 496)
FileIndex.java (Page 498)
SparseVector.java (Page 502)

Chapter 4: Graphs

4.1 Undirected Graphs

Graph.java (Page 522)
DepthFirstSearch.java (Page 530)
DepthFirstPaths.java (Page 535)
BreadthFirstPaths.java (Page 538)
CC.java (Page 543)
Cycle.java (Page 546)
TwoColor.java (Page 546)
SymbolGraph.java (Page 548)
DegreesOfSeparation.java (Page 553)

4.2 Directed Graphs

Digraph.java (Page 568)
SymbolDigraph.java (Page 568)
DirectedDFS.java (Page 570)
DepthFirstDirectedPaths.java (Page 573)
BreadthFirstDirectedPaths.java (Page 573)
DirectedCycle.java (Page 574)
DepthFirstOrder.java (Page 578)
Topological.java (Page 578)
TopologicalX.java (Page 583)
KosarajuSCC.java (Page 584)
TransitiveClosure.java (Page 590)

4.3 Minimum Spanning Trees

Edge.java (Page 608)
EdgeWeightedGraph.java (Page 608)
LazyPrimMST.java (Page 616)
PrimMST.java (Page 620)
KruskalMST.java (Page 624)

4.4 Shortest Paths

DirectedEdge.java (Page 641)
EdgeWeightedDigraph.java (Page 641)
DijkstraSP.java (Page 652)
DijkstraAllPairsSP.java (Page 656)
AcyclicSP.java (Page 658)
AcyclicLP.java (Page 661)
CPM.java (Page 663)
BellmanFordSP.java (Page 668)
EdgeWeightedDirectedCycle.java (Page 677)
Arbitrage.java (Page 679)

Chapter 5: Strings

Alphabet.java (Page 698)
Count.java (Page 699)

5.1 String Sorts

LSD.java (Page 706)
MSD.java (Page 710)
Quick3string.java (Page 719)

5.2 Tries

TrieST.java (Page 732)
TST.java (Page 746)

5.3 Substring Search

KMP.java (Page 762)
BoyerMoore.java (Page 770)
RabinKarp.java (Page 774)

5.4 Regular Expressions

NFA.java (Page 794)
GREP.java (Page 804)

5.5 Data Compression

BinaryDump.java (Page 813)
Genome.java (Page 819)
RunLength.java (Page 822)
Huffman.java (Page 826)
LZW.java (Page 839)