0 Analysis of Algorithms
Doubling Time and Other Useful Approximations
The Java API
Java Programming Style Guidelines

Stopwatch.java
TimeExperiment.java

Exercises - Analysis of Algorithms
1 Abstract Data Types
Stacks

Some Applications of Stacks:
Postfix Expressions
Evaluating Infix Expressions
Delimiter Matching
The Shunting Yard Algorithm
The N-Queens Problem & Backtracking
Exercises - Using Stacks I
2 Considerations when Implementing a Stack (and other Collections):
Generics & Type Parameters
Autoboxing & Auto-unboxing
Iterating over Collections
Resizing Arrays
Garbage Collection

StackOfStrings.java
(quick & dirty implementation, fixed capacity, array-based)

Stack.java (interface)
StackArray.java

Exercises - Using Stacks II
3 Queues
Bags
Queue.java (interface)
QueueArray.java
Trace QueueArray Operations

Bag.java (interface)
BagArray.java

Exercises - Using Queues

StackList.java
QueueList.java

Deque.java (interface)
DequeList.java

Exercises - Review Q2
Exercises - Review T1

More Practice - Stacks, Queues, and Linked Lists
5 Searching and Sorting - First Thoughts

Linear Search
Binary Search

Some Iterative Sorting Methods:
Bubble Sort
Selection Sort
Insertion Sort

Some Recursive Sorting Methods:
Merge Sort
Merge Sort Analysis

Quicksort
An Alternate Partitioning Technique
Quick Sort Analysis
Another Way to Analyze the Average Quicksort Case
Better Handling of Duplicates: 3-Way Quicksort

Decision Trees: Finding a Lower Bound on Comparison Cost
Stable Sorts
Sorter.java (interface)
InsertionSorter.java
SelectionSorter.java
MergeSorter.java
Merge Sort Trace
QuickSorter.java
Quick Sort Trace

Exercises - Sorting
6 Symbol Tables / Dictionaries

Binary Search Trees
Searching and Inserting in a Binary Search Trees
A Connection Between Binary Search Trees and Quicksort
Operations on Binary Trees Involving Key Order
Tree Traversals
Supporting Rank Operations in Binary Search Trees
Hibbard Deletion
SymbolTable.java
BinarySearchTree.java
Binary Search Tree Trace

Exercises - Binary Search Trees
7 Priority Queues and Heaps
Sinking and Swimming in a Heap
Immutability
Heapsort
Heapsort Analysis
Huffman Coding (For the curious)
PriorityQueue.java
MinHeapPQ
MaxHeapPQ
PriorityQueueTest

HeapSorter.java
Heap Sort Trace

Exercises - Heaps and Priority Queues
8 2-3 Trees
Red-Black Trees
Searching and Inserting in a Red-Black Tree
RedBlackBST.java
Red Black Tree Trace

Exercises - 2-3 Trees and Red-Black Trees

Review B1
Review B2
9 Hash Tables
Using the `hashCode()` Method
Generating Hash Codes
Resolving Collisions
KeyValueList.java

SeparateChainingHashTable.java
Hash Table (Separate Chaining) Trace

HashTableLinearProbe.java
Hash Table (Linear Probing) Trace

Exercises - Hash Tables
10 Graphs
Representing Graphs
Directed and Edge-Weighted Graphs
Graph.java
11 Traversing Graphs

DepthFirstTraversal.java
DepthFirstPaths.java
Depth-First Paths Trace

ConnectedComponents.java
CycleDetector.java
TwoColorDetector.java
12 Dijkstra's Shortest Path Algorithm
Some Results From Graph Theory
Prim's Algorithm
Digraph.java
Edge.java
WeightedGraph.java
TinyEWG.txt
DirectedEdge.java
WeightedDigraph.java
TinyEWDG.txt
IndexMinPQ.java
MinPQ.java
DijkstraShortestPaths.java
LazyPrimMST.java
13 The A* Algorithm AStarPathFinder.java

Dijkstra Shortest Paths Trace
Prim's MST (Lazy Version) Trace
A* Algorithm Trace

Review C