Rent 9780321322135 | Data Structures and Problem Solving Using Java

Summary Table of Contents

This book provides a practical introduction to data structures from a viewpoint of abstract thinking and problem solving, as well as the use of Java. It does this through what remains a unique approach that clearly separates each data structures interface (how to use a data structure) from its implementation (how to actually program that structure) into different parts of the book. Part I (Tour of Java), Part II (Algorithms and Building Blocks), and Part III (Applications) lay the groundwork by discussing basic concepts and tools and providing ... MORE

... MORE

part one Tour of Java

primitive java

(22)

the general environment

(1)

the first program

(1)

comments

(1)

main

(1)

terminal output

(1)

primitive types

(2)

the primitive types

(1)

constants

(1)

declaration and initialization of primitive types

(1)

terminal input and output

(1)

basic operators

(3)

assignment operators

(1)

binary arithmetic operators

(1)

unary operators

(1)

type conversions

(1)

conditional statements

(7)

relational and equality operators

(1)

logical operators

(1)

the if statement

(1)

the while statement

(1)

the for statement

(1)

the do statement

(1)

break and continue

(1)

the switch statement

(1)

the conditional operator

(1)

methods

(7)

overloading of method names

(1)

storage classes

(1)

summary

(1)

key concepts

(2)

common errors

(1)

on the internet

(1)

exercises

(2)

references

(38)

reference types

(1)

what is a reference?

(8)

basics of objects and references

(1)

the dot operator (.)

(1)

declaration of objects

(1)

garbage collection

(1)

the meaning of =

(1)

parameter passing

(1)

the meaning of ==

(1)

no operator overloading for objects

(1)

strings

(2)

basics of string manipulation

(1)

string concatenation

(1)

comparing strings

(1)

other String methods

(1)

converting other types to strings

(1)

arrays

(11)

declaration, assignment, and methods

(2)

dynamic array expansion

(3)

ArrayList

(2)

multidimensional arrays

(1)

command-line arguments

(1)

enhanced for loop

(2)

exception handling

(3)

processing exceptions

(1)

the finally clause

(2)

common exceptions

(1)

the throw and throws clauses

(1)

input and output

(12)

basic stream operations

(1)

the StringTokenizer type

(2)

sequential files

(3)

summary

(1)

key concepts

(2)

common errors

(1)

on the internet

(1)

exercises

(1)

references

(1)

objects and classes

(30)

what is object-oriented programming?

(2)

a simple example

(2)

javadoc

(3)

basic methods

(3)

constructors

(1)

mutators and accessors

(2)

output and toString

(1)

equals

(1)

main

(1)

static fields and methods

(1)

additional constructs

(5)

the this reference

(1)

the this shorthand for constructors

(1)

the instanceof operator

(1)

instance members versus static members

(1)

static fields and methods

(2)

static initializers

(1)

packages

(4)

the import directive

(2)

the package statement

(1)

the Classpath environment variable

(1)

package visibility rules

(1)

a design pattern: composite (pair)

(11)

summary

(1)

key concepts

(3)

common errors

(1)

on the internet

(1)

exercises

(3)

references

(2)

inheritance

(70)

what is inheritance?

(15)

creating new classes

(5)

type compatibility

(1)

dynamic dispatch and polymorphism

100

(1)

inheritance hierarchies

101

(1)

visibility rules

101

(1)

the constructor and super

102

(1)

final methods and classes

103

(2)

overriding a method

105

(1)

type compatibility revisited

105

(3)

compatibility of array types

108

(1)

covariant return types

108

(1)

designing hierarchies

109

(5)

abstract methods and classes

110

(4)

multiple inheritance

114

(1)

the interface

115

(3)

specifying an interface

115

(1)

implementing an interface

116

(1)

multiple interfaces

117

(1)

interfaces are abstract classes

117

(1)

fundamental inheritance in java

118

(6)

the Object class

118

(1)

the hierarchy of exceptions

119

(1)

i/o: the decorator pattern

120

(4)

implementing generic components using inheritance

124

(7)

using Object for genericity

124

(1)

wrappers for primitive types

125

(2)

autoboxing/unboxing

127

(1)

adapters: changing an interface

128

(1)

using interface types for genericity

129

(2)

implementing generic components using java 1.5 generics

131

(6)

simple generic classes and interfaces

131

(1)

wildcards with bounds

132

(1)

generic static methods

133

(1)

type bounds

134

(1)

type erasure

135

(1)

restrictions on generics

136

(1)

the functor (function objects)

137

(9)

nested classes

142

(1)

local classes

143

(1)

anonymous classes

144

(1)

nested classes and generics

145

(1)

dynamic dispatch details

146

(17)

summary

149

(1)

key concepts

150

(2)

common errors

152

(1)

on the internet

153

(1)

exercises

154

(6)

references

160

(3)

part two Algorithms and Building Blocks

algorithm analysis

163

(38)

what is algorithm analysis?

164

(4)

examples of algorithm running times

168

(1)

the maximum contiguous subsequence sum problem

169

(8)

the obvious O(N3) algorithm

170

(3)

an improved O(N2) algorithm

173

(1)

a linear algorithm

173

(4)

general big-oh rules

177

(4)

the logarithm

181

(2)

static searching problem

183

(5)

sequential search

183

(1)

binary search

184

(3)

interpolation search

187

(1)

checking an algorithm analysis

188

(1)

limitations of big-oh analysis

189

(12)

summary

190

(1)

key concepts

190

(1)

common errors

191

(1)

on the internet

192

(1)

exercises

192

(7)

references

199

(2)

the collections api

201

(50)

introduction

202

(1)

the iterator pattern

203

(5)

basic iterator design

204

(2)

inheritance-based iterators and factories

206

(2)

collections api: containers and iterators

208

(6)

the Collection interface

209

(3)

Iterator interface

212

(2)

generic algorithms

214

(6)

Comparator function objects

215

(1)

the Collections class

215

(3)

binary search

218

(1)

sorting

218

(2)

the List interface

220

(5)

the ListIterator interface

221

(2)

LinkedList class

223

(2)

stacks and queues

225

(3)

stacks

225

(1)

stacks and computer languages

226

(1)

queues

227

(1)

stacks and queues in the collections api

228

(1)

sets

228

(8)

the TreeSet class

229

(2)

the HashSet class

231

(5)

maps

236

(3)

priority queues

239

(12)

summary

243

(1)

key concepts

244

(1)

common errors

245

(1)

on the internet

245

(1)

exercises

246

(3)

references

249

(2)

recursion

251

(52)

what is recursion?

252

(1)

background: proofs by mathematical induction

253

(2)

basic recursion

255

(14)

printing numbers in any base

257

(2)

why it works

259

(2)

how it works

261

(1)

too much recursion can be dangerous

262

(1)

preview of trees

263

(1)

additional examples

264

(5)

numerical applications

269

(8)

modular arithmetic

269

(1)

modular exponentiation

270

(2)

greatest common divisor and multiplicative inverses

272

(3)

the rsa cryptosystem

275

(2)

divide-and-conquer algorithms

277

(10)

the maximum contiguous subsequence sum problem

278

(3)

analysis of a basic divide-and-conquer recurrence

281

(4)

a general upper bound for divide-and-conquer running times

285

(2)

dynamic programming

287

(4)

backtracking

291

(12)

summary

294

(2)

key concepts

296

(1)

common errors

297

(1)

on the internet

297

(1)

exercises

298

(4)

references

302

(1)

sorting algorithms

303

(40)

why is sorting important?

304

(1)

preliminaries

305

(1)

analysis of the insertion sort and other simple sorts

305

(4)

shellsort

309

(4)

performance of shellsort

310

(3)

mergesort

313

(3)

linear-time merging of sorted arrays

313

(2)

the mergesort algorithm

315

(1)

quicksort

316

(15)

the quicksort algorithm

317

(3)

analysis of quicksort

320

(3)

picking the pivot

323

(2)

a partitioning strategy

325

(2)

keys equal to the pivot

327

(1)

median-of-three partitioning

327

(1)

small arrays

328

(1)

java quicksort routine

329

(2)

quickselect

331

(1)

a lower bound for sorting

332

(11)

summary

334

(1)

key concepts

335

(1)

common errors

336

(1)

on the internet

336

(1)

exercises

336

(5)

references

341

(2)

randomization

343

(24)

why do we need random numbers?

343

(1)

random number generators

344

(5)

nonuniform random numbers

349

(4)

generating a random permutation

353

(1)

randomized algorithms

354

(3)

randomized primality testing

357

(10)

summary

360

(1)

key concepts

360

(1)

common errors

361

(1)

on the internet

362

(1)

exercises

362

(2)

references

364

(3)

part three Applications

fun and games

367

(22)

word search puzzles

367

(6)

theory

368

(1)

java implementation

369

(4)

the game of tic-tac-toe

373

(16)

alpha-beta pruning

374

(3)

transposition tables

377

(4)

computer chess

381

(3)

summary

384

(1)

key concepts

384

(1)

common errors

384

(1)

on the internet

384

(1)

exercises

385

(2)

references

387

(2)

stacks and compilers

389

(30)

balanced-symbol checker

389

(11)

basic algorithm

390

(1)

implementation

391

(9)

a simple calculator

400

(19)

postfix machines

402

(1)

infix to postfix conversion

403

(2)

implementation

405

(9)

expression trees

414

(1)

summary

415

(1)

key concepts

416

(1)

common errors

416

(1)

on the internet

417

(1)

exercises

417

(1)

references

418

(1)

utilities

419

(32)

file compression

420

(21)

prefix codes

421

(2)

huffman's algorithm

423

(2)

implementation

425

(16)

a cross-reference generator

441

(10)

basic ideas

441

(1)

java implementation

441

(4)

summary

445

(1)

key concepts

446

(1)

common errors

446

(1)

on the internet

446

(1)

exercises

446

(4)

references

450

(1)

simulation

451

(20)

the josephus problem

451

(6)

the simple solution

453

(1)

a more efficient algorithm

453

(4)

event-driven simulation

457

(14)

basic ideas

457

(1)

example: a modem bank simulation

458

(8)

summary

466

(1)

key concepts

466

(1)

common errors

467

(1)

on the internet

467

(1)

exercises

467

(4)

graphs and paths

471

(68)

definitions

472

(11)

representation

474

(9)

unweighted shortest-path problem

483

(6)

theory

483

(6)

java implementation

489

(1)

positive-weighted, shortest-path problem

489

(7)

theory: dijkstra's algorithm

490

(4)

java implementation

494

(2)

negative-weighted, shortest-path problem

496

(3)

theory

496

(1)

java implementation

497

(2)

path problems in acyclic graphs

499

(19)

topological sorting

499

(2)

theory of the acyclic shortest-path algorithm

501

(1)

java implementation

501

(3)

an application: critical-path analysis

504

(2)

summary

506

(1)

key concepts

507

(1)

common errors

508

(1)

on the internet

509

(1)

exercises

509

(4)

references

513

(5)

part four Implementations

inner classes and implementation of ArrayList

iterators and nested classes

518

(2)

iterators and inner classes

520

(4)

the AbstractCollection class

524

(4)

StringBuilder

528

(1)

implementation of ArrayList with an iterator

529

(10)

summary

534

(1)

key concepts

535

(1)

common errors

535

(1)

on the internet

535

(1)

exercises

535

(4)

stacks and queues

539

(24)

dynamic array implementations

539

(10)

stacks

540

(4)

queues

544

(5)

linked list implementations

549

(8)

stacks

550

(3)

queues

553

(4)

comparison of the two methods

557

(1)

the java.util.Stack class

557

(2)

double-ended queues

559

(4)

summary

559

(1)

key concepts

559

(1)

common errors

559

(1)

on the internet

559

(1)

exercises

560

(3)

linked lists

563

(32)

basic ideas

563

(5)

header nodes

565

(1)

iterator classes

566

(2)

java implementation

568

(6)

doubly linked lists and circularly linked lists

574

(3)

sorted linked lists

577

(2)

implementing the collections api LinkedList class

579

(16)

summary

590

(1)

key concepts

590

(1)

common errors

591

(1)

on the internet

591

(1)

exercises

591

(4)

trees

595

(34)

general trees

595

(7)

definitions

596

(1)

implementation

597

(1)

an application: file systems

598

(4)

binary trees

602

(7)

recursion and trees

609

(2)

tree traversal: iterator classes

611

(18)

postorder traversal

615

(4)

inorder traversal

619

(1)

preorder traversal

619

(3)

level-order traversals

622

(1)

summary

623

(1)

key concepts

624

(1)

common errors

625

(1)

on the internet

626

(1)

exercises

626

(3)

binary search trees

629

(84)

basic ideas

629

(10)

the operations

630

(2)

java implementation

632

(7)

order statistics

639

(5)

java implementation

640

(4)

analysis of binary search tree operations

644

(4)

avl trees

648

(9)

properties

649

(2)

single rotation

651

(3)

double rotation

654

(2)

summary of avl insertion

656

(1)

red-black trees

657

(13)

bottom-up insertion

658

(2)

top-down red-black trees

660

(1)

java implementation

661

(7)

top-down deletion

668

(2)

aa-trees

670

(10)

insertion

672

(2)

deletion

674

(1)

java implementation

675

(5)

implementing the collections apl TreeSet and TreeMap classes

680

(18)

b-trees

698

(15)

summary

704

(1)

key concepts

705

(1)

common errors

706

(1)

on the internet

706

(1)

exercises

707

(2)

references

709

(4)

hash tables

713

(32)

basic ideas

714

(1)

hash function

715

(2)

linear probing

717

(6)

naive analysis of linear probing

719

(1)

what really happens: primary clustering

720

(1)

analysis of the find operation

721

(2)

quadratic probing

723

(13)

java implementation

727

(6)

analysis of quadratic probing

733

(3)

separate chaining hashing

736

(1)

hash tables versus binary search trees

737

(1)

hashing applications

737

(8)

summary

738

(1)

key concepts

738

(1)

common errors

739

(1)

on the internet

740

(1)

exercises

740

(2)

references

742

(3)

a priority queue: the binary heap

745

(36)

basic ideas

746

(6)

structure property

746

(2)

heap-order property

748

(1)

allowed operations

749

(3)

implementation of the basic operations

752

(4)

insertion

752

(2)

the deleteMin operation

754

(2)

the buildHeap operation: linear-time heap construction

756

(5)

advanced operations: decreaseKey and merge

761

(1)

internal sorting: heapsort

761

(3)

external sorting

764

(17)

why we need new algorithms

764

(1)

model for external sorting

765

(1)

the simple algorithm

765

(2)

multiway merge

767

(1)

polyphase merge

768

(2)

replacement selection

770

(1)

summary

771

(1)

key concepts

772

(1)

common errors

772

(1)

on the internet

773

(1)

exercises

773

(4)

references

777

(4)

part five Advanced Data Structures

splay trees

781

(28)

self-adjustment and amortized analysis

782

(3)

amortized time bounds

783

(1)

a simple self-adjusting strategy (that does not work)

783

(2)

the basic bottom-up splay tree

785

(3)

basic splay tree operations

788

(1)

analysis of bottom-up splaying

789

(6)

proof of the splaying bound

792

(3)

top-down splay trees

795

(3)

implementation of top-down splay trees

798

(5)

comparison of the splay tree with other search trees

803

(6)

summary

804

(1)

key concepts

804

(1)

common errors

805

(1)

on the internet

805

(1)

exercises

805

(1)

references

806

(3)

merging priority queues

809

(22)

the skew heap

809

(5)

merging is fundamental

810

(1)

simplistic merging of heap-ordered trees

810

(1)

the skew heap: a simple modification

811

(1)

analysis of the skew heap

812

(2)

the pairing heap

814

(17)

pairing heap operations

815

(1)

implementation of the pairing heap

816

(6)

application: dijkstra's shortest weighted path algorithm

822

(4)

summary

826

(1)

key concepts

826

(1)

common errors

826

(1)

on the internet

827

(1)

exercises

827

(1)

references

828

(3)

the disjoint set class

831

(34)

equivalence relations

832

(1)

dynamic equivalence and applications

832

(10)

application: generating mazes

833

(3)

application: minimum spanning trees

836

(3)

application: the nearest common ancestor problem

839

(3)

the quick-find algorithm

842

(1)

the quick-union algorithm

843

(5)

smart union algorithms

845

(2)

path compression

847

(1)

java implementation

848

(3)

worst case for union-by-rank and path compression

851

(14)

analysis of the union/find algorithm

852

(7)

summary

859

(1)

key concepts

859

(1)

common errors

860

(1)

on the internet

860

(1)

exercises

861

(2)

references

863

(2)

appendix A operators

865

(2)

appendix B graphical user interfaces

867

(30)

the abstract window toolkit and swing

868

(1)

basic objects in swing

869

(9)

Component

870

(1)

Container

871

(1)

top-level containers

871

(1)

JPanel

872

(2)

important i/o components

874

(4)

basic principles

878

(19)

layout managers

879

(4)

graphics

883

(2)

events

885

(2)

event handling: adapters and anonymous inner classes

887

(2)

summary: putting the pieces together

889

(1)

is this everything i need to know about swing?

890

(1)

summary

891

(1)

key concepts

891

(2)

common errors

893

(1)

on the internet

894

(1)

exercises

894

(1)

references

895

(2)

appendix C bitwise operators

897

(4)

index

901

RENT TEXTBOOKS

Data Structures and Problem Solving Using Java

Why Rent from Knetbooks?

Top 5 reasons to order all your textbooks from Knetbooks:

Related Products