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 Operations Insertion in Hash Tables Deletion in Hash Tables Search Keys