Details

A Textbook of Data Structures and Algorithms, Volume 3


A Textbook of Data Structures and Algorithms, Volume 3

Mastering Advanced Data Structures and Algorithm Design Strategies
1. Aufl.

von: G. A. Vijayalakshmi Pai

126,99 €

Verlag: Wiley
Format: PDF
Veröffentl.: 09.12.2022
ISBN/EAN: 9781394191994
Sprache: englisch
Anzahl Seiten: 368

DRM-geschütztes eBook, Sie benötigen z.B. Adobe Digital Editions und eine Adobe ID zum Lesen.

Beschreibungen

<p>Data structures and algorithms is a fundamental course in Computer Science, which enables learners across any discipline to develop the much-needed foundation of efficient programming, leading to better problem solving in their respective disciplines.</p> <p><i>A Textbook of Data Structures and Algorithms</i> is a textbook that can be used as course material in classrooms, or as self-learning material. The book targets novice learners aspiring to acquire advanced knowledge of the topic. Therefore, the content of the book has been pragmatically structured across three volumes and kept comprehensive enough to help them in their progression from novice to expert.</p> <p>With this in mind, the book details concepts, techniques and applications pertaining to data structures and algorithms, independent of any programming language. It includes 181 illustrative problems and 276 review questions to reinforce a theoretical understanding and presents a suggestive list of 108 programming assignments to aid in the implementation of the methods covered.</p>
<p>Preface xi</p> <p>Acknowledgments xvii</p> <p><b>Chapter 13 Hash Tables 1</b></p> <p>13.1 Introduction 1</p> <p>13.1.1 Dictionaries 1</p> <p>13.2 Hash table structure 2</p> <p>13.3 Hash functions 4</p> <p>13.3.1 Building hash functions 4</p> <p>13.4 Linear open addressing 5</p> <p>13.4.1 Operations on linear open addressed hash tables 8</p> <p>13.4.2 Performance analysis 10</p> <p>13.4.3 Other collision resolution techniques with open addressing 11</p> <p>13.5 Chaining 13</p> <p>13.5.1 Operations on chained hash tables 15</p> <p>13.5.2 Performance analysis 17</p> <p>13.6 Applications 18</p> <p>13.6.1 Representation of a keyword table in a compiler 18</p> <p>13.6.2 Hash tables in the evaluation of a join operation on relational databases 19</p> <p>13.6.3 Hash tables in a direct file organization 22</p> <p>13.7 Illustrative problems 23</p> <p><b>Chapter 14 File Organizations 33</b></p> <p>14.1 Introduction 33</p> <p>14.2 Files 34</p> <p>14.3 Keys 36</p> <p>14.4 Basic file operations 38</p> <p>14.5 Heap or pile organization 38</p> <p>14.5.1 Insert, delete and update operations 39</p> <p>14.6 Sequential file organization 39</p> <p>14.6.1 Insert, delete and update operations 39</p> <p>14.6.2 Making use of overflow blocks 40</p> <p>14.7 Indexed sequential file organization 41</p> <p>14.7.1 Structure of the ISAM files 41</p> <p>14.7.2 Insert, delete and update operations for a naïve ISAM file 42</p> <p>14.7.3 Types of indexing 43</p> <p>14.8 Direct file organization 48</p> <p>14.9 Illustrative problems 50</p> <p><b>Chapter 15 k-d Trees and Treaps 61</b></p> <p>15.1 Introduction 61</p> <p>15.2 k-d trees: structure and operations 61</p> <p>15.2.1 Construction of a k-d tree 65</p> <p>15.2.2 Insert operation on k-d trees 69</p> <p>15.2.3 Find minimum operation on k-d trees 70</p> <p>15.2.4 Delete operation on k-d trees 72</p> <p>15.2.5 Complexity analysis and applications of k-d trees 74</p> <p>15.3 Treaps: structure and operations 76</p> <p>15.3.1 Treap structure 76</p> <p>15.3.2 Operations on treaps 77</p> <p>15.3.3 Complexity analysis and applications of treaps 82</p> <p>15.4 Illustrative problems 83</p> <p><b>Chapter 16 Searching 93</b></p> <p>16.1 Introduction 93</p> <p>16.2 Linear search 94</p> <p>16.2.1 Ordered linear search 94</p> <p>16.2.2 Unordered linear search 94</p> <p>16.3 Transpose sequential search 96</p> <p>16.4 Interpolation search 98</p> <p>16.5 Binary search 100</p> <p>16.5.1 Decision tree for binary search 101</p> <p>16.6 Fibonacci search 104</p> <p>16.6.1 Decision tree for Fibonacci search 105</p> <p>16.7 Skip list search 108</p> <p>16.7.1 Implementing skip lists 112</p> <p>16.7.2 Insert operation in a skip list 113</p> <p>16.7.3 Delete operation in a skip list 114</p> <p>16.8 Other search techniques 116</p> <p>16.8.1 Tree search 116</p> <p>16.8.2 Graph search 116</p> <p>16.8.3 Indexed sequential search 116</p> <p>16.9 Illustrative problems 118</p> <p><b>Chapter 17 Internal Sorting 131</b></p> <p>17.1 Introduction 131</p> <p>17.2 Bubble sort 132</p> <p>17.2.1 Stability and performance analysis 134</p> <p>17.3 Insertion sort 135</p> <p>17.3.1 Stability and performance analysis 136</p> <p>17.4 Selection sort 138</p> <p>17.4.1 Stability and performance analysis 140</p> <p>17.5 Merge sort 140</p> <p>17.5.1 Two-way merging 141</p> <p>17.5.2 k-way merging 143</p> <p>17.5.3 Non-recursive merge sort procedure 144</p> <p>17.5.4 Recursive merge sort procedure 145</p> <p>17.6 Shell sort 147</p> <p>17.6.1 Analysis of shell sort 153</p> <p>17.7 Quick sort 153</p> <p>17.7.1 Partitioning 153</p> <p>17.7.2 Quick sort procedure 156</p> <p>17.7.3 Stability and performance analysis 158</p> <p>17.8 Heap sort 159</p> <p>17.8.1 Heap 159</p> <p>17.8.2 Construction of heap 160</p> <p>17.8.3 Heap sort procedure 163</p> <p>17.8.4 Stability and performance analysis 167</p> <p>17.9 Radix sort 167</p> <p>17.9.1 Radix sort method 167</p> <p>17.9.2 Most significant digit first sort 171</p> <p>17.9.3 Performance analysis 171</p> <p>17.10 Counting sort 171</p> <p>17.10.1 Performance analysis 175</p> <p>17.11 Bucket sort 175</p> <p>17.11.1 Performance analysis 178</p> <p>17.12 Illustrative problems 179</p> <p><b>Chapter 18 External Sorting 197</b></p> <p>18.1 Introduction 197</p> <p>18.1.1 The principle behind external sorting 197</p> <p>18.2 External storage devices 198</p> <p>18.2.1 Magnetic tapes 199</p> <p>18.2.2 Magnetic disks 200</p> <p>18.3 Sorting with tapes: balanced merge 202</p> <p>18.3.1 Buffer handling 204</p> <p>18.3.2 Balanced P-way merging on tapes 205</p> <p>18.4 Sorting with disks: balanced merge 206</p> <p>18.4.1 Balanced k-way merging on disks 207</p> <p>18.4.2 Selection tree 208</p> <p>18.5 Polyphase merge sort 212</p> <p>18.6 Cascade merge sort 214</p> <p>18.7 Illustrative problems 216</p> <p><b>Chapter 19 Divide and Conquer 229</b></p> <p>19.1 Introduction 229</p> <p>19.2 Principle and abstraction 229</p> <p>19.3 Finding maximum and minimum 231</p> <p>19.3.1 Time complexity analysis 232</p> <p>19.4 Merge sort 233</p> <p>19.4.1 Time complexity analysis 233</p> <p>19.5 Matrix multiplication 234</p> <p>19.5.1 Divide and Conquer-based approach to “high school” method of matrix multiplication 234</p> <p>19.5.2 Strassen’s matrix multiplication algorithm 236</p> <p>19.6 Illustrative problems 239</p> <p><b>Chapter 20 Greedy Method 245</b></p> <p>20.1 Introduction 245</p> <p>20.2 Abstraction 245</p> <p>20.3 Knapsack problem 246</p> <p>20.3.1 Greedy solution to the knapsack problem 247</p> <p>20.4 Minimum cost spanning tree algorithms 249</p> <p>20.4.1 Prim’s algorithm as a greedy method 250</p> <p>20.4.2 Kruskal’s algorithm as a greedy method 250</p> <p>20.5 Dijkstra’s algorithm 251</p> <p>20.6 Illustrative problems 251</p> <p><b>Chapter 21 Dynamic Programming 261</b></p> <p>21.1 Introduction 261</p> <p>21.2 0/1 knapsack problem 263</p> <p>21.2.1 Dynamic programming-based solution 264</p> <p>21.3 Traveling salesperson problem 266</p> <p>21.3.1 Dynamic programming-based solution 267</p> <p>21.3.2 Time complexity analysis and applications of traveling salesperson problem 269</p> <p>21.4 All-pairs shortest path problem 269</p> <p>21.4.1 Dynamic programming-based solution 270</p> <p>21.4.2 Time complexity analysis 272</p> <p>21.5 Optimal binary search trees 272</p> <p>21.5.1 Dynamic programming-based solution 274</p> <p>21.5.2 Construction of the optimal binary search tree 276</p> <p>21.5.3 Time complexity analysis 279</p> <p>21.6 Illustrative problems 280</p> <p><b>Chapter 22 P and NP Class of Problems 287</b></p> <p>22.1 Introduction 287</p> <p>22.2 Deterministic and nondeterministic algorithms 289</p> <p>22.3 Satisfiability problem 292</p> <p>22.3.1 Conjunctive normal form and Disjunctive normal form 294</p> <p>22.3.2 Definition of the satisfiability problem 294</p> <p>22.3.3 Construction of CNF and DNF from a logical formula 295</p> <p>22.3.4 Transformation of a CNF into a 3-CNF 296</p> <p>22.3.5 Deterministic algorithm for the satisfiability problem 297</p> <p>22.3.6 Nondeterministic algorithm for the satisfiability problem 297</p> <p>22.4 NP-complete and NP-hard problems 297</p> <p>22.4.1 Definitions 298</p> <p>22.5 Examples of NP-hard and NP-complete problems 300</p> <p>22.6 Cook’s theorem 302</p> <p>22.7 The unsolved problem P = NP 303</p> <p>22.8 Illustrative problems 304</p> <p>References 311</p> <p>Index 313</p> <p>Summaries of other volumes 317 </p>
<p><b>G A Vijayalakshmi Pai</b>, SMIEEE, is a Professor of Computer Applications at PSG College of Technology, Coimbatore, India. She has authored books and investigated research projects funded by government agencies in the disciplines of Computational Finance and Computational Intelligence.</p>

Diese Produkte könnten Sie auch interessieren:

Intelligent Systems for Rehabilitation Engineering
Intelligent Systems for Rehabilitation Engineering
von: Roshani Raut, Pranav Pathak, Sandeep Kautish, Pradeep N.
EPUB ebook
190,99 €
Cyber Security and Digital Forensics
Cyber Security and Digital Forensics
von: Mangesh M. Ghonge, Sabyasachi Pramanik, Ramchandra Mangrulkar, Dac-Nhuong Le
PDF ebook
190,99 €
Smart Systems for Industrial Applications
Smart Systems for Industrial Applications
von: C. Venkatesh, N. Rengarajan, P. Ponmurugan, S. Balamurugan
EPUB ebook
190,99 €