Chapter 0 Week 1¶
- 0.1. CS3114/5040 Introduction
- 0.2. Data Structures and Algorithm Analysis Introduction
- 0.3. Project 1
- 0.3.1. General Project Rules
- 0.3.2. Project 1: Songs Database
- 0.3.3. What We Give You: The Starter Kit (1)
- 0.3.4. What We Give You: The Starter Kit (2)
- 0.3.5. Design Issues
- 0.3.6. What you need to know about Hash Tables
- 0.3.7. Insert/Delete
- 0.3.8. Quadratic Probing
- 0.3.9. What you need to know about memory management
- 0.3.10. Memory Management
- 0.3.11. Memory Manager ADT
- 0.3.12. Implementation Issues
- 0.3.13. Buddy Method
- 0.3.14. Buddy Method Example
Chapter 1 Week 2¶
- 1.1. Testing
- 1.2. Algorithm Analysis: Part 1
- 1.2.1. Algorithm Efficiency
- 1.2.2. How to Measure Efficiency?
- 1.2.3. Problems, Algorithms, Programs
- 1.2.4. Growth Rate Example (1)
- 1.2.5. Growth Rate Example (2)
- 1.2.6. Growth Rate Graph (1)
- 1.2.7. Growth Rate Graph (2)
- 1.2.8. Best, Worst, Average Cases
- 1.2.9. Which Analysis to Use?
- 1.2.10. Faster Computer or Algorithm?
Chapter 2 Week 3¶
- 2.1. Algorithm Analysis: Part 2
- 2.1.1. Asymptotic Analysis: Big-oh
- 2.1.2. Big-oh Notation (cont)
- 2.1.3. Big-Oh Examples
- 2.1.4. Big-Oh Examples (2)
- 2.1.5. A Common Misunderstanding
- 2.1.6. Big \(\Omega\)
- 2.1.7. Big-Omega Example
- 2.1.8. \(\Theta\) Notation
- 2.1.9. A Common Misunderstanding
- 2.1.10. Simplifying Rules
- 2.1.11. Summary (1)
- 2.1.12. Summary (2)
- 2.1.13. Time Complexity Examples (1)
- 2.1.14. Time Complexity Examples (2)
- 2.1.15. Time Complexity Examples (3)
- 2.1.16. Time Complexity Examples (4)
- 2.1.17. Binary Search
- 2.1.18. Other Control Statements
- 2.1.19. Analyzing Problems
- 2.1.20. Analyzing Problems: Example
- 2.1.21. Space/Time Tradeoff Principle
- 2.1.22. Multiple Parameters
- 2.1.23. Space Complexity
- 2.2. Project Management
- 2.2.1. Project Management
- 2.2.2. Scheduling
- 2.2.3. Historical Data
- 2.2.4. Historical Data 2
- 2.2.5. What is the Mechanism?
- 2.2.6. How to fail at implementing your project:
- 2.2.7. How to succeed at implementing your project:
- 2.2.8. Milestones
- 2.2.9. Working with a Partner (1)
- 2.2.10. Working with a Partner (2)
- 2.3. Lists
- 2.3.1. Lists
- 2.3.2. List Implementation Concepts
- 2.3.3. List ADT (1)
- 2.3.4. List ADT (2)
- 2.3.5. List ADT (3)
- 2.3.6. List ADT Examples
- 2.3.7. List Find Function
- 2.3.8. Array-Based List Class (1)
- 2.3.9. Array-Based List Insert
- 2.3.10. Link Class
- 2.3.11. Linked List Position (1)
- 2.3.12. Linked List Position (2)
- 2.3.13. Linked List Position (3)
- 2.3.14. Linked List Class (1)
- 2.3.15. Linked List Class (2)
- 2.3.16. Insertion
- 2.3.17. Removal
- 2.3.18. Prev
- 2.3.19. Overhead
- 2.3.20. Comparison of Implementations
- 2.3.21. Space Comparison
- 2.3.22. Space Example
- 2.3.23. Freelist
- 2.3.24. Doubly Linked Lists
- 2.3.25. Doubly Linked Node (1)
- 2.3.26. Doubly Linked Insert
- 2.3.27. Doubly Linked Remove
- 2.3.28. Container Class Design Issues
- 2.4. Clean Code
- 2.5. Stacks and Queues
Chapter 3 Week 4¶
- 3.1. Binary Trees
- 3.1.1. Binary Trees
- 3.1.2. A Recursive Data Structure
- 3.1.3. Binary Tree Node Class
- 3.1.4. Question
- 3.1.5. Traversals
- 3.1.6. Preorder Traversal (1)
- 3.1.7. Preorder Traversal (2)
- 3.1.8. How not to write a traversal
- 3.1.9. Recursion Examples
- 3.1.10. Full and Complete Binary Trees
- 3.1.11. Full Binary Tree Theorem (1)
- 3.1.12. Full Binary Tree Theorem (2)
- 3.1.13. Full Binary Tree Corollary
- 3.1.14. Binary Search Trees
- 3.1.15. BST
findhelp - 3.1.16. BST
inserthelp - 3.1.17. BST
deletemax - 3.1.18. BST
removehelp - 3.1.19. BST Analysis
- 3.1.20. Dictionary
- 3.1.21. Dictionary (2)
- 3.1.22. BST as a Dictionary (1)
- 3.1.23. BST as a Dictionary (2)
- 3.1.24. .
- 3.2. Over-Constrained Code
- 3.3. Advanced Mutation Testing
Chapter 4 Week 5¶
- 4.1. Project 2
- 4.2. Design Patterns
- 4.2.1. Comparison (1)
- 4.2.2. Comparison (2)
- 4.2.3. KVpair: A Truly General Solution
- 4.2.4. KVpair: Generics
- 4.2.5. Using the KVpair (1)
- 4.2.6. Binary Tree Implementation (1)
- 4.2.7. Binary Tree Implementation (2)
- 4.2.8. Inheritance (1)
- 4.2.9. Inheritance (3)
- 4.2.10. Design Patterns
- 4.2.11. Composite (1)
- 4.2.12. Composite (2)
- 4.2.13. Flyweight
- 4.3. Midterm 1
- 4.4. Heaps
Chapter 5 Week 6¶
Chapter 6 Week 7¶
- 6.1. Sorting Part 2
- 6.1.1. Shellsort
- 6.1.2. Shellsort (2)
- 6.1.3. Mergesort
- 6.1.4. Mergesort cost
- 6.1.5. Quicksort
- 6.1.6. Quicksort Partition
- 6.1.7. Quicksort Partition Cost
- 6.1.8. Quicksort Summary
- 6.1.9. Quicksort Worst Case
- 6.1.10. Quicksort Best Case
- 6.1.11. Quicksort Average Case
- 6.1.12. Optimizations for Quicksort
- 6.1.13. Heapsort
- 6.1.14. Heapsort Analysis
- 6.2. Sorting Part 3
Chapter 7 Week 8¶
- 7.1. File Processing and Buffer Pools
- 7.1.1. Programmer’s View of Files
- 7.1.2. Java File Functions
- 7.1.3. Primary vs. Secondary Storage
- 7.1.4. Comparisons
- 7.1.5. Golden Rule of File Processing
- 7.1.6. Disk Drives
- 7.1.7. Sectors
- 7.1.8. Terms
- 7.1.9. Seek Time
- 7.1.10. Other Factors
- 7.1.11. (Old) Disk Spec Example
- 7.1.12. Disk Access Cost Example (1)
- 7.1.13. Disk Access Cost Example (2)
- 7.1.14. How Much to Read?
- 7.1.15. Newer Disk Spec Example
- 7.1.16. Solid State Drive (SSD)
- 7.1.17. Buffers
- 7.1.18. Buffer Pools
- 7.1.19. Buffer Pools
- 7.1.20. Organizing Buffer Pools
- 7.1.21. LRU
- 7.1.22. Dirty Bit
- 7.1.23. Bufferpool ADT: Message Passing
- 7.1.24. Bufferpool ADT: Buffer Passing
- 7.1.25. Design Issues
- 7.1.26. Some Goals
- 7.1.27. Improved Interface
- 7.1.28. Improved Interface (2)
- 7.2. Project 3
- 7.3. External Sorting
- 7.3.1. External Sorting
- 7.3.2. Model of External Computation
- 7.3.3. Key Sorting
- 7.3.4. Simple External Mergesort (1)
- 7.3.5. Simple External Mergesort (2)
- 7.3.6. Simple External Mergesort (3)
- 7.3.7. Problems with Simple Mergesort
- 7.3.8. A Better Process
- 7.3.9. Breaking a File into Runs
- 7.3.10. Replacement Selection (1)
- 7.3.11. Replacement Selection (2)
- 7.3.12. RS Example
- 7.3.13. Snowplow Analogy (1)
- 7.3.14. Snowplow Analogy (2)
- 7.3.15. Problems with Simple Merge
- 7.3.16. Multiway Merge (1)
- 7.3.17. Multiway Merge (2)
- 7.3.18. Limits to Multiway Merge (1)
- 7.3.19. Limits to Multiway Merge (2)
- 7.3.20. General Principles
- 7.3.21. A Broader Principle: Algorithms, Code Tuning, and Power Consumption
- 7.3.22. Compute Cycles == Electricity == Money
Chapter 8 Week 9¶
- 8.1. Hashing
- 8.1.1. Hashing (1)
- 8.1.2. Hashing (2)
- 8.1.3. Simple Examples
- 8.1.4. Collisions (1)
- 8.1.5. Collisions (2)
- 8.1.6. Hash Functions (1)
- 8.1.7. Hash Functions (2)
- 8.1.8. Simple Mod Function
- 8.1.9. Binning
- 8.1.10. Mod vs. Binning
- 8.1.11. Mid-Square Method
- 8.1.12. Strings Function: Character Adding
- 8.1.13. String Folding
- 8.1.14. Open Hashing
- 8.1.15. Bucket Hashing (1)
- 8.1.16. Bucket Hashing (2)
- 8.1.17. Closed Hashing
- 8.1.18. Collision Resolution
- 8.1.19. Insertion
- 8.1.20. Search
- 8.1.21. Probe Function
- 8.1.22. Linear Probing (1)
- 8.1.23. Linear Probing (2)
- 8.1.24. Problem with Linear Probing
- 8.1.25. Linear Probing by Steps (1)
- 8.1.26. Linear Probing by Steps (2)
- 8.1.27. Pseudo-Random Probing (1)
- 8.1.28. Pseudo-Random Probing (2)
- 8.1.29. Quadratic Probing
- 8.1.30. Double Hashing (1)
- 8.1.31. Double Hashing (2)
- 8.1.32. Analysis of Closed Hashing
- 8.1.33. Deletion
- 8.1.34. Tombstones (1)
- 8.1.35. Tombstones (2)
- 8.2. Tries
Chapter 9 Week 10¶
- 9.1. Graphs
- 9.1.1. Graphs
- 9.1.2. Paths, Cycles
- 9.1.3. Connected Components
- 9.1.4. Directed Graph Representation
- 9.1.5. Undirected Graph Representation
- 9.1.6. Representation Space Costs
- 9.1.7. Graph ADT
- 9.1.8. Visiting Neighbors
- 9.1.9. Graph Traversals
- 9.1.10. Graph Traversals (2)
- 9.1.11. Depth First Search (1)
- 9.1.12. Depth First Search (2)
- 9.1.13. Depth First Search (3)
- 9.1.14. Breadth First Search (1)
- 9.1.15. Breadth First Search (3)
- 9.1.16. Topological Sort
- 9.1.17. Depth-First Topological Sort (1)
- 9.1.18. Depth-First Topological Sort (2)
- 9.1.19. Depth-First Topological Sort (3)
- 9.1.20. Queue-Based Topsort (1)
- 9.1.21. Queue-Based Topsort (2)
- 9.1.22. Shortest Paths Problems
- 9.1.23. Shortest Paths Definitions
- 9.1.24. Single-Source Shortest Paths
- 9.1.25. Dijkstra’s Algorithm Example
- 9.1.26. Dijkstra’s Implementation
- 9.1.27. Implementing minVertex
- 9.1.28. Approach 1
- 9.1.29. Approach 2
- 9.1.30. All-pairs Shortest Paths (1)
- 9.1.31. All-pairs Shortest Paths (2)
- 9.1.32. Floyd’s Algorithm
- 9.1.33. Minimal Cost Spanning Trees
- 9.1.34. MST Example
- 9.1.35. Prim’s MST Algorithm
- 9.1.36. Implementation 1
- 9.1.37. Alternate Implementation
- 9.1.38. Kruskal’s MST Algorithm (1)
- 9.1.39. Kruskal’s MST Algorithm (2)
- 9.1.40. Kruskal’s MST Algorithm (3)
Chapter 10 Week 11¶
- 10.1. Union/FIND
- 10.2. Midterm 2
- 10.3. Project 4
- 10.4. General Trees
- 10.4.1. General Trees
- 10.4.2. General Tree ADT
- 10.4.3. General Tree Traversal
- 10.4.4. Representation: Lists of Children
- 10.4.5. Representation: Dynamic Node (Array)
- 10.4.6. Representation: Dynamic Node (linked list)
- 10.4.7. Representation: Left-Child/Right-Sibling
- 10.4.8. Serialization
- 10.4.9. Binary tree serialization
- 10.4.10. Alternate serialization
- 10.4.11. Bit Vector Serialization
- 10.4.12. General Tree Serialization
Chapter 11 Week 12¶
Chapter 12 Week 13¶
- 12.1. B-trees
- 12.1.1. B-Trees (1)
- 12.1.2. B-Trees (2)
- 12.1.3. B-Tree Definition
- 12.1.4. B-Tree Search
- 12.1.5. B+-Trees
- 12.1.6. 23+-Tree Build Example
- 12.1.7. 23+-Tree Search Example
- 12.1.8. 23+-Tree Delete Example
- 12.1.9. B+-Tree Find
- 12.1.10. B+-Tree Insert
- 12.1.11. B+-Tree Deletion
- 12.1.12. B+-Tree Insert (Degree 5)
- 12.1.13. B-Tree Space Analysis (1)
- 12.1.14. B-Tree Space Analysis (2)
- 12.1.15. B-Trees: The Big Idea
- 12.2. Memory Management
- 12.2.1. Memory Management
- 12.2.2. Memory Manager ADT
- 12.2.3. Implementation Issues
- 12.2.4. Dynamic Storage Allocation
- 12.2.5. Fragmentation
- 12.2.6. Managing the Free Blocks
- 12.2.7. Selecting a Free Block
- 12.2.8. Sequential Fit Methods
- 12.2.9. Example
- 12.2.10. Buddy Method
- 12.2.11. Buddy Method Example
- 12.2.12. Failure Policies
