ALGORITHMS DESIGN TECHNIQUES AND ANALYSIS M. Alsuwaiyel Information & Computer Science Department KFUPM July, 1999 Preface The field of computer algorithms has flourished since the early 1960’s when the first users of electronic computers started to pay attention to the per- formance of programs. The limited resources of computers at that time resulted in additional impetus for devising efficient computer algorithms. After extensive research in this field, numerous efficient algorithms for dif- ferent problems emerged.
The similarities among different algorithms for certain classes of problems have resulted in general algorithm design tech- niques. This book emphasizes most of these algorithm design techniques that have proved their utility in the solution to many problems. It may be considered as an attempt to cover the most common techniques in the design of sequential algorithms. Each technique is presented as follows.
First, the context in which that technique can be applied. Second, the spe- cial characteristics of that technique that set it apart. Third, comparison with other techniques, whenever possible; finally, and most importantly, illustration of the technique by applying it to several problems. Although the main theme of the book is algorithm design techniques, it also emphasizes the other major component in algorithmic design: the analysis of algorithms.
It covers in detail the analysis of most of the algo- rithms presented. Chapter 2 covers most of the mathematical tools that are helpful in analyzing algorithms. Chapter 11 is an introduction to the field of computational complexity, and Chapter 12 covers the basics of establish- ing lower bounds on the solution of various problems. These chapters are indispensable for the design of efficient algorithms.
The focus of the presentation is on practical applications of the design techniques. Each technique is illustrated by providing an adequate num- i ii Preface ber of algorithms to solve some problems that quite often arise in many applications in science and engineering. The style of presentation of algorithms is straightforward, and uses pseudocode that is similar to the syntax of structured programming languages, e. if-then-else, for and while constructs.
The pseudocode is sometimes intermixed with English whenever necessary. Describing a portion of an algorithm in English is indeed instructive; it conveys the idea with minimum effort on the part of the reader. However, sometimes it is both easier and more formal to use a pseudocode statement. For example, the function of the assignment statement B[1.n] is to replace each entry B[i] with A[i] for all i, 1 ≤ i ≤ n.
Neither the for. end for construct nor plain English is more concise or easier to state than this notation. The book is divided into seven parts. Each part consists of chapters that cover those design techniques that have common characteristics or objectives.
Part 1 sets the stage for the rest of the book, in addition to providing the background material that is needed in subsequent chapters. Part 2 is devoted to the study of recursive design techniques, which are extremely important, as they emphasize a fundamental tool in the field of computer science: recursion. Part 3 covers two intuitive and natural design techniques: the greedy approach and graph traversals. Part 4 is concerned with those techniques needed to investigate a given problem and the pos- sibility of either coming up with an efficient algorithm for that problem, or proving its intractability.
This part covers NP-completeness, computa- tional complexity and lower bounds. In Part 5, techniques for coping with hard problems are presented. These include backtracking, randomization and finding approximate solutions that are reasonable and acceptable us- ing a reasonable amount of time. Part 6 introduces the concept of iterative improvement using two important problems that have received extensive attention, which resulted in increasingly efficient algorithms: the problem of finding a maximum flow in a network and the problem of finding a max- imum matching in an undirected graph.
Finally, Part 7 is an introduction to the relatively new field of computational geometry. In one chapter, the widely used technique of geometric sweeping is presented with examples of important problems in that field. In the other chapter, the versatile tool of Preface iii the Voronoi diagram is covered, and some of its applications are presented. The book is intended as a text in the field of the design and analysis of algorithms.
It includes adequate material for two courses in algorithms. Chapters 1 through 10 provide the core material for an undergraduate course in algorithms at the junior or senior level. Some of the material may be skipped such as the amortized analysis of the union-find algorithms, and the linear time algorithms in the case of dense graphs for the shortest path and minimum spanning tree problems. The instructor may find it useful to add some of the material in the following chapters such as backtracking, randomized algorithms, approximation algorithms or geometric sweeping.
The rest of the material is intended for a graduate course in algorithms. The prerequisites for this book have been kept to the minimum; only an elementary background in discrete mathematics and data structures are assumed. The author is grateful to King Fahd University of Petroleum & Minerals (KFUPM) for their support and providing facilities for the preparation of the manuscript. This book writing project has been funded by KFUPM under Project ics/algorithm/182.
The Author would like to thank those who have critically read various portions of the manuscript and offered many helpful suggestions, including the students of the undergraduate and graduate Algorithms courses at KFUPM. Special thanks go to S. Ghanta for their valuable comments. Dhahran, Saudi Arabia M.
Alsuwaiyel iv Contents Preface i PART 1 Basic Concepts and Introduction to Algo- rithms 1 Chapter 1 Basic Concepts in Algorithmic Analysis 5 1.1 Analysis of the binary search algorithm .4 Merging two Sorted Lists .7 Bottom-up Merge Sorting .1 Analysis of bottom-up merge sorting .1 Order of growth .6 Complexity Classes and the o-notation .11 How to Estimate the Running Time of an Algorithm .1 Counting the number of iterations .2 Counting the frequency of basic operations .3 Using recurrence relations .12 Worst case and average case analysis .1 Worst case analysis .2 Average case analysis .14 Input Size and Problem Instance. 59 Chapter 2 Mathematical Preliminaries 61 2.1 Sets, Relations and Functions .3 Proof by contradiction .4 Proof by counterexample .4 Floor and Ceiling Functions .5 Factorial and Binomial Coefficients .6 The pigeonhole principle .1 Approximation of summations by integration .1 Solution of linear homogeneous recurrences .2 Solution of inhomogeneous recurrences .3 Solution of divide-and-conquer recurrences .1 Expanding the recurrence .3 Change of variables. 98 Chapter 3 Data Structures 103 3.1 Stacks and queues .1 Representation of graphs .1 Some quantitative aspects of binary trees .2 Binary search trees. 114 Chapter 4 Heaps and the Disjoint Sets Data Structures 115 4.1 Operations on heaps .4 Min and Max Heaps .3 Disjoint Sets Data Structures .1 The union by rank heuristic .3 The union-find algorithms .4 Analysis of the union-find algorithms.
137 PART 2 Techniques Based on Recursion 139 Chapter 5 Induction 143 viii Contents 5.2 Two Simple Examples .1 The first algorithm .2 The second algorithm .7 Finding the Majority Element. 158 Chapter 6 Divide and Conquer 161 6.1 How the algorithm works .2 Analysis of the mergesort algorithm .4 The Divide and Conquer Paradigm .5 Selection: Finding the Median and the kth Smallest Element .1 Analysis of the selection algorithm .2 The sorting algorithm .3 Analysis of the quicksort algorithm .1 The worst case behavior .2 The average case behavior .4 Comparison of sorting algorithms .7 Multiplication of Large Integers .1 The traditional algorithm .4 Comparisons of the three algorithms .9 The Closest Pair Problem. 202 Chapter 7 Dynamic Programming 203 7.2 The Longest Common Subsequence Problem .3 Matrix Chain Multiplication .4 The Dynamic Programming Paradigm .5 The All-Pairs Shortest Path Problem .6 The Knapsack Problem. 226 PART 3 First-Cut Techniques 227 Chapter 8 The Greedy Approach 231 8.2 The Shortest Path Problem .1 A linear time algorithm for dense graphs .3 Minimum Cost Spanning Trees (Kruskal’s Algorithm) .4 Minimum Cost Spanning Trees (Prim’s Algorithm) .1 A linear time algorithm for dense graphs.
255 Chapter 9 Graph Traversal 257 9.2 Depth-First Search .1 Time complexity of depth-first search .3 Applications of Depth-First Search .3 Finding articulation points in a graph .4 Strongly connected components .4 Breadth-First Search .5 Applications of Breadth-First Search. 273 PART 4 Complexity of Problems 275 Chapter 10 NP-complete Problems 279 10.3 The Class NP .4 NP-complete Problems .1 The satisfiability problem .2 vertex cover, independent set and clique problems .3 More NP-complete Problems .5 The Class co-NP .6 The Class NPI .7 The Relationships Between the Four Classes. 298 Chapter 11 Introduction to Computational Complexity 299 11.2 Model of Computation: the Turing Machine .3 k-tape Turing machines and time complexity .4 Off-line Turing machines and space complexity .5 Tape compression and linear speed-up .6 Relationships Between Complexity Classes .1 Space and time hierarchy theorems .1 NLOGSPACE-complete problems .2 PSPACE-complete problems .4 Some conclusions of completeness .9 The Polynomial Time Hierarchy. 332 Contents xi Chapter 12 Lower Bounds 335 12.2 Trivial Lower Bounds .3 The Decision Tree Model .1 The search problem .2 The sorting problem .4 The Algebraic Decision Tree Model .1 The element uniqueness problem .5 Linear Time Reductions .1 The convex hull problem .2 The closest pair problem .3 The Euclidean minimum spanning tree problem.
346 PART 5 Coping with Hardness 349 Chapter 13 Backtracking 353 13.2 The 3-Coloring Problem .3 The 8-Queens Problem .4 The General Backtracking Method .5 Branch and Bound. 369 Chapter 14 Randomized Algorithms 371 14.2 Las Vegas and Monte Carlo Algorithms .5 Testing String Equality. 392 xii Contents Chapter 15 Approximation Algorithms 393 15.1 Planar graph coloring .2 Hardness result: the knapsack problem .4 Relative Performance Bounds .1 The bin packing problem .2 The Euclidean traveling salesman problem .3 The vertex cover problem .4 Hardness result: the traveling salesman problem .5 Polynomial Approximation Schemes .1 The knapsack problem .6 Fully Polynomial Approximation Schemes .1 The subset-sum problem. 413 PART 6 Iterative Improvement for Domain-Specific Problems 415 Chapter 16 Network Flow 419 16.3 The Ford-Fulkerson Method .4 Maximum Capacity Augmentation .5 Shortest Path Augmentation .7 The MPM Algorithm .3 The Network Flow Method .4 The Hungarian Tree Method for Bipartite Graphs .5 Maximum Matching in General Graphs .5 ) Algorithm for Bipartite Graphs.
457 PART 7 Techniques in Computational Geometry 459 Chapter 18 Geometric Sweeping 463 18.3 Computing the Intersections of Line Segments .4 The Convex Hull Problem .5 Computing the Diameter of a Set of Points. 480 Chapter 19 Voronoi Diagrams 481 19.2 Nearest-Point Voronoi Diagram .2 Construction of the Voronoi diagram .3 Applications of the Voronoi diagram .1 Computing the convex hull .2 All nearest neighbors.3 The Euclidean minimum spanning tree .4 Farthest-Point Voronoi Diagram .1 Construction of the farthest-point Voronoi diagram .5 Applications of the farthest-point Voronoi diagram .1 All farthest neighbors .2 Smallest enclosing circle. 499 Bibliography 501 Index 511 PART 1 Basic Concepts and Introduction to Algorithms 1 2 3 This part of the book is concerned with the study of the basic tools and prerequisites for the design and analysis of algorithms. Chapter 1 is intended to set the stage for the rest of the book.
In this chapter, we will discuss examples of simple algorithms for solving some of the fundamental problems encountered in almost all applications of com- puter science. These problems include searching, merging and sorting. Us- ing these example algorithms as a reference, we then investigate the math- ematical aspects underlying the analysis of algorithms. Specifically, we will study in detail the analysis of the running time and space required by a given algorithm.
Chapter 2 is devoted to the study of the most basic mathematical back- ground required for the analysis of algorithms. This chapter covers in details the most common summations and recurrence relations usually encountered when analyzing algorithms.