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 comon 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 trans-
parent. 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 under-
lying essences of the problem not only into a language that can be commu-
nicated to your friend standing with you on a streetcar, but also into a form
that can percolate down and dwell in your subconscious. Because, remem-
ber, 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.
Bookmarks
Cover
Half-title
Title
Copyright
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
17.3 Pruning Branches
17.4 Satisfiability
17.5 Exercises
18 Dynamic Programming Algorithms
18.1 Start by Developing a Recursive Backtracking
18.2 The Steps in Developing a Dynamic Programming Algorithm
18.3 Subtle Points
18.3.1 The Question for the Little Bird
18.3.2 Subinstances and Subsolutions
18.3.3 The Set of Subinstances
18.3.4 Decreasing Time and Space
18.3.5 Counting the Number of Solutions
18.3.6 The New Code
19 Examples of Dynamic Programs
19.1 The Longest-Common-Subsequence Problem
19.2 Dynamic Programs as More-of-the-Input Iterative Loop Invariant Algorithms
19.3 A Greedy Dynamic Program: The Weighted Job/Event Scheduling Problem
19.4 The Solution Viewed as a Tree: Chains of Matrix Multiplications
19.5 Generalizing the Problem Solved: Best AVL Tree
19.6 All Pairs Using Matrix Multiplication
19.7 Parsing with Context-Free Grammars
19.8 Designing Dynamic Programming Algorithms via Reductions
20 Reductions and NP-Completeness
20.1 Satisfiability Is at Least as Hard as Any Optimization Problem
20.2 Steps to Prove NP-Completeness
20.3 Example: 3-Coloring Is NP-Complete
20.4 An Algorithm for Bipartite Matching Using the Network Flow Algorithm
21 Randomized Algorithms
21.1 Using Randomness to Hide the Worst Cases
21.2 Solutions of Optimization Problems with a Random Structure
PART FOUR: Appendix
22 Existential and Universal Quantifiers
23 Time Complexity
23.1 The Time (and Space) Complexity of an Algorithm
23.2 The Time Complexity of a Computational Problem
24 Logarithms and Exponentials
25 Asymptotic Growth
25.1 Steps to Classify a Function
25.2 More about Asymptotic Notation
26 Adding-Made-Easy Approximations
26.1 The Technique
26.2 Some Proofs for the Adding-Made-Easy Technique
27 Recurrence Relations
27.1 The Technique
27.2 Some Proofs
28 A Formal Proof of Correctness
PART FIVE: Exercise Solutions
Chapter 1. Iterative Algorithms: Measures of Progress and Loop Invariants
Chapter 2. Examples UsingMore-of-the-Input Loop Invariant
Chapter 3. Abstract Data Types
Chapter 4. Narrowing the Search Space: Binary Search
Chapter 6. Euclid’s GCD Algorithm
Chapter 7. The Loop Invariant for Lower Bounds
Chapter 8. Abstractions, Techniques, and Theory
Chapter 9. Some Simple Examples of Recursive Algorithms
Chapter 10. Recursion on Trees
Chapter 11. Recursive Images
Chapter 12. Parsingwith Context-Free Grammars
Chapter 14. Graph Search Algorithms
Chapter 15. Network Flows and Linear Programming
Chapter 16: Greedy Algorithms
Chapter 17. Recursive Backtracking
Chapter 18. Dynamic Programming Algorithms
Chapter 19. Examples of Dynamic Programs
Chapter 20. Reductions and NP-Completeness
Chapter 22. Existential and Universal Quantifiers
Chapter 23. Time Complexity
Chapter 24. Logarithms and Exponentials
Chapter 25. Asymptotic Growth
Chapter 26. Adding-Made-Easy Approximations
Chapter 27. Recurrence Relations
CONCLUSION
INDEX
Jeff Edmonds received his Ph.D. in 1992 at University of Toronto in theoretical computer science. His thesis proved that certain computation problems require a given amount of time and space. He did his postdoctorate work at the ICSI in Berkeley on secure multi-media data transmission and in 1995 became an Associate Professor in the Department of Computer Science at York Univer...
(展开全部)
刘越女科精要 内容简介 本书记述了刘越对中国传统医学有关女科的思考与探索,是刘越先生一生业医、理论与实践的结晶和菁华的一部分。刘越女科精要 目录 总论证治源流一...
铁路交通事故典型案例分析与警示 本书特色 《铁路交通事故典型案例分析与警示》是北京铁路局职工教育处连同北京铁路局安监室编写的一本铁路交通事故典型案例分析图书。《...
“犯罪小说女王”阿加莎•克里斯蒂在她众多令人着迷的推理小说中,构思了无数悬念与谜团,也使用了各种各样的毒药。在小说里,毒药不仅是受害者被害的原因,也是推动情节发...
余华,1960年4月出生,1983年开始写作,主要作品有《兄弟》《活着》《许三观卖血记》《在细雨中呼喊》《第七天》等。其作品被翻译成40多种语言在美国、英国、澳...
天才建築師們的夢幻奇想!建築史上最令人驚嘆卻從未被實現的建築!大教堂、宮殿、監獄、紀念碑、摩天大樓、理想城市……從中世紀、文藝復興到二十一世紀的今日,50個顛覆...
《元曲三百首》内容简介:元曲是中国古代诗歌的最后绝响,被称为元代最佳之文学,与唐诗、宋词相提并论。元曲包括杂剧和散曲,本书
黄旭初是排在李宗仁、白崇禧、黄绍竑之后的桂系第四号人物。他以日记为基础,加上部分历史文献,经李宗仁亲自修订,回顾了李宗仁、白崇禧的桂系与蒋介石二十多年间的分分合...
肖大侠新旗互动创始人兼首席话题官,病毒营销6P方法论的提出者和实践者。“阿里铁军”老兵,入职数月即成为阿里巴巴浙江大区的销售冠军。拥有10年新媒体内容营销经验,...
柴田明彦,1959年东京生人,毕业于庆应义塾大学法学部政治学科。1983年进入电通股份有限公司工作,先后曾任报社出版、新闻开发部部长及业务推进部部长等职务。20...
约翰·密尔(John Stuart Mill,1806—1873),19世纪欧洲思想巨擘,英国著名的哲学家、经济学家与政治理论家,被世人誉为自由主义承先启后的大...
猫腻,曾用作者北洋鼠,备用作者乐俊,总是脱不开汤姆与杰瑞的范畴。七十年代生人,蜗于湖北夷陵之地三十载,昼伏夜出,好独行,不好独居。尝就学于川大,因惫懒故被逐,重...
李月亮,高人气自媒体人,畅销书作家,专业解决情感里的疑难杂症,及人生中的纷繁谜题。用温柔又有力的笔触,给岁月以深情的告白。已出版作品《愿你的生活既有软肋又有盔甲...
没有哪一颗星球,能像火星一样,承载人类如此多的想象和憧憬。也没有哪一场探索,能像探索火星一样,在过程中不断交织着反转和奇迹。这是一段历时四百多年的“追星”之旅,...
作品目录前言亲士修身所染法仪七患辞过三辩尚贤上尚贤中尚贤下尚同上尚同中尚同下兼爱上兼爱中兼爱下非攻上非攻中非攻下节用上节
刘勤字彦序,成都人。四川大学文学博士、中国社会科学院访问学者、四川师范大学251重点人才培养工程科研人员、副教授、中国民间文学大系编纂工程副主编。主要从事先秦文...
《生长:从战略到执行》内容简介:制定战略是CEO的事吗?战略有好坏之分吗?判断标准是什么?在制定战略时,如何站在“未来”看“现
艾西恩一直想弄明白自己是怎么回事:9岁去父亲单位时意外撞见尸体解剖;18岁立志学习心理学;22岁研习了全部医科院校解剖课程;23岁开始以闪苍为笔名创作犯罪心理小...
宗芳,别名Anna。政治大学历史系毕业。曾任职康轩文教文字编辑,日本航空资深空服员,目前为自由文字创作者。喜爱旅行、阅读、用文字记录感动的瞬间。作品曾获中国时报...
ThisbookexplorestheuniquehardwareprogrammabilityofFPGA(field-programmablegatearr...
《递归人工神经网络的定性分析和综合》目录专家评论读者评论我要留言《递归人工神经网络的定性分析和综合》系统地研究了递归人工神经网络的定性性能及其局限性,该类网络用...