Algorithms: Design Techniques and Analysis

Description

Problem solving is an essential part of every scientific discipline. It has two components: (1) problem identification and formulation, and (2) the solution to the formulated problem. One can solve a problem on its own using ad hoc techniques or by following techniques that have produced efficient solutions to similar problems. This requires the understanding of various algorithm design techniques, how and when to use them to formulate solutions, and the context appropriate for each of them.Algorithms: Design Techniques and Analysis advocates the study of algorithm design by presenting the most useful techniques and illustrating them with numerous examples emphasizing on design techniques in problem solving rather than algorithms topics like searching and sorting. Algorithmic analysis in connection with example algorithms are explored in detail. Each technique or strategy is covered in its own chapter through numerous examples of problems and their algorithms.Readers will be equipped with problem solving tools needed in advanced courses or research in science and engineering Content: Preface PART 1 Basic Concepts and Introduction to Algorithms Chapter 1 Basic Concepts in Algorithmic Analysis 1.1 Introduction 1.2 Historical Background 1.3 Binary Search 1.3.1 Analysis of the binary search algorithm 1.4 Merging Two Sorted Lists 1.5 Selection Sort 1.6 Insertion Sort 1.7 Bottom-up Merge Sorting 1.7.1 Analysis of bottom-up merge sorting 1.8 Time Complexity 1.8.1 Order of growth 1.8.2 The O-notation 1.8.3 The Ω-notation 1.8.4 The Θ-notation 1.8.5 Examples 1.8.6 Complexity classes and the o-notation 1.9 Space Complexity 1.10 Optimal Algorithms 1.11 How to Estimate the Running Time of an Algorithm1.11.1 Counting the number of iterations 1.11.2 Counting the frequency of basic operations 1.11.3 Using recurrence relations 1.12 Worst-Case and Average-Case Analyses 1.12.1 Worst-case analysis 1.12.2 Average-case analysis 1.13 Amortized Analysis 1.14 Input Size and Problem Instance 1.15 Divide-and-Conquer Recurrences 1.15.1 Expanding the recurrence 1.15.2 Substitution 1.15.3 Change of variables 1.16 Exercises 1.17 Bibliographic Notes Chapter 2 Data Structures 2.1 Introduction 2.2 Linked Lists 2.2.1 Stacks and queues 2.3 Graphs2.3.1 Representation of graphs 2.3.2 Planar graphs 2.4 Trees 2.5 Rooted Trees 2.5.1 Tree traversals 2.6 Binary Trees 2.6.1 Some quantitative aspects of binary trees 2.6.2 Binary search trees 2.7 Exercises 2.8 Bibliographic Notes Chapter 3 Heaps and the Disjoint Sets Data Structures 3.1 Introduction 3.2 Heaps 3.2.1 Operations on heaps 3.2.2 Creating a heap 3.2.3 Heapsort 3.2.4 Min and Max Heaps 3.3 Disjoint Sets Data Structures 3.3.1 The union by rank heuristic 3.3.2 Path compression 3.3.3 The union-find algorithms 3.3.4 Analysis of the union-find algorithms 3.4 Exercises3.5 Bibliographic Notes PART 2 Techniques Based on Recursion Chapter 4 Induction 4.1 Introduction 4.2 Finding the Majority Element 4.3 Integer Exponentiation 4.4 Evaluating Polynomials (Horner's Rule) 4.5 Radix Sort 4.6 Generating Permutations 4.6.1 The first algorithm 4.6.2 The second algorithm 4.7 Exercises 4.8 Bibliographic Notes Chapter 5 Divide and Conquer 5.1 Introduction 5.2 Binary Search 5.3 Mergesort 5.3.1 How the algorithm works 5.3.2 Analysis of the mergesort algorithm 5.4 The Divide-and-Conquer Paradigm 5.5 Selection: Finding the Median and the kth Smallest Element5.5.1 Analysis of the selection algorithm 5.6 Quicksort 5.6.1 A partitioning algorithm 5.6.2 The sorting algorithm 5.6.3 Analysis of the quicksort algorithm 5.6.3.1 The worst-case behavior 5.6.3.2 The average-case behavior 5.6.4 Comparison of sorting algorithms 5.7 Multiselection 5.8 Multiplication of Large Integers 5.9 Matrix Multiplication 5.9.1 The traditional algorithm 5.9.2 Strassen's algorithm 5.9.3 Comparisons of the two algorithms 5.10 The Closest Pair Problem 5.10.1 Time complexity 5.11 Exercises