Chapter 0 Preface¶
Chapter 1 Introduction for Data Structures and Algorithms Courses¶
Chapter 2 Programming Tutorials¶
Chapter 3 Design I¶
Chapter 4 Introduction to Pointers in Java¶
- 4.1. Pointers Chapter Introduction
- 4.2. Basic References Part 1
- 4.3. Basic References Part 2
- 4.4. Pointers Syntax
- 4.5. Local Memory
- 4.6. Heap Memory
- 4.7. Link Nodes
- 4.8. Link Nodes Practice Exercises
- 4.9. Additional Practice Exercises
Chapter 5 Mathematical Background¶
Chapter 6 Searching I¶
Chapter 7 Algorithm Analysis¶
- 7.1. Chapter Introduction
- 7.2. Problems, Algorithms, and Programs
- 7.3. Comparing Algorithms
- 7.4. Best, Worst, and Average Cases
- 7.5. Faster Computer, or Faster Algorithm?
- 7.6. Asymptotic Analysis and Upper Bounds
- 7.7. Lower Bounds and \(\Theta\) Notation
- 7.8. Calculating Program Running Time
- 7.9. Analyzing Problems
- 7.10. Common Misunderstandings
- 7.11. Multiple Parameters
- 7.12. Space Bounds
- 7.13. Code Tuning and Empirical Analysis
- 7.14. Algorithm Analysis Summary Exercises
- 7.15. Algorithm Analysis Summary Exercises
Chapter 8 Linear Structures¶
- 8.1. Chapter Introduction: Lists
- 8.2. The List ADT
- 8.3. Array-Based List Implementation
- 8.4. Linked Lists
- 8.5. Comparison of List Implementations
- 8.6. Doubly Linked Lists
- 8.7. List Element Implementations
- 8.8. Stacks
- 8.9. Linked Stacks
- 8.10. Freelists
- 8.11. Implementing Recursion
- 8.12. Queues
- 8.13. Linked Queues
- 8.14. Linear Structure Summary Exercises
Chapter 9 Recursion¶
- 9.1. Introduction
- 9.2. Writing a recursive function
- 9.3. Code Completion Practice Exercises
- 9.3.1. Introduction
- 9.3.2. Recursion Programming Exercise: Largest
- 9.3.3. Recursion Programming Exercise: Multiply
- 9.3.4. Recursion Programming Exercise: GCD
- 9.3.5. Recursion Programming Exercise: log
- 9.3.6. Recursion Programming Exercise: Cummulative Sum
- 9.3.7. Recursion Programming Exercise: Add odd values
- 9.3.8. Recursion Programming Exercise: Sum Of the Digits
- 9.3.9. Recursion Programming Exercise: Count Characters
- 9.4. Writing More Sophisticated Recursive Functions
- 9.5. Harder Code Completion Practice Exercises
- 9.6. Writing Practice Exercises
- 9.7. Tracing Recursive Code
- 9.8. Tracing Practice Exercises
- 9.9. Summary Exercises
Chapter 10 Design II¶
Chapter 11 Binary Trees¶
- 11.1. Binary Trees Chapter Introduction
- 11.2. Binary Trees
- 11.3. Binary Tree as a Recursive Data Structure
- 11.4. The Full Binary Tree Theorem
- 11.5. Binary Tree Traversals
- 11.6. Implementing Tree Traversals
- 11.7. Information Flow in Recursive Functions
- 11.7.1. Information Flow in Recursive Functions
- 11.7.2. Binary Tree Set Depth Exercise
- 11.7.3. Collect-and-return
- 11.7.4. Binary Tree Check Sum Exercise
- 11.7.5. Binary Tree Leaf Nodes Count Exercise
- 11.7.6. Binary Tree Sum Nodes Exercise
- 11.7.7. Combining Information Flows
- 11.7.8. Binary Tree Check Value Exercise
- 11.7.9. Combination Problems
- 11.7.10. Binary Tree Height Exercise
- 11.7.11. Binary Tree Get Difference Exercise
- 11.7.12. Binary Tree Has Path Sum Exercise
- 11.8. Binary Tree Node Implementations
- 11.9. Composite-based Expression Tree
- 11.10. Binary Tree Space Requirements
- 11.11. Binary Search Trees
- 11.12. Dictionary Implementation Using a BST
- 11.13. Binary Tree Guided Information Flow
- 11.14. Multiple Binary Trees
- 11.15. A Hard Information Flow Problem
- 11.16. Array Implementation for Complete Binary Trees
- 11.17. Heaps and Priority Queues
- 11.18. Huffman Coding Trees
- 11.19. Trees versus Tries
- 11.20. Proof of Optimality for Huffman Coding
- 11.21. Binary Tree Chapter Summary
Chapter 12 Sorting¶
- 12.1. Chapter Introduction: Sorting
- 12.2. Sorting Terminology and Notation
- 12.3. Insertion Sort
- 12.4. Bubble Sort
- 12.5. Selection Sort
- 12.6. The Cost of Exchange Sorting
- 12.7. Optimizing Sort Algorithms with Code Tuning
- 12.8. Shellsort
- 12.9. Mergesort Concepts
- 12.10. Implementing Mergesort
- 12.11. Quicksort
- 12.12. Heapsort
- 12.13. Binsort
- 12.14. Radix Sort
- 12.15. An Empirical Comparison of Sorting Algorithms
- 12.16. Lower Bounds for Sorting
- 12.17. Sorting Summary Exercises
Chapter 13 Hashing¶
Chapter 14 Memory Management¶
Chapter 15 Indexing¶
Chapter 16 General Trees¶
Chapter 17 Graphs¶
Chapter 18 Spatial Data Structures¶
Chapter 19 Searching¶
Chapter 20 Lower Bounds¶
Chapter 21 Number Problems¶
Chapter 22 Probabilistic Algorithms¶
Chapter 23 Search Structures¶
Chapter 24 Miscellaneous¶
- 24.1. The Sparse Matrix
- 24.2. Dynamic Programming
- 24.3. Amortized Analysis
- 24.4. 0/1 Knapsack Problem
- 24.5. Edit Distance
- 24.6. KMP String Search Algorithm
- 24.7. Boyer-Moore String Search Algorithm
- 24.8. Rabin-Karp String Search Algorithm [Draft]
- 24.9. General Tree Implementations
- 24.10. K-ary Tree Implementations
Chapter 25 Limits to Computing¶
- 25.1. Limits to Computing
- 25.2. Reductions
- 25.3. NP-Completeness
- 25.4. Circuit Satisfiability
- 25.5. Formula Satisfiability
- 25.6. 3-CNF Satisfiability
- 25.7. The Clique Problem
- 25.8. The Independent Set Problem
- 25.9. The Vertex Cover Problem
- 25.10. The Hamiltonian Cycle Problem
- 25.11. The Traveling Salesman Problem
- 25.12. NP-Completeness Proofs
- 25.13. Reduction of Circuit SAT to SAT
- 25.14. Reduction of SAT to 3-SAT
- 25.15. Reduction of 3-SAT to Clique
- 25.16. Reduction of Clique to Independent Set
- 25.17. Reduction of Independent Set to Vertex Cover
- 25.18. Reduction of 3-SAT to Hamiltonian Cycle
- 25.19. Reduction of Hamiltonian Cycle to Traveling Salesman
- 25.20. Coping with NP-Complete Problems
- 25.21. Unsolveable Problems
- 25.22. Turing Machines
