Data Structures and Algorithms with

Students will learn data structures and algorithms from a modern, object-oriented perspective with this new text. It uses a single class hierarchy as a framework to present all of the data structures. This framework clearly shows the relationships between data structures and illustrates how polymorphism and inheritance can be used effectively.

About the Author Bruno R. Preiss is an Associate Professor in the Department of Electrical and Computer Engineering at the University of Waterloo, Canada. He is a member of the Parallel and Distributed Systems Group, the Computer Communications Networks Group, and the VLSI Research Group. Professor Preiss received an M.A.Sc. and Ph.D. in Electrical Engineering from the University of Toronto, Canada.

CHAPTER 1 Introduction

1

(5)

1.1 What This Book Is About

1

(1)

1.2 Object-Oriented Design

1

(1)

1.3 Object Hierarchies and Design Patterns

2

(1)

1.4 The Features of C++ You Need to Know

3

(1)

1.5 How This Book Is Organized

4

(2)

CHAPTER 2 Algorithm Analysis

6

(28)

2.1 A Detailed Model of the Computer

7

(15)

2.2 A Simplified Model of the Computer

22

(9)

Exercises

31

(2)

Programming Projects

33

(1)

CHAPTER 3 Asymptotic Notation

34

(32)

3.1 An Asymptotic Upper Bound--Big Oh

34

(11)

3.2 An Asymptotic Lower Bound--Omega

45

(3)

3.3 More Notation--Theta and Little Oh

48

(1)

3.4 Asymptotic Analysis of Algorithms

49

(13)

Exercises

62

(2)

Programming Projects

64

(2)

CHAPTER 4 Foundational Data Structures

66

(29)

4.1 Dynamic Arrays

66

(7)

4.2 Singly-Linked Lists

73

(12)

4.3 Multidimensional Arrays

85

(8)

Exercises

93

(1)

Programming Projects

94

(1)

CHAPTER 5 Data Types and Abstraction

95

(31)

5.1 Abstract Data Types

95

(1)

5.2 Design Patterns

96

(26)

Exercises

122

(2)

Programming Projects

124

(2)

CHAPTER 6 Stacks, Queues, and Deques

126

(38)

6.1 Stacks

127

(15)

6.2 Queues

142

(10)

6.3 Deques

152

(8)

Exercises

160

(1)

Programming Projects

161

(3)

CHAPTER 7 Ordered Lists and Sorted Lists

164

(37)

7.1 Ordered Lists

164

(22)

7.2 Sorted Lists

186

(12)

Exercises

198

(1)

Programming Projects

199

(2)

CHAPTER 8 Hashing, Hash Tables, and Scatter Tables

201

(52)

8.1 Hashing--The Basic Idea

201

(3)

8.2 Hashing Methods

204

(4)

8.3 Hash Function Implementations

208

(10)

8.4 Hash Tables

218

(7)

8.5 Scatter Tables

225

(9)

8.6 Scatter Table using Open Addressing

234

(13)

8.7 Applications

247

(2)

Exercises

249

(2)

Programming Projects

251

(2)

CHAPTER 9 Trees

253

(45)

9.1 Basics

254

(3)

9.2 N-ary Trees

257

(4)

9.3 Binary Trees

261

(1)

9.4 Tree Traversals

262

(3)

9.5 Expression Trees

265

(2)

9.6 Implementing Trees

267

(28)

Exercises

295

(2)

Programming Projects

297

(1)

CHAPTER 10 Search Trees

298

(52)

10.1 Basics

298

(2)

10.2 Searching a Search Tree

300

(2)

10.3 Average Case Analysis

302

(6)

10.4 Implementing Search Trees

308

(7)

10.5 AVL Search Trees

315

(12)

10.6 M-Way Search Treees

327

(8)

10.7 B-Trees

335

(11)

10.8 Applications

346

(1)

Exercises

346

(3)

Programming Projects

349

(1)

CHAPTER 11 Heaps and Priority Queues

350

(42)

11.1 Basics

351

(2)

11.2 Binary Heaps

353

(9)

11.3 Leftist Heaps

362

(8)

11.4 Binomial Queues

370

(15)

11.5 Applications

385

(4)

Exercises

389

(1)

Programming Projects

390

(2)

CHAPTER 12 Sets, Multisets, and Partitions

392

(34)

12.1 Basics

393

(2)

12.2 Array and Bit-Vector Sets

395

(6)

12.3 Multisets

401

(7)

12.4 Partitions

408

(12)

12.5 Applications

420

(3)

Exercises

423

(1)

Programming Projects

424

(2)

CHAPTER 13 Dynamic Storage Allocation: The Other Kind of Heap

426

(37)

13.1 Basics

426

(6)

13.2 Singly-Linked Free Storage

432

(8)

13.3 Doubly-Linked Free Storage

440

(8)

13.4 Buddy System for Storage Management

448

(9)

13.5 Applications

457

(3)

Exercises

460

(1)

Programming Projects

461

(2)

CHAPTER 14 Algorithmic Patterns and Problem Solvers

463

(46)

14.1 Brute-Force and Greedy Algorithms

463

(4)

14.2 Backtracking Algorithms

467

(9)

14.3 Top-Down Algorithms: Divide-and-Conquer

476

(10)

14.4 Bottom-Up Algorithms: Dynamic Programming

486

(7)

14.5 Randomized Algorithms

493

(11)

Exercises

504

(3)

Programming Projects

507

(2)

CHAPTER 15 Sorting Algorithms and Sorters

509

(49)

15.1 Basics

509

(1)

15.2 Sorting and Sorters

510

(3)

15.3 Insertion Sorting

513

(5)

15.4 Exchange Sorting

518

(11)

15.5 Selection Sorting

529

(10)

15.6 Merge Sorting

539

(5)

15.7 A Lower Bound on Sorting

544

(2)

15.8 Distribution Sorting

546

(6)

15.9 Performance Data

552

(3)

Exercises

555

(1)

Programming Projects

556

(2)

CHAPTER 16 Graphs and Graph Algorithms

558

(61)

16.1 Basics

559

(8)

16.2 Implementing Graphs

567

(10)

16.3 Graph Traversals

577

(13)

16.4 Shortest-Path Algorithms

590

(10)

16.5 Minimum-Cost Spanning Trees

600

(9)

16.6 Application: Critical Path Analysis

609

(6)

Exercises

615

(3)

Programming Projects

618

(1)

APPENDIX A C++ and Object-Oriented Programming

619

(26)

A.1 Variables, Pointers, and References

619

(3)

A.2 Parameter Passing

622

(3)

A.3 Objects and Classes

625

(6)

A.4 Inheritance and Polymorphism

631

(10)

A.5 Templates

641

(1)

A.6 Exceptions

642

(3)

APPENDIX B Class Hierarchy Diagrams

645

(2)

APPENDIX C Character Codes

647

(1)

Bibliography

648

(3)

Index

651

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Summary

Author Biography

Table of Contents

Supplemental Materials

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Summary

Author Biography

Table of Contents

Supplemental Materials

Digital License