Chapter 0 Preface¶
Chapter 1 Appendix¶
Chapter 2 Background¶
- 2.1. Data Structures and Algorithm Analysis Introduction
- 2.1. Chapter Introduction
- 2.2. Sets and Relations
- 2.3. Logarithms
- 2.4. Miscellaneous Notation
- 2.5. Summations
- 2.6. Mathematical Proof Techniques
- 2.7. Chapter Summary Questions
- 2.8. Recurrence Relations
- 2.9. Math Background
- 2.9. Math Background
- 2.10. Algorithm Analysis
- 2.10.1. Algorithm Analysis
- 2.10.1.1. Algorithm Efficiency
- 2.10.1.2. How to Measure Efficiency?
- 2.10.1.3. Problems, Algorithms, Programs
- 2.10.1.4. Growth Rate Example (1)
- 2.10.1.5. Growth Rate Example (2)
- 2.10.1.6. Growth Rate Graph
- 2.10.1.7. Best, Worst, Average Cases
- 2.10.1.8. Which Analysis to Use?
- 2.10.1.9. Faster Computer or Algorithm?
- 2.10.1.10. Faster Computer or Algorithm? 2
- 2.10.1.11. Asymptotic Analysis: Big-oh
- 2.10.1.12. Big-oh Notation (cont)
- 2.10.1.13. Big-Oh Examples
- 2.10.1.14. Big-Oh Examples (2)
- 2.10.1.15. A Common Misunderstanding
- 2.10.1.16. Big-Omega \(\Omega\)
- 2.10.1.17. Big-Omega Example
- 2.10.1.18. Theta Notation \(\Theta\)
- 2.10.1.19. A Common Misunderstanding
- 2.10.1.20. Simplifying Rules
- 2.10.1.21. Summary
- 2.10.1.22. .
- 2.10.1.23. Time Complexity Examples (1)
- 2.10.1.24. Time Complexity Examples (2)
- 2.10.1.25. Time Complexity Examples (3)
- 2.10.1.26. Time Complexity Examples (4)
- 2.10.1.27. Binary Search
- 2.10.1.28. Other Control Statements
- 2.10.1.29. Analyzing Problems
- 2.10.1.30. Analyzing Problems: Example
- 2.10.1.31. Space/Time Tradeoff Principle
- 2.10.1.32. Multiple Parameters
- 2.10.1.33. Space Complexity
- 2.10.1. Algorithm Analysis
Chapter 3 Algorithm Analysis¶
- 3.1. Chapter Introduction
- 3.2. Analyzing Problems
- 3.3. Calculating Program Running Time
- 3.4. Best, Worst, and Average Cases
- 3.5. Common Misunderstandings
- 3.6. Problems, Algorithms, and Programs
- 3.7. Algorithm Analysis Summary Exercises
- 3.8. Algorithm Analysis Summary Exercises
- 3.1. Data Structures and Algorithm Analysis Introduction
- 3.10. Algorithm Analysis
- 3.10.1. Algorithm Analysis
- 3.10.1.1. Algorithm Efficiency
- 3.10.1.2. How to Measure Efficiency?
- 3.10.1.3. Problems, Algorithms, Programs
- 3.10.1.4. Growth Rate Example (1)
- 3.10.1.5. Growth Rate Example (2)
- 3.10.1.6. Growth Rate Graph
- 3.10.1.7. Best, Worst, Average Cases
- 3.10.1.8. Which Analysis to Use?
- 3.10.1.9. Faster Computer or Algorithm?
- 3.10.1.10. Faster Computer or Algorithm? 2
- 3.10.1.11. Asymptotic Analysis: Big-oh
- 3.10.1.12. Big-oh Notation (cont)
- 3.10.1.13. Big-Oh Examples
- 3.10.1.14. Big-Oh Examples (2)
- 3.10.1.15. A Common Misunderstanding
- 3.10.1.16. Big-Omega \(\Omega\)
- 3.10.1.17. Big-Omega Example
- 3.10.1.18. Theta Notation \(\Theta\)
- 3.10.1.19. A Common Misunderstanding
- 3.10.1.20. Simplifying Rules
- 3.10.1.21. Summary
- 3.10.1.22. .
- 3.10.1.23. Time Complexity Examples (1)
- 3.10.1.24. Time Complexity Examples (2)
- 3.10.1.25. Time Complexity Examples (3)
- 3.10.1.26. Time Complexity Examples (4)
- 3.10.1.27. Binary Search
- 3.10.1.28. Other Control Statements
- 3.10.1.29. Analyzing Problems
- 3.10.1.30. Analyzing Problems: Example
- 3.10.1.31. Space/Time Tradeoff Principle
- 3.10.1.32. Multiple Parameters
- 3.10.1.33. Space Complexity
- 3.10.1. Algorithm Analysis
Chapter 4 Lists, Stacks, and Queues¶
- 4.1. Lists
- 4.1.1. Lists
- 4.1.1.1. Lists
- 4.1.1.2. List Implementation Concepts
- 4.1.1.3. List ADT (1)
- 4.1.1.4. List ADT (2)
- 4.1.1.5. List ADT (3)
- 4.1.1.6. List ADT Examples
- 4.1.1.7. List Find Function
- 4.1.1.8. Array-Based List Class (1)
- 4.1.1.9. Array-Based List Insert
- 4.1.1.10. Link Class
- 4.1.1.11. Linked List Position (1)
- 4.1.1.12. Linked List Position (2)
- 4.1.1.13. Linked List Position (3)
- 4.1.1.14. Linked List Class (1)
- 4.1.1.15. Linked List Class (2)
- 4.1.1.16. Insertion
- 4.1.1.17. Removal
- 4.1.1.18. Prev
- 4.1.1.19. Overhead
- 4.1.1.20. Comparison of Implementations
- 4.1.1.21. Space Comparison
- 4.1.1.22. Space Example
- 4.1.1.23. Freelist
- 4.1.1.24. Doubly Linked Lists
- 4.1.1.25. Doubly Linked Node (1)
- 4.1.1.26. Doubly Linked Insert
- 4.1.1.27. Doubly Linked Remove
- 4.1.1. Lists
- 4.2. List Element Implementations
- 4.3. The List ADT
- 4.4. Stacks and Queues
- 4.4.1. Container Class Design Issues
- 4.4.2. Stacks
- 4.4.3. Stack ADT
- 4.4.4. Array-Based Stack (1)
- 4.4.5. Array-Based Stack (2)
- 4.4.6. Linked Stack
- 4.4.7. Queues
- 4.4.8. Queue Implementation (1)
- 4.4.9. Queue Implementation (2)
- 4.4.10. Queue Implementation (3)
- 4.4.11. Circular Queue (1)
- 4.4.12. Circular Queue (2)
- 4.4. Stacks and Queues
- 4.4.1. Container Class Design Issues
- 4.4.2. Stacks
- 4.4.3. Stack ADT
- 4.4.4. Array-Based Stack (1)
- 4.4.5. Array-Based Stack (2)
- 4.4.6. Linked Stack
- 4.4.7. Queues
- 4.4.8. Queue Implementation (1)
- 4.4.9. Queue Implementation (2)
- 4.4.10. Queue Implementation (3)
- 4.4.11. Circular Queue (1)
- 4.4.12. Circular Queue (2)
- 4.5. Chapter Introduction: Lists
- 4.6. Array-Based List Implementation
- 4.7. Comparison of List Implementations
- 4.8. Linked Lists
- 4.9. Stacks
- 4.10. Linked Stacks
- 4.11. Linked Queues
- 4.12. Queues
Chapter 5 Sorting¶
- 5.1. Sorting Part 1
- 5.1.1. Sorting Part 1
- 5.1.1.1. Sorting
- 5.1.1.2. Insertion Sort
- 5.1.1.3. Initial Step
- 5.1.1.4. Analysis: Worst Case
- 5.1.1.5. Analysis: Best Case
- 5.1.1.6. Analysis: Average Case
- 5.1.1.7. Bubble Sort
- 5.1.1.8. Analysis
- 5.1.1.9. Selection Sort
- 5.1.1.10. Analysis
- 5.1.1.11. Summary
- 5.1.1.12. Code Tuning (1)
- 5.1.1.13. Exchange Sorting
- 5.1.1. Sorting Part 1
- 5.2. Sorting: Faster Sorts
- 5.2.1. Faster Sorts
- 5.2.1.1. Shellsort
- 5.2.1.2. Shellsort (2)
- 5.2.1.3. Mergesort
- 5.2.1.4. .
- 5.2.1.5. Mergesort cost
- 5.2.1.6. Quicksort
- 5.2.1.7. Quicksort Partition
- 5.2.1.8. Quicksort Partition Cost
- 5.2.1.9. Quicksort Summary
- 5.2.1.10. Quicksort Worst Case
- 5.2.1.11. .
- 5.2.1.12. Quicksort Best Case
- 5.2.1.13. .
- 5.2.1.14. Quicksort Average Case
- 5.2.1.15. Optimizations for Quicksort
- 5.2.1.16. Heapsort
- 5.2.1.17. Heapsort Analysis
- 5.2.1. Faster Sorts
- 5.2. Sorting: Faster Sorts
- 5.2.1. Faster Sorts
- 5.2.1.1. Shellsort
- 5.2.1.2. Shellsort (2)
- 5.2.1.3. Mergesort
- 5.2.1.4. .
- 5.2.1.5. Mergesort cost
- 5.2.1.6. Quicksort
- 5.2.1.7. Quicksort Partition
- 5.2.1.8. Quicksort Partition Cost
- 5.2.1.9. Quicksort Summary
- 5.2.1.10. Quicksort Worst Case
- 5.2.1.11. .
- 5.2.1.12. Quicksort Best Case
- 5.2.1.13. .
- 5.2.1.14. Quicksort Average Case
- 5.2.1.15. Optimizations for Quicksort
- 5.2.1.16. Heapsort
- 5.2.1.17. Heapsort Analysis
- 5.2.1. Faster Sorts
- 5.3. Heapsort
- 5.4. Recursive Sorting
- 5.5. Implementing Mergesort
- 5.6. Quicksort
- 5.7. Mergesort Concepts
- 5.8. Implementing Recursion
- 5.9. An Empirical Comparison of Sorting Algorithms
- 5.10. Chapter Introduction: Sorting
- 5.11. Sorting Summary Exercises
Chapter 6 Binary Trees¶
- 6.1. General Trees
- 6.1.1. General Trees
- 6.1.1.1. General Trees
- 6.1.1.2. General Tree ADT
- 6.1.1.3. General Tree Traversal
- 6.1.1.4. Rep: Lists of Children
- 6.1.1.5. Rep: Dynamic Node (Array)
- 6.1.1.6. Rep: Dynamic Node (linked list)
- 6.1.1.7. Rep: Lift-Child/Right-Sibling
- 6.1.1.8. Serialization
- 6.1.1.9. Binary tree serialization
- 6.1.1.10. Alternate serialization
- 6.1.1.11. Bit Vector Serialization
- 6.1.1.12. General Tree Serialization
- 6.1.1. General Trees
- 6.2. Binary Trees Chapter Introduction
- 6.3. Binary Trees Part 1
- 6.4. Binary Trees Part 2
- 6.4.1. Binary Trees Part 2
- 6.4.1.1. Full and Complete Binary Trees
- 6.4.1.2. Full Binary Tree Theorem (1)
- 6.4.1.3. Full Binary Tree Theorem (2)
- 6.4.1.4. Full Binary Tree Corollary
- 6.4.1.5. Dictionary
- 6.4.1.6. .
- 6.4.1.7. Dictionary (2)
- 6.4.1.8. Binary Search Trees
- 6.4.1.9. BST as a Dictionary (1)
- 6.4.1.10. BST as a Dictionary (2)
- 6.4.1.11. BST
findhelp - 6.4.1.12. BST
inserthelp - 6.4.1.13. BST
deletemax - 6.4.1.14. BST
removehelp - 6.4.1.15. .
- 6.4.1.16. BST Analysis
- 6.4.1. Binary Trees Part 2
- 6.5. Binary Trees Part 3
- 6.5.1. Binary Trees Part 3
- 6.5.1.1. Comparison (1)
- 6.5.1.2. Comparison (2)
- 6.5.1.3. KVpair
- 6.5.1.4. .
- 6.5.1.5. KVpair: Generics
- 6.5.1.6. .
- 6.5.1.7. Using the KVpair (1)
- 6.5.1.8. Binary Tree Implementation (1)
- 6.5.1.9. Binary Tree Implementation (2)
- 6.5.1.10. Inheritance (1)
- 6.5.1.11. Inheritance (2)
- 6.5.1.12. Inheritance (3)
- 6.5.1.13. Design Patterns
- 6.5.1.14. Composite (1)
- 6.5.1.15. Composite (2)
- 6.5.1.16. Composite (3)
- 6.5.1.17. Space Overhead (1)
- 6.5.1.18. Space Overhead (2)
- 6.5.1. Binary Trees Part 3
- 6.6. Binary Trees
- 6.7. Binary Tree Node Implementations
- 6.8. Binary Tree Chapter Summary
- 6.9. Binary Tree as a Recursive Data Structure
- 6.10. Binary Tree Traversals
- 6.11. Implementing Tree Traversals
- 6.12. Array Implementation for Complete Binary Trees
- 6.13. Huffman Coding
- 6.13. Huffman Coding
- 6.14. Binary Search Trees
- 6.14. Binary Search Trees
- 6.15. Balanced Trees
- 6.16. The AVL Tree
- 6.17. The Splay Tree
Chapter 7 Heaps (Priority Queues)¶
Chapter 8 Hashing¶
- 8.1. Hashing
- 8.1.1. Hashing
- 8.1.1.1. Hashing (1)
- 8.1.1.2. Hashing (2)
- 8.1.1.3. Simple Examples
- 8.1.1.4. Collisions (1)
- 8.1.1.5. Collisions (2)
- 8.1.1.6. Hash Functions (1)
- 8.1.1.7. Hash Functions (2)
- 8.1.1.8. Simple Mod Function
- 8.1.1.9. Binning
- 8.1.1.10. Mod vs. Binning
- 8.1.1.11. Mid-Square Method
- 8.1.1.12. Strings Function: Character Adding
- 8.1.1.13. String Folding
- 8.1.1.14. Open Hashing
- 8.1.1.15. Bucket Hashing (1)
- 8.1.1.16. Bucket Hashing (2)
- 8.1.1.17. Closed Hashing
- 8.1.1.18. Collision Resolution
- 8.1.1.19. Insertion
- 8.1.1.20. Search
- 8.1.1.21. Probe Function
- 8.1.1.22. Linear Probing (1)
- 8.1.1.23. Linear Probing (2)
- 8.1.1.24. Problem with Linear Probing
- 8.1.1.25. Linear Probing by Steps (1)
- 8.1.1.26. Linear Probing by Steps (2)
- 8.1.1.27. Pseudo-Random Probing (1)
- 8.1.1.28. Pseudo-Random Probing (2)
- 8.1.1.29. Quadratic Probing
- 8.1.1.30. Double Hashing (1)
- 8.1.1.31. Double Hashing (2)
- 8.1.1.32. Analysis of Closed Hashing
- 8.1.1.33. Deletion
- 8.1.1.34. Tombstones (1)
- 8.1.1.35. Tombstones (2)
- 8.1.1. Hashing
- 8.1. Hashing
- 8.1.1. Hashing
- 8.1.1.1. Hashing (1)
- 8.1.1.2. Hashing (2)
- 8.1.1.3. Simple Examples
- 8.1.1.4. Collisions (1)
- 8.1.1.5. Collisions (2)
- 8.1.1.6. Hash Functions (1)
- 8.1.1.7. Hash Functions (2)
- 8.1.1.8. Simple Mod Function
- 8.1.1.9. Binning
- 8.1.1.10. Mod vs. Binning
- 8.1.1.11. Mid-Square Method
- 8.1.1.12. Strings Function: Character Adding
- 8.1.1.13. String Folding
- 8.1.1.14. Open Hashing
- 8.1.1.15. Bucket Hashing (1)
- 8.1.1.16. Bucket Hashing (2)
- 8.1.1.17. Closed Hashing
- 8.1.1.18. Collision Resolution
- 8.1.1.19. Insertion
- 8.1.1.20. Search
- 8.1.1.21. Probe Function
- 8.1.1.22. Linear Probing (1)
- 8.1.1.23. Linear Probing (2)
- 8.1.1.24. Problem with Linear Probing
- 8.1.1.25. Linear Probing by Steps (1)
- 8.1.1.26. Linear Probing by Steps (2)
- 8.1.1.27. Pseudo-Random Probing (1)
- 8.1.1.28. Pseudo-Random Probing (2)
- 8.1.1.29. Quadratic Probing
- 8.1.1.30. Double Hashing (1)
- 8.1.1.31. Double Hashing (2)
- 8.1.1.32. Analysis of Closed Hashing
- 8.1.1.33. Deletion
- 8.1.1.34. Tombstones (1)
- 8.1.1.35. Tombstones (2)
- 8.1.1. Hashing
- 8.2. Collision Resolution
- 8.3. Improved Collision Resolution
- 8.4. Introduction
- 8.5. Sample Hash Functions
- 8.6. Hash Function Principles
- 8.7. Deletion
- 8.8. Hashing Chapter Summary Exercises
Chapter 9 Maps and Sets¶
Chapter 10 Graphs¶
- 10.1. Graphs
- 10.1.1. Graphs
- 10.1.1.1. Graphs
- 10.1.1.2. Paths, Cycles
- 10.1.1.3. Connected Components
- 10.1.1.4. Directed Graph Representation
- 10.1.1.5. Undirected Graph Representation
- 10.1.1.6. Representation Space Costs
- 10.1.1.7. Graph ADT
- 10.1.1.8. .
- 10.1.1.9. Visiting Neighbors
- 10.1.1.10. Graph Traversals
- 10.1.1.11. Graph Traversals (2)
- 10.1.1.12. Depth First Search (1)
- 10.1.1.13. Depth First Search (2)
- 10.1.1.14. Depth First Search (3)
- 10.1.1.15. Breadth First Search (1)
- 10.1.1.16. Breadth First Search (3)
- 10.1.1.17. Topological Sort
- 10.1.1.18. Depth-First Topological Sort (1)
- 10.1.1.19. Depth-First Topological Sort (2)
- 10.1.1.20. .
- 10.1.1.21. Queue-Based Topsort (1)
- 10.1.1.22. .
- 10.1.1.23. Queue-Based Topsort (2)
- 10.1.1.24. .
- 10.1.1.25. Shortest Paths Problems
- 10.1.1.26. Shortest Paths Definitions
- 10.1.1.27. Single-Source Shortest Paths
- 10.1.1.28. Dijkstra’s Algorithm Example
- 10.1.1.29. .
- 10.1.1.30. Dijkstra’s Implementation
- 10.1.1.31. Implementing minVertex
- 10.1.1.32. Approach 1
- 10.1.1.33. Approach 2
- 10.1.1.34. .
- 10.1.1.35. All-pairs Shortest Paths (1)
- 10.1.1.36. All-pairs Shortest Paths (2)
- 10.1.1.37. Floyd’s Algorithm
- 10.1.1.38. Minimal Cost Spanning Trees
- 10.1.1.39. MST Example
- 10.1.1.40. Prim’s MST Algorithm
- 10.1.1.41. .
- 10.1.1.42. Implementation 1
- 10.1.1.43. Alternate Implementation
- 10.1.1.44. Kruskal’s MST Algorithm (1)
- 10.1.1.45. Kruskal’s MST Algorithm (2)
- 10.1.1.46. .
- 10.1.1.47. Kruskal’s MST Algorithm (3)
- 10.1.1. Graphs
- 10.1. Graphs
- 10.1.1. Graphs
- 10.1.1.1. Graphs
- 10.1.1.2. Paths, Cycles
- 10.1.1.3. Connected Components
- 10.1.1.4. Directed Graph Representation
- 10.1.1.5. Undirected Graph Representation
- 10.1.1.6. Representation Space Costs
- 10.1.1.7. Graph ADT
- 10.1.1.8. .
- 10.1.1.9. Visiting Neighbors
- 10.1.1.10. Graph Traversals
- 10.1.1.11. Graph Traversals (2)
- 10.1.1.12. Depth First Search (1)
- 10.1.1.13. Depth First Search (2)
- 10.1.1.14. Depth First Search (3)
- 10.1.1.15. Breadth First Search (1)
- 10.1.1.16. Breadth First Search (3)
- 10.1.1.17. Topological Sort
- 10.1.1.18. Depth-First Topological Sort (1)
- 10.1.1.19. Depth-First Topological Sort (2)
- 10.1.1.20. .
- 10.1.1.21. Queue-Based Topsort (1)
- 10.1.1.22. .
- 10.1.1.23. Queue-Based Topsort (2)
- 10.1.1.24. .
- 10.1.1.25. Shortest Paths Problems
- 10.1.1.26. Shortest Paths Definitions
- 10.1.1.27. Single-Source Shortest Paths
- 10.1.1.28. Dijkstra’s Algorithm Example
- 10.1.1.29. .
- 10.1.1.30. Dijkstra’s Implementation
- 10.1.1.31. Implementing minVertex
- 10.1.1.32. Approach 1
- 10.1.1.33. Approach 2
- 10.1.1.34. .
- 10.1.1.35. All-pairs Shortest Paths (1)
- 10.1.1.36. All-pairs Shortest Paths (2)
- 10.1.1.37. Floyd’s Algorithm
- 10.1.1.38. Minimal Cost Spanning Trees
- 10.1.1.39. MST Example
- 10.1.1.40. Prim’s MST Algorithm
- 10.1.1.41. .
- 10.1.1.42. Implementation 1
- 10.1.1.43. Alternate Implementation
- 10.1.1.44. Kruskal’s MST Algorithm (1)
- 10.1.1.45. Kruskal’s MST Algorithm (2)
- 10.1.1.46. .
- 10.1.1.47. Kruskal’s MST Algorithm (3)
- 10.1.1. Graphs
- 10.2. All-Pairs Shortest Paths
- 10.3. Graph Concepts Summary
- 10.4. Graphs Chapter Introduction
- 10.5. Kruskal’s Algorithm
- 10.6. Shortest-Paths Problems
- 10.7. Topological Sort
- 10.8. Graph Traversals
- 10.9. Minimal Cost Spanning Trees
