How to Think About Algorithms

Описание

HOW TO THINK ABOUT ALGORITHMS
There are many algorithm texts that provide lots of well-polished code and proofs of correctness. Instead, this one presents insights, notations, and analogies to help the novice describe and think about algorithms like an expert. It is a bit like a carpenter studying hammers instead of houses. Jeff Edmonds provides both the big picture and easy step-by-step methods for developing algorithms, while avoiding the common pitfalls. Paradigms such as loop invariants and recursion help to unify a huge range of algorithms into a few meta-algorithms. Part of the goal is to teach students to think abstractly. Without getting bogged down in formal proofs, the book fosters deeper understanding so that how and why each algorithm works is transparent. These insights are presented in a slow and clear manner accessible to second- or third-year students of computer science, preparing them to find on their own innovative ways to solve problems.
Abstraction is when you translate the equations, the rules, and the underlying essences of the problem not only into a language that can be communicated to your friend standing with you on a streetcar, but also into a form that can percolate down and dwell in your subconscious. Because, remember, it is your subconscious that makes the miraculous leaps of inspiration, not your plodding perspiration and not your cocky logic. And remember, unlike you, your subconscious does not understand Java code.
HOW TO THINK ABOUT ALGORITHMS
JEFF EDMONDS
York University
CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, Sao Paulo, Delhi
Cambridge University Press 32 Avenue of the Americas, New York, NY 10013-2473, USA
First published 2008
Printed in the United States of America
A catalog record for this publication is available from the British Library.
Library of Congress Cataloging in Publication data
Edmonds, Jeff, 1963– How to think about algorithms / Jeff Edmonds. p. cm. Includes index. ISBN 978-0-521-84931-9 (hardback) – ISBN 978-0-521-61410-8 (pbk.) 1. Algorithms – Study and teaching. 2. Loops (Group theory) – Study and teaching. 3. Invariants – Study and teaching. 4. Recursion theory – Study and teaching. I. Title. QA9.58.E36 2008 518′.1–dc22 2008001238
ISBN 978-0-521-84931-9 hardback ISBN 978-0-521-61410-8 paperback
Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party Internet Web sites referred to in this publication and does not guarantee that any content on such Web sites is, or will remain, accurate or appropriate.
Dedicated to my father, Jack, and to my sons, Joshua and Micah.
May the love and the mathematics continue to flow between the generations.
CONTENTS
Preface
Introduction
PART ONE. ITERATIVE ALGORITHMS AND LOOP INVARIANTS
1 Iterative Algorithms: Measures of Progress and Loop Invariants
1.1 A Paradigm Shift: A Sequence of Actions vs. a Sequence of Assertions
1.2 The Steps to Develop an Iterative Algorithm
1.3 More about the Steps
1.4 Different Types of Iterative Algorithms
1.5 Typical Errors
1.6 Exercises
2 Examples Using More-of-the-Input Loop Invariants
2.1 Coloring the Plane
2.2 Deterministic Finite Automaton
2.3 More of the Input vs. More of the Output
3 Abstract Data Types
3.1 Specifications and Hints at Implementations
3.2 Link List Implementation
3.3 Merging with a Queue
3.4 Parsing with a Stack
4 Narrowing the Search Space: Binary Search
4.1 Binary Search Trees
4.2 Magic Sevens
4.3 VLSI Chip Testing
4.4 Exercises
5 Iterative Sorting Algorithms
5.1 Bucket Sort by Hand
5.2 Counting Sort (a Stable Sort)
5.3 Radix Sort
5.4 Radix Counting Sort
6 Euclid’s GCD Algorithm
7 The Loop Invariant for Lower Bounds
PART TWO. RECURSION
8 Abstractions, Techniques, and Theory
8.1 Thinking about Recursion
8.2 Looking Forward vs. Backward
8.3 With a Little Help from Your Friends
8.4 The Towers of Hanoi
8.5 Checklist for Recursive Algorithms
8.6 The Stack Frame
8.7 Proving Correctness with Strong Induction
9 Some Simple Examples of Recursive Algorithms
9.1 Sorting and Selecting Algorithms
9.2 Operations on Integers
9.3 Ackermann’s Function
9.4 Exercises
10 Recursion on Trees
10.1 Tree Traversals
10.2 Simple Examples
10.3 Generalizing the Problem Solved
10.4 Heap Sort and Priority Queues
10.5 Representing Expressions with Trees
11 Recursive Images
11.1 Drawing a Recursive Image from a Fixed Recursive and a Base Case Image
11.2 Randomly Generating a Maze
12 Parsing with Context-Free Grammars
PART THREE. OPTIMIZATION PROBLEMS
13 Definition of Optimization Problems
14 Graph Search Algorithms
14.1 A Generic Search Algorithm
14.2 Breadth-First Search for Shortest Paths
14.3 Dijkstra’s Shortest-Weighted-Path Algorithm
14.4 Depth-First Search
14.5 Recursive Depth-First Search
14.6 Linear Ordering of a Partial Order
14.7 Exercise
15 Network Flows and Linear Programming
15.1 A Hill-Climbing Algorithm with a Small Local Maximum
15.2 The Primal–Dual Hill-Climbing Method
15.3 The Steepest-Ascent Hill-Climbing Algorithm
15.4 Linear Programming
15.5 Exercises
16 Greedy Algorithms
16.1 Abstractions, Techniques, and Theory
16.2 Examples of Greedy Algorithms
16.2.1 Example: The Job/Event Scheduling Problem
16.2.2 Example: The Interval Cover Problem
16.2.3 Example: The Minimum-Spanning-Tree Problem
16.3 Exercises
17 Recursive Backtracking
17.1 Recursive Backtracking Algorithms
17.2 The Steps in Developing a Recursive Backtracking

Детали