C455 Class Notes
C455 Class Notes
Modified
:
C455 Learning Goals
IEEE/ACM Curricula 2001 Body of Knowledge
The Learning Pyramid
Chapter 1
Chapter 2
Testing vs Verification
Reasoning About Loops
Loop Tracing Example
-
Loop Tracing Worked
Loop Invariant Example
-
Loop Invariant Worked
A Weak Loop Invariant
Java Validation
Divide two int's
Double an Array
Maximum of an Array
Recursive Factorial
Linear Search
Insertion Sort
Mathematical Induction
Induction Questions
Loop Invariant Proof
- Factorial
Induction Proof
- Factorial
Analysis Basics
Analysis of a Non-Recursive
Insertion Sort Algorithm
Divide & Conquer Algorithms
Chapter 3
Asymptotic Notation
Limits
Chapter 4
Recurrence Relations Tutorial
Substitution Method
Substitution Subtleties
Recursion Tree
Master Method
Chapter 6
Tree and Heap Proofs
Heaps
Heapify
Build-Heap
Heapsort
Sorting Machine
Priority Queues
Chapter 8
Decision Tree Proof
Chapter 11
Maps
Direct Access Tables
Hash Tables
Multiplication Method
Chapter 12
Binary Tree Notes
Sample Binary Trees
Chapter 15
Dynamic Programming
Chapter 16
Greedy Algorithms
Chapter 18
B-Tree Basics
B-Tree Height Proof
B-Tree Ops
Chapter 21
Disjoint Sets
Chapter 22
Graph Basics
BFS
BFS: Print-Path
DFS
Topological Sort
SCC
Chapter 23
Minimum Spanning Trees
MST-Kruskal
MST-Prim
Chapter 24
Single-Source Shortest Paths
D˙kstra's
Chapter 27
Multithreaded Algorithms
Chapter 34
Chapter 34 Intro
Chapter 34.1
Encoding Example
Chapter 34.2
Chapter 34.3
Chapter 34.4
Coping with Complexity
Backtracking
Branch-and-Bound or Best-First
