§ReadUse / Do
0 Analysis of Algorithms
Doubling Time and Other Useful Approximations
The Java API
Java Programming Style Guidelines
Make sure you have access to requisite software

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
4 Linked Lists
Common Linked List Operations
LinkedListH.java
LinkedListHT.java

StackList.java
QueueList.java

Deque.java (interface)
    DequeList.java
    (a double-ended queue, doubly-linked)

Exercises - Linked Lists

Exercises - Review Q2

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
Representing Red Links
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

BreadthFirstTraversal.java
    BreadthFirstPaths.java
    Breadth-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