Introduction to Algorithms and Data Structures

COVER PAGE
TITLE PAGE
COPYRIGHT PAGE
ABOUT THE AUTHOR
INTRODUCTION
ACKNOWLEDGMENTS
DEDICATION
CHAPTER 1. RECURSION
1.1. Introduction to Recursion
Calculating the Power of a Number Using Recursion
What Is Well-Defined Recursion?
Stack Overflow Errors
Advantages of Using Recursion
Tail Recursion
1.2. Examples of Recursive Methods
Computing Factorials with Recursion
Computing the Fibonacci Sequence
1.3. Direct and Indirect Recursion
Computing Squares of Numbers with Direct and Indirect Recursion
1.4. The Tower of Hanoi
Using Recursion to Solve the Tower of Hanoi Problem
1.5. Backtracking: Finding all Subsets
Why Use Backtracking?
Backtracking Solution
Summary
Key Terms
Review Questions
Programming Problems
Projects
CHAPTER 2. INTRODUCTION TO DATA STRUCTURES
2.1. Basic Data Structures and Algorithms
What Is a Data Structure?
What Is an Algorithm?
2.2. Abstract Data Types (ADTs)
The Stack
Why Use ADTs?
2.3. ADT Support in Popular Programming Languages
ADTs in Python
ADTs in C++
ADTs in Java
ADTs in Go
2.4. Linear and Non-Linear Data Structures
Storing Data in a List versus a Graph
Examples of Linear Data Structures
Examples of Non-Linear Data Structures
2.5. Static and Dynamic Data Structures
Arrays versus Lists
When to Use a Static Data Structure
2.6. Common Operations of Data Structures
Traversing a Data Structure
Searching for an Element
Modifying a Data Structure
Summary
Key Terms
Review Questions
Programming Problems
Projects
CHAPTER 3. DESIGNING EFFICIENT ALGORITHMS
3.1. Efficient Algorithms
Analyzing Algorithms
Comparing Algorithms
3.2. Big O Notation
Comparing Functions for Big Numbers
Upper Bounds for Functions
Principles for Asymptotic Analysis
3.3. Algorithm Time Complexity
Basic Asymptotical Analysis
Best, Worst, and Average Case
Complexity of Search in an Array
3.4. Space Complexity of Algorithms
Space Complexity
Space Complexity of Reversing a String
3.5. Heuristic Algorithms
Computationally Expensive Problems
Knapsack Problem
Summary
Key Terms
Review Questions
Programming Problems
Projects
CHAPTER 4. SORTING ALGORITHMS
4.1. Introduction to Sorting Algorithms
Finding the Video with Most Likes
What Is a Sorting Algorithm?
Types of Sorting Algorithms
4.2. Bubble Sort
Bubble Sort Example
Bubble Sort Details
Performance of Bubble Sort
4.3. Selection Sort
Selection Sort Example
Selection Sort Details
Performance of Selection Sort
4.4. Insertion Sort
Insertion Sort Example
Insertion Sort Details
Performance of Insertion Sort
4.5. Quicksort
Quicksort Example
Quicksort Details
Performance of Quicksort
4.6. Merge Sort
Merge Sort Example
Merge Sort Details
Performance of Merge Sort
Summary
Key Terms
Review Questions
Programming Problems
Projects
CHAPTER 5. SEARCH ALGORITHMS
5.1. Introduction to Search Algorithms
Finding a Friend's Phone Number
Sorted and Unsorted Searches
5.2. Sequential Search
Sequential Search Algorithm Details
Time Complexity of Sequential Search
5.3. Binary (Interval) Search
Searching without Checking All Elements
Binary Search Algorithm
Time Complexity of Binary Search
5.4. Recursive Binary Search Method
Binary Search Using Recursion
Space Complexity of Binary Search
Summary
Key Terms
Review Questions
Programming Problems
Projects
CHAPTER 6. LINKED LISTS, STACKS, AND QUEUES
6.1. Abstract Data Types: Linked Lists, Stacks, and Queues
Linked Lists
Stacks
Queues
6.2. Common Linked Lists Operations
Why Use Linked Lists?
Singly Linked Lists
Doubly Linked Lists
Circular Linked Lists
6.3. Common Stack ADT Methods
Why Use Stacks?
Main Stack Operations
Keeping Parentheses Balanced with Stacks
6.4. Queue ADT Methods
Why Use Queues?
Main Queue Operations
Printing Elements of a Queue in Reverse Order
6.5. Array-Based Stacks and Queues
Implementing Stacks with Arrays
Implementing Queues with Arrays
Summary
Key Terms
Review Questions
Programming Problems
Projects
CHAPTER 7. HASH TABLES
7.1. Introduction to Hash Tables
Why Hash Tables?
When to Use a Hash Table
Perfect Hashing and Collisions
7.2. Primary Hash Table Operati