By Nell Dale, Henry M. Walker

This article expands the conventional direction concentration to check not just the constitution of a knowledge item, but additionally its kind. This broader concentration calls for a new paradigm for classifying info varieties. inside each one class, the diversified ADTs are awarded utilizing axiomatic necessities. a variety of implementation choices are mentioned for every ADT and algorithms are written in a pseudo-code in accordance with the Pascal-Modula- 2-Ada version. subsequent, the Big-O complexity of every implementation is mentioned and every ADT is utilized in an program. vintage algorithms supply functions for a few of the ADTs; implementation of a formerly outlined ADT is the appliance for others. The result's a transparent, logical presentation that offers scholars an effective, sensible beginning in present software program engineering ideas. functions are incorporated to illustrate how the ADTs are utilized in problem-solving. confirmed pedagogical positive aspects resembling unique examples, highlighted definitions, quite a few illustrations, and routines train problem-solving talents.

Show description

Read or Download Abstract data types: specifications, implementations, and applications PDF

Best data modeling & design books

Modeling Reality: How Computers Mirror Life

The bookModeling fact covers a variety of attention-grabbing topics, obtainable to a person who desires to find out about using laptop modeling to unravel a various variety of difficulties, yet who doesn't own a really good education in arithmetic or desktop technology. the fabric awarded is pitched on the point of high-school graduates, although it covers a few complex themes (cellular automata, Shannon's degree of knowledge, deterministic chaos, fractals, video game conception, neural networks, genetic algorithms, and Turing machines).

Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-23, 2006, Revised Papers

This ebook constitutes the completely refereed post-proceedings of the thirty second foreign Workshop on Graph-Theoretic thoughts in machine technology, WG 2006, held in Bergen, Norway in June 2006. The 30 revised complete papers provided including one invited paper have been rigorously chosen from ninety one submissions.

Neo4j in Action

SummaryNeo4j in motion is a finished advisor to Neo4j, geared toward software builders and software program architects. utilizing hands-on examples, you are going to learn how to version graph domain names obviously with Neo4j graph constructions. The publication explores the entire strength of local Java APIs for graph info manipulation and querying.

Python Data Analysis Cookbook

Key FeaturesAnalyze massive info units, create beautiful visualizations, and manage and procedure a number of information typesPacked with wealthy recipes that will help you examine and discover impressive algorithms for facts and desktop learningAuthored through Ivan Idris, specialist in python programming and proud writer of 8 hugely reviewed booksBook DescriptionData research is a quickly evolving box and Python is a multi-paradigm programming language compatible for object-oriented software improvement and sensible layout styles.

Additional info for Abstract data types: specifications, implementations, and applications

Example text

Integer numbers seem very concrete because we are used to working with numbers. However, we do not know how they are represented in a particular computer, how multiplication or division is actually accomplished between two integer numbers, or if the integers are limited to a specific range and what that range might be. All we know is what the syntax and operations of a language tell us. For example, Modula-2 defines three formats for integers (octal, decimal, and hexadecimal), two unary operations (+ and -), and eleven binary operations (+, -, *, MOD, DIV, =, <>, <, >, <=, >=).

Bounded Abstract Data Types 125 Implementation 127 Lists 127 Hashing 129 Application 143 Static 143 Dynamic 144 Names and Routing on the Internet 144 Summary 146 Exercises 147 5 Semi-Structured Data Types 151 Stack 152 Specification 152 Implementation 152 Application: Paired Symbols 153 FIFO Queue 155 Specification 155 Implementation 156 Array-Based Implementation 156 Linked-Structure Implementation 162 Application 163 External Sorting 163 Priority Queue 178 Specification 178 Implementation 180 As List Implemented in an Array 180 As List Implemented in a Linked Structure 181 Page xviii Other Implementation Structures 183 Comparison of Implementation Structures 183 Application 183 Summary 189 Exercises 190 6 Structured Linear Data Types 193 Arrays 194 Specification 194 One-Dimensional Array 194 Multi-Dimensional Array 195 Implementation 196 Complexity 199 Application: Matrix Module 200 Review of Matrix Multiplication 200 Implementation of Matrix Module 202 Complexity 204 Complexity of Factoring Algorithm 211 Application: Searching and Sorting 212 Parallel Searching 212 Parallel Sorting 218 Sequences 222 Specification 222 Implementation 224 Application: Strings 229 Knuth-Morris-Pratt Pattern-Matching Algorithm 233 Unsorted 236 Specification 236 Implementation 237 Sorted 237 Specification 237 Implementation 238 Application: Sparse Matrices 238 Complexity 243 Summary 244 Exercises 244 Page xix 7 Binary Trees 251 General Trees 252 Binary Trees 256 Specification 257 Implementation 260 Complexity 266 Threaded Trees 267 Application: Decision Trees 274 Searching an n-Element Ordered List, Implemented in an Array 275 Sorting an Array-Based List 280 Heaps 281 Specification 281 A General Heap Specification 282 A More Constrained Heap Specification 285 Comparison of Specification Approaches 291 Implementation 292 A Bottom-Up Approach to Insertion 295 A Top-Down Approach to Insertion 298 Complexity 305 Application: Implementation of Priority Queues 306 Summary 306 Exercises 307 8 Binary Search Trees 313 Shape and Searching 314 Elementary Search Trees 316 Specification 316 Implementation 318 Complexity of Elementary Insertion 322 Static Binary Trees 325 Optimal Binary Search Trees 330 Application: Symbol Tables 342 Huffman Algorithm 343 Application: Variable-Length Codes 347 Dynamic Binary Trees 351 AVL Trees 352 Page xx Summary 372 Exercises 373 9 Multi-Way Search Trees 377 Multi-Way Trees 378 Specification 381 Implementation 384 Simple Insertion and Deletion 384 2-3 Trees 389 Detailed Examination of Insertion Algorithm 396 Detailed Examination of Deletion Algorithm 406 B-Trees 417 B+-Trees 424 Other Tree Structures 426 2-3-4 Trees 426 Red/Black Trees 432 Complexity 434 Application: Files 434 Summary 436 Exercises 436 10 Directed Graphs or Digraphs 439 Definitions 440 Specification 449 Implementation 452 Adjacency Matrix 453 Theoretical Results 454 Adjacency Lists 460 Internal and External Names 461 Digraph Implementation Details 462 Complexity of Operations to Build a Digraph 468 Adjacency Array Implementation 468 Adjacency Lists Implementation 468 Application: Dependency Graphs 469 Example: Solving ax2 + bx + c = 0 Using the Quadratic Formula 469 Dependency Graphs and Ability to Parallelize Computations 470 Page xxi Application: Common Graph Algorithms 472 Traversals 472 Depth-First Traversal 473 Breadth-First Traversal 475 Single-Source Shortest Path 476 Topological Sort 479 Hamiltonian Circuit 483 Complexity of Application Algorithms 484 Summary 485 Exercises 486 11 Undirected Graphs and Complexity 491 A Computer-Networking Example 492 Specification 493 Implementation 494 Application: Sequential Graph Algorithms 494 Connectivity 495 Spanning Trees 499 Depth-First and Breadth-First 499 Minimum Cost 499 Application: Parallel Graph Algorithms 503 Parallel Graph Traversals 504 Matrix Multiplication 507 Traveling Salesperson Problem 512 Computational Complexity 513 Classes P and NP 517 Tractable and Intractable Problems 520 Regular-Expression Non-Universality Problem 521 The Halting Problem 525 Classification of Problems 526 Summary 527 Exercises 527 Page xxii 12 Generalized Lists 533 The Translation of Several ADTs to Generalized Lists 534 Specification 536 Implementation 537 Hierarchy of List Interpretations 537 Lists with No Shared Reference 540 Variant Records 544 Details of Generalized List Operations 545 Lists with Shared Reference 547 ImplementationStatic Interpretation 548 ImplementationDynamic Interpretation 548 Recursive Lists 553 Applications 553 List Input, Output, and Evaluation 554 Input 555 Output 564 Expression Evaluation 565 Some Uses of Generalized Lists Within LISP 569 Property Lists in LISP 569 Association Lists in LISP 572 Use of Generalized Lists Within Expert Systems 573 Analysis 575 Summary 576 Exercises 577 13 Memory Management 581 Functions of the Memory Manager 582 Interface with the Memory Manager 582 Fixed-Sized Blocks 585 Complexity 586 Stack-Based Order (Fixed- or Mixed-Sized Blocks) 586 Complexity 588 Mixed- (Variable-) Sized Blocks 588 Available Space List 590 Avail Separate from Blocks of Storage 590 Avail Within Blocks of Storage 592 Page xxiii Allocation and Deallocation Strategies 593 Fragmentation 597 Coalescing 598 Boundary Tag System 599 Buddy Systems 604 Binary Buddy System 604 Fibonacci Buddy System 614 Garbage Collection 615 Identifying Inaccessible Blocks 616 Making the Free Space Available 618 Complexity 618 Memory Compaction 619 Complexity 618 Summary 620 Exercises 621 Appendix A Abstract Models a1 Appendix B Interactive Algebraic Specifications: Using the Mathematica Programming Language a7 Partial Bibliography a23 Glossary a25 Answers to Selected Exercises a33 Index a83 Page 1 1 Abstract Specification Techniques In this chapter, we lay the groundwork for the rest of the book.

In particular the authors wish to thank the Department of Computer Sciences at The University of Texas at Austin and Dean Charles Duke and the Grinnell College Grant Board for their help and support in this project. Suggestions for improvements and clarifications for this text have come from many reviewers and students. The authors particular want to thank Jeff Brumfield (The University of Texas at Austin) and the other formal reviewers for their very helpful comments: Linda Elliott, La Salle University; Sue Crane Fitzgerald, Rockhurst College; Henry G.

Download PDF sample

Download Abstract data types: specifications, implementations, and by Nell Dale, Henry M. Walker PDF
Rated 4.27 of 5 – based on 28 votes