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.
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. Knuth–Morris–Pratt (KMP) Algorithm
Pattern Searching
Naive Pattern Searching
Rabin–Karp 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
-
Cengage Cengage
N/A
-
Key Terms are identified and defined throughout the chapter and are listed again at the chapter’s completion. A glossary at the end of the book lists all key terms in alphabetical order, along with their working definition.
Cengage Testing, powered by Cognero® for Cengage's Introduction To Algorithms And Data Structures
9780357673645
Cengage Testing, powered by Cognero® for Cengage's Introduction To Algorithms And Data Structures, Instant Access
9780357673652
Instructor's Companion Website for Cengage's Introduction To Algorithms And Data Structures, 1st
9780357673584
Student Companion Website for Cengage's Introduction to Algorithms And Data Structures
9798214003399