Introduction to Computing and Algorithms

by Shackelford, Russel L

• ISBN13: 9780201314519
• ISBN10: 0201314517
• Edition: 1st
• Format: Paperback
• Copyright: 1997-10-16
• Publisher: Pearson
• More Book Details

Summary

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.

Author Biography

Russell Shackelford is currently the Director of Lower Division Studies in The College of Computing at Georgia Tech. He holds various degrees in Computer Science, Education, and Psychology. His work is aimed at integrating research and practice concerning computing education, and at the development of computing tools and associated human methods for supporting education. Besides having a well-rounded education, Dr. Shackelford also loves baseball and occasionally can be found walking on the beach somewhere in Alabama.

0201314517AB04062001

Table of Contents

PART I The Computing Perspective	1	(52)
CHAPTER 1 Prologue: A History of Technology and Culture	3	(24)
1.1 Technology and Human Evolution	4	(2)
1.1.1 A Historical Pattern	4	(1)
1.1.2 Paradigmatic Change in Science	5	(1)
1.1.3 Hallmarks of a Paradigm Shift	6	(1)
1.2 An Outline of Paradigmatic History	6	(6)
1.2.1 The Age of Tribal Consciousness	6	(1)
1.2.2 The Alphabet and the Roots of Abstraction	7	(1)
1.2.3 The Age of Absolute Abstraction	8	(1)
1.2.4 Mechanical Media Technology	9	(1)
1.2.5 The Age of Mechanistic Thinking	10	(2)
1.2.6 Electronic Media Technology	12	(1)
1.3 The Significance of Recent Developments	12	(6)
1.3.1 Evidence of Paradigmatic Transformation	13	(2)
1.3.2 Attributes of the Emerging Paradigm	15	(1)
1.3.3 The Central Theme of the New Paradigm	16	(2)
1.4 The Emerging Paradigm	18	(6)
1.4.1 An Algorithmic Conception of Phenomena	18	(1)
1.4.2 A Means of Simulation and Experimentation	19	(3)
1.4.3 What It Means for You	22	(2)
Exercises	24	(3)
CHAPTER 2 The Algorithmic Model	27	(26)
2.1 What Is an Algorithm?	27	(4)
2.2 Properties of Good Algorithms	31	(4)
2.2.1 Precision	32	(1)
2.2.2 Simplicity	32	(1)
2.2.3 Levels of Abstraction	32	(3)
2.3 Algorithms and Computers	35	(6)
2.3.1 What Computers Do	36	(1)
2.3.2 Computers and Binary Data	36	(1)
2.3.3 Levels of Abstraction in Computers	37	(3)
2.3.4 Algorithms vs. Computer Programs	40	(1)
2.3.5 Data vs. Information	40	(1)
2.4 Algorithm Components	41	(3)
2.4.1 Data Structures	42	(1)
2.4.2 Data Manipulation Instructions	42	(1)
2.4.3 Conditional Expressions	42	(1)
2.4.4 Control Structures	43	(1)
2.4.5 Modules	43	(1)
2.5 Seeing Things from the Computing Perspective	44	(6)
2.5.1 Conceiving Behavior as Expressions of Algorithms	44	(1)
2.5.2 Conceiving of Things That Exhibit Behavior as Processes	44	(1)
2.5.3 Conceiving of Algorithms as Having Levels of Abstraction	45	(1)
2.5.4 Understanding How an Algorithm's Usefulness Is Limited by Its Complexity	45	(2)
2.5.5 Putting Aside Other Perspectives	47	(3)
Summary	50
Exercises	5
PART II The Algorithm Toolkit	53	(298)
CHAPTER 3 Basic Data and Operations	55	(32)
3.1 A Language for Algorithms	55	(2)
3.2 Creating Simple Variables	57	(1)
3.2.1 Variable Identifiers	58	(1)
3.3 Operators	58	(5)
3.3.1 Assignment Operators	58	(2)
3.3.2 Arithmetic Operators	60	(1)
3.3.3 Input/Output Operators	61	(2)
3.4 Atomic Data Types	63	(2)
3.4.1 Numbers	64	(1)
3.4.2 Characters	64	(1)
3.4.3 Booleans	65	(1)
3.4.4 Pointers	65	(1)
3.5 Complex Data Types	65	(1)
3.5.1 Strings	65	(1)
3.5.2 Other Complex Data Types	66	(1)
3.6 Declaring and Initializing Variables	66	(1)
3.6.1 Location of Data Declarations	66	(1)
3.6.2 Choosing Identifier Names	66	(1)
3.6.3 Initializing Variables	67	(1)
3.7 Fixed Data	67	(2)
3.7.1 Constants	68	(1)
3.7.2 Literal Values	68	(1)
3.8 General Rules	69	(2)
3.8.1 General Structure of an Algorithm	69	(1)
3.8.2 Formats for Identifiers	70	(1)
3.8.3 Type Matching	71	(1)
3.9 Algorithmic Decisions	71	(12)
3.9.1 The Basis of Decisions	72	(1)
3.9.2 Decisions and Data Types	72	(1)
3.9.3 Acting on Decisions	73	(4)
3.9.4 Complex Decisions via Boolean Operators	77	(3)
3.9.5 Nested Decisions	80	(3)
Summary	83	(1)
Exercises	84	(3)
CHAPTER 4 Tools for Procedural Abstraction	87	(54)
4.1 The Basic Idea	88	(1)
4.2 Why Modularity?	89	(1)
4.3 The Need for Module Interfaces	90	(1)
4.3.1 Parameters	90	(1)
4.3.2 Three Types of Parameters	90	(1)
4.4 Modules: Their Creation and Use	91	(9)
4.4.1 Creating Procedures and Functions	91	(4)
4.4.2 Calling Procedures and Functions	95	(1)
4.4.3 Using Multiple Parameters	96	(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