算法教程：基础与实践 - Jeff Erickson 草稿

4星 · 超过85%的资源需积分: 10 130 浏览量更新于2024-07-17 收藏 9.4MB PDF 举报

"《算法教程 - Jeff Erickson》是一本由美国伊利诺伊大学香槟分校教授Jeff Erickson编写的权威教材，源自他多年为该大学算法课程所准备的课堂讲稿。自1999年起，这些讲稿每年都会被更新和教授，随着本科教育的理论课程改革，Erickson在2016年对其笔记进行了大幅度的修订，将部分内容汇集成这本书，重点展示了初级理论课程中核心的算法内容。该教材涵盖了广泛的算法基础知识，适合计算机科学入门者和高级学习者深入理解。这本书的最新预印版日期为2018年12月29日，遵循Creative Commons Attribution 4.0国际许可协议，读者可以在jeffe.cs.illinois.edu/teaching/algorithms 或 algorithms.wtf网站上免费下载，同时鼓励读者报告任何发现的错误，可以通过https://github.com/jeffgerickson/algorithms 提交反馈。章节内容丰富，从基本的排序算法、搜索算法，如冒泡排序、快速排序、二分查找，到更复杂的图论、动态规划和数据结构等，都得到了详尽的讲解。书中不仅包含了理论分析，还包含了一些编程实践，通过机械复制的方式帮助读者巩固理解和应用所学知识。作者以寓教于乐的方式引导读者，引用古人的智慧，如中世纪学者Ioannis Hispalensis（塞维利亚的约翰？）的诗句，以及Henry Home, Lord Kames在18世纪的信件，强调了书籍在理解和掌握算法中的重要性，提醒读者个人在探索过程中可能遇到的错误与合作的价值。《算法教程 - Jeff Erickson》是一本实用且深入的教材，它不仅是学习算法的基石，也是那些希望在IT领域深入发展的专业人士不可多得的参考资料。通过阅读和实践，读者可以提升算法设计和分析能力，为未来的编程生涯打下坚实的基础。"

T  C

6 Depth-First Search 223

6.1 Preorder and Postorder . . . . . . . . . . . . . . . . . . . . . . . . . 225

Classifying Vertices and Edges

6.2 Detecting Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

6.3 Topological Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230

Implicit Topological Sort

6.4 Memoization and Dynamic Programming . . . . . . . . . . . . . . 232

Dynamic Programming in Dags

6.5 Strong Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

6.6 Strong Components in Linear Time . . . . . . . . . . . . . . . . . . 236

Koraraju and Sharir’s Algorithm •

Tarjan’s Algorithm

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

7 Minimum Spanning Trees 255

7.1 Distinct Edge Weights . . . . . . . . . . . . . . . . . . . . . . . . . . 255

7.2 The Only Minimum Spanning Tree Algorithm . . . . . . . . . . . 257

7.3 Borůvka’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 259

This is the MST Algorithm You Want

7.4 Jarník’s (“Prim’s”) Algorithm . . . . . . . . . . . . . . . . . . . . . . 261

Improving Jarník’s Algorithm

7.5 Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

8 Shortest Paths 271

8.1 Shortest Path Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272

8.2

Negative Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272

8.3 The Only SSSP Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 274

8.4 Unweighted Graphs: Breadth-First Search . . . . . . . . . . . . . . 276

8.5 Directed Acyclic Graphs: Depth-First Search . . . . . . . . . . . . 280

8.6 Best-First: Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . 283

No Negative Edges •

Negative Edges

8.7 Relax ALL the Edges: Bellman-Ford . . . . . . . . . . . . . . . . . . 287

Moore’s Improvement • Dynamic Programming Formulation

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295

9 All-Pairs Shortest Paths 307

9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

9.2 Lots of Single Sources . . . . . . . . . . . . . . . . . . . . . . . . . . 308

9.3 Reweighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

9.4 Johnson’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 310

9.5 Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . 311

9.6 Divide and Conquer . . . . . . . . . . . . . . . . . . . . . . . . . . . 313

xii

Table of Contents

9.7 Funny Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . 314

9.8 (Kleene-Roy-)Floyd-Warshall(-Ingerman) . . . . . . . . . . . . . . 316

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318

10 Maximum Flows & Minimum Cuts 325

10.1 Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326

10.2 Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327

10.3 The Maxﬂow-Mincut Theorem . . . . . . . . . . . . . . . . . . . . . 329

10.4 Ford and Fulkerson’s augmenting-path algorithm . . . . . . . . . 332

Irrational Capacities

10.5 Combining and Decomposing Flows . . . . . . . . . . . . . . . . . 334

10.6 Edmonds and Karp’s Algorithms . . . . . . . . . . . . . . . . . . . . 338

Fattest Augmenting Paths • Shortest Augmenting Paths

10.7 Further Progress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342

11 Applications of Flows and Cuts 351

11.1 Edge-Disjoint Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351

11.2 Vertex Capacities and Vertex-Disjoint Paths . . . . . . . . . . . . . 352

11.3 Bipartite Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353

11.4 Tuple Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354

Exam Scheduling

11.5 Disjoint-Path Covers . . . . . . . . . . . . . . . . . . . . . . . . . . . 357

Minimal Teaching Assignment

11.6 Baseball Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . 360

11.7 Project Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365

12 NP-Hardness 377

12.1 A Game You Can’t Win . . . . . . . . . . . . . . . . . . . . . . . . . . 377

12.2 P versus NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379

12.3 NP-hard, NP-easy, and NP-complete . . . . . . . . . . . . . . . . . . 380

12.4

Formal Deﬁnitions (HC SVNT DRACONES) . . . . . . . . . . . . . 382

12.5 Reductions and Sat . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383

12.6 3Sat (from Sat) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386

12.7 Maximum Independent Set (from 3Sat) . . . . . . . . . . . . . . . 388

12.8 The General Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . 390

12.9 Clique and Vertex Cover (from Independent Set) . . . . . . . . . 391

12.10 Graph Coloring (from 3Sat) . . . . . . . . . . . . . . . . . . . . . . 392

12.11 Hamiltonian Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395

From Vertex Cover • From 3Sat • Variants and Extensions

12.12 Subset Sum (from Vertex Cover) . . . . . . . . . . . . . . . . . . . . 400

xiii

. I

(

ἄλγος

), meaning “pain”. Rather, it is a corruption of the name of the 9th century

Persian mathematician Mu

ammad ibn M

a al-Khw

arizm

ı.

Al-Khw

arizm

ı is

perhaps best known as the writer of the treatise Al-Kit

ab al-mukhta

ar f

ıh

ıs

al-ğabr

wa’l-muq

abala,

from which the modern word algebra derives. In a

diﬀerent treatise, al-Khw

arizm

ı described the modern decimal system for writing

and manipulating numbers—in particular, the use of a small circle or

ifr to

represent a missing quantity—which had been developed in India several

centuries earlier. The methods described in Al-Kit

ab, using either written ﬁgures

or counting stones, became known in English as algorism or augrym, and its

ﬁgures became known in English as ciphers.

Although both place-value notation and al-Khw

arizm

ı’s works were already

known by some European scholars, the “Hindu-Arabic” numeric system was

popularized in Europe by the medieval Italian mathematician and tradesman

Leonardo of Pisa, better known as Fibonacci. Thanks in part to his 1202 book

Liber Abaci,

written ﬁgures began to replace the counting table (then known

as an abacus) and ﬁnger arithmetic

as the preferred platform for calculation

in Europe in the 13th century—not because written decimal ﬁgures were any

easier to learn or use, but because they provided an audit trail. Ciphers became

common in Western Europe only with the advent of movable type, and truly

ubiquitous only after cheap paper became plentiful in the early 19th century.

Eventually the word algorism evolved into the modern algorithm, via folk

etymology from the Greek arithmos (and perhaps the previously mentioned

algos).

Thus, until very recently, the word algorithm referred exclusively

“Mohammad, father of Adbdulla, son of Moses, the Kw

arizmian”. Kw

arizm is an ancient

city, now called Khiva, in the Khorezm Province of Uzbekistan.

“The Compendious Book on Calculation by Completion and Balancing”

While it is tempting to translate the title Liber Abaci as “The Book of the Abacus”, a more

accurate translation is “The Book of Calculation”. Both before and after Fibonacci, the Italian

word abaco was used to describe anything related to numerical calculation—devices, methods,

schools, books, and so on—much in the same way that “computer science” is used today in

English, or as the Chinese phrase for “operations research” translates literally as “the study of

using counting rods”.

+ Reckoning with digits!

The word calculate derives from the Latin word calculus, meaning “small rock”, referring to

the stones on a counting table, or as Chaucer called them, augrym stones. In 440bc, Herodotus

wrote in his Histories (II.36) that “The Greeks write and calculate (

λογίζεσθαι ψήφοις

, literally

“reckon with pebbles”) from left to right; the Egyptians do the opposite. Yet they say that their

way of writing is toward the right, and the Greek way toward the left.” (Herodotus is strangely

silent on which end of the egg the Egyptians ate ﬁrst.)

Some medieval sources claim that the Greek preﬁx “algo-” means “art” or “introduction”.

Others claim that algorithms were invented by a Greek philosopher, or a king of India, or perhaps

a king of Spain, named “Algus” or “Algor” or “Argus”. A few, possibly including Dante Alighieri,

even identiﬁed the inventor with the mythological Greek shipbuilder and eponymous argonaut.

It’s unclear whether any of these risible claims were intended to be historically accurate, or

merely mnemonic.

剩余447页未读，继续阅读

fdtsaid

粉丝: 186
资源: 86

算法教程：基础与实践 - Jeff Erickson 草稿

Algorithms Jeff 2019最新版

Jeff Erickson算法大全

Algorithm--Jeff ERickson

如何理解快速排序算法的时间复杂度及其效率分析？请结合《算法教程：基础与实践 - Jeff Erickson 草稿》中的相关章节进行详细说明。

《算法》：Jeff Erickson的讲义汇编

《算法》(Jeff Erickson)：预发布版

UIUC Jeff Erickson教授 算法教程原版

算法英文教材——Jeff Erickson

Jeff Erickson 的算法 讲义

Jeff Erickson算法讲义及习题

最新资源

UIUC Jeff Erickson教授算法教程原版

Jeff Erickson 的算法讲义