Chapter 0 Preface¶
Chapter 1 Object Oriented Programming¶
Chapter 2 Debugging¶
Chapter 3 Testing Concepts¶
- 3.1. Testing
- 3.2. Another Example
- 3.3. Bowling Example
- 3.4. JUnit Testing And You
- 3.5. Writing JUnit Tests
- 3.6. Testing for Code Coverage
- 3.7. Code Coverage In JUnit
- 3.8. JUnit Testing
- 3.8.1. Testing
- 3.8.2. JUnit testing and code coverage
- 3.8.3. Philosophy
- 3.8.4. A Bad test (1)
- 3.8.5. A Bad test (2)
- 3.8.6. Full test of output
- 3.8.7. Selective Testing of Output
- 3.8.8. What would be good testing for Project 1?
- 3.8.9. Models
- 3.8.10. What if your model is wrong?
- 3.8.11. Regression testing
Chapter 4 Introduction to Data Structures¶
Chapter 5 Recursion¶
- 5.1. Introduction
- 5.2. Writing a recursive function
- 5.3. Code Completion Practice Exercises
- 5.3.1. Introduction
- 5.3.2. Recursion Programming Exercise: Largest
- 5.3.3. Recursion Programming Exercise: Multiply
- 5.3.4. Recursion Programming Exercise: GCD
- 5.3.5. Recursion Programming Exercise: log
- 5.3.6. Recursion Programming Exercise: Cummulative Sum
- 5.3.7. Recursion Programming Exercise: Add odd values
- 5.3.8. Recursion Programming Exercise: Sum Of the Digits
- 5.3.9. Recursion Programming Exercise: Count Characters
- 5.4. Writing More Sophisticated Recursive Functions
- 5.5. Harder Code Completion Practice Exercises
- 5.6. Writing Practice Exercises
- 5.7. Tracing Recursive Code
- 5.8. Tracing Practice Exercises
- 5.9. Summary Exercises
Chapter 6 Lists¶
- 6.1. The List ADT
- 6.2. Array-Based List Implementation
- 6.3. Lists
- 6.3.1. Lists
- 6.3.1.1. Lists
- 6.3.1.2. List Implementation Concepts
- 6.3.1.3. List ADT (1)
- 6.3.1.4. List ADT (2)
- 6.3.1.5. List ADT (3)
- 6.3.1.6. List ADT Examples
- 6.3.1.7. List Find Function
- 6.3.1.8. Array-Based List Class (1)
- 6.3.1.9. Array-Based List Insert
- 6.3.1.10. Link Class
- 6.3.1.11. Linked List Position (1)
- 6.3.1.12. Linked List Position (2)
- 6.3.1.13. Linked List Position (3)
- 6.3.1.14. Linked List Class (1)
- 6.3.1.15. Linked List Class (2)
- 6.3.1.16. Insertion
- 6.3.1.17. Removal
- 6.3.1.18. Prev
- 6.3.1.19. Overhead
- 6.3.1.20. Comparison of Implementations
- 6.3.1.21. Space Comparison
- 6.3.1.22. Space Example
- 6.3.1.23. Freelist
- 6.3.1.24. Doubly Linked Lists
- 6.3.1.25. Doubly Linked Node (1)
- 6.3.1.26. Doubly Linked Insert
- 6.3.1.27. Doubly Linked Remove
- 6.3.1. Lists
Chapter 7 Algorithm Analysis¶
- 7.1. Problems, Algorithms, and Programs
- 7.2. Comparing Algorithms
- 7.3. Best, Worst, and Average Cases
- 7.4. Faster Computer, or Faster Algorithm?
- 7.5. Asymptotic Analysis and Upper Bounds
- 7.6. Calculating Program Running Time
- 7.7. Algorithm Analysis Summary Exercises
- 7.8. Algorithm Analysis
- 7.8.1. Algorithm Analysis
- 7.8.1.1. Algorithm Efficiency
- 7.8.1.2. How to Measure Efficiency?
- 7.8.1.3. Problems, Algorithms, Programs
- 7.8.1.4. Growth Rate Example (1)
- 7.8.1.5. Growth Rate Example (2)
- 7.8.1.6. Growth Rate Graph
- 7.8.1.7. Best, Worst, Average Cases
- 7.8.1.8. Which Analysis to Use?
- 7.8.1.9. Faster Computer or Algorithm?
- 7.8.1.10. Faster Computer or Algorithm? 2
- 7.8.1.11. Asymptotic Analysis: Big-oh
- 7.8.1.12. Big-oh Notation (cont)
- 7.8.1.13. Big-Oh Examples
- 7.8.1.14. Big-Oh Examples (2)
- 7.8.1.15. A Common Misunderstanding
- 7.8.1.16. Big-Omega \(\Omega\)
- 7.8.1.17. Big-Omega Example
- 7.8.1.18. Theta Notation \(\Theta\)
- 7.8.1.19. A Common Misunderstanding
- 7.8.1.20. Simplifying Rules
- 7.8.1.21. Summary
- 7.8.1.22. .
- 7.8.1.23. Time Complexity Examples (1)
- 7.8.1.24. Time Complexity Examples (2)
- 7.8.1.25. Time Complexity Examples (3)
- 7.8.1.26. Time Complexity Examples (4)
- 7.8.1.27. Binary Search
- 7.8.1.28. Other Control Statements
- 7.8.1.29. Analyzing Problems
- 7.8.1.30. Analyzing Problems: Example
- 7.8.1.31. Space/Time Tradeoff Principle
- 7.8.1.32. Multiple Parameters
- 7.8.1.33. Space Complexity
- 7.8.1. Algorithm Analysis
Chapter 8 Searching¶
Chapter 9 Stacks¶
- 9.1. Stacks
- 9.2. Linked Stacks
- 9.3. Stacks and Queues
- 9.3.1. Container Class Design Issues
- 9.3.2. Stacks
- 9.3.3. Stack ADT
- 9.3.4. Array-Based Stack (1)
- 9.3.5. Array-Based Stack (2)
- 9.3.6. Linked Stack
- 9.3.7. Queues
- 9.3.8. Queue Implementation (1)
- 9.3.9. Queue Implementation (2)
- 9.3.10. Queue Implementation (3)
- 9.3.11. Circular Queue (1)
- 9.3.12. Circular Queue (2)
Chapter 10 Queues¶
Chapter 11 Sorting¶
- 11.1. Chapter Introduction: Sorting
- 11.2. Sorting Terminology and Notation
- 11.3. Comparing Records
- 11.4. Insertion Sort
- 11.5. Bubble Sort
- 11.6. Selection Sort
- 11.7. Sorting Part 1
- 11.7.1. Sorting Part 1
- 11.7.1.1. Sorting
- 11.7.1.2. Insertion Sort
- 11.7.1.3. Initial Step
- 11.7.1.4. Analysis: Worst Case
- 11.7.1.5. Analysis: Best Case
- 11.7.1.6. Analysis: Average Case
- 11.7.1.7. Bubble Sort
- 11.7.1.8. Analysis
- 11.7.1.9. Selection Sort
- 11.7.1.10. Analysis
- 11.7.1.11. Summary
- 11.7.1.12. Code Tuning (1)
- 11.7.1.13. Exchange Sorting
- 11.7.1. Sorting Part 1
- 11.8. Sorting Part 2
- 11.8.1. Sorting Part 2
- 11.8.1.1. Shellsort
- 11.8.1.2. Shellsort (2)
- 11.8.1.3. Mergesort
- 11.8.1.4. .
- 11.8.1.5. Mergesort cost
- 11.8.1.6. Quicksort
- 11.8.1.7. Quicksort Partition
- 11.8.1.8. Quicksort Partition Cost
- 11.8.1.9. Quicksort Summary
- 11.8.1.10. Quicksort Worst Case
- 11.8.1.11. .
- 11.8.1.12. Quicksort Best Case
- 11.8.1.13. .
- 11.8.1.14. Quicksort Average Case
- 11.8.1.15. Optimizations for Quicksort
- 11.8.1.16. Heapsort
- 11.8.1.17. Heapsort Analysis
- 11.8.1.18. Binsort
- 11.8.1.19. Radix Sort: Linked List
- 11.8.1.20. .
- 11.8.1.21. Radix Sort: Array
- 11.8.1.22. Radix Sort Implementation
- 11.8.1.23. .
- 11.8.1.24. Radix Sort Analysis
- 11.8.1.25. Empirical Analysis
- 11.8.1.26. Sorting Lower Bound (1)
- 11.8.1.27. Sorting Lower Bound (2)
- 11.8.1. Sorting Part 2
- 11.9. Shellsort
- 11.10. Mergesort Concepts
- 11.11. Quicksort
- 11.12. Heapsort
- 11.13. Sorting Summary Exercises
Chapter 12 Linked Lists¶
Chapter 13 Binary Trees¶
- 13.1. Binary Trees Chapter Introduction
- 13.2. Binary Trees
- 13.3. Binary Tree as a Recursive Data Structure
- 13.4. The Full Binary Tree Theorem
- 13.5. Binary Tree Traversals
- 13.6. General Trees
- 13.7. Implementing Tree Traversals
- 13.8. Information Flow in Recursive Functions
- 13.8.1. Information Flow in Recursive Functions
- 13.8.2. Binary Tree Set Depth Exercise
- 13.8.3. Collect-and-return
- 13.8.4. Binary Tree Check Sum Exercise
- 13.8.5. Binary Tree Leaf Nodes Count Exercise
- 13.8.6. Binary Tree Sum Nodes Exercise
- 13.8.7. Combining Information Flows
- 13.8.8. Binary Tree Check Value Exercise
- 13.8.9. Combination Problems
- 13.8.10. Binary Tree Height Exercise
- 13.8.11. Binary Tree Get Difference Exercise
- 13.8.12. Binary Tree Has Path Sum Exercise
- 13.9. Binary Tree Node Implementations
- 13.10. Composite-based Expression Tree
- 13.11. Binary Tree Space Requirements
- 13.12. Binary Search Trees
- 13.13. Dictionary Implementation Using a BST
- 13.14. Binary Tree Guided Information Flow
- 13.15. Multiple Binary Trees
- 13.16. A Hard Information Flow Problem
- 13.17. Heaps and Priority Queues
- 13.18. Array Implementation for Complete Binary Trees
- 13.17. Heaps and Priority Queues
- 13.19. Huffman Coding Trees
- 13.20. Trees versus Tries
- 13.21. Proof of Optimality for Huffman Coding
- 13.22. Binary Tree Chapter Summary
- 13.23. General Trees
- 13.23.1. General Trees
- 13.23.1.1. General Trees
- 13.23.1.2. General Tree ADT
- 13.23.1.3. General Tree Traversal
- 13.23.1.4. Rep: Lists of Children
- 13.23.1.5. Rep: Dynamic Node (Array)
- 13.23.1.6. Rep: Dynamic Node (linked list)
- 13.23.1.7. Rep: Lift-Child/Right-Sibling
- 13.23.1.8. Serialization
- 13.23.1.9. Binary tree serialization
- 13.23.1.10. Alternate serialization
- 13.23.1.11. Bit Vector Serialization
- 13.23.1.12. General Tree Serialization
- 13.23.1. General Trees
Chapter 14 Hashing¶
- 14.1. Introduction
- 14.2. Hash Function Principles
- 14.3. Sample Hash Functions
- 14.4. Open Hashing
- 14.5. Bucket Hashing
- 14.6. Collision Resolution
- 14.7. Improved Collision Resolution
- 14.8. Analysis of Closed Hashing
- 14.9. Deletion
- 14.10. Hashing Chapter Summary Exercises
- 14.11. Hashing
- 14.11.1. Hashing
- 14.11.1.1. Hashing (1)
- 14.11.1.2. Hashing (2)
- 14.11.1.3. Simple Examples
- 14.11.1.4. Collisions (1)
- 14.11.1.5. Collisions (2)
- 14.11.1.6. Hash Functions (1)
- 14.11.1.7. Hash Functions (2)
- 14.11.1.8. Simple Mod Function
- 14.11.1.9. Binning
- 14.11.1.10. Mod vs. Binning
- 14.11.1.11. Mid-Square Method
- 14.11.1.12. Strings Function: Character Adding
- 14.11.1.13. String Folding
- 14.11.1.14. Open Hashing
- 14.11.1.15. Bucket Hashing (1)
- 14.11.1.16. Bucket Hashing (2)
- 14.11.1.17. Closed Hashing
- 14.11.1.18. Collision Resolution
- 14.11.1.19. Insertion
- 14.11.1.20. Search
- 14.11.1.21. Probe Function
- 14.11.1.22. Linear Probing (1)
- 14.11.1.23. Linear Probing (2)
- 14.11.1.24. Problem with Linear Probing
- 14.11.1.25. Linear Probing by Steps (1)
- 14.11.1.26. Linear Probing by Steps (2)
- 14.11.1.27. Pseudo-Random Probing (1)
- 14.11.1.28. Pseudo-Random Probing (2)
- 14.11.1.29. Quadratic Probing
- 14.11.1.30. Double Hashing (1)
- 14.11.1.31. Double Hashing (2)
- 14.11.1.32. Analysis of Closed Hashing
- 14.11.1.33. Deletion
- 14.11.1.34. Tombstones (1)
- 14.11.1.35. Tombstones (2)
- 14.11.1. Hashing
Chapter 15 Graphs¶
- 15.1. Graphs Chapter Introduction
- 15.2. Graph Traversals
- 15.3. Graph Implementations
- 15.4. Graph Concepts Summary
- 15.5. Kruskal’s Algorithm
- 15.6. All-Pairs Shortest Paths
- 15.7. Minimal Cost Spanning Trees
- 15.8. Shortest-Paths Problems
- 15.9. Topological Sort
- 15.10. Graphs
- 15.10.1. Graphs
- 15.10.1.1. Graphs
- 15.10.1.2. Paths, Cycles
- 15.10.1.3. Connected Components
- 15.10.1.4. Directed Graph Representation
- 15.10.1.5. Undirected Graph Representation
- 15.10.1.6. Representation Space Costs
- 15.10.1.7. Graph ADT
- 15.10.1.8. .
- 15.10.1.9. Visiting Neighbors
- 15.10.1.10. Graph Traversals
- 15.10.1.11. Graph Traversals (2)
- 15.10.1.12. Depth First Search (1)
- 15.10.1.13. Depth First Search (2)
- 15.10.1.14. Depth First Search (3)
- 15.10.1.15. Breadth First Search (1)
- 15.10.1.16. Breadth First Search (3)
- 15.10.1.17. Topological Sort
- 15.10.1.18. Depth-First Topological Sort (1)
- 15.10.1.19. Depth-First Topological Sort (1)
- 15.10.1.20. .
- 15.10.1.21. Queue-Based Topsort (1)
- 15.10.1.22. .
- 15.10.1.23. Queue-Based Topsort (2)
- 15.10.1.24. .
- 15.10.1.25. Shortest Paths Problems
- 15.10.1.26. Shortest Paths Definitions
- 15.10.1.27. Single-Source Shortest Paths
- 15.10.1.28. Dijkstra’s Algorithm Example
- 15.10.1.29. .
- 15.10.1.30. Dijkstra’s Implementation
- 15.10.1.31. Implementing minVertex
- 15.10.1.32. Approach 1
- 15.10.1.33. Approach 2
- 15.10.1.34. .
- 15.10.1.35. All-pairs Shortest Paths (1)
- 15.10.1.36. All-pairs Shortest Paths (2)
- 15.10.1.37. Floyd’s Algorithm
- 15.10.1.38. Minimal Cost Spanning Trees
- 15.10.1.39. MST Example
- 15.10.1.40. Prim’s MST Algorithm
- 15.10.1.41. .
- 15.10.1.42. Implementation 1
- 15.10.1.43. Alternate Implementation
- 15.10.1.44. Kruskal’s MST Algorithm (1)
- 15.10.1.45. Kruskal’s MST Algorithm (2)
- 15.10.1.46. .
- 15.10.1.47. Kruskal’s MST Algorithm (3)
- 15.10.1. Graphs
