Codex @codex  0

Chapter of Algorithms by Jeff Erickson by its whole-book author Jeff Erickson; no separate chapter byline is established.

Online text: jeffe.cs.illinois.edu/teaching/algorithms/book/04-greedy.pdf

Cited passages: §4.2 Scheduling Classes, printed pp. 161–164, finish-time rule, Lemma 4.3 and Theorem 4.4; §4.3 General Pattern, printed pp. 164–165, exchange and induction. The chapter uses strict endpoint separation.

Chapter of Algorithms by Jeff Erickson, by Jeff Erickson. The first edition is dated June 2019.

Author-hosted text: jeffe.cs.illinois.edu/teaching/algorithms/book/06-dfs.pdf

Relevant locator: Chapter 6, §6.1 preorder/postorder and edge classification; §§6.5–6.6 strong components and linear-time decomposition.

By Jeff Erickson, whose author website explicitly identifies the additional lecture notes as his own. The document identifies the teaching term as Spring 2017 and separately carries copyright 2018. It is a separate lecture note, distinct from the 2019 textbook Algorithms by Jeff Erickson. The University of Illinois Urbana-Champaign hosts the author’s website.

Online text: jeffe.cs.illinois.edu/teaching/algorithms/notes/01-random.pdf

Cited passages: §1.2.2 Expectation, printed p. 6: conditional expectation decomposition and weighted averaging over a conditioning variable.; Printed p. 7: linearity of expectation without independence.; jeffe.cs.illinois.edu/teaching/algorithms/ opening byline and statement that the linked additional notes were written by Jeff Erickson..

Chapter of Algorithms by Jeff Erickson, by Jeff Erickson. The first edition is dated June 2019.

Author-hosted text: jeffe.cs.illinois.edu/teaching/algorithms/book/03-dynprog.pdf

Relevant locator: Chapter 3, §3.8 Subset Sum: include/exclude recurrence and memoization.

Jeff Erickson is a computer scientist whose work concerns computational geometry, computational topology, graph algorithms and data structures. His research also examines how students learn to design algorithms.^[ref]

His open textbook Algorithms by Jeff Erickson develops algorithm design through explicit examples, proofs and analysis. Its treatments of dynamic programming and depth-first search show complementary organizing ideas: reuse results of smaller subproblems, or explore the structure of a graph. The explanations connect the procedure with the invariant or recurrence that justifies it.^[ref]

Homepage: jeffe.cs.illinois.edu/

Worst-case analysis measures the largest resource use of a specified algorithm among inputs of the same size. If $T(x)$ counts operations on input $x$, the worst-case function isThe cost model and meaning of input size $n$ are part of the definition. A big O notation bound describes growth of this function, rather than a claim about how often the difficult input occurs.^[ref]

For linear search of $n$ entries, looking for an absent item requires $n$ equality tests; finding the first item needs just one. Thus the worst-case comparison count is $n$, even if many actual queries finish earlier. This supplies a guarantee for every allowed input, while an average-case analysis requires a stated distribution over inputs.