Algorithms API Documentation

Based on the book by Robert Sedgewick and Kevin Wayne: "Algorithms", 4th edition. This code base is mostly for exploration of the topic of the book.

• AlgorithmsSW: Detailed descriptions of all APIs, classes, methods, and more.
• DataStructures: Provide default implementations of common data structures.

My purpose

I wanted to get experience with programming algorithms, including:

• Writing them as readable as possible. It annoys me how poorly written algorithms are (in textbooks, papers and Wikipedia). nk readability is important at writing correct code.
• Developing debugging techniques.
• Getting experience with using Unit tests to ensure correctness.
• To write documentation for the algorithms (although there is a lot lacking).
• To get experience with measuring performance and optimizing algorithms.

Contents

(This list is incomplete; I only started my method to mark code recently, so not everything is marked yet.)

Chapter 1

Page References

• Page 121: Class IStack<T>
• Page 121: Class IQueue<T>
• Page 121: Class IBag<T>
• Page 135: Class FixedCapacityStack<T>

Algorithms

• Algorithm 1.1: Class StackWithResizeableArray<T>
• Algorithm 1.2: Class StackWithLinkedList<T>
• Algorithm 1.3: Class QueueWithLinkedList<T>
• Algorithm 1.4: Class BagWithLinkedList<T>
• Algorithm 1.5: Class UnionFind

Section 3

• Exercise 1.3.1: Property IsFull
• Exercise 1.3.4: Method AreDelimitersBalanced
• Exercise 1.3.7: Property Peek
• Exercise 1.3.14: Class QueueWithResizeableArray<T>
• Exercise 1.3.19: Method RemoveLast
• Exercise 1.3.24: Method RemoveAfter
• Exercise 1.3.25: Method InsertAfter
• Exercise 1.3.30: Method Reverse
• Exercise 1.3.31: Class DoublyLinkedList<T>
• Exercise 1.3.32: Class Steque<T>
• Exercise 1.3.33: Class DequeWithDoublyLinkedList<T>
• Exercise 1.3.37: Method JosephusSequence
• Exercise 1.3.39: Class RingBuffer<T>
• Exercise 1.3.44: Class GapBufferWithStacks<T>
• Exercise 1.3.50: Method GetEnumerator

Chapter 2

Page References

• Page 309: Class IPriorityQueue<T>

Algorithms

• Algorithm 2.1: Method SelectionSort
• Algorithm 2.2: Method InsertionSort
• Algorithm 2.3: Method ShellSortWithPrattSequence
• Algorithm 2.4: Method MergeSort
• Algorithm 2.5: Method QuickSort
• Algorithm 2.6: Class FixedCapacityMinBinaryHeap<T>
• Algorithm 2.7: Method HeapSort

Section 1

• Exercise 2.1.14: Method DequeueSortWithDeque
• Exercise 2.1.14: Method DequeueSortWithDeque
• Exercise 2.1.14: Method DequeueSortWithQueue

Section 2

• Exercise 2.2.14: Method Merge
• Exercise 2.2.15: Method MergeSortBottomsUpWithQueues
• Exercise 2.2.16: Method MergeSortNatural
• Exercise 2.2.22: Method Merge3Sort
• Exercise 2.2.22: Method MergeKSort
• Exercise 2.2.25: Method MergeK

Section 4

• Exercise 2.4.3: Class PriorityQueueWithOrderedArray<T>
• Exercise 2.4.3: Class PriorityQueueWithOrderedLinkedList<T>
• Exercise 2.4.3: Class PriorityQueueWithUnorderedArray<T>
• Exercise 2.4.3: Class PriorityQueueWithUnorderedLinkedList<T>
• Exercise 2.4.21: Class StackWithPriorityQueue<T>
• Exercise 2.4.29: Class MinMaxPriorityQueue<T>
• Exercise 2.4.30: Class MedianDoubleHeap<T>

Section 5

• Exercise 2.5.4: Method SortAndRemoveDuplicates

Chapter 3

Section 1

• Exercise 3.1.2: Class SymbolTableWithKeyArray<TKey, TValue>
• Exercise 3.1.2: Class SymbolTableWithSelfOrderingKeyArray<TKey, TValue>
• Exercise 3.1.12: Class OrderedSymbolTableWithOrderedKeyArray<TKey, TValue>

Section 4

• Exercise 3.4.26: Class HashTableWithLinearProbingAndLazyDelete<TKey, TValue>
• Exercise 3.4.28: Class HashSet<T>
• Exercise 3.4.28: Class HashTableWithLinearProbing2<TKey, TValue>

Chapter 4

Algorithms

• Algorithm 4.9: Class Dijkstra<TWeight>

Section 1

• Exercise 4.1.4: Method ContainsEdge
• Exercise 4.1.5: Class GraphWithAdjacentsSet
• Exercise 4.1.10: Method FindNodeSafeToDelete
• Exercise 4.1.23: Method DistanceHistogram
• Exercise 4.1.26: Class DepthFirstLimited
• Exercise 4.1.33: Property HasOddCycles
• Exercise 4.1.36: Class EdgeConnectivity

Section 2

• Exercise 4.2.3: Method ContainsEdge
• Exercise 4.2.9: Method IsTopologicalOrder
• Exercise 4.2.23: Class StrongComponents
• Exercise 4.2.24: Class HamiltonianPathWithDegrees

Section 3

• Exercise 4.3.14: Method DeleteEdge
• Exercise 4.3.15: Method AddEdge
• Exercise 4.3.16: Method FindMaxWeightThat
• Exercise 4.3.17: Method ToString
• Exercise 4.3.22: Method MstForest

Section 4

• Exercise 4.4.7: Class KShortestPaths<TWeight>
• Exercise 4.4.7: Class OverlappingYensAlgorithm<TWeight>
• Exercise 4.4.7: Class YensAlgorithm<TWeight>
• Exercise 4.4.8: Class Diameter<TWeight>
• Exercise 4.4.22: Method ToEdgeWeightedDigraph
• Exercise 4.4.23: Class DijkstraBidirectional<TWeight>
• Exercise 4.4.23: Class DijkstraSourceSink<TWeight>
• Exercise 4.4.24: Class DijkstraMultiSource
• Exercise 4.4.25: Class DijkstraSets
• Exercise 4.4.27: Class EuclideanDistanceDigraph
• Exercise 4.4.28: Class AcyclicLongestPaths<TWeight>
• Exercise 4.4.31: Class LineGraphDistances
• Exercise 4.4.32: Class BellmanFordWithParentCheckingHeuristic<TWeight>
• Exercise 4.4.33: Method GetFullGrid
• Exercise 4.4.37: Class CriticalEdgesExamineIntersectingShortestPaths<TWeight>
• Exercise 4.4.37: Class ICriticalEdge<TWeight>
• Exercise 4.4.39: Class DijkstraLazy<TWeight>

Chapter 5

Algorithms

• Algorithm 5.1: Method LeastSignificantDigitSort
• Algorithm 5.1: Method LeastSignificantDigitSort
• Algorithm 5.1: Method LeastSignificantDigitSort
• Algorithm 5.2: Method MostSignificantDigitSort

Section 1

• Exercise 5.1.1: Method CountSort
• Exercise 5.1.7: Method CountSortWithQueues

Chapter 6