算法设计：UCLA课程解析

需积分: 10 5 浏览量更新于2024-07-23 收藏 5.12MB PDF 举报

"《算法设计》是一本由UCLA开设的课程教材，专注于讲解算法设计的核心概念和技术。本书旨在帮助读者理解和掌握算法在计算机科学中的关键作用，以及如何设计、分析和优化这些算法以解决实际问题。教材涵盖了广泛的主题，包括数据结构、排序算法、搜索算法、动态规划、图算法等，这些都是现代IT专业人士必备的基础知识。该书由Matt Goldstein负责获取编辑工作，Maite Suarez-Rivas担任项目编辑，Marilyn Lloyd作为生产监督，确保了整个出版流程的专业性和质量。Marketing团队由Michelle Brown负责市场管理，Jake Zavracky担任营销协调，共同推广和营销这本书。项目管理方面，本书由Windfall Software进行处理。在创作上，本书采用Windfall Software的ZzT技术完成，展示了高效的协作和创新。书中包含了详尽的技术插图，由Dartmouth Publishing负责绘制，确保了理论与实践的直观结合。Carol Leyba担任文案编辑，对文字进行了精细校对，而Jennifer McClain则进行了严格的校对工作，保证了内容的准确无误。Indexer Ted Laux负责编纂索引，便于读者快速查找所需信息。封面设计由Joyce Cosentino Wells操刀，配有一张由Tim Laman拍摄的非洲织布鸟合作筑巢的国家地理照片，生动体现了合作与复杂性在算法中的象征意义。印刷和制造由Caroline Fell负责，通过Courier Westford完成了高质量的印刷工作。想要获取更多关于Addison-Wesley出版的计算机科学书籍信息，读者可以访问出版社的官方网站http://www.aw-bc.com/computing。值得注意的是，书中提及的某些产品名称和制造商标识可能被用作商标，当它们在书中出现时，表明Addison-Wesley已知并尊重这些商标权利。全书通过一系列实用的示例和练习，帮助读者不仅了解理论，还能在实践中应用所学的算法知识。整体而言，《算法设计》是一本深入浅出的教科书，是IT专业学生和从业人员学习和提升算法技能的宝贵资源。"

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页未读，继续阅读

peterzhang0506

粉丝: 0
资源: 1

算法设计：UCLA课程解析

Jon Kleinberg, Eva Tardos Algorithm Design 2005

《algorithm design》/《算法设计》的pdf版本的课件(slides)个人觉得挺有用的

algorithm design foundations analysis and internet examples 中文版

kleinberg——algorithm design课后题答案

algorithm design中文版答案

jon kleinberg and eva tardos. algorithm design答案

j. kleinberg and e. tardos. algorithm design. pearson education, 2006.

algorithm design csdn

algorithm design solution

最短路径dijkstra算法参考文献

最新资源