These units represent the material covered in the class. The order and the timing may vary according to the dynamics of the class, students and new projects.
Few more topics may be introduced according to the students interests and goals.
Unit 1: Fundamentals: Basic Programming Model
Basic Programming Model
Java libraries
PU libraries
Your own libraries
What is the purpose of an API?
The String class
Input and output
Redirection and piping
Input and output from a file
Standard drawing
Unit 2: Fundamentals: Data Abstraction
Using abstract data types
An API for an abstract data type
Inherited methods
Client code
Objects
Creating objects
Invoking instance methods
Using objects
Assignment statements
Objects as arguments
Objects as return values
Arrays are objects
Arrays of objects
Examples of ADTs:
Java’s ADTs
PU’s ADTs
Geometric objects
Information processing
Strings as ADTs
StdIn and StdOut ADTs
Implementing an abstract data type
Instance variables
Constructors
Instance methods
Scope
API, clients, and implementations
More ADT implementations
Date ADT
Maintaining multiple implementations
Accumulator API
Visual Accumulator API
Data-type design
Encapsulation
Designing API’s
Algorithms and abstract data types
Interface inheritance
Implementation inheritance
String conversion
Wrapper types
Equality
Memory management
Immutability
Design by contract
Exceptions and errors
Assertions
Unit 3: Fundamentals: Bags, Queues, and Stacks
Autoboxing
Bag ADT
FIFO queue ADT
Pushdown LIFO stack ADT
Arithmetic expression evaluation
Implementing collections
Generics
Array resizing
Loitering
Iteration
Linked lists
Building a linked list
Insert at the beginning
Remove from the beginning
Insert at the end
Insert/remove at other positions
Traversal
Stack implementation
Queue implementation
Bag implementation
Unit 4: Fundamentals: Analysis of Algorithms
Scientific method
Observations
Analysis of experimental data
Mathematical models
Tilde approximations
Approximate running time
Order-of-growth hypothesis
Analysis of algorithms
Cost model
Order-of-growth classifications
Designing faster algorithms
Doubling ratio experiments
Estimating the feasibility of solving large problems
Estimating the value of using a faster computer
Caveats
Large constants
Nondominant inner loop
Instruction time
System considerations
Too close to call
Strong dependence on inputs
Multiple problem parameters
Coping with dependence on inputs
Input models
Worst-case performance guarantees
Randomizing algorithms
Sequence of operations
Amortized analysis
Memory
Objects
Linked lists
Arrays
String objects
String values and substrings
Perspective
Unit 5: Fundamentals: Case study: Union-Find
Dynamic connectivity
Networks
Variable-name equivalence
Mathematical sets
Implementations
Quick-find
Quick-find analysis
Quick-union
Forest-of-trees representation
Quick-union analysis
Weighted quick-union
Weighted quick-union analysis
Optimal algorithms
Amortized cost plots
Perspective
Unit 6: Sorting: Elementary Sorts
Rule of the game
Certification
Running time
Extra memory
Types of data
Selection sort
Running time is insensitive to input
Data movement is minimal
Insertion sort
Visualizing sorting algorithms
Comparing two sorting algorithms
Shell sort
Unit 7: Sorting: Mergesort
Abstract in-place merge
Top-down mergersort
Use insertion sort for small subarrays
Test whether the array is already in order
Eliminate the copy to the auxiliary array
Bottom-up mergesort
The complexity of sorting
Unit 8: Sorting: Quicksort
The basic algorithm
Partitioning in place
Staying in bounds
Preserving randomness
Terminating the loop
Handling items with keys equal to the partitioning item’s key
Terminating the recursion
Performance characteristics
Algorithmic improvements
Cutoff to insertion sort
Median-of-three partitioning
Entropy-optimal sorting
Unit 9: Sorting: Priority Queues
API
A priority-queue client
Elementary implementations
Array representation (unordered)
Array representation (ordered)
Linked-list representations
Heap definitions
Binary heap representation
Algorithms on heaps
Bottom-up reheapify (swim)
Top-down reheapify (sink)
Insert
Remove the maximum
Multiway heaps
Array resizing
Inmutability of keys
Index priority queue
Index priority-queue client
Heapsort
Heap construction
Sortdown
Sink to the bottom, then swim
Unit 10: Sorting: Applications
Sorting various types of data
Transaction example
Pointer sorting
Keys are inmutable
Exchanges are inexpensive
Alternate orderings
Items with multiple keys
Priority queues with comparators
Stability
Which sorting algorithm should I use?
Sorting primitive types
Java system sort
Reductions
Duplicates
Rankings
Priority-queue reductions
Median and order statistics
A brief survey of sorting applications
Commercial computing
Search for information
Operations research
Event-driven simulation
Numerical computations
Combinatorial search
Unit 11: Searching: Symbol Tables
Generics
Duplicate keys
Null keys
Null values
Deletion
Shorthand methods
Iteration
Key equality
Ordered symbol tables
Minimum and maximum
Floor and ceiling
Rank and selection
Range queries
Exceptional cases
Shorthand methods
Key equality (revisited)
Cost model
Sample clients
Test client
Performance client
Sequential search in an unordered linked list
Binary search in an ordered array
Analysis of binary search
Unit 12: Searching: Binary Search Trees
Basic implementation
Representation
Search
Insert
Recursion
Analysis
Experiments
Order-based methods and deletion
Minimum and maximum
Floor and ceiling
Selection
Rank
Delete the minimum/maximum
Range queries
Analysis
Unit 13: Searching: Balanced Search Trees
2-3 search trees
Search
Insert into a tree consisting of a single 3-node
Insert into a 3-node whose parent is a 2-node
Insert into a 3-node whose parent is a 3-node
Splitting the root
Global properties
Red-black BSTs
Encoding 3-nodes
An equivalent definition
A 1-1 correspondence
Color representation
Rotations
Resetting the link in the parent after a rotation
Insert into a single 2-node
Insert into a 2-node at the bottom
Insert into a tree with two keys (in a 3-node)
Flipping colors
Keeping the root black
Insert into a 3-node at the bottom
Passing a red link up the tree
Implementation
Deletion
Top-down 2 3-4 trees
Delete the minimum
Properties of red-black BSTs
Analysis
Ordered symbol-table API
Unit 14: Searching: Hash Tables
Hash functions
Typical example
Positive integers
Floating-point numbers
Strings
Compound keys
Java conventions
Converting a hashCode() to an array index
User-defined hashCode()
Software caching
Hashing with separate chaining
Table size
Deletion
Ordered operations
Hashing with linear probing
Deletion
Clustering
Analysis of linear probing
Array resizing
Separate chaining
Amortized analysis
Memory
Unit 15: Searching: Applications
Which symbol-table implementation should I use?
Primitive types
Duplicate keys
Java libraries
Set APIs
Dedup
Whitelist and blacklist
Dictionary clients
Indexing clients
Inverted index
Sparse vectors
Unit 16: Graphs: Undirected Graphs
Anomalies
Undirected graph data type
Representation alternatives
Adjacency-lists data structures
Design pattern for graph processing
Depth-first search
Searching in a maze
Warmup
One-way passages
Detailed trace of depth-first search
Finding paths
Implementation
Detailed trace
Breadth-first search
Connected components
Union-find
Symbol graphs
Degrees of separation
Unit 17: Graphs: Directed Graphs
Diagraph data type
Representation
Input format
Reversing a diagraph
Symbolic names
Reachability in diagraphs
Single-source reachability
Multiple-source reachability
Mark-and-sweep garbage collection
Finding paths in diagraphs
Single-source directed paths
Single-sourced shortest directed paths
Cycles and DAGs
Scheduling problems
Precedence-constrained scheduling
Topological sort
Cycles in diagraphs
Directed cycle detection
Depth-first orders and topological sort
Strong connectivity in diagraphs
Strong components
Examples of applications
Kosaraju’s algorithm
Reachability revisited
Unit 18: Graphs: Minimum Spanning Trees
Minimum spanning tree
Underlying principles
Cut property
Greedy algorithm
Edge-weighted graph data type
Comparing edges by weight
Parallel edges
Self-loops
MST API and test client
Test client
Test data
Prim’s algorithm
Data structures
Maintaining the set of crossing edges
Unit 19: Graphs: Shortest Paths
Properties of shortest paths
Shortest-paths tree
Edge-weighted diagraph data types
Shortest-paths API
Data structures for shortest paths
Edge relaxation
Vertex relaxation
Client query methods
Theoretical basis for shortest-paths algorithms
Optimality conditions
Certification
Generic algorithm
Dijkstra’s algorithm
Data structures
Variants
Source-sink shortest paths
All-pairs shortest paths
Shortest paths in Euclidean graphs
Acyclic edge-weighted digraphs
Longest paths
Parallel job scheduling
Parallel job scheduling with relative deadlines
Shortest paths in general edge-weighted digraphs
Strawman I
Strawman II
Negative Cycles
Strawman III
Queue-based Bellman-Ford
Negative weights
Negative cycle detection
Arbitrage
Unit 20: Strings
String sorts
Key-Indexed Counting
LSD String sort
MSD String sort
Three-way string quicksort
Which string-sorting algorithm would you choose?
Tries
Properties of tries
Ternary search tries (TSTs)
Properties of TSTs
Which string symbol-table implementation should I use?
Substring Search
Brute-force substring search
Knuth-Morris-Pratt substring search
Boyer-Moore substring search
Rabin-Karp fingerprint search
Regular Expressions
Describing patterns with regular expressions
Shortcuts
REs in applications
Nondeterministic finite-state automata
Simulating an NFA
Building an NFA corresponding to an RE
Data Compression
Rules of the game
Limitations
Warmup: genomics
Run-length encoding
Huffman Compression
Unit 21: Context
Event-driven simulation
B-Trees
Suffix Arrays
Network-flow algorithms
Reduction
Intractability