Chapter 0 Week 1¶
Chapter 1 Week 2¶
- 1.1. Memory Management
- 1.1.1. Memory Management
- 1.1.1.1. Memory Management
- 1.1.1.2. Memory Manager ADT
- 1.1.1.3. Implementation Issues
- 1.1.1.4. Dynamic Storage Allocation
- 1.1.1.5. Fragmentation
- 1.1.1.6. Managing the Free Blocks
- 1.1.1.7. Selecting a Free Block
- 1.1.1.8. Sequential Fit Methods
- 1.1.1.9. Example
- 1.1.1.10. .
- 1.1.1.11. Buddy Method
- 1.1.1.12. Buddy Method Example
- 1.1.1.13. .
- 1.1.1.14. Failure Policies
- 1.1.1. Memory Management
- 1.2. Project Management
- 1.2.1. Project Management
- 1.2.1.1. Project Management
- 1.2.1.2. Scheduling
- 1.2.1.3. Historical Data
- 1.2.1.4. Historical Data 2
- 1.2.1.5. Historical Data 3
- 1.2.1.6. What is the Mechanism?
- 1.2.1.7. How to fail at implementing your project:
- 1.2.1.8. How to succeed at implementing
- 1.2.1.9. How to Survive
- 1.2.1.10. Being Organized 1
- 1.2.1.11. Being Organized 2
- 1.2.1.12. Memory Can’t Handle It
- 1.2.1.13. Spread Work Over Time
- 1.2.1.14. Incremental Development
- 1.2.1.15. Milestones
- 1.2.1.16. Working with a Partner (1)
- 1.2.1.17. Working with a Partner (2)
- 1.2.1. Project Management
- 1.3. Algorithm Analysis
- 1.3.1. Algorithm Analysis
- 1.3.1.1. Algorithm Efficiency
- 1.3.1.2. How to Measure Efficiency?
- 1.3.1.3. Problems, Algorithms, Programs
- 1.3.1.4. Growth Rate Example (1)
- 1.3.1.5. Growth Rate Example (2)
- 1.3.1.6. Growth Rate Graph
- 1.3.1.7. Best, Worst, Average Cases
- 1.3.1.8. Which Analysis to Use?
- 1.3.1.9. Faster Computer or Algorithm?
- 1.3.1.10. Faster Computer or Algorithm? 2
- 1.3.1.11. Asymptotic Analysis: Big-oh
- 1.3.1.12. Big-oh Notation (cont)
- 1.3.1.13. Big-Oh Examples
- 1.3.1.14. Big-Oh Examples (2)
- 1.3.1.15. A Common Misunderstanding
- 1.3.1.16. Big-Omega \(\Omega\)
- 1.3.1.17. Big-Omega Example
- 1.3.1.18. Theta Notation \(\Theta\)
- 1.3.1.19. A Common Misunderstanding
- 1.3.1.20. Simplifying Rules
- 1.3.1.21. Summary
- 1.3.1.22. .
- 1.3.1.23. Time Complexity Examples (1)
- 1.3.1.24. Time Complexity Examples (2)
- 1.3.1.25. Time Complexity Examples (3)
- 1.3.1.26. Time Complexity Examples (4)
- 1.3.1.27. Binary Search
- 1.3.1.28. Other Control Statements
- 1.3.1.29. Analyzing Problems
- 1.3.1.30. Analyzing Problems: Example
- 1.3.1.31. Space/Time Tradeoff Principle
- 1.3.1.32. Multiple Parameters
- 1.3.1.33. Space Complexity
- 1.3.1. Algorithm Analysis
Chapter 2 Week 3¶
- 2.1. Lists
- 2.1.1. Lists
- 2.1.1.1. Lists
- 2.1.1.2. List Implementation Concepts
- 2.1.1.3. List ADT (1)
- 2.1.1.4. List ADT (2)
- 2.1.1.5. List ADT (3)
- 2.1.1.6. List ADT Examples
- 2.1.1.7. List Find Function
- 2.1.1.8. Array-Based List Class (1)
- 2.1.1.9. Array-Based List Insert
- 2.1.1.10. Link Class
- 2.1.1.11. Linked List Position (1)
- 2.1.1.12. Linked List Position (2)
- 2.1.1.13. Linked List Position (3)
- 2.1.1.14. Design Principle: Design to Avoid Special Cases
- 2.1.1.15. Linked List Class (1)
- 2.1.1.16. Linked List Class (2)
- 2.1.1.17. Insertion
- 2.1.1.18. Removal
- 2.1.1.19. Prev
- 2.1.1.20. Overhead
- 2.1.1.21. Comparison of Implementations
- 2.1.1.22. Space Comparison
- 2.1.1.23. Space Example
- 2.1.1.24. Freelist
- 2.1.1.25. Doubly Linked Lists
- 2.1.1.26. Doubly Linked Node (1)
- 2.1.1.27. Doubly Linked Insert
- 2.1.1.28. Doubly Linked Remove
- 2.1.1. Lists
- 2.2. Stacks and Queues
- 2.2.1. Container Class Design Issues
- 2.2.2. Stacks
- 2.2.3. Stack ADT
- 2.2.4. Array-Based Stack (1)
- 2.2.5. Array-Based Stack (2)
- 2.2.6. Linked Stack
- 2.2.7. Queues
- 2.2.8. Queue Implementation (1)
- 2.2.9. Queue Implementation (2)
- 2.2.10. Queue Implementation (3)
- 2.2.11. Circular Queue (1)
- 2.2.12. Circular Queue (2)
Chapter 3 Week 4¶
- 3.1. Binary Trees Part 1
- 3.1.1. Binary Trees Part 1
- 3.1.1.1. Binary Trees
- 3.1.1.2. A Recursive Data Structure
- 3.1.1.3. Binary Tree Node Class
- 3.1.1.4. Question
- 3.1.1.5. Traversals
- 3.1.1.6. Preorder Traversal (1)
- 3.1.1.7. Preorder Traversal (2)
- 3.1.1.8. How not to write a traversal
- 3.1.1.9. Recursion Examples
- 3.1.1.10. Full and Complete Binary Trees
- 3.1.1.11. Full Binary Tree Theorem (1)
- 3.1.1.12. Full Binary Tree Theorem (2)
- 3.1.1.13. Full Binary Tree Corollary
- 3.1.1.14. Dictionary
- 3.1.1.15. .
- 3.1.1.16. Dictionary (2)
- 3.1.1. Binary Trees Part 1
- 3.2. Clean Code
- 3.3. Binary Search Trees
Chapter 4 Week 5¶
- 4.1. Project 2 Design
- 4.1.1. Project 2 Design
- 4.1.1.1. Project 2 Design (1)
- 4.1.1.2. Project 2 Design (2)
- 4.1.1.3. Project 2 Design (2)
- 4.1.1.4. Spatial Data Structures
- 4.1.1.5. Bintree (1)
- 4.1.1.6. Bintree (2)
- 4.1.1.7. Bintree Visualization
- 4.1.1.8. Ineractive Bintree
- 4.1.1.9. Implementation
- 4.1.1.10. Tree/Node Implementation (1)
- 4.1.1.11. Tree/Node Implementation (2)
- 4.1.1.12. Design Patterns (1)
- 4.1.1.13. Design Patterns (2)
- 4.1.1.14. Design Patterns (3)
- 4.1.1. Project 2 Design
- 4.2. Binary Trees Part 3
- 4.2.1. Binary Trees Part 3
- 4.2.1.1. Binary Tree Implementation (1)
- 4.2.1.2. Binary Tree Implementation (2)
- 4.2.1.3. Inheritance (1)
- 4.2.1.4. Inheritance (2)
- 4.2.1.5. Inheritance (3)
- 4.2.1.6. Design Patterns
- 4.2.1.7. Composite (1)
- 4.2.1.8. Composite (2)
- 4.2.1.9. Composite (3)
- 4.2.1.10. Space Overhead (1)
- 4.2.1.11. Space Overhead (2)
- 4.2.1. Binary Trees Part 3
- 4.3. Over-Constrained Code
- 4.4. Comparison
Chapter 5 Week 6¶
Chapter 6 Week 7¶
- 6.1. Tries
- 6.2. Sorting: Quadratic Sorts
- 6.2.1. Quadratic Sorts
- 6.2.1.1. Sorting
- 6.2.1.2. Insertion Sort
- 6.2.1.3. Initial Step
- 6.2.1.4. Analysis: Worst Case
- 6.2.1.5. Analysis: Best Case
- 6.2.1.6. Analysis: Average Case
- 6.2.1.7. Bubble Sort
- 6.2.1.8. Analysis
- 6.2.1.9. Selection Sort
- 6.2.1.10. Analysis
- 6.2.1.11. Summary
- 6.2.1.12. Code Tuning (1)
- 6.2.1.13. Exchange Sorting
- 6.2.1. Quadratic Sorts
- 6.3. Sorting: Faster Sorts
- 6.3.1. Faster Sorts
- 6.3.1.1. Shellsort
- 6.3.1.2. Shellsort (2)
- 6.3.1.3. Mergesort
- 6.3.1.4. .
- 6.3.1.5. Mergesort cost
- 6.3.1.6. Quicksort
- 6.3.1.7. Quicksort Partition
- 6.3.1.8. Quicksort Partition Cost
- 6.3.1.9. Quicksort Summary
- 6.3.1.10. Quicksort Worst Case
- 6.3.1.11. .
- 6.3.1.12. Quicksort Best Case
- 6.3.1.13. .
- 6.3.1.14. Quicksort Average Case
- 6.3.1.15. Optimizations for Quicksort
- 6.3.1.16. Heapsort
- 6.3.1.17. Heapsort Analysis
- 6.3.1. Faster Sorts
Chapter 7 Week 8¶
- 7.1. Sorting: Limits to Sorting
- 7.2. Disk Drives
- 7.2.1. Disk Drives
- 7.2.1.1. Programmer’s View of Files
- 7.2.1.2. Java File Functions
- 7.2.1.3. Primary vs. Secondary Storage
- 7.2.1.4. Comparisons
- 7.2.1.5. Golden Rule of File Processing
- 7.2.1.6. Disk Drives
- 7.2.1.7. Sectors
- 7.2.1.8. Terms
- 7.2.1.9. Seek Time
- 7.2.1.10. Other Factors
- 7.2.1.11. (Old) Disk Spec Example
- 7.2.1.12. Disk Access Cost Example (1)
- 7.2.1.13. Disk Access Cost Example (2)
- 7.2.1.14. How Much to Read?
- 7.2.1.15. Newer Disk Spec Example
- 7.2.1.16. Buffers
- 7.2.1. Disk Drives
Chapter 8 Week 9¶
- 8.1. Project 3 Design
- 8.2. Buffer Pools
- 8.2.1. Buffer Pools
- 8.2.1.1. Buffer Pools
- 8.2.1.2. Buffer Pools
- 8.2.1.3. Organizing Buffer Pools
- 8.2.1.4. LRU
- 8.2.1.5. Dirty Bit
- 8.2.1.6. Bufferpool ADT: Message Passing
- 8.2.1.7. Bufferpool ADT: Buffer Passing
- 8.2.1.8. Design Issues
- 8.2.1.9. Some Goals
- 8.2.1.10. Improved Interface
- 8.2.1.11. Improved Interface (2)
- 8.2.1.12. External Sorting
- 8.2.1.13. Model of External Computation
- 8.2.1.14. Key Sorting
- 8.2.1.15. Simple External Mergesort (1)
- 8.2.1.16. Simple External Mergesort (2)
- 8.2.1.17. Simple External Mergesort (3)
- 8.2.1.18. Problems with Simple Mergesort
- 8.2.1.19. A Better Process
- 8.2.1.20. Breaking a File into Runs
- 8.2.1.21. Replacement Selection (1)
- 8.2.1.22. Replacement Selection (2)
- 8.2.1.23. RS Example
- 8.2.1.24. Snowplow Analogy (1)
- 8.2.1.25. Snowplow Analogy (2)
- 8.2.1.26. Problems with Simple Merge
- 8.2.1.27. Multiway Merge (1)
- 8.2.1.28. Multiway Merge (2)
- 8.2.1.29. Limits to Multiway Merge (1)
- 8.2.1.30. Limits to Multiway Merge (2)
- 8.2.1.31. General Principles
- 8.2.1. Buffer Pools
Chapter 9 Week 10¶
- 9.1. Hashing
- 9.1.1. Hashing
- 9.1.1.1. Hashing (1)
- 9.1.1.2. Hashing (2)
- 9.1.1.3. Simple Examples
- 9.1.1.4. Collisions (1)
- 9.1.1.5. Collisions (2)
- 9.1.1.6. Hash Functions (1)
- 9.1.1.7. Hash Functions (2)
- 9.1.1.8. Simple Mod Function
- 9.1.1.9. Binning
- 9.1.1.10. Mod vs. Binning
- 9.1.1.11. Mid-Square Method
- 9.1.1.12. Strings Function: Character Adding
- 9.1.1.13. String Folding
- 9.1.1.14. Open Hashing
- 9.1.1.15. Bucket Hashing (1)
- 9.1.1.16. Bucket Hashing (2)
- 9.1.1.17. Closed Hashing
- 9.1.1.18. Collision Resolution
- 9.1.1.19. Insertion
- 9.1.1.20. Search
- 9.1.1.21. Probe Function
- 9.1.1.22. Linear Probing (1)
- 9.1.1.23. Linear Probing (2)
- 9.1.1.24. Problem with Linear Probing
- 9.1.1.25. Linear Probing by Steps (1)
- 9.1.1.26. Linear Probing by Steps (2)
- 9.1.1.27. Pseudo-Random Probing (1)
- 9.1.1.28. Pseudo-Random Probing (2)
- 9.1.1.29. Quadratic Probing
- 9.1.1.30. Double Hashing (1)
- 9.1.1.31. Double Hashing (2)
- 9.1.1.32. Analysis of Closed Hashing
- 9.1.1.33. Deletion
- 9.1.1.34. Tombstones (1)
- 9.1.1.35. Tombstones (2)
- 9.1.1. Hashing
- 9.2. Union/FIND
Chapter 10 Weeks 11/12¶
- 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
Chapter 11 Week 13¶
Chapter 12 Week 14¶
- 12.1. B-Trees
- 12.1.1. B-Trees
- 12.1.1.1. B-Trees (1)
- 12.1.1.2. B-Trees (2)
- 12.1.1.3. B-Tree Definition
- 12.1.1.4. B-Tree Search
- 12.1.1.5. B+-Trees
- 12.1.1.6. 23+-Tree Build Example
- 12.1.1.7. 23+-Tree Search Example
- 12.1.1.8. 23+-Tree Delete Example
- 12.1.1.9. B+-Tree Find
- 12.1.1.10. B+-Tree Insert
- 12.1.1.11. B+-Tree Deletion
- 12.1.1.12. B+-Tree Insert (Degree 5)
- 12.1.1.13. B-Tree Space Analysis (1)
- 12.1.1.14. B-Tree Space Analysis (2)
- 12.1.1.15. B-Trees: The Big Idea
- 12.1.1. B-Trees
- 12.2. SkipLists
