基本介绍

内容简介

本书是国际著名算法专家李德财教授主编的系列丛书“Lecture Notes Series on Computing”中的一本。本书涵盖了绝大多数算法设计中的一般技术，在表达每一种技术时，阐述它的应用背景，注意用与其他技术比较的方法说明它的特征，并提供大量相应实际问题的例子。本书同时也强调了对每一种算法的详细的复杂性分析。 本书包含以下几部分  基本概念和算法导引  基于递归的技术  最先割技术  问题的复杂性  克服困难性  域指定问题的迭代改进  计算几何技术

作者简介

M．H．Alsuwaiyel在沙特阿拉伯的King Fahd University of Petroleum＆Minerals(KFUPM，皇家法哈德石油矿业大学)完成大学学业，在南加州(USC)大学获得计算机科学硕士和博士学位。作者曾任KFUPM的计算机科学系主任、工程与计算机学院院长。他在沙特阿拉伯有广泛的学术影响，是政府(包括内务部和国防部在内)的高级顾问。

图书目录

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 Algorithm 1.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 analysis 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 Exercises 1.16 Bibliographic Notes Chapter 2 Mathematical Preliminaries 2.1 Sets, Relations and Functions 2.1.1 Sets 2.1.2 Relations 2.1.2.1 Equivalence relations 2.1.3 Functions 2.2 Proof Methods 2.2.1 Direct proof 2.2.2 Indirect proof 2.2.3 Proof by contradiction 2.2.4 Proof by counterexample 2.2.5 Mathematical induction 2.3 Logarithms 2.4 Floor and Ceiling Functions 2.5 Factorial and Binomial Coefficients 2.5.1 Factorials 2.5.2 Binomial coefficients 2.6 The Pigeonhole Principle 2.7 Summations 2.7.1 Approximation of summations by integration 2.8 Recurrence Relations 2.8.1 Solution of linear homogeneous recurrences 2.8.2 Solution of inhomogeneous recurrences 2.8.3 Solution of divide-and-conquer recurrences 2.8.3.1 Expanding the recurrence 2.8.3.2 Substitution 2.8.3.3 Change of variables 2.9 Exercises Chapter 3 Data Structures 3.1 Introduction 3.2 Linked Lists 3.2.1 Stacks and queues 3.3 Graphs 3.3.1 Representation of graphs 3.3.2 Planar graphs 3.4 Trees 3.5 Rooted Trees 3.5.1 Tree traversals 3.6 Binary Trees 3.6.1 Some quantitative aspects of binary trees 3.6.2 Binary search trees 3.7 Exercises 3.8 Bibliographic Notes Chapter 4 Heaps and the Disjoint Sets Data Structures 4.1 Introduction 4.2 Heaps 4.2.1 Operations on heaps 4.2.2 Creating a heap 4.2.3 Heapsort 4.2.4 Min and max heaps 4.3 Disjoint Sets Data Structures 4.3.1 The union by rank heuristic 4.3.2 Path compression 4.3.3 The union-find algorithms 4.3.4 Analysis of the union-find algorithms 4.4 Exercises 4.5 Bibliographic Notes PART 2 Techniques Based on Recursion Chapter 5 Induction 5.1 Introduction 5.2 Two Simple Examples 5.2.1 Selection sort 5.2.2 Insertion sort 5.3 Radix Sort 5.4 Integer Exponentiation 5.5 Evaluating Polynomials (Hornet's Rule) 5.6 Generating Permutations 5.6.1 The first algorithm 5.6.2 The second algorithm 5.7 Finding the Majority Element 5.8 Exercises 5.9 Bibliographic Notes Chapter 6 Divide and Conquer 6.1 Introduction 6.2 Binary Search 6.3 Mergesort 6.3.1 How the algorithm works 6.3.2 Analysis cf the mergesort algorithm 6.4 The Divide and Conquer Paradigm 6.5 Selection: Finding the Median and the kth Smallest Element 6.5.1 Analysis cf the selection algorithm 6.6 Quicksort 6.6.1 A partitioning algorithm 6.6.2 The sorting algorithm 6.6.3 Analysis of the quicksort algorithm 6.6.3.1 The worst case behavior 6.6.3.2 The average case behavior 6.6.4 Compariscn of sorting algorithms 6.7 Multiplication of Large Integers 6.8 Matrix Multiplication 6.8.1 The traditional algorithm 6.8.2 Recursive version 6.8.3 Strassen's algorithm 6.8.4 Comparisons cf the three algorithms 6.9 The Closest Pair Problem 6.9.1 Time complexity …… PART 3 First-Cut Techniques PART 4 Complexity of Problems PART 5 Coping with Hardness PART 6 Iterative Improvement for Domain-Specific Problems PART 7 Techniques in Computational Geometry

序言

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 performance 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 different problems emerged. The similarities among different algorithms for certain classes of problems have resulted in general algorithm design techniques. 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 special 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 algorithms 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 establishing 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 number 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.g. 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[l..n+] A[ l . .n] is to replace each entry B[i] with A[i] for all i , l 5 i 5 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 possibility of either coming up with an efficient algorithm for that problem, or proving its intractability. This part covers NP-completeness, computational 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 using 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 maximum 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 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 materia1 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/l82. 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. Albassam, H. AImuallim, and S. Ghanta for their valuable comments. Dhahmn, Saudi Arabia M. H. Alsuwaiyel