Chapter 1 Introduction¶
Chapter 2 Arrays: Searching and Sorting¶
- 2.1. Chapter Introduction: Arrays
- 2.2. Searching in an Array
- 2.3. Chapter Introduction: Sorting
- 2.4. Sorting Terminology and Notation
- 2.5. Insertion Sort
- 2.6. Bubble Sort (optional)
- 2.7. Selection Sort
- 2.8. The Cost of Exchange Sorting (optional)
- 2.9. Optimizing Sort Algorithms with Code Tuning (optional)
- 2.10. Mergesort Concepts
- 2.11. Implementing Mergesort
- 2.12. Quicksort
- 2.13. An Empirical Comparison of Sorting Algorithms
- 2.14. Lower Bounds for Sorting (optional)
- 2.15. Arrays as Sets or Maps
- 2.16. Sorting Summary Exercises
Chapter 3 Algorithm Analysis¶
- 3.1. Chapter Introduction: Algorithm Analysis
- 3.2. Problems, Algorithms, and Programs
- 3.3. Comparing Algorithms
- 3.4. Best, Worst, and Average Cases
- 3.5. Faster Computer, or Faster Algorithm?
- 3.6. Asymptotic Analysis and Upper Bounds
- 3.7. Lower Bounds and \(\Theta\) Notation
- 3.8. Calculating Program Running Time
- 3.9. Analyzing Problems
- 3.10. Common Misunderstandings
- 3.11. Multiple Parameters
- 3.12. Space Bounds
- 3.13. Code Tuning and Empirical Analysis
- 3.14. Algorithm Analysis Summary Exercises
- 3.15. Algorithm Analysis Summary Exercises
- 3.16. Growth Rates Review (optional) (WORK IN PROGRESS)
- 3.17. Summation Techniques (optional) (WORK IN PROGRESS)
- 3.18. Solving Recurrence Relations (optional) (WORK IN PROGRESS)
- 3.19. Amortized Analysis (optional) (WORK IN PROGRESS)
Chapter 4 Linear Structures¶
- 4.1. Chapter Introduction: Lists
- 4.2. The List ADT
- 4.3. Static Array-Based Lists
- 4.4. Dynamic Array-Based Lists
- 4.5. Linked Lists
- 4.6. Comparison of List Implementations
- 4.7. Implementing Maps using Lists
- 4.8. Doubly Linked Lists (optional)
- 4.9. Dynamic Array-Based Stacks
- 4.10. Linked Stacks
- 4.11. Implementing Recursion
- 4.12. Array-Based Queues
- 4.13. Linked Queues
- 4.14. Linear Structure Summary Exercises
Chapter 5 Binary Trees¶
- 5.1. Chapter Introduction: Binary Trees
- 5.2. Binary Trees
- 5.3. Binary Tree as a Recursive Data Structure
- 5.4. Binary Tree Node Implementations
- 5.5. The Full Binary Tree Theorem (optional)
- 5.6. Binary Tree Traversals
- 5.7. Implementing Tree Traversals
- 5.8. Information Flow in Recursive Functions
- 5.9. Binary Tree Space Requirements (optional)
- 5.10. Multiple Binary Trees (optional)
- 5.11. A Hard Information Flow Problem (optional)
- 5.12. Binary Tree Chapter Summary
Chapter 6 General Trees and Union-Find (optional)¶
Chapter 7 Search Trees¶
Chapter 8 Priority Queues¶
Chapter 9 Hash Tables¶
- 9.1. Chapter Introduction: Hashing
- 9.2. Hash Function Principles
- 9.3. Sample Hash Functions
- 9.4. Separate Chaining
- 9.5. Converting Objects to Table Indices
- 9.6. Bucket Hashing (optional)
- 9.7. Open Addressing
- 9.8. Improved Collision Resolution
- 9.9. Analysis of Open Addressing
- 9.10. Open Addressing, Deletion
- 9.11. Hash Tables in Real Life (optional)
- 9.12. Hashing Chapter Summary Exercises
Chapter 10 Graphs¶
Chapter 11 Limits to Computing (optional)¶
- 11.1. Limits to Computing (optional) (WORK IN PROGRESS)
- 11.2. Reductions (optional) (WORK IN PROGRESS)
- 11.3. NP-Completeness (optional) (WORK IN PROGRESS)
- 11.4. Circuit Satisfiability (optional) (WORK IN PROGRESS)
- 11.5. Formula Satisfiability (optional) (WORK IN PROGRESS)
- 11.6. 3-CNF Satisfiability (optional) (WORK IN PROGRESS)
- 11.7. The Clique Problem (optional) (WORK IN PROGRESS)
- 11.8. The Independent Set Problem (optional) (WORK IN PROGRESS)
- 11.9. The Vertex Cover Problem (optional) (WORK IN PROGRESS)
- 11.10. The Hamiltonian Cycle Problem (optional) (WORK IN PROGRESS)
- 11.11. The Traveling Salesman Problem (optional) (WORK IN PROGRESS)
- 11.12. NP-Completeness Proofs (optional) (WORK IN PROGRESS)
- 11.13. Reduction of Circuit SAT to SAT (optional) (WORK IN PROGRESS)
- 11.14. Reduction of SAT to 3-SAT (optional) (WORK IN PROGRESS)
- 11.15. Reduction of 3-SAT to Clique (optional) (WORK IN PROGRESS)
- 11.16. Reduction of Clique to Independent Set (optional) (WORK IN PROGRESS)
- 11.17. Reduction of Independent Set to Vertex Cover (optional) (WORK IN PROGRESS)
- 11.18. Reduction of 3-SAT to Hamiltonian Cycle (optional) (WORK IN PROGRESS)
- 11.19. Reduction of Hamiltonian Cycle to Traveling Salesman (optional) (WORK IN PROGRESS)
- 11.20. Coping with NP-Complete Problems (optional) (WORK IN PROGRESS)
- 11.21. Unsolveable Problems (optional) (WORK IN PROGRESS)
- 11.22. Turing Machines (optional) (WORK IN PROGRESS)
