英文版算法设计参考书：深入理解数据结构后的学习宝典

需积分: 10 131 浏览量更新于2024-07-18 2 收藏 4.79MB PDF 举报

"《算法设计英文版》是一本深度剖析和实践算法理论的专业书籍，适合在掌握一定数据结构基础后进一步提升算法设计能力的学习者使用。该书由经验丰富的Acquisitions Editor Matt Goldstein主导项目编辑工作，Maite Suarez-Rivas负责具体实施，Marilyn Lloyd担任生产监督，确保项目的高效进行。Marketing团队由Michelle Brown担任经理，Jake Zavracky协助市场协调，而Windfall Software则提供了项目管理支持。本书采用Windfall Software的ZzT技术进行编排，保证了内容的专业性和易读性。Carol Leyba负责文字校对，确保语言准确无误，而Dartmouth Publishing的专业技术人员提供了技术插图，使得抽象的概念更加生动易懂。Jennifer McClain担任了最终的校对工作，保证了内容的准确性。Indexer Ted Laux精心编制索引，方便读者快速查找所需信息。封面设计出自Joyce Cosentino Wells之手，配以Tim Laman拍摄的非洲织布鸟合作筑巢的照片，体现了生物学与计算机科学的巧妙融合。印刷和制造由Caroline Fell负责，通过Courier Westford完成，同时，读者可以通过Addison-Wesley的官方网站http://www.aw-bc.com/computing获取更多关于此系列图书的最新资讯。值得注意的是，书中所提及的产品名称和商标多处使用，通常代表制造商或销售商对其产品独特的标识。在符合法律规定的前提下，这些标志被标注为全大写或首字母大写，体现了尊重知识产权的原则。书中包含的实际程序和应用程序，不仅展示了理论知识的应用，还鼓励读者动手实践，提升编程技能。整体而言，《算法设计英文版》是一部兼具理论深度与实践指导价值的权威之作，是计算机科学专业人员和高级学习者不可或缺的学习资料。"

xiv

Preface

problems out in the world. At their most effective, then, algorithmic ideas do

not just provide solutions to well-posed problems; they form the language that

lets you cleanly express the underlying questions.

The goal of our book is to convey this approach to algorithms, as a design

process that begins with problems arising across the full range of computing

applications, builds on an understanding of algorithm design techniques, and

results in the development of efﬁcient solutions to these problems. We seek

to explore the role of algorithmic ideas in computer science generally, and

relate these ideas to the range of precisely formulated problems for which we

can design and analyze algorithms. In other words, what are the underlying

issues that motivate these problems, and how did we choose these particular

ways of formulating them? How did we recognize which design principles were

appropriate in different situations?

In keeping with this, our goal is to offer advice on how to identify clean

algorithmic problem formulations in complex issues from different areas of

computing and, from this, how to design efﬁcient algorithms for the resulting

problems. Sophisticated algorithms are often best understood by reconstruct-

ing the sequence of ideas—including false starts and dead ends—that led from

simpler initial approaches to the eventual solution. The result is a style of ex-

position that does not take the most direct route from problem statement to

algorithm, but we feel it better reﬂects the way that we and our colleagues

genuinely think about these questions.

Overview

The book is intended for students who have completed a programming-

based two-semester introductory computer science sequence (the standard

“CS1/CS2” courses) in which they have written programs that implement

basic algorithms, manipulate discrete structures such as trees and graphs, and

apply basic data structures such as arrays, lists, queues, and stacks. Since

the interface between CS1/CS2 and a ﬁrst algorithms course is not entirely

standard, we begin the book with self-contained coverage of topics that at

some institutions are familiar to students from CS1/CS2, but which at other

institutions are included in the syllabi of the ﬁrst algorithms course. This

material can thus be treated either as a review or as new material; by including

it, we hope the book can be used in a broader array of courses, and with more

ﬂexibility in the prerequisite knowledge that is assumed.

In keeping with the approach outlined above, we develop the basic algo-

rithm design techniques by drawing on problems from across many areas of

computer science and related ﬁelds. To mention a few representative examples

here, we include fairly detailed discussions of applications from systems and

networks (caching, switching, interdomain routing on the Internet), artiﬁcial

Preface

intelligence (planning, game playing, Hopﬁeld networks), computer vision

(image segmentation), data mining (change-point detection, clustering), op-

erations research (airline scheduling), and computational biology (sequence

alignment, RNA secondary structure).

The notion of computational intractability, and NP-completeness in par-

ticular, plays a large role in the book. This is consistent with how we think

about the overall process of algorithm design. Some of the time, an interest-

ing problem arising in an application area will be amenable to an efﬁcient

solution, and some of the time it will be provably NP-complete; in order to

fully address a new algorithmic problem, one should be able to explore both

of these options with equal familiarity. Since so many natural problems in

computer science are NP-complete, the development of methods to deal with

intractable problems has become a crucial issue in the study of algorithms,

and our book heavily reﬂects this theme. The discovery that a problem is NP-

complete should not be taken as the end of the story, but as an invitation to

begin looking for approximation algorithms, heuristic local search techniques,

or tractable special cases. We include extensive coverage of each of these three

approaches.

Problems and Solved Exercises

An important feature of the book is the collection of problems. Across all

chapters, the book includes over 200 problems, almost all of them developed

and class-tested in homework or exams as part of our teaching of the course

at Cornell. We view the problems as a crucial component of the book, and

they are structured in keeping with our overall approach to the material. Most

of them consist of extended verbal descriptions of a problem arising in an

application area in computer science or elsewhere out in the world, and part of

the problem is to practice what we discuss in the text: setting up the necessary

notation and formalization, designing an algorithm, and then analyzing it and

proving it correct. (We view a complete answer to one of these problems as

consisting of all these components: a fully explained algorithm, an analysis of

the running time, and a proof of correctness.) The ideas for these problems

come in large part from discussions we have had over the years with people

working in different areas, and in some cases they serve the dual purpose of

recording an interesting (though manageable) application of algorithms that

we haven’t seen written down anywhere else.

To help with the process of working on these problems, we include in

each chapter a section entitled “Solved Exercises,” where we take one or more

problems and describe how to go about formulating a solution. The discussion

devoted to each solved exercise is therefore signiﬁcantly longer than what

would be needed simply to write a complete, correct solution (in other words,

xvi

Preface

signiﬁcantly longer than what it would take to receive full credit if these were

being assigned as homework problems). Rather, as with the rest of the text,

the discussions in these sections should be viewed as trying to give a sense

of the larger process by which one might think about problems of this type,

culminating in the speciﬁcation of a precise solution.

It is worth mentioning two points concerning the use of these problems

as homework in a course. First, the problems are sequenced roughly in order

of increasing difﬁculty, but this is only an approximate guide and we advise

against placing too much weight on it: since the bulk of the problems were

designed as homework for our undergraduate class, large subsets of the

problems in each chapter are really closely comparable in terms of difﬁculty.

Second, aside from the lowest-numbered ones, the problems are designed to

involve some investment of time, both to relate the problem description to the

algorithmic techniques in the chapter, and then to actually design the necessary

algorithm. In our undergraduate class, we have tended to assign roughly three

of these problems per week.

Pedagogical Features and Supplements

In addition to the problems and solved exercises, the book has a number of

further pedagogical features, as well as additional supplements to facilitate its

use for teaching.

As noted earlier, a large number of the sections in the book are devoted

to the formulation of an algorithmic problem—including its background and

underlying motivation—and the design and analysis of an algorithm for this

problem. To reﬂect this style, these sections are consistently structured around

a sequence of subsections: “The Problem,” where the problem is described

and a precise formulation is worked out; “Designing the Algorithm,” where

the appropriate design technique is employed to develop an algorithm; and

“Analyzing the Algorithm,” which proves properties of the algorithm and

analyzes its efﬁciency. These subsections are highlighted in the text with an

icon depicting a feather. In cases where extensions to the problem or further

analysis of the algorithm is pursued, there are additional subsections devoted

to these issues. The goal of this structure is to offer a relatively uniform style

of presentation that moves from the initial discussion of a problem arising in a

computing application through to the detailed analysis of a method to solve it.

A number of supplements are available in support of the book itself. An

instructor’s manual works through all the problems, providing full solutions to

each. A set of lecture slides, developed by Kevin Wayne of Princeton University,

is also available; these slides follow the order of the book’s sections and can

thus be used as the foundation for lectures in a course based on the book. These

ﬁles are available at www.aw.com. For instructions on obtaining a professor

Preface

xvii

contact your local Addison-Wesley representative.

Finally, we would appreciate receiving feedback on the book. In particular,

as in any book of this length, there are undoubtedly errors that have remained

in the ﬁnal version. Comments and reports of errors can be sent to us by e-mail,

at the address algbook@cs.cornell.edu; please include the word “feedback”

in the subject line of the message.

Chapter-by-Chapter Synopsis

Chapter 1 starts by introducing some representative algorithmic problems. We

begin immediately with the Stable Matching Problem, since we feel it sets

up the basic issues in algorithm design more concretely and more elegantly

than any abstract discussion could: stable matching is motivated by a natural

though complex real-world issue, from which one can abstract an interesting

problem statement and a surprisingly effective algorithm to solve this problem.

The remainder of Chapter 1 discusses a list of ﬁve “representative problems”

that foreshadow topics from the remainder of the course. These ﬁve problems

are interrelated in the sense that they are all variations and/or special cases

of the Independent Set Problem; but one is solvable by a greedy algorithm,

one by dynamic programming, one by network ﬂow, one (the Independent

Set Problem itself) is NP-complete, and one is PSPACE-complete. The fact that

closely related problems can vary greatly in complexity is an important theme

of the book, and these ﬁve problems serve as milestones that reappear as the

book progresses.

Chapters 2 and 3 cover the interface to the CS1/CS2 course sequence

mentioned earlier. Chapter 2 introduces the key mathematical deﬁnitions and

notations used for analyzing algorithms, as well as the motivating principles

behind them. It begins with an informal overview of what it means for a prob-

lem to be computationally tractable, together with the concept of polynomial

time as a formal notion of efﬁciency. It then discusses growth rates of func-

tions and asymptotic analysis more formally, and offers a guide to commonly

occurring functions in algorithm analysis, together with standard applications

in which they arise. Chapter 3 covers the basic deﬁnitions and algorithmic

primitives needed for working with graphs, which are central to so many of

the problems in the book. A number of basic graph algorithms are often im-

plemented by students late in the CS1/CS2 course sequence, but it is valuable

to present the material here in a broader algorithm design context. In par-

ticular, we discuss basic graph deﬁnitions, graph traversal techniques such

as breadth-ﬁrst search and depth-ﬁrst search, and directed graph concepts

including strong connectivity and topological ordering.

xviii

Preface

Chapters 2 and 3 also present many of the basic data structures that will

be used for implementing algorithms throughout the book; more advanced

data structures are presented in subsequent chapters. Our approach to data

structures is to introduce them as they are needed for the implementation of

the algorithms being developed in the book. Thus, although many of the data

structures covered here will be familiar to students from the CS1/CS2 sequence,

our focus is on these data structures in the broader context of algorithm design

and analysis.

Chapters 4 through 7 cover four major algorithm design techniques: greedy

algorithms, divide and conquer, dynamic programming, and network ﬂow.

With greedy algorithms, the challenge is to recognize when they work and

when they don’t; our coverage of this topic is centered around a way of clas-

sifying the kinds of arguments used to prove greedy algorithms correct. This

chapter concludes with some of the main applications of greedy algorithms,

for shortest paths, undirected and directed spanning trees, clustering, and

compression. For divide and conquer, we begin with a discussion of strategies

for solving recurrence relations as bounds on running times; we then show

how familiarity with these recurrences can guide the design of algorithms that

improve over straightforward approaches to a number of basic problems, in-

cluding the comparison of rankings, the computation of closest pairs of points

in the plane, and the Fast Fourier Transform. Next we develop dynamic pro-

gramming by starting with the recursive intuition behind it, and subsequently

building up more and more expressive recurrence formulations through appli-

cations in which they naturally arise. This chapter concludes with extended

discussions of the dynamic programming approach to two fundamental prob-

lems: sequence alignment, with applications in computational biology; and

shortest paths in graphs, with connections to Internet routing protocols. Fi-

nally, we cover algorithms for network ﬂow problems, devoting much of our

focus in this chapter to discussing a large array of different ﬂow applications.

To the extent that network ﬂow is covered in algorithms courses, students are

often left without an appreciation for the wide range of problems to which it

can be applied; we try to do justice to its versatility by presenting applications

to load balancing, scheduling, image segmentation, and a number of other

problems.

Chapters 8 and 9 cover computational intractability. We devote most of

our attention to NP-completeness, organizing the basic NP-complete problems

thematically to help students recognize candidates for reductions when they

encounter new problems. We build up to some fairly complex proofs of NP-

completeness, with guidance on how one goes about constructing a difﬁcult

reduction. We also consider types of computational hardness beyond NP-

completeness, particularly through the topic of PSPACE-completeness. We

剩余863页未读，继续阅读

月珑

粉丝: 0
资源: 1

英文版算法设计参考书：深入理解数据结构后的学习宝典

英文版算法设计 作者: [美]克菜因伯格 / 塔多斯

算法设计（英文文字版）by Jon_Kleinberg & Eva_Tardos

Algorithms,《算法》第四版 英文版

分布式算法导论 英文 pdf

算法导论英文版pdf第四版

算法导论 第二版 英文版 pdf

写一下输入一行字符，分别统计出其中英文字母、数字和其它字符的个数，采用指针操作完成上述工作的算法设计思路和必要的算法流程图，界面设计说明，使用模块及变量的说明

python算法学习资料

用Java语言使用Trie树实现T9键盘的算法设计代码

ACM算法自学推荐书目

最新资源

英文版算法设计作者: [美]克菜因伯格 / 塔多斯

Algorithms,《算法》第四版英文版

分布式算法导论英文 pdf

算法导论第二版英文版 pdf