实例介绍
【实例简介】
较老的一本资料，网上有pdf格式，我这里做了裁剪，页面干净，且加了封面。
Preface The feld 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- piques. 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 ain 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- ng 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 echniques. Each technique is illustrated by providing an adequate num- 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. 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[1.川]←A1n is to replace each ent酬 with Ai for al,1≤讠≤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 chapt 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 appro ach 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 eficient algorithm for that problem, or proving its intractability. This part covers NP-completens 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 ug- 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 fow 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 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 SsUme 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. Albassam H. Almuallim, and S Ghanta for their valuable comments Dhahran, Saudi arabia M.H. Alsuwaiyel Contents Preface PART 1 Basic Concepts and Introduction to algorithms 1 Chapter 1 Basic Concepts in Algorithmic Analysis 1.1 Introduction 1.2 Historical Background 6 1.3 Binary Search 8 1.3.1 Analysis of the binary search algorithm 1.4 Merging Two Sorted Lists 12 1.5 Selection Sort 14 1.6 Insertion Sort 15 1.7 Bottom-Up Merge Sorting 1.7.1 Analysis of bottom-up merge sorting 19 1. 8 Time Complexity 1.8.1 Order of growth 21 1.8.2 The O-notation 25 1.8.3 The n-notation 26 1.8.4 The e-notation 1.8.5 Examples 29 1.8.6 Complexity classes and the o-notation 3 1.9 Space Complexity 32 1.10 Optimal Algorithms 34 I Contents 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 38 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 红46红 1. 13 Amortized Analysis 1.14 Input Size and Problem Instance 50 1. 15 Exercises 52 1. 16 Bibliographic Notes 19 Chapter 2 Mathematical Preliminaries 6 2.1 Sets, Relationg and Functions..,,...............61 2.1.1 Sets 62 2. 1.2 Relations 63 2.1.2.1 Equivalence reations 2.1.3 Functions 2.2 Proof Methods 2.2.1 Direct proof 2.2.2 Indirect proof...,,. 66 2.2.3 Proof by contradiction 66 2.2.4 Proof by counterexample ....... 67 2. 2.5 Mathematical induction 68 2.3 Logarithms 69 2. 4 Floor and Ceiling Fanctions 2.5 Factorial and Binomial Coeficients 2.5.1 Factorials 2.5.2 Binomial coeficients 2.6 The Pigeonhole Principle 75 27 Summations.··· 76 2.7.1 Approximation of summations by integration 8 2.8 Recurrence relations 82 2.8,1 Solution of linear homogeneous recurrences 83 2.8.2 Solution of inhomogeneous recurrence 2.8.3 Solution of divide-and-conquer recurrences 87 2.8.3. 1 Expanding the recurrence 87 2.8.3.2 Substitution 91 C0ten打 2. 9 Exercise 0 3 Change of variables Chapter 3 Data Structures 103 3.1 Introduction 103 3.2 Linked lists 103 3.2. 1 Stacks and queues 104 3.3 Graphs...,., 10 3.3. 1 Representation of graph 3.3.2 Planar graphs 107 34鱼k 108 3.5 Rooted Tre 3.5. 1 ree traversals 109 3.6 Binary Th 109 3.6.1 Some quantitative aspects of binary trees 111 3.6.2 Binary search trees 112 3.7 Erercise 112 3. 8 Bibliographic Notes 114 Chapter 4 Heaps and the disjoint Sets Data Structures 115 4. 1 Introduction ◆··■● 115 4.2 Hea 4.2.1 Operationa on heat 116 4.2.2 Creating a heap 120 4.2.3 Heapsort 124 4.2.4 Min and max heaps 125 4.3 Disjoint Sets Data Structures 125 4.3.1 The union by rank heuristic 127 4.3. 2 Path compression 129 4.3.3 The union-find algorithms ....130 4.3.4 Analysis of the union-find algorithms 132 4.4 Exercises .134 4.5 Bibliographic Notes 137 PART 2 Techniques Based on Recursion 139 Chapter 5 Induction 14s XIV Contents 5.1 Introduction ,,。,,143 5.2 Two Simple Examples 。,,,,,,,14生 5.2.1 Selection sort 144 5.2.2 Insertion sort 5.3 Radix sort 145 5.4 Integer Exponentiation 5.5 Evaluating Polynomials(Horner's Rule) 149 5.6 Generating Permutations 。..,,150 5.6. 1 The first algorithm 150 5.6.2 The second algorithm 152 5.7 Finding the Majority Element 154 5.8 Exercise 。..,155 5.9 Bibliographic Notes 158 Chapter 6 Divide and Conquer 161 6.1 Introduction 161 6.2 Binary Search 163 6.3 Mergesort 165 6.3.1 How the algorithm works 166 6.3, 2 Analysis of the mergesort algorithm ,167 6.4 The Divide and Conquer Paradigm 169 6.5 Selection: Finding the Median and the kth Smallest Element. 172 6.5. 1 Analysis of the selection algorithm ..175 6.6 Quicksort 177 6.6. 1 A partitioning algorith 177 6.6.2 The sorting algorithm 179 6.6.3 Analysis of the quicksort algorithm 18l 6.6.3.1 The worst case behavior ,,181 6.6.3.2 The average case behavior.....,.... 184 6.6.4 Comparison of sorting algorithms 186 6.7 Multiplication of Large Integers 187 6.8 Matrix Multiplication 188 6.8.1 The traditional algorithm 188 6.8.2 Recursive version 188 6.8.3 Strassen's algorithm 190 6.8.4 Comparisons of the three algoritH 19 6.9 The Closest Pair Problem 192 6.9.1 Time complexity 194 Con tents XY 6.10 Exercises 195 6.11 Bibliographic Notes 202 Chapter 7 Dynamic Programming 203 7.1 Introduction 203 7. 2 The Longest Common Subsequence Problem 205 7.3 Matrix Chain Multiplication 208 7 4 The Dymamic Programming Paradigm 214 7.5 The All-Pairs Shortest Path Problem 215 7. 6 The Knapsack Problen 21 7.7 Exercises 7. 8 Bibliographic Notes .226 PART 3 First-Cut Techniques 227 Chapter 8 The Greedy Approach 21 8.1 Introduction。,,, 231 8.2 The Shortest Path Problem 232 8.2.1 A linear time algorithm for dense graphs 237 8.3 Minimum Cost Spanning Trees(Kruskal's Algorithm) 239 8.4 Minimum Cost Spanning Trees(Prim,s Algorithm) 242 8.4.1 A linear time algorithm for dense graphs 246 8.5 File compression 248 8.6 Exercises 5 8.7 Bibliographic Notes 255 Chapter g Graph Traversal 257 0.1 Introduction 257 9.2 Depth-First Search 257 9.2.1 Time complexity of depth-first search 261 9.3 Applications of Depth-First Search 262 9.3.1 Graph acyclicity 262 9.3.2 Topological sorting 262 9.3.3 Finding articulation points in a graph 263 9.3.4 Strongly connected components 266 9.4 Breadth-First Search 267 9.5 Applications of Breadth- First Search 269 【实例截图】
【核心代码】
较老的一本资料，网上有pdf格式，我这里做了裁剪，页面干净，且加了封面。
Preface The feld 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- piques. 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 ain 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- ng 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 echniques. Each technique is illustrated by providing an adequate num- 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. 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[1.川]←A1n is to replace each ent酬 with Ai for al,1≤讠≤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 chapt 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 appro ach 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 eficient algorithm for that problem, or proving its intractability. This part covers NP-completens 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 ug- 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 fow 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 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 SsUme 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. Albassam H. Almuallim, and S Ghanta for their valuable comments Dhahran, Saudi arabia M.H. Alsuwaiyel Contents Preface PART 1 Basic Concepts and Introduction to algorithms 1 Chapter 1 Basic Concepts in Algorithmic Analysis 1.1 Introduction 1.2 Historical Background 6 1.3 Binary Search 8 1.3.1 Analysis of the binary search algorithm 1.4 Merging Two Sorted Lists 12 1.5 Selection Sort 14 1.6 Insertion Sort 15 1.7 Bottom-Up Merge Sorting 1.7.1 Analysis of bottom-up merge sorting 19 1. 8 Time Complexity 1.8.1 Order of growth 21 1.8.2 The O-notation 25 1.8.3 The n-notation 26 1.8.4 The e-notation 1.8.5 Examples 29 1.8.6 Complexity classes and the o-notation 3 1.9 Space Complexity 32 1.10 Optimal Algorithms 34 I Contents 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 38 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 红46红 1. 13 Amortized Analysis 1.14 Input Size and Problem Instance 50 1. 15 Exercises 52 1. 16 Bibliographic Notes 19 Chapter 2 Mathematical Preliminaries 6 2.1 Sets, Relationg and Functions..,,...............61 2.1.1 Sets 62 2. 1.2 Relations 63 2.1.2.1 Equivalence reations 2.1.3 Functions 2.2 Proof Methods 2.2.1 Direct proof 2.2.2 Indirect proof...,,. 66 2.2.3 Proof by contradiction 66 2.2.4 Proof by counterexample ....... 67 2. 2.5 Mathematical induction 68 2.3 Logarithms 69 2. 4 Floor and Ceiling Fanctions 2.5 Factorial and Binomial Coeficients 2.5.1 Factorials 2.5.2 Binomial coeficients 2.6 The Pigeonhole Principle 75 27 Summations.··· 76 2.7.1 Approximation of summations by integration 8 2.8 Recurrence relations 82 2.8,1 Solution of linear homogeneous recurrences 83 2.8.2 Solution of inhomogeneous recurrence 2.8.3 Solution of divide-and-conquer recurrences 87 2.8.3. 1 Expanding the recurrence 87 2.8.3.2 Substitution 91 C0ten打 2. 9 Exercise 0 3 Change of variables Chapter 3 Data Structures 103 3.1 Introduction 103 3.2 Linked lists 103 3.2. 1 Stacks and queues 104 3.3 Graphs...,., 10 3.3. 1 Representation of graph 3.3.2 Planar graphs 107 34鱼k 108 3.5 Rooted Tre 3.5. 1 ree traversals 109 3.6 Binary Th 109 3.6.1 Some quantitative aspects of binary trees 111 3.6.2 Binary search trees 112 3.7 Erercise 112 3. 8 Bibliographic Notes 114 Chapter 4 Heaps and the disjoint Sets Data Structures 115 4. 1 Introduction ◆··■● 115 4.2 Hea 4.2.1 Operationa on heat 116 4.2.2 Creating a heap 120 4.2.3 Heapsort 124 4.2.4 Min and max heaps 125 4.3 Disjoint Sets Data Structures 125 4.3.1 The union by rank heuristic 127 4.3. 2 Path compression 129 4.3.3 The union-find algorithms ....130 4.3.4 Analysis of the union-find algorithms 132 4.4 Exercises .134 4.5 Bibliographic Notes 137 PART 2 Techniques Based on Recursion 139 Chapter 5 Induction 14s XIV Contents 5.1 Introduction ,,。,,143 5.2 Two Simple Examples 。,,,,,,,14生 5.2.1 Selection sort 144 5.2.2 Insertion sort 5.3 Radix sort 145 5.4 Integer Exponentiation 5.5 Evaluating Polynomials(Horner's Rule) 149 5.6 Generating Permutations 。..,,150 5.6. 1 The first algorithm 150 5.6.2 The second algorithm 152 5.7 Finding the Majority Element 154 5.8 Exercise 。..,155 5.9 Bibliographic Notes 158 Chapter 6 Divide and Conquer 161 6.1 Introduction 161 6.2 Binary Search 163 6.3 Mergesort 165 6.3.1 How the algorithm works 166 6.3, 2 Analysis of the mergesort algorithm ,167 6.4 The Divide and Conquer Paradigm 169 6.5 Selection: Finding the Median and the kth Smallest Element. 172 6.5. 1 Analysis of the selection algorithm ..175 6.6 Quicksort 177 6.6. 1 A partitioning algorith 177 6.6.2 The sorting algorithm 179 6.6.3 Analysis of the quicksort algorithm 18l 6.6.3.1 The worst case behavior ,,181 6.6.3.2 The average case behavior.....,.... 184 6.6.4 Comparison of sorting algorithms 186 6.7 Multiplication of Large Integers 187 6.8 Matrix Multiplication 188 6.8.1 The traditional algorithm 188 6.8.2 Recursive version 188 6.8.3 Strassen's algorithm 190 6.8.4 Comparisons of the three algoritH 19 6.9 The Closest Pair Problem 192 6.9.1 Time complexity 194 Con tents XY 6.10 Exercises 195 6.11 Bibliographic Notes 202 Chapter 7 Dynamic Programming 203 7.1 Introduction 203 7. 2 The Longest Common Subsequence Problem 205 7.3 Matrix Chain Multiplication 208 7 4 The Dymamic Programming Paradigm 214 7.5 The All-Pairs Shortest Path Problem 215 7. 6 The Knapsack Problen 21 7.7 Exercises 7. 8 Bibliographic Notes .226 PART 3 First-Cut Techniques 227 Chapter 8 The Greedy Approach 21 8.1 Introduction。,,, 231 8.2 The Shortest Path Problem 232 8.2.1 A linear time algorithm for dense graphs 237 8.3 Minimum Cost Spanning Trees(Kruskal's Algorithm) 239 8.4 Minimum Cost Spanning Trees(Prim,s Algorithm) 242 8.4.1 A linear time algorithm for dense graphs 246 8.5 File compression 248 8.6 Exercises 5 8.7 Bibliographic Notes 255 Chapter g Graph Traversal 257 0.1 Introduction 257 9.2 Depth-First Search 257 9.2.1 Time complexity of depth-first search 261 9.3 Applications of Depth-First Search 262 9.3.1 Graph acyclicity 262 9.3.2 Topological sorting 262 9.3.3 Finding articulation points in a graph 263 9.3.4 Strongly connected components 266 9.4 Breadth-First Search 267 9.5 Applications of Breadth- First Search 269 【实例截图】
【核心代码】
标签：
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论