Normal view MARC view ISBD view

A practical introduction to data structures and algorithm analysis / (Record no. 6877)

MARC details
000 -LEADER
fixed length control field	07790cam a22002294a 4500
020 ## - INTERNATIONAL STANDARD BOOK NUMBER
ISBN	9780130284464
Terms of availability	TZS 127,500/=
040 ## - CATALOGING SOURCE
Original cataloging agency	MUL
Language of cataloging	eng.
Description conventions	AACR
082 00 - DEWEY DECIMAL CLASSIFICATION NUMBER
Classification number	005.73 SHA
100 1# - MAIN ENTRY--AUTHOR NAME
Personal name	Shaffer, Clifford A.
245 12 - TITLE STATEMENT
Title	A practical introduction to data structures and algorithm analysis /
Statement of responsibility, etc	Clifford A. Shaffer.
246 3# - Varying form of Title
Title proper/short title	Introduction to data structures and algorithm analysis
246 3# - Varying form of Title
Title proper/short title	Data structures and algorithm analysis
250 ## - Edition Statement
Edition statement	2nd ed.
260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT)
Place of publication	Upper Saddle River, N.J. :
Name of publisher	Prentice Hall,
Year of publication	c2001.
300 ## - PHYSICAL DESCRIPTION
Number of Pages	xvi, 512 p. :
Other physical details	ill. ;
Dimensions	25 cm.
504 ## - BIBLIOGRAPHY, ETC. NOTE
Bibliography, etc	Includes bibliographical references (p. 497-501) and index.
505 ## - Formatted Contents
Formatted contents note	Preface xi <br/>I PRELIMINARIES 1 (84)<br/> Data Structures and Algorithms<br/> 3 (18)<br/> A Philosophy of Data Structures<br/> 4 (4)<br/> The Need for Data Structures<br/> 4 (2)<br/> Costs and Benefits<br/> 6 (2)<br/> Abstract Data Types and Data Structures<br/> 8 (4)<br/> Problems, Algorithms, and Programs<br/> 12 (3)<br/> Further Reading<br/> 15 (2)<br/> Exercises<br/> 17 (4)<br/> Mathematical Preliminaries<br/> 21 (28)<br/> Sets and Relations<br/> 21 (4)<br/> Miscellaneous Notation<br/> 25 (1)<br/> Logarithms<br/> 26 (2)<br/> Recursion<br/> 28 (2)<br/> Summations and Recurrences<br/> 30 (4)<br/> Mathematical Proof Techniques<br/> 34 (7)<br/> Proof by Contradiction<br/> 34 (1)<br/> Proof by Mathematical Induction<br/> 35 (6)<br/> Estimating<br/> 41 (2)<br/> Further Reading<br/> 43 (1)<br/> Exercises<br/> 43 (6)<br/> Algorithm Analysis<br/> 49 (36)<br/> Introduction<br/> 49 (6)<br/> Best, Worst, and Average Cases<br/> 55 (2)<br/> A Faster Computer, or a Faster Algorithm?<br/> 57 (2)<br/> Asymptotic Analysis<br/> 59 (6)<br/> Upper Bounds<br/> 60 (2)<br/> Lower Bounds<br/> 62 (1)<br/> Θ Notation<br/> 63 (1)<br/> Simplifying Rules<br/> 64 (1)<br/> Calculating the Running Time of a Program<br/> 65 (5)<br/> Analyzing Problems<br/> 70 (1)<br/> Common Misunderstandings<br/> 71 (1)<br/> Multiple Parameters<br/> 72 (1)<br/> Space Bounds<br/> 73 (3)<br/> Some Practical Considerations<br/> 76 (2)<br/> Further Reading<br/> 78 (1)<br/> Exercises<br/> 79 (4)<br/> Projects<br/> 83 (2)<br/>II FUNDAMENTAL DATA STRUCTURES 85 (132)<br/> Lists, Stacks, and Queues<br/> 87 (54)<br/> Lists<br/> 88 (25)<br/> Array-Based List Implementation<br/> 91 (4)<br/> Linked Lists<br/> 95 (10)<br/> Comparison of List Implementations<br/> 105 (2)<br/> Element Implementations<br/> 107 (1)<br/> Doubly Linked Lists<br/> 108 (5)<br/> The Dictionary ADT<br/> 113 (6)<br/> Stacks<br/> 119 (9)<br/> Array-Based Stacks<br/> 121 (1)<br/> Linked Stacks<br/> 122 (2)<br/> Comparison of Array-Based and Linked Stacks<br/> 124 (1)<br/> Implementing Recursion<br/> 125 (3)<br/> Queues<br/> 128 (5)<br/> Array-Based Queues<br/> 129 (4)<br/> Linked Queues<br/> 133 (1)<br/> Comparison of Array-Based and Linked Queues<br/> 133 (1)<br/> Further Reading<br/> 133 (1)<br/> Exercises<br/> 133 (5)<br/> Projects<br/> 138 (3)<br/> Binary Trees<br/> 141 (50)<br/> Definitions and Properties<br/> 141 (5)<br/> The Full Binary Tree Theorem<br/> 143 (2)<br/> A Binary Tree Node ADT<br/> 145 (1)<br/> Binary Tree Traversals<br/> 146 (3)<br/> Binary Tree Node Implementations<br/> 149 (10)<br/> Pointer-Based Node Implementations<br/> 149 (5)<br/> Space Requirements<br/> 154 (3)<br/> Array Implementation for Complete Binary Trees<br/> 157 (2)<br/> Binary Search Trees<br/> 159 (8)<br/> Heaps and Priority Queues<br/> 167 (7)<br/> Huffman Coding Trees<br/> 174 (11)<br/> Building Huffman Coding Trees<br/> 176 (6)<br/> Assigning and Using Huffman Codes<br/> 182 (3)<br/> Further Reading<br/> 185 (1)<br/> Exercises<br/> 186 (3)<br/> Projects<br/> 189 (2)<br/> Non-Binary Trees<br/> 191 (26)<br/> General Tree Definitions and Terminology<br/> 191 (4)<br/> An ADT for General Tree Nodes<br/> 192 (1)<br/> General Tree Traversals<br/> 193 (2)<br/> The Parent Pointer Implementation<br/> 195 (7)<br/> General Tree Implementations<br/> 202 (5)<br/> List of Children<br/> 202 (1)<br/> The Left-Child/Right-Sibling Implementation<br/> 203 (2)<br/> Dynamic Node Implementations<br/> 205 (2)<br/> Dynamic ``Left-Child/Right-Sibling'' Implementation<br/> 207 (1)<br/> K-ary Trees<br/> 207 (1)<br/> Sequential Tree Implementations<br/> 208 (3)<br/> Further Reading<br/> 211 (1)<br/> Exercises<br/> 211 (3)<br/> Projects<br/> 214 (3)<br/>III Sorting and Searching 217 (140)<br/> Internal Sorting<br/> 219 (40)<br/> Sorting Terminology and Notation<br/> 219 (2)<br/> Three Θ(n2) Sorting Algorithms<br/> 221 (6)<br/> Insertion Sort<br/> 221 (2)<br/> Bubble Sort<br/> 223 (1)<br/> Selection Sort<br/> 224 (2)<br/> The Cost of Exchange Sorting<br/> 226 (1)<br/> Shellsort<br/> 227 (2)<br/> Quicksort<br/> 229 (6)<br/> Mergesort<br/> 235 (3)<br/> Heapsort<br/> 238 (3)<br/> Binsort and Radix Sort<br/> 241 (6)<br/> An Empirical Comparison of Sorting Algorithms<br/> 247 (2)<br/> Lower Bounds for Sorting<br/> 249 (4)<br/> Further Reading<br/> 253 (1)<br/> Exercises<br/> 254 (3)<br/> Projects<br/> 257 (2)<br/> File Processing and External Sorting<br/> 259 (34)<br/> Primary versus Secondary Storage<br/> 259 (3)<br/> Disk Drives<br/> 262 (8)<br/> Disk Drive Architecture<br/> 263 (5)<br/> Disk Access Costs<br/> 268 (2)<br/> Buffers and Buffer Pools<br/> 270 (5)<br/> The Programmer's View of Files<br/> 275 (1)<br/> External Sorting<br/> 276 (3)<br/> Simple Approaches to External Sorting<br/> 279 (2)<br/> Replacement Selection<br/> 281 (4)<br/> Multiway Merging<br/> 285 (3)<br/> Further Reading<br/> 288 (1)<br/> Exercises<br/> 288 (3)<br/> Projects<br/> 291 (2)<br/> Searching<br/> 293 (34)<br/> Searching Sorted Arrays<br/> 294 (1)<br/> Self-Organizing Lists<br/> 295 (6)<br/> Searching in Sets<br/> 301 (1)<br/> Hashing<br/> 302 (19)<br/> Hash Functions<br/> 303 (4)<br/> Open Hashing<br/> 307 (1)<br/> Closed Hashing<br/> 308 (13)<br/> Further Reading<br/> 321 (1)<br/> Exercises<br/> 321 (3)<br/> Projects<br/> 324 (3)<br/> Indexing<br/> 327 (30)<br/> Linear Indexing<br/> 329 (2)<br/> ISAM<br/> 331 (3)<br/> Tree Indexing<br/> 334 (2)<br/> 2-3 Trees<br/> 336 (7)<br/> B-Trees<br/> 343 (9)<br/> B+-Trees<br/> 344 (6)<br/> B-Tree Analysis<br/> 350 (2)<br/> Further Reading<br/> 352 (1)<br/> Exercises<br/> 353 (2)<br/> Projects<br/> 355 (2)<br/>IV Applications and Advanced Topics 357 (136)<br/> Graphs<br/> 359 (34)<br/> Terminology and Representations<br/> 360 (4)<br/> Graph Implementations<br/> 364 (3)<br/> Graph Traversals<br/> 367 (10)<br/> Depth-First Search<br/> 370 (1)<br/> Breadth-First Search<br/> 371 (4)<br/> Topological Sort<br/> 375 (2)<br/> Shortest-Paths Problems<br/> 377 (5)<br/> Single-Source Shortest Paths<br/> 377 (4)<br/> All-Pairs Shortest Paths<br/> 381 (1)<br/> Minimum-Cost Spanning Trees<br/> 382 (5)<br/> Prim's Algorithm<br/> 383 (3)<br/> Kruskal's Algorithm<br/> 386 (1)<br/> Further Reading<br/> 387 (1)<br/> Exercises<br/> 388 (2)<br/> Projects<br/> 390 (3)<br/> Lists and Arrays Revisited<br/> 393 (30)<br/> Skip Lists<br/> 393 (6)<br/> Multilists<br/> 399 (3)<br/> Matrix Representations<br/> 402 (4)<br/> Memory Management<br/> 406 (12)<br/> Dynamic Storage Allocation<br/> 407 (7)<br/> Failure Policies and Garbage Collection<br/> 414 (4)<br/> Further Reading<br/> 418 (1)<br/> Exercises<br/> 419 (1)<br/> Projects<br/> 420 (3)<br/> Advanced Tree Structures<br/> 423 (28)<br/> Tries<br/> 423 (5)<br/> Balanced Trees<br/> 428 (6)<br/> The AVL Tree<br/> 428 (3)<br/> The Splay Tree<br/> 431 (3)<br/> Spatial Data Structures<br/> 434 (13)<br/> The K-D Tree<br/> 436 (5)<br/> The PR quadtree<br/> 441 (4)<br/> Other Spatial Data Structures<br/> 445 (2)<br/> Further Reading<br/> 447 (1)<br/> Exercises<br/> 447 (1)<br/> Projects<br/> 448 (3)<br/> Analysis Techniques<br/> 451 (18)<br/> Summation Techniques<br/> 452 (3)<br/> Recurrence Relations<br/> 455 (6)<br/> Estimating Upper and Lower Bounds<br/> 455 (1)<br/> Expanding Recurrences<br/> 456 (1)<br/> Divide and Conquer Recurrences<br/> 457 (2)<br/> Average-Case Analysis of Quicksort<br/> 459 (2)<br/> Amortized Analysis<br/> 461 (3)<br/> Further Reading<br/> 464 (1)<br/> Exercises<br/> 464 (4)<br/> Projects<br/> 468 (1)<br/> Limits to Computation<br/> 469 (24)<br/> Reductions<br/> 470 (5)<br/> Hard Problems<br/> 475 (7)<br/> NP-Completeness<br/> 476 (5)<br/> Getting Around NP-Complete Problems<br/> 481 (1)<br/> Impossible Problems<br/> 482 (7)<br/> Uncountability<br/> 483 (3)<br/> The Halting Problem Is Unsolvable<br/> 486 (2)<br/> Determining Program Behavior Is Unsolvable<br/> 488 (1)<br/> Further Reading<br/> 489 (1)<br/> Exercises<br/> 489 (2)<br/> Projects<br/> 491 (2)<br/>V APPENDIX 493 (4)<br/> A Utility Functions<br/> 495 (2)<br/>Bibliography 497 (6)<br/>Index 503
546 ## - LANGUAGE NOTE
Language note	eng.
650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM
Topical Term	Data structures (Computer science)
650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM
Topical Term	Computer algorithms.
942 ## - ADDED ENTRY ELEMENTS
Item type	Book

Holdings
Withdrawn status	Lost status	Damaged status	Not for loan	Permanent Location	Current Location	Date acquired	Source of acquisition	Full call number	Accession Number	Copy number	Price effective from	Koha item type
				Mzumbe University Main Campus Library	Mzumbe University Main Campus Library	03/31/2003	Donated by Agder	005.73 SHA	0047995	1	12/12/2022	Book