Shaffer, Clifford A. <br/><br/>
A practical introduction to data structures and algorithm analysis / 
 Introduction to data structures and algorithm analysis  Data structures and algorithm analysis 
Clifford A. Shaffer. 
 - 2nd ed. 
 - Upper Saddle River, N.J. :  Prentice Hall,  c2001. 
 - xvi, 512 p. :  ill. ;  25 cm. 
<br/><br/>Includes bibliographical references (p. 497-501) and index. 
<br/><br/>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	 
<br/><br/><br/>eng. 
<br/><br/><label>ISBN: </label>9780130284464  TZS 127,500/= 
<br/><br/><label>Subjects--Topical Terms: </label><br/>Data structures (Computer science)<br/>Computer algorithms.
<br/><br/><label>Dewey Class. No.: </label>005.73 SHA