Introduction to Algorithms and Data Structures

所需积分/C币:10 2018-07-17 10:11:53 1.73MB PDF
收藏 收藏

3.2 Sorted lists and binary search 72 3.3 Binary search trcs 3.4 Self-balancing binary and multiway search trees 77 82 3.5 Hash table 88 3.6 Notes..,,,, 101 II Introduction to Graph algorithms 4 The Graph Abstract Data Type l04 4.1 Basic definitions 104 4.2 Digraphs and data structures ,,,,,.,,,110 4.3 Implementation of digraph ADT operations 4.1 Notes ,116 5 Graph Traversals and applications 1l7 5.1 Generalities on graph traversal 1l7 5.2 DES and bfs 5.3 Additional properties of depth-first scarch 124 5.4 Additional properties of breadth-first search 129 5.5 Priority-first search 132 5.6 Acyclic digraphs and topological ordering .............. 133 5.7 Connectivity ,,138 5.8 Cycles 142 5.9 Maximum matchings 145 5.10 Notes 150 6 Weighted Digraphs and Optimization Problems 15l 6.1 Weighted digraphs 15l 6.2 Distance and diameter in the unweighted case 153 6.3 Single-source shortest path problem 154 6.4 All-pairs shortest path problem 16l 6.5 Minimum spanning tree problem ,164 6.6 Hard graph problems l68 6.7N 169 Ill Appendices l70 a Java code for Searching and Sorting l71 A1 Sorting and selection l71 A2 Search methods 176 B Java graph ADT 178 B. 1 Java adjaccncy matrix implementation ,,,,,,,,181 B 2 Java adjacency lists implementation ,,186 B 3 Standardized Java graph class ......191 B4 Extended graph classes: weighted edges 着·香 l92 C Background on Data Structures 20l C1 Informal discussion of adts 20l C2 Notes on a more formal approach 203 D Mathematical Background 204 D,1 Sets ,....,204 D2 Mathematical induction .205 D3 Relations 205 D 4 Basic rules of logarithms ,,.,206 D5 LHOpitals rule 207 D6 Arithmetic, geometric, and other series .207 D.7 Trees,,,,,,,,,, ,,,,,209 E Solutions to selected exercises 21I Bibliography 234 Index 235 List of Figures 1.1 Linear-time algorithm to sum an array 17 1.2 Quadratic time algorithm to compute sums of an array 18 1.3 Linear-time algorithm to compute sums of an array 19 1.4 Big Oh"property: g n)is o(n) 23 1.5 Telescoping as a recursive substitution 34 2.1 Insertion sort for arrays 2.2 Recursive mergesort for arrays 48 2. 3 Linear time merge for arrays 49 2.4 Basic array-based quicksort 55 2.5 Complete binary tree and its array representation 56 2.6 Maximum heap and its array representation 58 2.7 Heapsort 番垂 61 2.8 Basic array-based quickselect 2.9 Dccision trcc for n=3 66 3.1 A sequential search algorithm 72 3.2 Binary search for the key 42 3.3 Binary tree representation of a sorted array. 3.4 Binary search with thrcc-way comparisons 76 3.5 Faster binary search with two-way comparisons 3.6 Binary trees: only the leftmost tree is a binary search tree 77 3.7 Search and insertion in the binary search tree 78 3. 8 Removal of the node with key 10 from the binary search tree 79 3.9 Binary search trees obtained by permutations of 1, 2, 3, 4. 80 3.10 Binary search trees of height about logn. 81 3.11 Binary search trees of height about n 81 3. 12 Left and right rotations of a bst 83 3.13 Multiway search tree of order m= 4 3. 14 2-4 B-trec with the lcaf storage sizc 7 87 3.15 Birthday paradox: Pr365(n) 94 4.1 A graph GI and a digraph G2 105 4.2 A subdigraph and a spanning subdigraph of G2 ,,108 4.3 The subdigraph of G2 induced by ( 1, 2, 3....................109 4.4 The reverse of digraph G2 l09 4.5 The underlying graph of G2 l10 5.1 Graph traversal schema ,,,,,,,118 5.2 Node states in the middle of a digraph traversal l18 5.3 Decomposition of a digraph in terms of search trees ,,,,,,.120 5.4 A graph GI and a digraph G2 ··· 123 5.5 BFS trees for GI and G2, rooted at O ,123 5.6 DFS trees for Gi and g2, rooted at O .124 5.7 Depth-first search algorithm 126 5.8 Recursive DFS visit algorithm ,,127 5.9 Breadth-first search algorithm l30 5.10 Priority-first search algorithm (first kind) ,,,134 5.11 Digraph describing structure of an arithmetic expression........... 135 5.12 Topological orders of some DAgs 136 5.13 A digraph and its strongly connected components 140 5.14 Structure of a digraph in terms of its strong components 14 40 5. 15 Some(di)graphs with different cycle behaviour. ,,143 5. 16 A bipartite graph l44 5. 17 A maximal and maximum matching in a bipartite graph. ,,146 5. 18 An algorithm to find an augmenting path ...147 5. 19 Structure of the graph traversal tree for finding augmenting paths..... 149 6.1 Some weighted (di)graphs ..152 6.2 Dijkstra's algorithm, first version. ,155 6.3 Picture for proof of Dijkstra's algorithm ,157 6.4 Dijkstra's algorithm, PFS version .158 6.5 Bellman-Ford algorithm ,159 6.6 Floyd's algorithm ...,,162 6.7 Prims algorithm 167 6.8 Kruskal's algorithm l68 B. 1 Sample output of the graph test program. ,,193 D 1 Approximation of an integral by lower rectangles 209 List of Tables 1.1 Relative growth of linear and quadratic terms in an expression 1. 2 Relative growth of running time T(n)when the input size increases..... 27 1.3 The largest data sizes n that can be processed by an algorithm 28 2.1 Sample execution of insertion sort ·· 42 2.2 Number of inversions i, comparisons Ci and data moves Mi 44 2.3 Partitioning in quicksort with pivot p=31 54 2.4 Inserting a new node with the key 75 in the heap in Figure 2.6........ 59 2. 5 Deletion of the maximum key from the heap in Figure 2.6 59 2.6 Successive steps of heapsort 62 3.1 A map between airport codes and locations. 3.2 Height of the optimal m-ary search tree with n nodes 85 3.3 Open addressing with linear probing (OALP ..90 3.4 Open addressing with double hashing (OADh) 91 3.5 Birthday paradox: Pr365(n) 93 3.6 Average search time bounds in hash tables with load factor n 97 4.1 Digraph operations in terms of data structures l14 4.2 Comparative worst-case performance of adjacency lists and matrices... 115 6.1 Illustrating Dijkstra's algorithm 156 Introduction to the fourth edition The fourth edition follows the third edition, while incorporates fixes for the errata discovered in the third edition The textbook's coverpage displays the complete list of 88 connected forbidden minors for graphs with vertex cover at most 6, computed by m.J. Dinneen and L Xiong in 2001 This work is licensed under a creative commons attribution - Non commercial 3.0 Unported license Michael Dinne Georgy gimel'farb Mark C. wilson Department of Computer Science University of Auckland Auckland New zealand imjd, georgy, mcwj@cs. auckland. ac, nz 2016 Introduction to the third edition The focus for this third edition has been to make an electronic version that students can read on the tablets and laptops that they bring to lectures. The main changes from the sccond edition arc Incorporated fixes for the errata discovered in the second edition Made e-book friendly by adding cross referencing links to document elements and formatted pages to fit on most small screen tablets (i. e, width of margins minimized) Limited material for University of Auckland,'s CompSci 220 currently taught topics. Removed the two chapters on formal languages(Part Iln) and truncated the book title e This work is licensed under a creative Commons attribution -Non commercial 3.0 Unported licens Michael]. Dinneen Georgy gimel'farb Mark c. wilson Department of Computer science University of Auckland Auckland. New zealand imjd, georgy, mcu I@cs. auckland. ac nz March 2013 Introduction to the second edition Writing a second edition is a thankless task, as is well known to authors. Much of the time is spent on small improvements that are not obvious to readers We have taken considcrable cfforts to correct a large number of crrors found in the first edition, and to improve explanation and presentation throughout the book, while retaining the philosophy behind the original. As far as material goes, the main changes are more cxcrciscs and solutions to many of thcm a new section on maximum matching(Section 5.9) a new section on string searching(Part IID a Java graph library updated to Java 1.6 and freely available for download Thewebsite vides additional material including source code Readers finding errors are encour aged to contact us after viewing the errata page at this web site In addition to the acknowledgments in the first edition, we thank Sonny datt for help with updating the Java graph library, andrew Hay for help with exercise solu tions and Cris Calude for comments. Rob Randtoul( PlasmaDesign co uk)kindl allowed us to use his cube artwork for the books cover. Finally, we thank MJD all students who have struggled to learn from the first edition and have given us feedback, either positive or negative GlG my wife Natasha and all the family for their permanent help and support MCW my wife golbon and sons Yusef and Yahya, for their sacrifices during the writ ing of this book, and the joy they bring to my life even in the toughest times 31 October 2008

试读 127P Introduction to Algorithms and Data Structures
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    关注 私信 TA的资源
    Introduction to Algorithms and Data Structures 10积分/C币 立即下载
    Introduction to Algorithms and Data Structures第1页
    Introduction to Algorithms and Data Structures第2页
    Introduction to Algorithms and Data Structures第3页
    Introduction to Algorithms and Data Structures第4页
    Introduction to Algorithms and Data Structures第5页
    Introduction to Algorithms and Data Structures第6页
    Introduction to Algorithms and Data Structures第7页
    Introduction to Algorithms and Data Structures第8页
    Introduction to Algorithms and Data Structures第9页
    Introduction to Algorithms and Data Structures第10页
    Introduction to Algorithms and Data Structures第11页
    Introduction to Algorithms and Data Structures第12页
    Introduction to Algorithms and Data Structures第13页
    Introduction to Algorithms and Data Structures第14页
    Introduction to Algorithms and Data Structures第15页
    Introduction to Algorithms and Data Structures第16页
    Introduction to Algorithms and Data Structures第17页
    Introduction to Algorithms and Data Structures第18页
    Introduction to Algorithms and Data Structures第19页
    Introduction to Algorithms and Data Structures第20页


    10积分/C币 立即下载 >