Chapter 0 Week 1¶
- 0.1. CS3114 Introduction
- 0.1.1. Introduction
- 0.1.1.1. Introduction
- 0.1.1.2. Administration stuff
- 0.1.1.3. Course Mechanics
- 0.1.1.4. Canvas
- 0.1.1.5. OpenDSA
- 0.1.1.6. Web-CAT
- 0.1.1.7. Milestones
- 0.1.1.8. Course Introduction
- 0.1.1.9. Role in the Curriculum
- 0.1.1.10. Costs and Benefits
- 0.1.1.11. Data Structure
- 0.1.1.12. Logical vs. Physical Form
- 0.1.1.13. Logical vs. Physical Form (2)
- 0.1.1.14. Homework
- 0.1.1.15. Before you leave today
- 0.1.1. Introduction
- 0.2. Program Management
- 0.2.1. Program Management
- 0.2.1.1. Project Management
- 0.2.1.2. Historical Data
- 0.2.1.3. Historical Data 2
- 0.2.1.4. Historical Data 3
- 0.2.1.5. What is the Mechanism?
- 0.2.1.6. How to fail at implementing your project:
- 0.2.1.7. How to succeed at implementing your project
- 0.2.1.8. How to Survive
- 0.2.1.9. Being Organized 1
- 0.2.1.10. Being Organized 2
- 0.2.1.11. Memory Can't Handle It
- 0.2.1.12. Spread Work Over Time
- 0.2.1.13. Incremental Development
- 0.2.1.14. Milestones
- 0.2.1. Program Management
- 0.3. Memory Management
- 0.4. Project 1 Implementation Details
Chapter 1 Week 2¶
- 1.1. Algorithm Analysis
- 1.1.1. Algorithm Analysis
- 1.1.1.1. Algorithm Efficiency
- 1.1.1.2. How to Measure Efficiency?
- 1.1.1.3. Problems, Algorithms, Programs
- 1.1.1.4. Growth Rate Example (1)
- 1.1.1.5. Growth Rate Example (2)
- 1.1.1.6. Growth Rate Graph
- 1.1.1.7. Best, Worst, Average Cases
- 1.1.1.8. Which Analysis to Use?
- 1.1.1.9. Faster Computer or Algorithm?
- 1.1.1.10. Faster Computer or Algorithm? 2
- 1.1.1.11. Asymptotic Analysis: Big-oh
- 1.1.1.12. Big-oh Notation (cont)
- 1.1.1.13. Big-Oh Examples
- 1.1.1.14. Big-Oh Examples (2)
- 1.1.1.15. A Common Misunderstanding
- 1.1.1.16. Big-Omega \(\Omega\)
- 1.1.1.17. Big-Omega Example
- 1.1.1.18. Theta Notation \(\Theta\)
- 1.1.1.19. A Common Misunderstanding
- 1.1.1.20. Simplifying Rules
- 1.1.1.21. Time Complexity Examples (1)
- 1.1.1.22. Time Complexity Examples (2)
- 1.1.1.23. Time Complexity Examples (3)
- 1.1.1.24. Time Complexity Examples (4)
- 1.1.1.25. Binary Search
- 1.1.1.26. Other Control Statements
- 1.1.1.27. Analyzing Problems
- 1.1.1.28. Analyzing Problems: Example
- 1.1.1.29. Space/Time Tradeoff Principle
- 1.1.1.30. Multiple Parameters
- 1.1.1.31. Space Complexity
- 1.1.1. Algorithm Analysis
Chapter 2 Week 3¶
- 2.1. JUnit Testing
- 2.1.1. Testing
- 2.1.2. JUnit testing and code coverage
- 2.1.3. Philosophy
- 2.1.4. A Bad test (1)
- 2.1.5. A Bad test (2)
- 2.1.6. Full test of output
- 2.1.7. Selective Testing of Output
- 2.1.8. What would be good testing for Project 1?
- 2.1.9. Models
- 2.1.10. What if your model is wrong?
- 2.1.11. Regression testing
- 2.2. Clean Code
- 2.3. Lists
- 2.3.1. Lists
- 2.3.1.1. Lists, Stacks, Queues
- 2.3.1.2. List Implementation Concepts
- 2.3.1.3. List ADT (1)
- 2.3.1.4. List ADT (2)
- 2.3.1.5. List ADT (3)
- 2.3.1.6. List ADT Examples
- 2.3.1.7. List Find Function
- 2.3.1.8. Array-Based List Class (1)
- 2.3.1.9. Array-Based List Insert
- 2.3.1.10. Link Class
- 2.3.1.11. Linked List Position (1)
- 2.3.1.12. Linked List Position (2)
- 2.3.1.13. Linked List Position (3)
- 2.3.1.14. Linked List Class (1)
- 2.3.1.15. Linked List Class (2)
- 2.3.1.16. Insertion
- 2.3.1.17. Removal
- 2.3.1.18. Prev
- 2.3.1.19. Overhead
- 2.3.1.20. Comparison of Implementations
- 2.3.1.21. Space Comparison
- 2.3.1.22. Space Example
- 2.3.1.23. Freelist
- 2.3.1.24. Doubly Linked Lists
- 2.3.1.25. Container Class Design Issues
- 2.3.1.26. Doubly Linked Node (1)
- 2.3.1.27. Doubly Linked Insert
- 2.3.1.28. Doubly Linked Remove
- 2.3.1.29. Stacks
- 2.3.1.30. Stack ADT
- 2.3.1.31. Array-Based Stack (1)
- 2.3.1.32. Array-Based Stack (2)
- 2.3.1.33. Linked Stack
- 2.3.1.34. Queues
- 2.3.1.35. Queue Implementation (1)
- 2.3.1.36. Queue Implementation (2)
- 2.3.1.37. Queue Implementation (3)
- 2.3.1.38. Circular Queue (1)
- 2.3.1.39. Circular Queue (2)
- 2.3.1. Lists
- 2.4. Binary Trees Part 1
Chapter 3 Week 4¶
- 3.1. Binary Trees Part 2
- 3.1.1. Binary Trees Part 2
- 3.1.1.1. Full and Complete Binary Trees
- 3.1.1.2. Full Binary Tree Theorem (1)
- 3.1.1.3. Full Binary Tree Theorem (2)
- 3.1.1.4. Full Binary Tree Corollary
- 3.1.1.5. Dictionary
- 3.1.1.6. .
- 3.1.1.7. Dictionary (2)
- 3.1.1.8. Binary Search Trees
- 3.1.1.9. BST as a Dictionary (1)
- 3.1.1.10. BST as a Dictionary (2)
- 3.1.1.11. BST
findhelp - 3.1.1.12. BST
inserthelp - 3.1.1.13. BST
deletemax - 3.1.1.14. BST
removehelp - 3.1.1.15. .
- 3.1.1.16. BST Analysis
- 3.1.1. Binary Trees Part 2
- 3.2. Binary Trees Part 3
- 3.2.1. Binary Trees Part 3
- 3.2.1.1. Comparison (1)
- 3.2.1.2. Comparison (2)
- 3.2.1.3. KVpair
- 3.2.1.4. .
- 3.2.1.5. KVpair: Generics
- 3.2.1.6. .
- 3.2.1.7. Using the KVpair (1)
- 3.2.1.8. Binary Tree Implementation (1)
- 3.2.1.9. Binary Tree Implementation (2)
- 3.2.1.10. Inheritance (1)
- 3.2.1.11. Inheritance (2)
- 3.2.1.12. Inheritance (3)
- 3.2.1.13. Design Patterns
- 3.2.1.14. Composite (1)
- 3.2.1.15. Composite (2)
- 3.2.1.16. Composite (3)
- 3.2.1.17. Space Overhead (1)
- 3.2.1.18. Space Overhead (2)
- 3.2.1. Binary Trees Part 3
Chapter 4 Week 5¶
Chapter 5 Week 6¶
Chapter 6 Week 7-8¶
- 6.1. Sorting Part 1
- 6.2. Sorting Part 2
- 6.2.1. Sorting Part 2
- 6.2.1.1. Shellsort
- 6.2.1.2. Shellsort (2)
- 6.2.1.3. Mergesort
- 6.2.1.4. Mergesort cost
- 6.2.1.5. Quicksort
- 6.2.1.6. Quicksort Partition
- 6.2.1.7. Quicksort Partition Cost
- 6.2.1.8. Quicksort Summary
- 6.2.1.9. Quicksort Worst Case
- 6.2.1.10. .
- 6.2.1.11. Quicksort Best Case
- 6.2.1.12. .
- 6.2.1.13. Quicksort Average Case
- 6.2.1.14. Optimizations for Quicksort
- 6.2.1.15. Heapsort
- 6.2.1.16. Heapsort Analysis
- 6.2.1.17. Binsort
- 6.2.1.18. Radix Sort: Linked List
- 6.2.1.19. .
- 6.2.1.20. Radix Sort: Array
- 6.2.1.21. Radix Sort Implementation
- 6.2.1.22. .
- 6.2.1.23. Radix Sort Analysis
- 6.2.1.24. Empirical Analysis
- 6.2.1.25. Sorting Lower Bound (1)
- 6.2.1.26. Sorting Lower Bound (2)
- 6.2.1. Sorting Part 2
Chapter 7 Week 8-9¶
- 7.1. File Processing and Buffer Pools
- 7.1.1. File Processing and Buffer Pools
- 7.1.1.1. Programmer’s View of Files
- 7.1.1.2. Java File Functions
- 7.1.1.3. Primary vs. Secondary Storage
- 7.1.1.4. Comparisons
- 7.1.1.5. Golden Rule of File Processing
- 7.1.1.6. Disk Drives
- 7.1.1.7. Sectors
- 7.1.1.8. Terms
- 7.1.1.9. Seek Time
- 7.1.1.10. Other Factors
- 7.1.1.11. (Old) Disk Spec Example
- 7.1.1.12. Disk Access Cost Example (1)
- 7.1.1.13. Disk Access Cost Example (2)
- 7.1.1.14. How Much to Read?
- 7.1.1.15. Newer Disk Spec Example
- 7.1.1.16. Buffers
- 7.1.1.17. Buffer Pools
- 7.1.1.18. Buffer Pools
- 7.1.1.19. Organizing Buffer Pools
- 7.1.1.20. LRU
- 7.1.1.21. Dirty Bit
- 7.1.1.22. Bufferpool ADT: Message Passing
- 7.1.1.23. Bufferpool ADT: Buffer Passing
- 7.1.1.24. Design Issues
- 7.1.1.25. Some Goals
- 7.1.1.26. Improved Interface
- 7.1.1.27. Improved Interface (2)
- 7.1.1.28. External Sorting
- 7.1.1.29. Model of External Computation
- 7.1.1.30. Key Sorting
- 7.1.1.31. Simple External Mergesort (1)
- 7.1.1.32. Simple External Mergesort (2)
- 7.1.1.33. Simple External Mergesort (3)
- 7.1.1.34. Problems with Simple Mergesort
- 7.1.1.35. A Better Process
- 7.1.1.36. Breaking a File into Runs
- 7.1.1.37. Replacement Selection (1)
- 7.1.1.38. Replacement Selection (2)
- 7.1.1.39. RS Example
- 7.1.1.40. Snowplow Analogy (1)
- 7.1.1.41. Snowplow Analogy (2)
- 7.1.1.42. Problems with Simple Merge
- 7.1.1.43. Multiway Merge (1)
- 7.1.1.44. Multiway Merge (2)
- 7.1.1.45. Limits to Multiway Merge (1)
- 7.1.1.46. Limits to Multiway Merge (2)
- 7.1.1.47. General Principles
- 7.1.1. File Processing and Buffer Pools
Chapter 8 Week 10¶
- 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. Simple Strings Function (1)
- 8.1.1.13. Simple Strings Function (2)
- 8.1.1.14. String Folding (1)
- 8.1.1.15. .
- 8.1.1.16. String Folding (2)
- 8.1.1.17. Open Hashing
- 8.1.1.18. Bucket Hashing (1)
- 8.1.1.19. Bucket Hashing (2)
- 8.1.1.20. Closed Hashing
- 8.1.1.21. Collision Resolution
- 8.1.1.22. Insertion
- 8.1.1.23. Search
- 8.1.1.24. Probe Function
- 8.1.1.25. Linear Probing (1)
- 8.1.1.26. Linear Probing (2)
- 8.1.1.27. Problem with Linear Probing
- 8.1.1.28. Linear Probing by Steps (1)
- 8.1.1.29. Linear Probing by Steps (2)
- 8.1.1.30. Pseudo-Random Probing (1)
- 8.1.1.31. Pseudo-Random Probing (2)
- 8.1.1.32. Quadratic Probing
- 8.1.1.33. Double Hashing (1)
- 8.1.1.34. Double Hashing (2)
- 8.1.1.35. Analysis of Closed Hashing
- 8.1.1.36. Deletion
- 8.1.1.37. Tombstones (1)
- 8.1.1.38. Tombstones (2)
- 8.1.1. Hashing
Chapter 9 Week 11¶
Chapter 10 Week 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. .
- 10.1.1.15. Breadth First Search (1)
- 10.1.1.16. Breadth First Search (2)
- 10.1.1.17. Breadth First Search (3)
- 10.1.1.18. .
- 10.1.1.19. Topological Sort
- 10.1.1.20. Depth-First Topological Sort (1)
- 10.1.1.21. Depth-First Topological Sort (1)
- 10.1.1.22. .
- 10.1.1.23. Queue-Based Topsort (1)
- 10.1.1.24. .
- 10.1.1.25. Queue-Based Topsort (2)
- 10.1.1.26. .
- 10.1.1.27. Shortest Paths Problems
- 10.1.1.28. Shortest Paths Definitions
- 10.1.1.29. Single-Source Shortest Paths
- 10.1.1.30. Dijkstra’s Algorithm Example
- 10.1.1.31. .
- 10.1.1.32. Dijkstra’s Implementation
- 10.1.1.33. Implementing minVertex
- 10.1.1.34. Approach 1
- 10.1.1.35. Approach 2
- 10.1.1.36. .
- 10.1.1.37. All-pairs Shortest Paths (1)
- 10.1.1.38. All-pairs Shortest Paths (2)
- 10.1.1.39. Floyd's Algorithm
- 10.1.1.40. Minimal Cost Spanning Trees
- 10.1.1.41. MST Example
- 10.1.1.42. Prim’s MST Algorithm
- 10.1.1.43. .
- 10.1.1.44. Implementation 1
- 10.1.1.45. Alternate Implementation
- 10.1.1.46. Kruskal’s MST Algorithm (1)
- 10.1.1.47. Kruskal’s MST Algorithm (2)
- 10.1.1.48. .
- 10.1.1.49. Kruskal’s MST Algorithm (3)
- 10.1.1. Graphs
Chapter 11 Week 13¶
- 11.1. Indexing
- 11.1.1. Indexing
- 11.1.1.1. Indexing
- 11.1.1.2. Files and Indexing
- 11.1.1.3. Keys and Indexing
- 11.1.1.4. Linear Indexing (1)
- 11.1.1.5. Linear Indexing (2)
- 11.1.1.6. Tree Indexing (1)
- 11.1.1.7. Tree Indexing (2)
- 11.1.1.8. Tree Indexing (3)
- 11.1.1.9. Tree Indexing (4)
- 11.1.1.10. 2-3 Tree
- 11.1.1.11. 2-3 Tree Example
- 11.1.1.12. 2-3 Tree Insertion (1)
- 11.1.1.13. 2-3 Tree Insertion (2)
- 11.1.1.14. 2-3 Tree Insertion (3)
- 11.1.1.15. B-Trees (1)
- 11.1.1.16. B-Trees (2)
- 11.1.1.17. B-Tree Search
- 11.1.1.18. B+-Trees
- 11.1.1.19. B+-Tree Example
- 11.1.1.20. B+-Tree Insertion
- 11.1.1.21. B+-Tree Deletion (1)
- 11.1.1.22. B+-Tree Deletion (2)
- 11.1.1.23. B+-Tree Deletion (3)
- 11.1.1.24. .
- 11.1.1.25. B-Tree Space Analysis (1)
- 11.1.1.26. B-Tree Space Analysis (2)
- 11.1.1.27. B-Trees: The Big Idea
- 11.1.1. Indexing
Chapter 12 Week 14¶
- 12.1. General Trees
- 12.1.1. General Trees
- 12.1.1.1. General Trees
- 12.1.1.2. General Tree ADT
- 12.1.1.3. General Tree Traversal
- 12.1.1.4. Rep: Lists of Children
- 12.1.1.5. Rep: Dynamic Node (Array)
- 12.1.1.6. Rep: Dynamic Node (linked list)
- 12.1.1.7. Rep: Lift-Child/Right-Sibling
- 12.1.1.8. Serialization
- 12.1.1.9. Binary tree serialization
- 12.1.1.10. Alternate serialization
- 12.1.1.11. Bit Vector Serialization
- 12.1.1.12. General Tree Serialization
- 12.1.1. General Trees
