Introduction to Algorithms and Data Structures

Résumé
With Perez's INTRODUCTION TO ALGORITHMS AND DATA STRUCTURES, 1st Edition, a student will master basic programming patterns and learn how to use them to solve problems. One of the cornerstones of solving problems is knowing which patterns to apply. This is where algorithms and data structures become fundamental. Familiarity with data structures and algorithms allows a programmer to tackle unthinkable problems, using only a programming language's basic control flow and loops. The book explores several common ideas -- backtracking, depth-first, breadth-first, recursion, divide and conquer and dynamic programming. Not only this will prepare students with problem-solving skills, it will also equip students with employability through technical interview tips and best practices. conquer, and dynamic programming. Not only this will prepare students with problem solving skills, it will also equip students with employability through technical interview tips and best practices.

Contenu
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 in Hash Tables 7.3. Hash Functions and Hash Codes Hash Functions for Integer Keys Polynomial Hash Codes Hashing Composite Keys 7.4. Compressing Hash Codes Residue or Division Method Multiplication Method 7.5. Handling Hash Collisions Solving Collisions with Chaining Open Addressing Using Linear Probing Open Addressing Using Double Hashing 7.6. Hash Efficiency Static Hashing Collisions and Efficiency in Chaining Collisions and Efficiency in Open Addressing Summary Key Terms Review Questions Programming Problems Programming Projects CHAPTER 8. TREES 8.1. Introduction to Trees Main Characteristics of Trees Types of Trees Tree ADT and Implementation Recursion in Trees 8.2. Tree Operations and the Traversal Process Depth-First and Breadth-First Traversal In-Order Traversal Other Traversals in Binary Trees 8.3. Binary Search Trees What Is a Binary Search Tree? Searching in a BST Complexity of Searching in BSTs Insertion and Deletion in BSTs 8.4. Adelson-Velsky-Landis (AVL) Trees Properties of AVL Trees Balancing a Tree by Left and Right Rotation Insertion in AVL Trees Deletion in AVL Trees 8.5. Heaps and Treaps What Is a Heap? The Heapify Operation Insertion and Deletion in a Heap What Is a Treap? Insertion and Deletion in a Treap 8.6. Tries What Is a Trie? Time Complexity of Search in a Trie Insertion and Deletion in a Trie Summary Key Terms Review Questions Programming Problems Projects CHAPTER 9. GRAPHS 9.1. Introduction to Graphs Network Connections Additional Examples 9.2. Graph Terminologies A Graph as an Abstract Data Structure The Adjacency Matrix The Adjacency List 9.3. Depth-First Traversal Implementing Depth-First Traversal 9.4. Breadth-First Traversal Implementing Breadth-First Traversal 9.5. Directed and Undirected Graphs 9.6. Weighted Graphs Describing the Cost of Travels in a Network Multigraphs Summary Key Terms Review Questions Programming Problems Projects CHAPTER 10. ADVANCED ALGORITHMS 10.1. Greedy Algorithms Parts of a Greedy Algorithm Huffman Coding Algorithm 10.2. Dynamic Programming Parts of Dynamic Programming 0-1 Knapsack Dynamic Programming Solution Longest Common Sub-String 10.3. Dijkstra's Algorithm for the Shortest Path Dijkstra's Algorithm Examples Dijkstra's Algorithm Details 10.4. KnuthMorrisPratt (KMP) Algorithm Pattern Searching Naive Pattern Searching RabinKarp String Matching Algorithm Overview of the KMP Algorithm Implementing the KMP Algorithm 10.5. Spanning Trees Minimum Spanning Trees Prim's Algorithm 10.6. Contours and Regions in Binary Images Flood Filling Contour Finding Summary Key Terms Review Questions Programming Problems Projects