Algorithms, 4th edition

A collection of notes and solutions created for Algorithms, 4th ed. by Robert Sedgewick and Kevin Wayne

Running the Code

The output for all code can be run with the newest version of node (tested on v6.9.3), which supports ES2015 syntax. For older versions, transpilation using a Babel watcher or using babel-node is required. To run the code, simply execute node [filename] in the /src directory.

Using the Notes

The notes were written for personal benefit and reference and were intended neither as a substitute for the book nor a comprehensive reference. They are included here for completeness and can be accessed through the /notes directory or via the Table of Contents.

Table of Contents

1. Case Study: Union Find

• Chapter Notes
  • dynamic connectivity, quick-find, quick-union, weighted quick-union, path compression
• Quick Find
• Quick Union
• Weighted Quick Union with Path Compression *
• Percolation *
• Percolation Stats
• Successor With Delete

2. Analysis of Algorithms

• Chapter Notes
  • mathematical models, tilde notation, two sum, three sum
• Binary Search
• Two Sum
• Three Sum
• Bitonic Array Search

3. Bags, Stacks, and Queues

• Chapter Notes
  • bags, queues, stacks, dijkstra's algorithm, linked lists
• Stack
• Stack with Linked List
• Queue
• Queue with Linked List
• Dijkstra's Algorithm for Expression Evaluation
• Stack With 2 Queues
• Stack with Max
• Deque *
• Randomized Queue
• Subset Client

4. Elementary Sorts

• Chapter Notes
  • selection sort, insertion sort, shellsort
• Selection Sort
• Insertion Sort
• ShellSort *
• Knuth Shuffle
• Intersection of 2 Sets *
• Permutation
• Dutch National Flag *

5. Mergesort

• Chapter Notes
  • top-down mergesort, bottom-up mergesort
• Top-down Mergesort *
• Bottom-up Mergesort
• Point Data Type
• Line Segment Data Type
• Brute Collinear Points
• Fast Collinear Points *
• Merging with Smaller Auxiliary Array
• Counting Inversions **

6. Quicksort

• Chapter Notes
  • quicksort, 3- way partitioning, quick-selection
• Quicksort
• Quickselect
• 3-way Partitioning
• Nuts and Bolts
• Selection From Two Sorted Arrays *
• Decimal Dominants

7. Priority Queues

• Chapter Notes
  • binary heaps, priority queues, multi-way heaps, index priority queues, heapsort
• Max Priority Queue
• Heapsort
• Dynamic Median
• Randomized Priority Queue
• Taxicab Numbers
• 8 Puzzle
• 8 Puzzle Solver

8. Symbol Tables

• Chapter Notes
  • symbol tables, ordered symbol tables, elementary implementations, binary search trees

Special Instructions

To use the graph application for the collinear points pattern recognition solver, open /src/mergesort/graph.html and select a file from the /input/mergesort folder. This will plot the points and collinear points as such: