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

• FrequencyCounter.java (Page 371)
• SequentialSearchST.java (Page 374)
• BinarySearchST.java (Page 378)

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)