Algorithms and Data Structures: the Science of Computing

Site Index

Part I:  The Science of Computing’s Three Methods of Inquiry

Chapter 1: What is the Science of Computing?

• Algorithms and the Science of Computing
  • Problems
  • Algorithms
  • Describing Algorithms
• Computer Science’s Methods of Inquiry
  • Design
  • Theory
  • Empirical Analysis
• Concluding Remarks
• Further Reading

Chapter 2: Abstraction: An Introduction to Design

• Abstraction with Objects
  • Objects
  • Messages
  • Classes
  • Objects as Abstractions
• Preconditions and Postconditions
• Algorithms that Produce Effects
  • Design from Pre- and Postconditions
  • Subclasses
  • Method Abstraction
• Algorithms that Produce Values
  • Expressions
  • Abstractions of Expressions
  • Values and Side-Effects
• Encapsulating Values
• Concluding Remarks
• Further Reading

Chapter 3: Proof: An Introduction to Theory

• Basic Ideas
  • Correctness
  • Proof
  • Proving an Algorithm Correct
  • Proof Methods
• Correctness of Methods
  • An Example
  • Proof Structure
• Correctness of Side-Effects
  • The Square-Drawing Problem Revisited
  • drawLine
  • drawSquare
• Correctness of Classes
  • Class Invariants
  • Object Initialization and Constructors
  • Proving Class Invariants
• Applying the Proof Techniques
  • The Correctness of MakeChange
  • Proofs and Incorrect Algorithms
• Analyzing Efficiency
  • An Example
  • Efficiency and Problem Size
  • Execution Time
  • Resources
• Concluding Remarks
• Further Reading

Chapter 4: Experimentation: An Introduction to the Scientific Method

• Theories and Hypotheses
  • The Role of Experiments
• Predictions
• Experimental Procedure
  • Define Variables
  • Use Appropriate Instruments
  • Thoroughly Explore the Independent Variable
  • Control Differences between Subjects
  • Make Multiple Measurements
• Experimental Error
  • Systematic Error
  • Random Error
• Data Analysis
  • Estimating True Values
  • The Error in an Average
  • Relative Error
• Forming Conclusions
• Measuring Time in Computer Science Experiments
  • Defining Time as a Variable
  • Measuring Time
  • Error Sources in Time Measurements
• An Example Experiment
• Other Uses of Experiments in Computer Science
  • Programming
  • Hardware/Software Systems
  • Human Considerations
• Concluding Remarks
• Further Reading

Part II:  Program Design

Chapter 5: Conditionals

• Review of Terminology
• TheTest: Boolean Expressions
  • Conjunction (And)
  • Disjunction (Or)
  • Negation (Not)
  • Implication
  • Boolean Expressions and Java
• Boolean Algebra
  • Complex Truth Tables
  • Truth Tables as a Proof Technique
  • Manipulating Boolean Expressions
• Correctness: Proof by Case
  • Separation of Cases
• Performance Analysis and Conditionals
  • Expanding the Definition of Execution Time
  • Bounding Execution Time
  • What the Best Case and Worst Case Can Tell Us
• Boolean Algebra as a Program Design Tool
  • Robust Algorithms: the Power of Conditionals
  • Construction of Boolean Methods
  • Interpreting Nested Conditionals
  • Finding Design Flaws
  • Establishing Test Data
• Empirical Measure and Conditional Statements
• Concluding Remarks
• Further Reading

Chapter 6: Designing with Recursion

• Basics of Recursive Thinking
  • Stating the Problem Recursively
  • Restating in Computational Terms
  • A Recursive Java Method
  • Recursion is Ubiquitous
• Controlling Recursion: Indices
  • Simple Indices
  • General Principles for Indices
  • Non–Numeric Indices
• Value Producing Recursion
  • Inductive Definitions in Mathematics
  • Converting a Mathematical Definition to a Method
  • The Index as Result
• Assuring Termination
• Recursive Descriptions as Algorithms
  • Understanding the Execution of Recursive Algorithms
  • Classifying Recursive Algorithms
  • Algorithms with Multiple Recursive References
  • Recursive Call is Never First
  • Hiding Recursion
• Concluding Remarks
• Further Reading

Chapter 7: Analysis of Recursion

• Correctness
  • Induction in Mathematics
  • Induction and the Correctness of Recursive Algorithms
• Efficiency
  • Recurrence Relations in Mathematics
  • Recurrence Relations and Recursive Algorithms
• Concluding Remarks
• Further Reading

Chapter 8: Creating Correct Iterative Algorithms

• Loop Invariants
  • Formal Definition
  • Design with Loop Invariants
• Correctness of Iterative Algorithms
  • Proving Termination
  • Proving Loop Invariants
  • Proving Postconditions
  • A Complete Correctness Proof
• Concluding Remarks
• Further Reading

Chapter 9: Iteration and Efficiency

• Counting the Steps in Iterative Algorithms
  • Overview
  • Simple Loops
  • Varying Number of Steps per Iteration
  • Deriving the Number of Iterations
• Relating Step Counts to Execution Time
  • Introductory Examples
  • Asymptotic Notation
  • Testing Asymptotic Hypotheses
• Iteration and Measuring Short Execution Times
  • The Basic Technique
  • Controlling for Overhead
  • Error
• Concluding Remarks
• Further Reading

Chapter 10: A Case-Study in Design and Analysis: Efficient Sorting

• An Initial Insight
  • The Insight
  • Example
  • Strategy: Divide and Conquer
• Quicksort Design
  • Refining Quicksort’s Design
  • Partitioning
• Quicksort Performance
  • The Number of Comparisons in Partition
  • Accounting for Quicksort’s Recursion
  • Quicksort’s Best Case Performance
  • Quicksort’s Worst-Case Performance
• Mergesort
  • Overall Design
  • The Merge Algorithm
  • Performance
• Concluding Remarks
• Further Reading

Part III:  Introduction to Data Structures

Chapter 11: Lists

• Examples of Lists or Sequences
  • Real World Lists
  • Of Special Importance to Computer Scientists
• Developing the Concept of a List
  • Manipulating Lists
  • Visiting the Subparts
  • A Unifying Observation
  • The Empty List
• A Formal Definition of the Class List
  • Basic Methods
  • Examples
• Implementing the Class
  • Constructing a Basic List Class
• Making an Extendable List Class
  • Creating New Methods for Lists
  • The Final List Class
  • Ordered List as an Extension of List
  • Complex Elements
  • Case Study: Insertion Sort
• Variants on the Concept of List
  • Alternate Representations of the Base Class
  • Two Way Lists
• Concluding Remarks
• Further Reading

Chapter 12: Queues and Stacks

• Queues
  • Motivation from the Real World
  • Computer Science Examples
  • The Queue Interface
  • Implementation and Efficiency
  • A Workable Definition
  • Implementing the Queue Class
• Stacks
  • Real World Motivations for Stacks
  • Stacks and Computer Science
  • Designing the Stack Class
  • Implementing the Class Stack
  • Stacks and Recursion
  • Implications of Stacks for Common Computing Problems
• Concluding Remarks
  • Queues vs. Stacks
  • Looking Ahead to Other Structures
• Further Reading

Chapter 13: Binary Trees

• Hierarchical Organization
  • Real World Trees
  • Trees as Analogies
  • Trees and Computer Science
• Formalizing the Concept of Tree
  • Trees as Data Structures
  • Visualizing a Formalism
• Ordered Trees
  • Definition of an Ordered Tree
  • Traversal
  • Constructing an Ordered Tree
  • Searching an Ordered Tree
  • Performance Analysis for Ordered Trees
  • Trees that Are not Fully Balanced
  • Empirical Evaluation of Construction and Search Time
• An OrderedTree Class for Java
• Restructuring Ordered Trees
  • Deleting Nodes from Trees
  • Balancing a Tree
• Arithmetic Expressions as Trees
• Other Implementations
  • Null Empty Trees
  • n-ary Trees
• Concluding Remarks
• Further Reading

Chapter 14: Case Studies in Design: Abstracting Indirection

• Indirection Without Formal Pointers
  • Review of Indirection in Java
  • Abstracting the Concept of Indirection
• Using Arrays to Hold Dynamic Data Structures
  • Arrays as Lists
  • Circle Queue
  • Stacks
  • Array–Based Trees
• Hash Coding
  • Content–Based Pointers
  • Collisions
  • Uneven Distribution
  • Dealing with Collisions
  • Hashing and Empirical Results
• Priority Queues
  • The Public Interface
  • What We Already Know Might Help Us
  • Some Nice Ideas and What’s Wrong with Them
  • The Heap Approach
  • One Final Detail: Finding the Oldest
• Concluding Remarks
• Further Reading

Part IV:  The Limits of Computer Science

Chapter 15: Exponential Growth

• Warm-up: The Towers of Hanoi
  • The Problem
  • The Algorithm
  • Execution Time
• Drawing Trees
  • The Algorithm
  • The Execution Time of the Tree-Drawing Algorithm
  • A Variation on the Algorithm
• The Empirical Significance of Exponential Time
• Reducing Exponential Costs
  • The Fibonacci Numbers
  • An Obvious Fibonacci Number Algorithm
  • The Dynamic Programming Algorithm
• Concluding Remarks
• Further Reading

Chapter 16: Limits to Performance

• Preliminary Remarks
• Finding Lower Bounds and Proving Optimality
  • The Towers of Hano
  • Other Problems
• Open Questions
  • Tractable and Intractable Problems
  • Factoring and Cryptography
  • The Travelling Sales Representative and NP-Hard Problems
• Concluding Remarks
• Further Reading

Chapter 17: The Halting Problem

• Applying Computer Science to Computer Science
  • Programs as Strings
  • A Proposed Tool: Checking for Infinite Loops
• The Halting Problem (at Last)
  • A Preview: Dealing with Paradoxical Questions
  • Resolving the Halting Problem
• Implications of the Halting Problem for Computer Science
  • Some Problems Just Cannot Be Computed
  • There are More Functions than There are Programs
  • Computable Problems
  • All Computers are Equivalent
  • Mathematics is Incomplete
• Concluding Remarks
• Further Reading

Appendix: Object Oriented Programming in Java

• Program Structure
  • A First Program
  • Naming Source Files
• Non-Object Features
  • Data Types and Expressions
  • Control Structures
• Using Objects
  • Declaring Objects
  • Creating Objects
  • Sending Messages to Objects
• Defining Classes
  • Overall Form
  • Member Variables
  • Method Declarations
  • Constructors
  • Subclasses
  • Static Members
• Imprecise Classes
  • Class “Object”
  • Casts
  • Interfaces
• Packages
  • Using Classes from a Package
• Java’s Implementation of Objects
  • Object Variables are Pointers
  • Assignments to Object Variables
  • Comparing Objects
  • Null Pointers
• Further Reading

Copyright © 2004 Charles River Media. All rights reserved.

Revised Aug. 9, 2005 by Doug Baldwin

Site Index