Always Learning

Data Structures and Their Algorithms
Harry R. Lewis, Harvard University
Larry Denenberg, Harvard University

ISBN-10: 067339736X
ISBN-13:  9780673397362

Publisher:  Addison-Wesley
Copyright:  1991
Format:  Paper; 509 pp
Published:  01/08/1997
Status: Instock


Customers outside the U.S., click here.


Print this content

In this section:


Description

Using only practically useful techniques, this book teaches methods for organizing, reorganizing, exploring, and retrieving data in digital computers, and the mathematical analysis of those techniques. The authors present analyses that are relatively brief and non-technical but illuminate the important performance characteristics of the algorithms. Data Structures and Their Algorithms covers algorithms, not the expression of algorithms in the syntax of particular programming languages. The authors have adopted a pseudocode notation that is readily understandable to programmers but has a simple syntax.


Table of Contents

I. INTRODUCTION PROGRAMMING AS AN ENGINEERING ACTIVITY.

Computer Science Background.

Memory and Data in Von Neuman Computers.

Notation for Programs; Locatives.

Abstract Data Types.

Mathematical Background.

Finite and Infinite Series.

Logarithms, Powers, and Exponentials.

Order Notation.

Recurrence Relations.

Naive Probability Theory.

II. ALGORITHM ANALYSIS.

Properties of an Algorithm.

Effectiveness; Correctness.

Termination; Efficiency.

Program Complexity.

Exact vs. Growth-Rate Analysis.

Principles of Mathematical Analysis.

Expected Case and Amortized Analysis.

Algorithm Paradigms.

Brute-Force and Exhaustive Search.

Greedy Algorithms.

Dynamic Programming.

NP Completeness.

III. LISTS.

List Operations.

Basic List Representations.

Stack Representation in Contiguous Memory.

Queue Representation in Contiguous Memory.

Stack Representation in Linked Memory.

Queue Representation in Linked Memory.

Stacks and Recursions.

List Representations for Traversals.

Doubly Linked Lists.

IV. TREES BASIC DEFINITIONS.

Special Kinds of Trees.

Tree Operations and Traversals.

Tree Implementations.

Representation of Binary Trees.

Representation of Ordered Trees.

Representation of Complete Binary Trees.

Implementing Tree Traversals and Scans.

Stack-Based Traversals.

Link Inversion Traversal.

Scanning a Tree in Constant Space.

ThreadedTrees.

Implementing Level-Order Traversal.

Summary.

V. ARRAYS AND STRINGS.

Arrays as Abstract Data Types.

Multidimensional Arrays.

Contiguous Representation of Arrays.

Constant Time Initialization.

Sparse Arrays.

List Representations.

Hierarchical Tables.

Arrays with Special Shapes.

Representation of Strings.

Huffman Encoding; Lempel Ziv Encoding.

String Searching.

The Knuth-Morris-Pratt Algorithm.

The Boyer-Moore Algorithm.

Fingerprinting and the Karp-Rabin Algorithm.

VI. LIST AND TREE IMPLEMENTATION OF SETS.

Sets and Dictionaries as Abstract Data Types.

Unordered Lists.

Ordered Lists.

Binary Search; Interpolation Search; Skip Lists.

Binary Search Trees.

Insertion; Deletion.

Static Binary Search Trees.

Optimal Trees; Probability-Balanced.

Trees; Median Split Trees.

VII. TREE STRUCTURES FOR DYNAMIC DICTIONARIES.

AVL Trees: Insertion; Deletion.

23 Trees and Btrees.

23 Trees; Red-Black Trees.

(a,b)Trees and B Trees.

Self-Adjusting Binary Search Trees.

VIII. SETS OF DIGITAL DATA.

Bit Vectors.

Tries and Digital Search Trees.

Hashing Techniques.

Chaining Strategies; Open Addressing Strategies.

Deletions; Extendable Hashing.

Hashing Functions.

Hashing by Division; Hashing by Multiplication.

Perfect Hashing of Static Data; Universal Classes of Hash Functions.

IX. SETS WITH SPECIAL OPERATIONS.

Priority Queues.

Balanced Tree Implementations.

Heaps; Leftist Trees.

Disjoint Sets with Union.

Up-Trees; Path Compression.

Range Searching: kdTrees for Multidimensional Searching.

Quad Trees; Grid Files.

X. MEMORY MANAGEMENT.

The Problem of Memory Management.

Records of a Single Size.

Reference Counts; Mark and Sweep.

Garbage Collection; Collecting by Copying.

Final Cautions on Garbage Collection.

Compaction of Records of Various Sizes.

Managing A Pool of Blocks of Various Sizes.

Allocation Strategies; Data Structures for Freeing; Buddy Systems.

XI. SORTING.

Kinds of Sorting Algorithms.

Insertion and Shell Sort.

Selection and Heap Sort.

Quick Sort.

The Information-Theoretic Lower Bound.

Digital Sorting.

Bucket Sort; Radix Sort; Radix Exchange Sort.

External Sorting.

Merge Sorts; Polyphase Merge Sort.

Generating the Initial Runs.

Finding the Median.

XII. GRAPHS.

Graphs and Their Representation.

Trees.

Graph Searching.

Breadth-First Search; Depth-First Search.

Greedy Algorithms on Graphs.

Minimum Spanning Trees; Single-Source Least-Cost Paths.

All Pairs Least-Cost Paths.

Network Flow.

Finding Maximum Flows.

Implementing the Max Flow.

Algorithm.

Applications of Max Flow.

XIII. ENGINEERING WITH DATA STRUCTURES.

Locatives. 067339736XT04062001



Back to top

Print this content

In this section:


Backcover Copy

This book in an all-inclusive presentation introduces the datastructures (and their algorithms) that comprise the foundationof software engineering. Designed to show students at the sophomorelevel the connection between a programming approach and mathematicaltheory, the text focuses on practical techniques for studentsto master data structures and efficient algorithm implementation.Other topics pertinent to programmers also receive coverage. Chapter-endingproblems and references give students a helpful review and solidifychapter concepts.



067339736XB04062001

Back to top

Print this content

In this section:


Websites and online courses

CS Support-Student Support Material
Addison-Wesley
©2008  |  Addison-Wesley  |  On-line Supplement  |  Live
ISBN-10: 0321446852  |  ISBN-13: 9780321446855
More Info

Log in to the Instructor Resource Center

Login name: 

  Password: 

Forgot login/password?  |  Need to redeem an access code?

        

Instructor Resource Center File Download

This work is protected by local and international copyright laws and is provided solely for the use of instructors in teaching their courses and assessing student learning. Dissemination or sale of any part of this work (including on the World Wide Web) will destroy the integrity of the work and is not permitted. The work and materials from this site should never be made available to students except by instructors using the accompanying text in their classes. All recipients of this work are expected to abide by these restrictions and to honor the intended pedagogical purposes and the needs of other instructors who rely on these materials.

Cancel     I accept, proceed with download

Print this content

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students, browse our available packages below, or contact your Pearson Higher Education representative to create your own package.

Package ISBN-10: 0321207483 | ISBN-13: 9780321207487
©2000 | Instock (Additional assembly time required)
Suggested retail price: $147.80  Buy from myPearsonStore

This package contains:

Lewis & Denenberg | ©1991 | Addison-Wesley | Paper; 509 pp
Stroustrup | ©2000 | Addison-Wesley | Cloth; 1040 pp


Back to top