Introduction to Computing and Algorithms

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

ISBN: 9780201314519 | 0201314517
Cover: Paperback
Copyright: 10/16/1997

Rent

(Recommended)

$93.93

Term

Due

Price

Semester

Dec 12

$98.87

Quarter

Aug 13

$93.93

Short Term

Jul 22

$88.98

*This item is part of an exclusive publisher rental program and requires an additional convenience fee. This fee will be reflected in the shopping bag.
Buy Used

Usually Ships in 3-5 Business Days

$114.04
Buy New

Currently Available, Usually Ships in 24-48 Hours

$158.23

This book prepares students for the world of computing by giving them a solid foundation in the "science" of computer science - algorithms. By taking an algorithm-based approach to the subject, this new book helps readers grasp overall concepts, rather than getting them bogged down with specific syntax details of a programming language that can become obsolete quickly. By working with algorithms from the start and applying the concepts to the real world, students will understand the power of computers as problem solving tools and learn to think like programmers.

PART I The Computing Perspective

(52)

CHAPTER 1 Prologue: A History of Technology and Culture

(24)

1.1 Technology and Human Evolution

(2)

1.1.1 A Historical Pattern

(1)

1.1.2 Paradigmatic Change in Science

(1)

1.1.3 Hallmarks of a Paradigm Shift

(1)

1.2 An Outline of Paradigmatic History

(6)

1.2.1 The Age of Tribal Consciousness

(1)

1.2.2 The Alphabet and the Roots of Abstraction

(1)

1.2.3 The Age of Absolute Abstraction

(1)

1.2.4 Mechanical Media Technology

(1)

1.2.5 The Age of Mechanistic Thinking

(2)

1.2.6 Electronic Media Technology

(1)

1.3 The Significance of Recent Developments

(6)

1.3.1 Evidence of Paradigmatic Transformation

(2)

1.3.2 Attributes of the Emerging Paradigm

(1)

1.3.3 The Central Theme of the New Paradigm

(2)

1.4 The Emerging Paradigm

(6)

1.4.1 An Algorithmic Conception of Phenomena

(1)

1.4.2 A Means of Simulation and Experimentation

(3)

1.4.3 What It Means for You

(2)

Exercises

(3)

CHAPTER 2 The Algorithmic Model

(26)

2.1 What Is an Algorithm?

(4)

2.2 Properties of Good Algorithms

(4)

2.2.1 Precision

(1)

2.2.2 Simplicity

(1)

2.2.3 Levels of Abstraction

(3)

2.3 Algorithms and Computers

(6)

2.3.1 What Computers Do

(1)

2.3.2 Computers and Binary Data

(1)

2.3.3 Levels of Abstraction in Computers

(3)

2.3.4 Algorithms vs. Computer Programs

(1)

2.3.5 Data vs. Information

(1)

2.4 Algorithm Components

(3)

2.4.1 Data Structures

(1)

2.4.2 Data Manipulation Instructions

(1)

2.4.3 Conditional Expressions

(1)

2.4.4 Control Structures

(1)

2.4.5 Modules

(1)

2.5 Seeing Things from the Computing Perspective

(6)

2.5.1 Conceiving Behavior as Expressions of Algorithms

(1)

2.5.2 Conceiving of Things That Exhibit Behavior as Processes

(1)

2.5.3 Conceiving of Algorithms as Having Levels of Abstraction

(1)

2.5.4 Understanding How an Algorithm's Usefulness Is Limited by Its Complexity

(2)

2.5.5 Putting Aside Other Perspectives

(3)

Summary

Exercises

PART II The Algorithm Toolkit

(298)

CHAPTER 3 Basic Data and Operations

(32)

3.1 A Language for Algorithms

(2)

3.2 Creating Simple Variables

(1)

3.2.1 Variable Identifiers

(1)

3.3 Operators

(5)

3.3.1 Assignment Operators

(2)

3.3.2 Arithmetic Operators

(1)

3.3.3 Input/Output Operators

(2)

3.4 Atomic Data Types

(2)

3.4.1 Numbers

(1)

3.4.2 Characters

(1)

3.4.3 Booleans

(1)

3.4.4 Pointers

(1)

3.5 Complex Data Types

(1)

3.5.1 Strings

(1)

3.5.2 Other Complex Data Types

(1)

3.6 Declaring and Initializing Variables

(1)

3.6.1 Location of Data Declarations

(1)

3.6.2 Choosing Identifier Names

(1)

3.6.3 Initializing Variables

(1)

3.7 Fixed Data

(2)

3.7.1 Constants

(1)

3.7.2 Literal Values

(1)

3.8 General Rules

(2)

3.8.1 General Structure of an Algorithm

(1)

3.8.2 Formats for Identifiers

(1)

3.8.3 Type Matching

(1)

3.9 Algorithmic Decisions

(12)

3.9.1 The Basis of Decisions

(1)

3.9.2 Decisions and Data Types

(1)

3.9.3 Acting on Decisions

(4)

3.9.4 Complex Decisions via Boolean Operators

(3)

3.9.5 Nested Decisions

(3)

Summary

(1)

Exercises

(3)

CHAPTER 4 Tools for Procedural Abstraction

(54)

4.1 The Basic Idea

(1)

4.2 Why Modularity?

(1)

4.3 The Need for Module Interfaces

(1)

4.3.1 Parameters

(1)

4.3.2 Three Types of Parameters

(1)

4.4 Modules: Their Creation and Use

(9)

4.4.1 Creating Procedures and Functions

(4)

4.4.2 Calling Procedures and Functions

(1)

4.4.3 Using Multiple Parameters

(4)

4.5 Parameter Lists

100

(1)

4.6 The Scope of Data

101

(2)

4.6.1 Three Philosophies of Scope

101

(1)

4.6.2 The Scope of Variables

102

(1)

4.6.3 The Scope of Constants

102

(1)

4.7 The Kinds of Parameters

103

(9)

4.7.1 Input Parameters

104

(2)

4.7.2 Output Parameters

106

(4)

4.7.3 Input Output Parameters

110

(2)

4.8 A Larger Example

112

(3)

4.9 The Importance of Procedural Abstraction

115

(6)

4.9.1 Writing Algorithms

115

(2)

4.9.2 Testing Code

117

(1)

4.9.3 Maintaining Code

117

(1)

4.9.4 Reusing Logic

118

(2)

4.9.5 Reusing Code in Different Algorithms

120

(1)

4.10 Recursive Control

121

(2)

4.10.1 Two Forms for Recursion

121

(2)

4.10.2 Tracing Execution of a Recursive Module

123

(2)

4.10.3 Problem Solving with Recursion

125

(1)

4.10.4 Using a Stack to Trace Your Code

126

(5)

4.10.5 The Role of Recursion

131

(2)

Summary

133

(1)

Exercises

134

(7)

CHAPTER 5 Tools for Data Abstraction

141

(80)

5.1 The Meaning of Data

141

(1)

5.2 Organizing Multiple Pieces of Data

142

(1)

5.3 Records

143

(3)

5.3.1 Creating New Record Data Types

144

(1)

5.3.2 Accessing the Fields of a Record

145

(1)

5.4 Distinction Between Types and Variables

146

(2)

5.4.1 Data Types Expand the Language

146

(1)

5.4.2 The Scope of Data Types

146

(1)

5.4.3 The Abstraction Power of User-Defined Data Types

147

(1)

5.4.4 Anonymous Data Types

147

(1)

5.5 Pointers

148

(3)

5.6 Dynamic Data Structures

151

(1)

5.7 Linked Lists

152

(21)

5.7.1 The Structure of a Linked List

152

(2)

5.7.2 Using Pointers to Access Nodes

154

(5)

5.7.3 Using Pointers to Add Nodes

159

(2)

5.7.4 Using Pointers to Delete Nodes

161

(1)

5.7.5 Navigating Through a Linked List

162

(1)

5.7.6 Traversing a Linked List

162

(1)

5.7.7 A Recursive Linked List Traversal

163

(3)

5.7.8 A Recursive Linked List Search

166

(1)

5.7.9 Short Circuit Evaluation

167

(1)

5.7.10 Building a Linked List

168

(3)

5.7.11 Deleting Values from a Linked List

171

(1)

5.7.12 Summary of Linked List Features

172

(1)

5.8 The Scope of Linked Data

173

(4)

5.8.1 Static vs. Dynamic Variables

173

(3)

5.8.2 A Loophole in Parameter Protection for Linked Data

176

(1)

5.9 Binary Trees

177

(13)

5.9.1 Traversing Binary Trees

179

(2)

5.9.2 Binary Search Trees

181

(1)

5.9.3 Inorder BST Traversal

181

(5)

5.9.4 Preorder and Postorder Traversals

186

(1)

5.9.5 Searching a Binary Search Tree

187

(2)

5.9.6 Adding Nodes to a BST

189

(1)

5.9.7 Deleting Nodes from a BST

189

(1)

5.10 Graphs

190

(2)

5.11 Iterative Control

192

(3)

5.12 Iterative vs. Recursion

195

(2)

5.13 Arrays

197

(6)

5.13.1 Arrays vs. Linked Lists

199

(1)

5.13.2 Traversing Arrays

200

(1)

5.13.3 Searching Arrays

200

(1)

5.13.4 A More Efficient Array Search

201

(2)

5.14 The Abstraction Power of Constants

203

(2)

5.14.1 Ease of Change

203

(1)

5.14.2 Readability

204

(1)

5.15 The Abstraction Power of Creating New Data Types

205

(8)

5.15.1 Mixing Atomic and Complex Types

205

(1)

5.15.2 Arrays of Records

206

(3)

5.15.3 Records of Records

209

(2)

5.15.4 Arrays of Arrays

211

(2)

Summary

213

(2)

Exercises

215

(6)

CHAPTER 6 Algorithmic Methods

221

(32)

6.1 Traversals

222

(10)

6.1.1 Traversals of Linear Structures

222

(1)

6.1.2 Traversals of Nonlinear Structures

223

(2)

6.1.3 Stacks and Queues

225

(4)

6.1.4 Breadth-First Traversal

229

(2)

6.1.5 Implementation of Breadth-First Traversal

231

(1)

6.2 Searches

232

(3)

6.2.1 Simple Search via Traversal

232

(1)

6.2.2 Key Fields

233

(1)

6.2.3 More Efficient Searches

233

(2)

6.3 Sorting

235

(2)

6.4 Divide and Conquer

237

(4)

6.5 Optimization

241

(6)

6.5.1 Greedy Algorithms

241

(3)

6.5.2 Dynamic Programming

244

(3)

Summary

247

(1)

Exercises

248

(5)

CHAPTER 7 Tools for Modeling Real-World Objects

253

(44)

7.1 The Object-Oriented Paradigm

254

(1)

7.1.1 The Benefits of the OO Approach

255

(1)

7.1.2 Required Features

255

(1)

7.2 Achieving Superior Encapsulation

255

(6)

7.2.1 The Limitations of Procedural and Data Abstractions

256

(1)

7.2.2 The Concept of Abstract Data Types

256

(1)

7.2.3 Using Classes to Define ADTs

257

(3)

7.2.4 Using Objects to Create Instances of ADTs

260

(1)

7.3 The Anatomy of a Class

261

(6)

7.3.1 The Public Section

263

(1)

7.3.2 The Protected Section

263

(1)

7.3.3 Scope of Data Within a Class

264

(1)

7.3.4 Contracts

265

(1)

7.3.5 Declaring and Using Objects

266

(1)

7.4 Generic Parameters and Reusability

267

(3)

7.5 Tracing the Execution of Object Behaviors

270

(2)

7.6 Copy and Clone Operations

272

(2)

7.7 Achieving Superior Adaptability

274

(6)

7.7.1 Inheriting and Extending Behaviors

275

(1)

7.7.2 Redefining Inherited Identifiers

276

(2)

7.7.3 Changing Public/Protected Status

278

(1)

7.7.4 Summary of the Kinds of Inheritance

279

(1)

7.7.5 Resolving Ambiguity

279

(1)

7.8 Achieving Polymorphism

280

(4)

7.9 Everything Is an Object

284

(5)

Summary

289

(2)

Exercises

291

(6)

CHAPTER 8 Tools for Verifying Correctness

297

(20)

8.1 Bugs and Debugging

298

(7)

8.1.1 Ambiguity

298

(1)

8.1.2 Syntax Errors

299

(1)

8.1.3 Semantic Errors

300

(1)

8.1.4 Logic Errors

301

(4)

8.2 Proving Correctness

305

(2)

8.3 Verification

307

(1)

8.4 The Most Important Thing You Can Do

308

(3)

Summary

311

(1)

Exercises

312

(5)

CHAPTER 9 Tools for Estimating Cost and Complexity

317

(34)

9.1 Measures of Performance

318

(3)

9.2 Measures of Work

321

(1)

9.3 Analysis of Work Done

322

(1)

9.4 Actual vs. Random Input

323

(1)

9.5 Increasing the Complexity

324

(5)

9.6 Performance and Data Structures

329

(2)

9.7 Increasing the Complexity Some More

331

(3)

9.8 Estimating Bubblesort's Complexity

334

(5)

9.9 Reasonable vs. Unreasonable Algorithms

339

(4)

9.10 Categories of Unreasonable Algorithms

343

(3)

Summary

346

(1)

Exercises

347

(4)

PART III The Limits of Computing

351

(50)

CHAPTER 10 Concurrency and Parallelism

353

(24)

10.1 Overview: Concurrency vs. Parallelism

353

(3)

10.1.1 What is Concurrency?

354

(1)

10.1.2 What is Parallelism?

354

(2)

10.1.3 Confusion Between the Two

356

(1)

10.2 Concurrency

356

(2)

10.2.1 Multiprogramming

356

(1)

10.2.2 Multiprocessing

357

(1)

10.2.3 Multitasking

357

(1)

10.2.4 Distributed Systems

357

(1)

10.3 Issues in Concurrency

358

(3)

10.3.1 Protection

358

(1)

10.3.2 Fairness

359

(1)

10.3.3 Deadlock

360

(1)

10.3.4 Summary of Concurrency Ideas

361

(1)

10.4 Parallelism

361

(2)

10.5 Limits of Parallelism

363

(10)

10.5.1 Fixed Number of Processors

364

(1)

10.5.2 Overhead Costs

365

(1)

10.5.3 Dependencies

366

(3)

10.5.4 Precedences

369

(4)

Summary

373

(1)

Exercises

374

(3)

CHAPTER 11 The Hierarchy of Problem Complexity

377

(16)

11.1 Problem Complexity

377

(2)

11.2 Open vs. Closed Problems

379

(1)

11.3 Tractable vs. Intractable Problems

379

(1)

11.4 Problems that Cross the Line

380

(1)

11.5 NP-Complete Problems

381

(1)

11.6 Certificates, Oracles, and Determinism

382

(2)

11.6.1 Certificates

383

(1)

11.6.2 Oracles

383

(1)

11.6.3 Determinism vs. Nondeterminism

384

(1)

11.7 NP-Complete vs. Intractable Problems

384

(1)

11.8 Undecidability

384

(5)

11.8.1 Certificates for Undecidable Problems

386

(3)

Summary

389

(1)

Exercises

390

(3)

CHAPTER 12 Epilogue: A History of Computing and Algorithms

393

(8)

12.1 The Literal Paradigm

394

(1)

12.2 The Advent of Abstraction

394

(1)

12.3 The Paradigm of Absolute Abstractions

394

(1)

12.4 The Advent of Mechanism

395

(1)

12.5 The Paradigm of Mechanistic Thinking

396

(1)

12.6 The Advent of Instantaneous Connectivity

396

(1)

12.7 The Paradigm of Interdependent Processes

397

(2)

12.8 What Happens Next?

399

(2)

Index

401

Please wait while the item is added to your bag...

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

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

Introduction to Computing and Algorithms

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

Introduction to Computing and Algorithms

Summary

Author Biography

Table of Contents

Supplemental Materials

Digital License