With approximately 2500 problems, this book provides a collection of practical problems on the basic and advanced data structures, design, and analysis of algorithms. To make this book suitable for self-instruction, about one-third of the algorithms are supported by solutions, and some others are supported by hints and comments. This book is intended for students wishing to deepen their knowledge of algorithm design in an undergraduate or beginning graduate class on algorithms, for those teaching courses in this area, for use by practicing programmers who wish to hone and expand their skills, and as a self-study text for graduate students who are preparing for the qualifying examination on algorithms for a Ph.D. program in Computer Science or Computer Engineering. About all, it is a good source for exam problems for those who teach algorithms and data structure. The format of each chapter is just a little bit of instruction followed by lots of problems. This book is intended to augment the problem sets found in any standard algorithms textbook. This book • begins with four chapters on background material that most algorithms instructors would like their students to have mastered before setting foot in an algorithms class. The introductory chapters include mathematical induction, complexity notations, recurrence relations, and basic algorithm analysis methods. • provides many problems on basic and advanced data structures including basic data structures (arrays, stack, queue, and linked list), hash, tree, search, and sorting algorithms. • provides many problems on algorithm design techniques: divide and conquer, dynamic programming, greedy algorithms, graph algorithms, and backtracking algorithms. • is rounded out with a chapter on NP-completeness.
Author(s): Habib Izadkhah
Edition: 1
Publisher: Springer
Year: 2022
Language: English
Commentary: Publisher PDF
Pages: 525
City: Cham, Switzerland
Tags: Algorithms; Algorithm Analysis; Greedy Algorithms; Backtracking Algorithms; Software Engineering; Mathematical Induction; Functions Growth; Big-O Notation; Data Structures; Hash; Tree; Graph; P Problems; NP Problems; NP-Complete Problems; NP-Hard Problems
Preface
Contents
1 Mathematical Induction
1.1 Lecture Notes
1.2 Exercises
1.2.1 Summations
1.2.2 Inequalities
1.2.3 Floors and Ceilings
1.2.4 Divisibility
1.2.5 Postage Stamps
1.2.6 Fibonacci Numbers
1.2.7 Binomial Coefficients
1.2.8 Miscellaneous
1.3 Solutions
2 Growth of Functions
2.1 Lecture Notes
2.1.1 Orders of Growth
2.1.2 Useful Theorems Involving the Asymptotic Notations
2.1.3 Applying Limits for Analyzing Orders of Growth
2.1.4 Iterated Function
2.2 Exercises
2.2.1 Size of Problem
2.2.2 True or False?
2.2.3 Rank the Functions
2.2.4 Prove Using the Definition of Notation
2.2.5 Find Notations
2.2.6 Property of Notations
2.2.7 More Exercises
2.3 Solutions
3 Recurrence Relations
3.1 Lecture Notes
3.1.1 Catalog of Recurrence
3.1.2 Solving Recurrence
3.1.3 Linear Homogeneous Recurrences
3.1.4 Nonhomogeneous
3.1.5 Recurrence Tree
3.1.6 Master Method
3.2 Exercises
3.2.1 The Iteration Method
3.2.2 Homogeneous Linear Recurrence Equation with Constant Coefficients
3.2.3 Nonhomogeneous Recurrences Equation with Constant Coefficients
3.2.4 General Formula
3.2.5 Changing Variables in Recurrence Relations
3.2.6 More Difficult Recurrences
3.2.7 Recurrence with Full History
3.2.8 Recurrence with Floors and Ceilings
3.2.9 The Master Method
3.2.10 Recursion Tree Method
3.2.11 Recurrence Relations with More Than One Variable
3.2.12 Generating Functions
3.3 Solutions
4 Algorithm Analysis
4.1 Lecture Notes
4.2 Exercises
4.2.1 Iterative Algorithms
4.2.2 What is Returned?
4.2.3 Recursive Algorithm
4.2.4 Recurrence Relations for Recursive Functions
4.3 Solutions
5 Basic Data Structure
5.1 Lecture Notes
5.1.1 Arrays
5.1.2 Stack
5.1.3 Queue
5.1.4 Linked List
5.2 Exercises
5.2.1 Arrays
5.2.2 Stack
5.2.3 Queue
5.2.4 Linked List
5.3 Solutions
6 Hash
6.1 Lecture Notes
6.2 Exercises
6.2.1 Basic
6.2.2 Applications
6.3 Solutions
7 Tree
7.1 Lecture Notes
7.2 Exercises
7.2.1 Tree
7.2.2 Binary Tree
7.2.3 Binary Search Tree
7.2.4 Heap
7.2.5 Applications
7.3 Solutions
8 Search
8.1 Lecture Notes
8.2 Exercises
8.2.1 Preliminary
8.2.2 Linear Search
8.2.3 Binary Search
8.2.4 Ternary Search
8.2.5 Binary Search Tree (BST)
8.2.6 Fibonacci Search
8.2.7 Exponential Search
8.2.8 Interpolation Search
8.2.9 Applications
8.3 Solutions
9 Sorting
9.1 Lecture Notes
9.2 Exercises
9.2.1 Introduction
9.2.2 Selection Sort
9.2.3 Bubble Sort
9.2.4 Insertion Sort
9.2.5 Heapsort
9.2.6 Shell Sort
9.2.7 Introsort
9.2.8 Tim Sort
9.2.9 Binary Tree Sort
9.2.10 Counting Sort
9.2.11 Radix Sort
9.2.12 Mergesort
9.2.13 QuickSort
9.2.14 Shell Sort
9.2.15 Cycle Sort
9.2.16 Library Sort
9.2.17 Strand Sort
9.2.18 Cocktail Sort
9.2.19 Comb Sort
9.2.20 Gnome Sort
9.2.21 Bogo Sort
9.2.22 Sleep Sort
9.2.23 Pigeonhole Sort
9.2.24 Bucket Sort (Uniform Keys)
9.2.25 Bead Sort
9.2.26 Pancake Sort
9.2.27 Odd-Even Sort
9.2.28 Stooge Sort
9.2.29 Permutation Sort
9.2.30 Recursive Bubble Sort
9.2.31 Binary Insertion Sort
9.2.32 Recursive Insertion Sort
9.2.33 Tree Sort
9.2.34 Cartesian Tree Sorting
9.2.35 3-Way Quicksort
9.2.36 3-Way Mergesort
9.3 Solutions
10 Divide and Conquer
10.1 Lecture Notes
10.2 Exercises
10.2.1 Preliminary
10.2.2 Binary Search
10.2.3 Finding Minimum and Maximum
10.2.4 Greatest Common Divisor (gcd)
10.2.5 Mergesort
10.2.6 Quicksort
10.2.7 Finding the Median
10.2.8 Integer Multiplication
10.2.9 Matrix Multiplication
10.2.10 Application
10.3 Solutions
11 Dynamic Programming
11.1 Lecture Notes
11.2 Exercises
11.2.1 Preliminary
11.2.2 Mathematics Numbers
11.2.3 All-Pairs Shortest Paths
11.2.4 Matrix Chain Multiplication
11.2.5 The Knapsack Problem
11.2.6 Optimal Binary Search Tree
11.2.7 Longest Common Subsequence (LCS)
11.2.8 String Matching
11.2.9 Traveling Salesman Problem (TSP)
11.3 Solutions
12 Greedy Algorithms
12.1 Lecture Notes
12.2 Exercises
12.2.1 Basics
12.2.2 Activity Selection Problem
12.2.3 Minimum Spanning Tree
12.2.4 Huffman Coding
12.2.5 Dijkstra's Shortest Path Algorithm
12.2.6 Job Sequencing Problem
12.2.7 Knapsack Problem
12.2.8 Travelling Salesman Problem
12.2.9 Applications
12.3 Solutions
13 Graph
13.1 Lecture Notes
13.2 Exercises
13.2.1 Preliminary
13.2.2 Graph Traversal Techniques
13.2.3 Applications of DFS/BFS
13.2.4 Graph Cycle
13.2.5 Topological Sorting
13.2.6 Shortest Paths
13.2.7 Connectivity
13.2.8 Maximum Flow
13.3 Solutions
14 Backtracking Algorithms
14.1 Lecture Notes
14.2 Exercises
14.2.1 The Knight's Tour Problem
14.2.2 N-Queen Problem
14.2.3 The Sum-of-Subsets Problem
14.2.4 M-Coloring Problem
14.2.5 Applications
14.3 Solutions
15 P, NP, NP-Complete, and NP-Hard Problems
15.1 Lecture Notes
15.1.1 Polynomial Algorithms
15.1.2 NP Problems
15.1.3 NP-Complete Problems
15.1.4 NP-Hard Problems
15.2 Exercises
15.2.1 Basic
15.2.2 Classification of Problems: Class P and NP
15.2.3 Reduction
15.3 Solutions
Appendix References
