# Donald Knuth

76 results back to index

pages: 429 words: 114,726

The Computer Boys Take Over: Computers, Programmers, and the Politics of Technical Expertise by Nathan L. Ensmenger

Nicholas Metropolis, Jack Howlett, and Gian-Carlo Rota (New York: Academic Press, 1980), 125–135. 60. Frederick Brooks, The Mythical Man-Month: Essays on Software Engineering (New York: Addison-Wesley, 1975), 7. 61. Donald Ervin Knuth, The Art of Computer Programming. Addison-Wesley Series in Computer Science and Information Processing (Reading, MA: Addison-Wesley, 1968); Donald Knuth, Literate Programming (Stanford, CA: Center for the Study of Language/Information, 1992). 62. P. Mody, “Is Programming an Art?” Software Engineering Notes 17, no. 4 (1992): 19–21; Steve Lohr, Go to: The Story of the Math Majors, Bridge Players, Engineers, Chess Wizards, Maverick Scientists, and Iconoclasts—The Programmers Who Created the Software Revolution (New York: Basic Books, 2001). 63.

Technology and Culture 47 (3) (2006): 513–535. Knoebel, Robert M. “The Federal Government’s Role in the Education of Data Processing Personnel.” In SIGCPR ’67: Proceedings of the Fifth SIGCPR Conference on Computer Personnel Research, 77–84. New York: ACM Press, 1967. Knuth, Donald Ervin. The Art of Computer Programming, Volume 1: Fundamental Algorithms. Reading, MA: Addison-Wesley, 1968. Knuth, Donald Ervin. Literate Programming. Stanford, CA: Center for the Study of Language/Information, 1992. Koss, Adele Mildred. “Programming on the Univac 1.” IEEE Annals of the History of Computing 25 (1) (2003): 48–59. Kraft, Philip. Programmers and Managers: The Routinization of Computer Programming in the United States.

The seeming paradox between the inevitable progress promised by Moore’s Law and the perpetual crisis in software production challenges conventional assumptions about the progressive nature of computer technology. This is perhaps the most significant lessons to be learned from the history of software: There is no Moore’s Law for software technology. But the real problem with software is not so much that it is “hard” (as computer scientist Donald Knuth famously declared) but rather that it is inherently contested; the problem was generally not that the software itself did not work but instead that the work that it did do turned out to have undesirable side effects for the organizations that used them.23 Computerization projects created “unusual internal implications,” “placed stress on established organizational relationships,” and demanded “skills not provided by the previous experience of people assigned to the task.”24 Such projects generally crossed organizational boundaries and disrupted existing hierarchies and power relationships.

pages: 1,758 words: 342,766

Code Complete (Developer Best Practices) by Steve McConnell

Creating Effective Software: Computer Program Design Using the Jackson Methodology. New York, NY: Yourdon Press. [bib36entry269] Knuth,Donald. 1971. “"An Empirical Study of FORTRAN programs,"” Software—Practice and Experience 1:105–33. [bib36entry270] Knuth,Donald. 1974. “"Structured Programming with go to Statements."” In Classics in Software Engineering, edited by Edward Yourdon. Englewood Cliffs, NJ: Yourdon Press, 1979. [bib36entry271] Knuth,Donald. 1986. Computers and Typesetting, Volume B, TEX: The Program. Reading, MA: Addison-Wesley. [bib36entry272] Knuth,Donald. 1997a. The Art of Computer Programming, vol. 1, Fundamental Algorithms, 3d ed.

Newcomer is an experienced systems programmer who describes the various pitfalls of ineffective optimization strategies in graphic detail. Algorithms and Data Types cc2e.com/2599 Knuth, Donald. The Art of Computer Programming, vol. 1, Fundamental Algorithms, 3d ed. Reading, MA: Addison-Wesley, 1997. Knuth, Donald. The Art of Computer Programming, vol. 2, Seminumerical Algorithms, 3d ed. Reading, MA: Addison-Wesley, 1997. Knuth, Donald. The Art of Computer Programming, vol. 3, Sorting and Searching, 2d ed. Reading, MA: Addison-Wesley, 1998. These are the first three volumes of a series that was originally intended to grow to seven volumes.

The Art of Computer Programming, vol. 1, Fundamental Algorithms, 3d ed. Reading, MA: Addison-Wesley. [bib36entry273] Knuth,Donald. 1997b. The Art of Computer Programming, vol. 2, Seminumerical Algorithms, 3d ed. Reading, MA: Addison-Wesley. [bib36entry274] Knuth,Donald. 1998. The Art of Computer Programming, vol. 3, Sorting and Searching, 2d ed. Reading, MA: Addison-Wesley. [bib36entry275] Knuth,Donald. 2001. Literate Programming. Cambridge University Press. [bib36entry276] Korson,TimothyD., and VijayK.Vaishnavi. 1986. “"An Empirical Study of Modularity on Program Modifiability."” In Soloway and Iyengar 1986: 168–86. [bib36entry277] Kouchakdjian,Ara, ScottGreen, and VictorBasili. 1989.

pages: 236 words: 50,763

The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow

But one Turing Award for the P versus NP problem is not enough, and in 1985 Richard Karp received the award for his work on algorithms, most notably for the twenty-one NP-complete problems. What’s in a Name? Karp’s paper gave the names P and NP that we use today. But what should people call those hardest problems in NP? Cook called them by a technical name “deg({DNF tautologies}),” and Karp used the term “(polynomial) complete.” But these names didn’t feel right. Donald Knuth took up this cause. In 1974 Knuth received the Turing Award for his research and his monumental three-volume series, The Art of Computer Programming. For the fourth volume, Knuth, realizing the incredible importance of the P versus NP problem, wanted to settle the naming issue for the hardest sets in NP.

He truly wanted a single English world that captured the intuitive meaning of hard search problems, a term for the masses. In a 1974 wrap-up of his survey, Knuth wrote “NP-complete actually smacks of being a little too technical for a mass audience, but it’s not so bad as to be unusable.” “NP-complete” quickly became the standard terminology. It took Donald Knuth about four decades to finish volume 4. Knuth should have pushed a bit harder for less technical names for “NP-complete,” and perhaps for “P” and “NP” as well. The P versus NP problem has taken on an importance that goes well beyond computer science, and using terminology that just abbreviates a technical definition hides this import from outsiders.

* Computers and Intractability: A Guide to the Theory of NP-Completeness, by Michael Garey and David Johnson (New York: W. H. Freeman, 1979). Chapter 5 THE PREHISTORY OF P VERSUS NP One does not fear the Perebor, but rather uses it reasonably.* IN THE LAST CHAPTER WE RECOUNTED Donald Knuth’s ultimately unsuccessful attempt to find a good English word to capture NP-completeness. Knuth could have turned east to the Russians to find perebor (Перебор). Perebor means “brute force search,” the process of trying all possibilities to find the best solution. P versus NP asks whether we need perebor to solve the clique problem or whether some faster approach could work.

pages: 523 words: 143,139

Algorithms to Live By: The Computer Science of Human Decisions by Brian Christian, Tom Griffiths

And in the private sector, interrupt coalescing offers a redemptive view of one of the most maligned office rituals: the weekly meeting. Whatever their drawbacks, regularly scheduled meetings are one of our best defenses against the spontaneous interruption and the unplanned context switch. Perhaps the patron saint of the minimal-context-switching lifestyle is the legendary programmer Donald Knuth. “I do one thing at a time,” he says. “This is what computer scientists call batch processing—the alternative is swapping in and out. I don’t swap in and out.” Knuth isn’t kidding. On January 1, 2014, he embarked on “The TeX Tuneup of 2014,” in which he fixed all of the bugs that had been reported in his TeX typesetting software over the previous six years.

the record for sorting a deck of cards: While we couldn’t find a video of Bradáč’s performance, there are plenty of videos online of people trying to beat it. They tend to sort cards into the four suits, and then sort the numbers within each suit. “But there is a faster way to do the trick!” urges Donald Knuth in The Art of Computer Programming: First, deal out the cards into 13 piles based on their face value (with one pile containing all the 2s, the next all the 3s, etc.). Then, after gathering up all the piles, deal the cards out into the four suits. The result will be one pile for each suit, with the cards ordered within each.

Subsequent engineers have suggested that Bogobogosort isn’t even the bottom of the well, and have proposed getting even more meta and Bogosorting the program rather than the data: randomly flipping bits in the computer memory until it just so happens to take the form of a sorting program that sorts the items. The time bounds of such a monstrosity are still being explored. The quest for pessimality continues. Computer science has developed a shorthand: Big-O notation originated in the 1894 book Die analytische zahlentheorie by Paul Bachmann. See also Donald Knuth, The Art of Computer Programming, §1.2.11.1. Formally, we say that the runtime of an algorithm is O(f(n)) if it is less than or equal to a multiple (with a coefficient that is a positive constant) of f(n). There is also the kindred “Big-Omega” notation, with Ω(f(n)) indicating that the runtime is greater than or equal to a multiple of f(n), and “Big-Theta” notation, with Θ(f(n)) meaning the runtime is both O(f(n)) and Ω(f(n)).

pages: 1,201 words: 233,519

Coders at Work by Peter Seibel

Jamie Zawinski and Dan Ingalls emphasized the importance of getting code up and running right away while Joshua Bloch described how he designs APIs and tests whether they can support the code he wants to write against them before he does any implementation and Donald Knuth described how he wrote a complete version of his typesetting software TeX in pencil before he started typing in any code. And while Fran Allen lay much of the blame for the decline in interest in computer science in recent decades at the feet of C and Bernie Cosell called it the “biggest security problem to befall modern computers”, Ken Thompson argued that security problems are caused by programmers, not their programming languages and Donald Knuth described C's use of pointers as one of the “most amazing improvements in notation” he's seen.

This is a good time to be an over-the-hill programmer emeritus, because you have a few props because you did it once, but the world is so wondrous that you can take advantage of it, maybe even get a little occasional credit for it without having to still be able to do it. Whereas if you were in college—if you major in computer science and you have to go out there and you have to figure out how you are going to add to this pile of stuff—save me. Donald Knuth Of all the subjects of this book, Donald Knuth perhaps least needs an introduction. For the past four decades he has been at work on his multivolume masterwork The Art of Computer Programming, the bible of fundamental algorithms and data structures, which American Scientist included on its list of the top 12 physical-sciences monographs of the century, in the company of works by Russell and Whitehead, Einstein, Dirac, Feynman, and von Neumann.

Guide to LaTeX by Helmut Kopka, Patrick W. Daly

For bibliographies with author–year citations (Section 9.3.4) the entries in the thebibliography are the same, except that the optional label must be present, taking a special form that will transfer the author and year texts to the citation commands. A sample (numerical) thebibliography environment could look as follows: \begin{thebibliography}{99} \bibitem{lamport} Leslie Lamport. \textsl{\LaTeX\ -- A Document Preparation System}, 2nd edition. Addison-Wesley, Reading, MA, 1994 . . . . . . . . . \bibitem{knuth} Donald E. Knuth. \textsl{Computers and Typesetting Vol.\ A--E}. Addison-Wesley, Reading, MA, 1986 \bibitem[6a]{knuth:a} Vol A: \textsl{The {\TeX}book}, 1986 . . . . . . . . . \bibitem[6e]{knuth:e} Vol E: \textsl{Computer Modern Typefaces}, 1986 \end{thebibliography} Here lamport, knuth, and knuth:a have been chosen as keys.

In fact, we feel that even for a single document, it is simpler to make an entry into the database than to adhere to the very precise and fiddly requirements of a literature list, especially regarding punctuation and positioning of the authors’ initials. The database entry proceeds very quickly and easily if one has a generalized template, as illustrated in Section 14.2.6. The entries in a bibliographic database are of the form @BOOK{knuth:86a, AUTHOR = "Donald E. Knuth", TITLE = {The \TeX{}book}, EDITION = "third", PUBLISHER = "Addison--Wesley", ADDRESS = {Reading, Massachusetts}, YEAR = 1986 } The first word, prefixed with @, determines the entry type, as explained in the next section. The entry type is followed by the reference information for that entry enclosed in curly braces { }.

In the next Section we outline the development of TEX and LATEX, and go on to show that LATEX, a product of the mid 1980’s, is a programmable markup language that is ideally suited for the modern world of electronic publishing. 6 Chapter 1. Introduction 1.3 TEX and its offspring The most powerful formatting program for producing book quality text of scientific and technical works is that of Donald E. Knuth (Knuth, 1986a, 1986b, 1986c, 1986d, 1986e). The program is called TEX, which is a rendering in capitals of the Greek letters τχ. For this reason the last letter is pronounced not as an x, but as the ch in Scottish loch or German ach, or as the Spanish j or Russian kh. The name is meant to emphasize that the printing of mathematical texts is an integral part of the program and not a cumbersome add-on.

Speaking Code: Coding as Aesthetic and Political Expression by Geoff Cox, Alex McLean

Nevertheless, there is more to coding than simply the demonstration of formal logic, as if everything could be reduced to binary representation at a fundamental level. The conventions of writing and reading, of both text and code, might be considered to be part of coded systems of input and output (abbreviated as I/0), and yet formal logic fails to break the apparent paradox of language. In The Art of Computer Programming (1968), Donald Knuth already emphasized the depth of the relationship between writing a computer program and the logic that underpins it— what he referred to as “literate programming”—and so acknowledged programming to be somewhat like composing poetry or music.28 He also demonstrated how reading could be understood as procedural and reflexive in his “Procedures for Reading This Set of Books.”

(Available at http://www.electronicbookreview.com/thread/electropoetics/codology? mode=print.) 26. Piet is an esoteric programming language written by David Morgan-Mar. His explanation of the Piet “Hello world!” program is available at http://www.retas.de/thomas/computer/programs/ useless/piet/explain.html. Notes to Pages 7–12 113 27. Kittler, “Code,” 46. 28. Donald Knuth, The Art of Computer Programming, vol. 1, Fundamental Algorithms (Reading, MA: Addison-Wesley, 1981), v. 29. Ibid., xv–xvi. 30. N. Katherine Hayles, Writing Machines (Cambridge, MA: MIT Press, 2002), 25. 31. Roland Barthes, “The Death of the Author,” in Image, Music, Text (London: Fontana, 1977), 142–148. 32.

InformatikerInnen für eine andere Informatik, 34–44. Bonn: FIfF, 1991. Kittler, Friedrich. “There Is No Software.” In Timothy Druckrey, ed., Electronic Culture, 331–337. New York: Aperture, 1996. Kleiner, Dmytri. The Telekommunist Manifesto. Network Notebooks 03. Amsterdam: Institute of Network Cultures, 2010. Knuth, Donald. The Art of Computer Programming. Vol. 1, Fundamental Algorithms. Reading, MA: Addison-Wesley, 1981. Lakoff, George, and Mark Johnson. Philosophy in the Flesh: The Embodied Mind and Its Challenge to Western Thought. New York: HarperCollins, 1999. Laporte, Dominique. History of Shit. Cambridge, MA: MIT Press, 2000.

pages: 255 words: 76,834

Creative Selection: Inside Apple's Design Process During the Golden Age of Steve Jobs by Ken Kocienda

So, did Edison really talk about his working method exactly as we say that he did? I don’t know, but posterity seems to be voting in the affirmative, and by using this quotation again myself, I realize I’m just adding another log onto the fire. 4. One Simple Rule 1. Donald E. Knuth, The Art of Computer Programming (Boston: Addison-Wesley, various years). 2. Donald Knuth, “Structured Programming with go to Statements,” ACM Computing Surveys 6, no. 4 (1974): 261–301. I love how Knuth’s famous statement on optimization comes in an article that references one of the other most famous statements in computer science, that from the age of “structured programming,” the assertion made by E.

When an essential bit of new code caused a slowdown, things could get tricky. Finding remedies for speed setbacks typically involved the prickly issue of software optimization, and that term warrants some explanation. * * * There aren’t many famous computer scientists, even among programmers, but Donald Knuth is rightly revered. He is the author of The Art of Computer Programming, one of the foundational texts of computer science, a multivolume treatise that he’s been writing, with something approximating monklike asceticism and devotion, since 1962.1 Knuth undertakes meticulous research, writes with extreme care, and issues publications with titles like Introduction to Combinatorial Algorithms and Boolean Functions, Bitwise Tricks & Techniques; Binary Decision Diagrams, and Generating All Trees—History of Combinatorial Generation.

I can use Kant, but only if I know about him, and only to the extent that I’ve internalized what he said and what it means to me. The same goes for the whole scope of creative achievement, from the paintings of Frida Kahlo, the blues music of the Reverend Gary Davis, the theories of Charles Darwin, the philosophy of Lao Tzu, the software optimization ideas of Donald Knuth, or the beliefs and practices of the ancient Greek visitors to the Delphic Oracle. When I study the past, I make a point of deciding what I like, and sometimes this built-up catalog of refined-like responses about past works finds a suitable outlet and a natural expression in my present-day work.

pages: 394 words: 118,929

Dreaming in Code: Two Dozen Programmers, Three Years, 4,732 Bugs, and One Quest for Transcendent Software by Scott Rosenberg

“I think we need to be ashamed” and “Everything we’ve done”: Richard Gabriel talk at the Software Development Forum, Palo Alto, California, January 23, 2003. “art meant something devised” and “The chief goal of my work”: Donald Knuth, “Computer Programming as an Art,” 1974 Turing Award lecture, in Communications of the ACM, December 1974. “couldn’t stand to write books”: Donald Knuth quoted in Steve Ditlea, “Rewriting the Bible in 0’s and 1’s,” Technology Review, September–October1999. “Beware of bugs in the above code”: Knuth explains the exact origins of the much-cited quote at http://www-cs-faculty.stanford.edu/~knuth/faq.htm. “What were the lessons I learned”: Donald Knuth, Selected Papers on Computer Science (CSLI Publicational/Cambridge University Press, 1996), p. 161.

CONTENTS TITLE PAGE DEDICATION EPIGRAPH AUTHOR’S NOTE CHAPTER 0 SOFTWARE TIME [1975–2000] CHAPTER 1 DOOMED [JULY 2003] CHAPTER 2 THE SOUL OF AGENDA [1968–2001] CHAPTER 3 PROTOTYPES AND PYTHON [2001–NOVEMBER 2002] CHAPTER 4 LEGO LAND [NOVEMBER 2002–AUGUST 2003] CHAPTER 5 MANAGING DOGS AND GEEKS [APRIL–AUGUST 2003] CHAPTER 6 GETTING DESIGN DONE [JULY–NOVEMBER 2003] CHAPTER 7 DETAIL VIEW [JANUARY–MAY 2004] CHAPTER 8 STICKIES ON A WHITEBOARD [JUNE–OCTOBER 2004] CHAPTER 9 METHODS CHAPTER 10 ENGINEERS AND ARTISTS CHAPTER 11 THE ROAD TO DOGFOOD [NOVEMBER 2004–NOVEMBER 2005] EPILOGUE A LONG BET [2005–2029 AND BEYOND] NOTES ACKNOWLEDGMENTS ABOUT THE AUTHOR COPYRIGHT For my parents Software is hard. —Donald Knuth, author of The Art of Computer Programming AUTHOR’S NOTE The shelves of the world are full of how-to books for software developers. This is not one of them. I’m barely an elementary programmer myself. I wouldn’t presume to try to teach the experts. And if my research had uncovered some previously unknown innovation or fail-safe insight into building better software, I’d be smarter to seek investors, not readers.

Could some radical breakthrough be right around the corner? Or is there something at the root of what software is, its abstractness and intricateness and malleability, that dooms its makers to a world of intractable delays and ineradicable bugs—some instability or fickleness that will always let us down? “Software is hard,” wrote Donald Knuth, author of the programming field’s most respected textbooks. But why? Maybe you noticed that I’ve called this Chapter 0. I did not mean to make an eccentric joke but, rather, to tip my hat to one small difference between computer programmers and the rest of us: Programmers count from zero, not from one.

pages: 450 words: 569

ANSI Common LISP by Paul Graham

If this were inconvenient, you could use the following read-macro instead: 409 NOTES (defvar *symtab* (make-hash-table :test #'equal)) (defun pseudo-intern (name) (or (gethash name *symtab*) (setf (gethash name *symtab*) (gensym)))) (set-dispatch-macro-character #\# #$#'(lambda (stream charl char2) (do ((ace nil (cons char ace)) (char (read-char stream) (read-char stream))) ((eql char #$) (pseudo-intern ace))))) Then it would be possible to say just: (defclass counter () ((#[state] rinitform 0))) (defmethod increment ((c counter)) (incf (slot-value c '#[state]))) (defmethod clear ((c counter)) (setf ( s l o t - v a l u e c ' # [ s t a t e ] ) 0)) 204 The following macro pushes new elements into binary search trees: (defmacro bst-push (obj bst <) (multiple-value-bind (vars forms var s e t access) (get-setf-expansion bst) ( l e t ((g (gensym))) ' ( l e t * ( ( , g ,obj) ,®(mapcar # ' l i s t vars forms) ( , ( c a r var) ( b s t - i n s e r t ! ,g ,access , < ) ) ) ,set)))) 213 Knuth, Donald E. Structured Programming with goto Statements. Computing Surveys, 6:4 (December 1974), pp. 261-301. 214 Knuth, Donald E. Computer Programming as an Art. In ACM Turing Award Lectures: The First Twenty Years. ACM Press, 1987. This paper and the preceding one are reprinted in: Knuth, Donald E. Literate Programming. CSLI Lecture Notes #27, Stanford University Center for the Study of Language and Information, Palo Alto, 1992. 216 Steele, Guy L., Jr.

I'm glad to have had the chance to work with Alan Apt again. The people at Prentice Hall—Alan, Mona Pompili, Shirley McGuire, and Shirley Michaels—are really a pleasure to work with. The cover is again the work of the incomparable Gino Lee, of the Bow & Arrow Press, Cambridge. This book was typeset using L^TgX, a language written by Leslie Lamport atop Donald Knuth's Tj3C, with additional macros by L. A. Carr, Van Jacobson, and Guy Steele. The diagrams were done with Idraw, by John Vlissides and Scott Stanton. The whole was previewed with Ghostview, by Tim Theisen, which is built on Ghostscript, by L. Peter Deutsch. I owe thanks to many others, including Henry Baker, Kim Barrett, Ingrid Bassett, Trevor Blackwell, Paul Becker, Gary Bisbee, Frank Deutschmann, Frances Dickey, Rich and Scott Draves, Bill Dubuque, Dan Friedman, Jenny X PREFACE Graham, Alice Hartley, David Hendler, Mike Hewett, Glenn Holloway, Brad Karp, Sonya Keene, Ross Knights, Mutsumi Komuro, Steffi Kutzia, David Kuznick, Madi Lord, Julie Mallozzi, Paul McNamee, Dave Moon, Howard Mullings, Mark Nitzberg, Nancy Parmet and her family, Robert Penny, Mike Plusch, Cheryl Sacks, Hazem Sayed, Shannon Spires, Lou Steinberg, Paul Stoddard, John Stone, Guy Steele, Steve Strassmann, Jim Veitch, Dave Watkins, Idelle and Julian Weber, the Weickers, Dave Yost, and Alan Yuille.

I owe thanks to many others, including Henry Baker, Kim Barrett, Ingrid Bassett, Trevor Blackwell, Paul Becker, Gary Bisbee, Frank Deutschmann, Frances Dickey, Rich and Scott Draves, Bill Dubuque, Dan Friedman, Jenny X PREFACE Graham, Alice Hartley, David Hendler, Mike Hewett, Glenn Holloway, Brad Karp, Sonya Keene, Ross Knights, Mutsumi Komuro, Steffi Kutzia, David Kuznick, Madi Lord, Julie Mallozzi, Paul McNamee, Dave Moon, Howard Mullings, Mark Nitzberg, Nancy Parmet and her family, Robert Penny, Mike Plusch, Cheryl Sacks, Hazem Sayed, Shannon Spires, Lou Steinberg, Paul Stoddard, John Stone, Guy Steele, Steve Strassmann, Jim Veitch, Dave Watkins, Idelle and Julian Weber, the Weickers, Dave Yost, and Alan Yuille. Most of all, I'd like to thank my parents, and Jackie. Donald Knuth called his classic series The Art of Computer Programming. In his Turing Award Lecture, he explained that this title was a conscious choice—that what drew him to programming was "the possibility of writing beautiful programs." Like architecture, programming has elements of both art and science.

pages: 239 words: 64,812

Geek Sublime: The Beauty of Code, the Code of Beauty by Vikram Chandra

Formal languages “contrast with natural languages such as English whose rules, evolving as they do with use, fall short of being either a complete or a precise definition of the syntax, much less the semantics, of the language.”6 So these formal dialects may be less flexible and less forgiving of ambiguity than natural languages, but coders—like poets—manipulate linguistic structures and tropes, search for expressivity and clarity. While a piece of code may pass instructions to a computer, its real audience, its readers, are the programmers who will add features and remove bugs in the days and years after the code is first created. Donald Knuth is the author of the revered magnum opus on computer algorithms and data structures, The Art of Computer Programming. Volume 3 of the Art was published in 1973; the first part of Volume 4 appeared in 2011, the next part is “under preparation.” If ever there was a person who fluently spoke the native idiom of machines, it is Knuth, computing’s great living sage.

The snarl in the dependency diagram (figure 6.1) may strike the civilian as a pretty picture, with its swirl of lines and punctuating sparks of gray; to the programmer, it is an abomination because it speaks of incoherence, incomprehensibility, unpredictability, sticky seams of connection that prevent swift diagnosis and make excision and replacement all but impossible. With his emphasis on programmer happiness, Matz makes explicit his allegiance to Donald Knuth’s literate programming. He writes: Programs share some attributes with essays. For essays, the most important question readers ask is, “What is it about?” For programs, the main question is, “What does it do?” In fact, the purpose should be sufficiently clear that neither question ever needs to be uttered … Both essays and lines of code are meant—before all else—to be read and understood by human beings.3 The trouble of course is that as software programs grow bigger and more complex, the code they comprise tends to become unreadable and incomprehensible to human beings.

Programmers like to point out that if each line of code, or even each logical statement (which may spread to more than one physical line), is understood to be a component, software systems are the most complicated things that humans have ever built: the Lucent 5ESS switch, used in telephone exchanges, derives its functionality from a hundred million lines of code; the 2008 Fedora 9 distribution of Linux comprises over two hundred million lines of code.4 No temple, no cathedral has ever contained as many moving parts. So if you’ve ever written code, you understand in your bones the truth of Donald Knuth’s assertion, “Software is hard. It’s harder than anything else I’ve ever had to do.”5 If you’ve ever written code, the fact that so much software works so much of the time can seem profoundly miraculous. Software is complicated because it tries to model the irreducible complexity of the world.

pages: 351 words: 123,876

Beautiful Testing: Leading Professionals Reveal How They Improve Software (Theory in Practice) by Adam Goucher, Tim Riley

If there are too few buckets, the test is not very demanding and errors could go undetected. On the other hand, if there are too many buckets, then we do not expect to find many samples in each bucket and the theoretical requirements of the test are not met. A common rule of thumb is that the expected number of samples in ‖ Knuth, Donald E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1998. 138 CHAPTER TEN each bucket should be at least five.# This is no problem because we are generating our data rather than collecting it. We can determine our number of buckets first, then choose the number of samples n so large that we expect well more than five samples in each bucket.

The counts in each bucket would not be affected by such a bug, and if the generator were otherwise correct, the bucket test would pass most of the time. We would like a more fine-grained test of how the random samples are distributed. Here’s one way to proceed. Take a large number of samples n. For each sample xi we can compare the actual proportion of samples less than xi to the proportion of samples we would expect to have # Knuth, Donald E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1998. * In case you’re curious: xi = tan(π(0.1 i − 0.5)). TESTING A RANDOM NUMBER GENERATOR 139 seen. In other words, we will compare the empirical distribution function with the theoretical distribution function.

We’re going to pull a rabbit out of the hat and give range values without saying where they came from. For large n, we expect K+ to be between 0.07089 and 1.5174 around 98% of the time. How large does n need to be for this to hold? Values of n that you would want to use for testing, say n = 1,000, are more than big enough. Donald Knuth’s book gives more details concerning the K-S test, such as an explanation of where the range values come from and how to find your own values based on how often you want the test to pass. If the K-S test usually passes, this is strong evidence that the transformation from uniform to nonuniform random values was implemented correctly.

Deep Work: Rules for Focused Success in a Distracted World by Cal Newport

But supporting this decision with the strategies that follow—or strategies of your own devising that are motivated by the same principles—will significantly increase the probability that you succeed in making deep work a crucial part of your professional life. Decide on Your Depth Philosophy The famed computer scientist Donald Knuth cares about deep work. As he explains on his website: “What I do takes long hours of studying and uninterruptible concentration.” A doctoral candidate named Brian Chappell, who is a father with a full-time job, also values deep work, as it’s the only way he can make progress on his dissertation given his limited time.

This strategy will help you avoid this fate by presenting four different depth philosophies that I’ve seen work exceptionally well in practice. The goal is to convince you that there are many different ways to integrate deep work into your schedule, and it’s therefore worth taking the time to find an approach that makes sense for you. The Monastic Philosophy of Deep Work Scheduling Let’s return to Donald Knuth. He’s famous for many innovations in computer science, including, notably, the development of a rigorous approach to analyzing algorithm performance. Among his peers, however, Knuth also maintains an aura of infamy for his approach to electronic communication. If you visit Knuth’s website at Stanford with the intention of finding his e-mail address, you’ll instead discover the following note: I have been a happy man ever since January 1, 1990, when I no longer had an email address.

These efforts, I argued, were aimed at increasing the intensity of Jung’s deep work to a level that would allow him to succeed in intellectual combat with Freud and his many supporters. In recalling this story I want to emphasize something important: Jung did not deploy a monastic approach to deep work. Donald Knuth and Neal Stephenson, our examples from earlier, attempted to completely eliminate distraction and shallowness from their professional lives. Jung, by contrast, sought this elimination only during the periods he spent at his retreat. The rest of Jung’s time was spent in Zurich, where his life was anything but monastic: He ran a busy clinical practice that often had him seeing patients until late at night; he was an active participant in the Zurich coffeehouse culture; and he gave and attended many lectures in the city’s respected universities.

pages: 509 words: 92,141

The Pragmatic Programmer by Andrew Hunt, Dave Thomas

Aspect-oriented programming. In European Conference on Object-Oriented Programming (ECOOP), volume LNCS 1241. Springer-Verlag, June 1997. [Knu97a] Donald Ervin Knuth. The Art of Computer Programming: Fundamental Algorithms, volume 1. Addison Wesley Longman, Reading, MA, third edition, 1997. [Knu97b] Donald Ervin Knuth. The Art of Computer Programming: Seminumerical Algorithms, volume 2. Addison Wesley Longman, Reading, MA, third edition, 1997. [Knu98] Donald Ervin Knuth. The Art of Computer Programming: Sorting and Searching, volume 3. Addison Wesley Longman, Reading, MA, second edition, 1998. [KP99] Brian W.

Related sections include: Estimating, page 64 Challenges Every developer should have a feel for how algorithms are designed and analyzed. Robert Sedgewick has written a series of accessible books on the subject ([Sed83, SF96, Sed92] and others). We recommend adding one of his books to your collection, and making a point of reading it. For those who like more detail than Sedgewick provides, read Donald Knuth's definitive Art of Computer Programming books, which analyze a wide range of algorithms [Knu97a, Knu97b, Knu98]. In Exercise 34, we look at sorting arrays of long integers. What is the impact if the keys are more complex, and the overhead of key comparison is high? Does the key structure affect the efficiency of the sort algorithms, or is the fastest sort always fastest?

Pragmatic Programmers embrace documentation as an integral part of the overall development process. Writing documentation can be made easier by not duplicating effort or wasting time, and by keeping documentation close at hand—in the code itself, if possible. These aren't exactly original or novel thoughts; the idea of wedding code and documentation appears in Donald Knuth's work on literate programming and in Sun's JavaDoc utility, among others. We want to downplay the dichotomy between code and documentation, and instead treat them as two views of the same model (see It's Just a View, page 157). In fact, we want to go a little further and apply all of our pragmatic principles to documentation as well as to code.

pages: 394 words: 108,215

What the Dormouse Said: How the Sixties Counterculture Shaped the Personal Computer Industry by John Markoff

SAIL research also led to a wave of AI startups in the late seventies and early eighties. Ultimately, the dream of AI went unrealized, but SAIL nurtured an eclectic group of computer hackers who passed through before going on in a computing diaspora that eventually was every bit as influential as the later scattering from Xerox PARC. During the evenings, Donald Knuth, a Stanford computer scientist who invented several of the field’s most important algorithms, would show up to use the SAIL computer along with other hackers. Knuth eventually wrote The Art of Computer Programming, the definitive text in the field. Years later, after becoming annoyed with the declining quality of the typesetting in the production of math books, he designed an advanced text-formatting language called TeX.

There was just one small problem: Lehtman knew almost nothing about computers. The visit ended inconclusively, but the computing bug had bitten Lehtman. He discovered a new program that was being started at UCSD in physics and information. He entered the graduate school and was given the responsibility for teaching a computer-science course. Since Donald Knuth’s first volume of The Art of Computer Programming had recently been published, he got a copy and throughout the quarter managed to keep barely ahead of everyone in the class. During the summer of 1969 he called Bill English and told him, “I know about computers now.” He arrived as a summer intern and then came to work full-time the next year.

Designing simple electronic circuits grew into a captivating hobby, and upon graduating from Harvard, Ingalls, remembering a childhood visit, decided to head for California’s beaches and Stanford University. Once at Stanford, his passion for hardware cooled a bit, and he began spending more and more time trying to pursue the softer side of computing. He took a colloquium taught by Donald Knuth, the Stanford computer scientist who spent his evenings hacking at SAIL. The Knuth course explored program optimization, the craft of speeding software performance. It opened new vistas for Ingalls, who became deft at designing programs called optimizers—software that would overcome bottlenecks in programs that were inefficient.

pages: 285 words: 86,853

What Algorithms Want: Imagination in the Age of Computing by Ed Finn

That is to say, an algorithm reliably delivers an expected result within a finite amount of time (except, perhaps, for those edge cases that fascinate mathematicians and annoy engineers). Historian Nathan Ensmenger recounts how the academic discipline of computer science coalesced only after its advocates embraced the concept of the algorithm, with one of the field’s founders, Donald Knuth, tracing the field’s origins to al-Khwarizmi in his seminal textbook The Art of Computer Programming.6 The algorithm was an ideal object of study, both easily grasped and endlessly puzzling: By suggesting that the algorithm was as fundamental to the technical activity of computing as Sir Isaac Newton’s laws of motion were to physics, Knuth and his fellow computer scientists could claim full fellowship with the larger community of scientists.7 And yet, as mathematician Yiannis Moschovakis points out, Knuth’s argument about what algorithms actually are is an extremely rare instance where the question is foregrounded.8 For computer scientists the term remains more of an intuitive, unexamined notion than a delineated logical concept grounded in a mathematical theory of computation.

The Huffington Post, March 5, 2015. http://www.huffingtonpost.com/2015/03/05/tip-uber-driver_n_6810296.html. Kline, Ronald R. The Cybernetics Moment: Or Why We Call Our Age the Information Age. Johns Hopkins University Press, 2015. Knack, Ruth Eckdish. “Pay As You Park.” Planning Magazine, May 2005. http://shoup.bol.ucla.edu/PayAsYouPark.htm. Knuth, Donald E. “Ancient Babylonian Algorithms.” Communications of the ACM 15 (7) (July 1972): 671–677. doi:10.1145/361454.361514. Kolbe, Winrich, director. “Evolution.” Star Trek: The Next Generation, September 23, 1989. http://www.imdb.com/title/tt0708710. Kosner, Anthony Wing. “Facebook Is Recycling Your Likes to Promote Stories You’ve Never Seen to All Your Friends.”

Algorithms Unlocked by Thomas H. Cormen

[KL08] Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography. Chapman & Hall/CRC, 2008. [Knu97] Donald E. Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley, third edition, 1997. [Knu98a] Donald E. Knuth. The Art of Computer Programming, Volume 2: Seminumeral Algorithms. Addison-Wesley, third edition, 1998. [Knu98b] Donald E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, second edition, 1998. [Knu11] Donald E. Knuth. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part I. Addison-Wesley, 2011.

MacCormick’s treatment is less technical than this book. If you find that my approach in this book is too mathematical, then I recommend that you try reading MacCormick’s book. You should be able to follow much of it even if you have a meager mathematical background. In the unlikely event that you find CLRS too watered down, you can try Donald Knuth’s multi-volume set The Art of Computer Programming [Knu97, Knu98a, Knu98b, Knu11]. Although the title of the series makes it sound like it might focus on details of writing code, these books Chapter 1: What Are Algorithms and Why Should You Care? 9 contain brilliant, in-depth analyses of algorithms.

Design Patterns: Elements of Reusable Object-Oriented Software (Joanne Romanovich's Library) by Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides

ACM Press. [JZ91] Ralph E. Johnson and Jonathan Zweig. Delegation in C++. Journal of Object-Oriented Programming, 4(11):22-35, November 1991. [Kir92] David Kirk. Graphics Gems III. Harcourt, Brace, Jovanovich, Boston, MA, 1992. [Knu73] Donald E. Knuth. The Art of Computer Programming, Volumes 1, 2, and 3. Addison-Wesley, Reading, MA, 1973. [Knu84] Donald E. Knuth. The TEXbook. Addison-Wesley, Reading, MA, 1984. [Kof93] Thomas Kofler. Robust iterators in ET++. Structured Programming, 14:62-85, March 1993. [KP88] Glenn E. Krasner and Stephen T. Pope. A cookbook for using the model-view controller user interface paradigm in Smalltalk-80.

(Judging from this book, we suspect “architecture encyclopedia” will be a more appropriate name than “architecture handbook.”) That first workshop has led to a series of meetings, the most recent of which being the first conference on Pattern Languages of Programs held in August 1994. This has created a community of people interested in documenting software expertise. Of course, others have had this goal as well. Donald Knuth’s The Art of Computer Programming [Knu73] was one of the first attempts to catalog software knowledge, though he focused on describing algorithms. Even so, the task proved too great to finish. The Graphics Gems series [Gla90, Arv91, Kir92] is another catalog of design knowledge, though it too tends to focus on algorithms.

pages: 400 words: 94,847

Reinventing Discovery: The New Era of Networked Science by Michael Nielsen

Their heroes were people who could, in a few days, whip up a program that would take lesser programmers months to write. To give you the flavor of what skills were valued in those days, consider this story from one of the great pioneers of modern computing, Alan Kay, a recipient of the Turing Award, the highest honor in computer science. It’s an admiring story about the programming prowess of Donald Knuth, another legend of computing and Turing Award recipient: When I was at Stanford with the [artificial intelligence] project [in the late 1960s] one of the things we used to do every Thanksgiving is have a programming contest with people on research projects in the Bay area. The prize I think was a turkey.

Other forums used to propose new features include an online mailing list, a wiki, and even a weekly conference phone call of Firefox developers. p 58 more than a billion lines: This and the estimate of the rate of code growth are conservative estimates, based on work by Deshpande and Riehle [51], current as of the end of 2006. p 58: Alan Kay’s story about Donald Knuth is from page 101 of [192]. p 59 “Good programmers code; great programmers reuse other people’s code”: Variants of this saying have floated around the open source world for years, but I haven’t been able to track down the original source. This is fitting. There’s more, too: the quote is a paraphrase of a quote often attributed to Picasso, “Good artists copy; great artists steal.”

See also citations; papers, scientific Justinian (emperor), 158 Kacheishvili, Giorgi, 25 Karpov, Anatoly, 18 Kasparov, Garry, 15–18 on hybrid chess tournament, 114 limits on expertise of, 32 Kasparov versus the World, 15–18 amplifying collective intelligence in, 21, 66, 75 collective insight and, 66–68 conversational critical mass in, 30 dynamic division of labor in, 34–36 expert attention and, 24–26, 28, 66 microcontributions in, 64 shared praxis in, 75 superiority to committees, 39 Katznelson, Yitzhak, 212 Kay, Alan, 58 Kelly, Kevin, 221, 233 Kepler, Johannes, 104, 172–73 Kepler Mission, 201 Khalifman, Alexander, 26 Kleinberg, Jon, 217 knowledge: aggregated by the market, 37–39 current change in construction of, 10, 206 entire body of, 123 of information commons, 59 modern expansion of, 31–32 public accessibility of, 96. See also meaning found in knowledge Knuth, Donald, 58 Krush, Irina, 16–18, 24–26, 35, 66, 67–68, 74 Lakhani, Karim, 218 language translation by machine, 124–26 Lanier, Jaron, 223 Large Hadron Collider (LHC), 161 Large Synoptic Survey Telescope (LSST), 107, 151 lasers, 157 Lauer, Tod, 100–101, 103, 114 lean manufacturing, 36 Leibniz, Gottfried Wilhelm, 174 Lessig, Lawrence, 220 Lévy, Pierre, 217, 221 libraries, and new knowledge tools, 235–36 line-free configurations, 209–10, 212 Lintott, Chris, 133, 134–35 Linus’s Law, 223 Linux: conscious modularity in development of, 51–52, 56–57 microcontributions to, 63 near-fracturing of, 49–50 origin of, 20, 44–45 release 2.0, 52 societal change and, 158 ubiquity of, 45 Lockheed Martin Skunk Works, 36 Lockyer, Joseph Norman, 138 machine translation, 124–26 Mackay, Charles, 218 Mad Max (film), 34 Magellanic clouds, 99 Manhattan Project, 36 markets: collaboration markets, 85, 86, 87, 182, 196 delivering social benefits of science, 156–57, 158 online collaboration compared to, 37–38 subsumed by online tools, 38–39, 224 Masum, Hassan, 171 mathematical proof.

pages: 855 words: 178,507

The Information: A History, a Theory, a Flood by James Gleick

♦ “THIS PROCESS OF CONQUEST AND INFLUENCE”: Julian Jaynes, The Origin of Consciousness in the Breakdown of the Bicameral Mind, 198. ♦ TO FORM LARGE NUMBERS, THE BABYLONIANS: Donald E. Knuth, “Ancient Babylonian Algorithms,” Communications of the Association for Computing Machinery 15, no. 7 (1972): 671–77. ♦ “IT WAS ASSUMED THAT THE BABYLONIANS”: Asger Aaboe, Episodes from the Early History of Mathematics (New York: L. W. Singer, 1963), 5. ♦ “OUR TASK CAN THEREFORE PROPERLY BE COMPARED”: Otto Neugebauer, The Exact Sciences in Antiquity, 2nd ed. (Providence, R.I.: Brown University Press, 1957), 30 and 40–46. ♦ “A CISTERN. THE HEIGHT IS 3,20”: Donald E. Knuth, “Ancient Babylonian Algorithms,” 672. ♦ “FUNDAMENTALLY LETTERS ARE SHAPES”: John of Salisbury, Metalogicon, I:13, quoted and translated by M.

In 1949, when the number of cuneiform tablets housed in museums reached (at his rough guess) a half million, Neugebauer lamented, “Our task can therefore properly be compared with restoring the history of mathematics from a few torn pages which have accidentally survived the destruction of a great library.”♦ In 1972, Donald Knuth, an early computer scientist at Stanford, looked at the remains of an Old Babylonian tablet the size of a paperback book, half lying in the British Museum in London, one-fourth in the Staatliche Museen in Berlin, and the rest missing, and saw what he could only describe, anachronistically, as an algorithm: A cistern.

“Andrei Nikolaevich Kolmogorov. 25 April 1903–20 October 1987.” Biographical Memoirs of Fellows of the Royal Society 37 (1991): 301–19. Keynes, John Maynard. A Treatise on Probability. London: Macmillan, 1921. Kneale, William. “Boole and the Revival of Logic.” Mind 57, no. 226 (1948): 149–75. Knuth, Donald E. “Ancient Babylonian Algorithms.” Communications of the Association for Computing Machinery 15, no. 7 (1972): 671–77. Kolmogorov, A. N. “Combinatorial Foundations of Information Theory and the Calculus of Probabilities.” Russian Mathematical Surveys 38, no. 4 (1983): 29–43. ———. Selected Works of A.

pages: 398 words: 107,788

Coding Freedom: The Ethics and Aesthetics of Hacking by E. Gabriella Coleman

He characterized computer programs as “writings” to argue that software was unfit for patents, although appropriate for copyrights and thus free speech protections (patents being for invention, and copyright being for expressive content). The idea that coding was a variant of writing was also gaining traction, in part because of the popular publications of Stanford Computer Science professor Donald Knuth (1998; see also Black 2002) on the art of programming. During the early 1990s, a new ethical sentiment emerged among Usenet enthusiasts (many of them hackers and developers) that the Internet should be a place for unencumbered free speech (Pfaffenberger 1996). This sensibility in later years would become specified and attached to technical artifacts such as source code.

Boston: Little, Brown and Company. Klein, Naomi. 2008. The Shock Doctrine: The Rise of Disaster Capitalism. New York: Henry Holt and Company. Kollock, Peter. 1999. The Economies of Online Cooperation: Gifts and Public Goods. In Communities in Cyberspace, ed. Marc A. Smith and Peter Kollock, 219–39. London: Routledge. Knuth, Donald. 1998. The Art of Computer Programming, Vol. 1. New York: Addison-Wesley. Lakoff, George. 2004. Don’t Think of an Elephant! Know Your Values and Frame the Debate. White River Junction, VT: Chelsea Green. 2006. Whose Freedom? The Battle over America’s Most Important Idea. New York: Farrar, Straus, Giroux.

See poetics of hacking Johansen, Jon Lech, 86, 161, 162, 170–73, 180, 181. See also DeCSS joking. See humor jurisgenesis, 124 Kant, Immanuel, 157, 221n23 KDE, 44, 75, 167 Kelty, Chris, 58, 68, 76, 123, 127, 189, 198, 209 kernel, 43, 46, 74, 75. See also Linux Kidder, Tracy, 61 Klecker, Joel “Espy,” 53 Knuth, Donald, 169 Kraft, Martin “madduck,” 54 Latour, Bruno, 57, 76, 185, 190, 197, 198 lawsuits, 46, 64, 72, 86, 161, 171–72, 180–82 legal education of hackers. See hackers: legal consciousness of Lehman, Bruce, 73 Lessig, Lawrence, 26, 41–42, 82, 83, 168, 180, 181, 190, 197–200. See also Creative Commons Levy, Steven, 19 liberalism, 2, 17, 68, 121, 211n4; definition of, 2–4; relation of to F/OSS, 3, 13, 15, 17, 75, 185, 189, 192, 202; history of, 2–4, 211n2; and notions of selfhood, 11, 94, 95, 118, 121, 202; principles of, 2, 3, 9, 17, 189, 195.

pages: 625 words: 167,349

The Alignment Problem: Machine Learning and Human Values by Brian Christian

When Hoare himself was asked about the quote in 2004, he said he had “no recollection” of where it came from, suggesting perhaps it was the kind of thing that Edsger Dijkstra might have said, and adding, “I think it would be fair for you assume it is common culture or folklore” (Hans Gerwitz, “Premature Optimization Is the Root of All Evil,” https://hans.gerwitz.com/2004/08/12/premature-optimization-is-the-root-of-all-evil.html). Knuth, in 2012, conceded, “I did say things like ‘Premature optimization is the root of all evil in programming’” (Mark Harrison, “A note from Donald Knuth about TAOCP,” http://codehaus.blogspot.com/2012/03/note-from-donald-knuth-about-taocp.html). In all likelihood, the phrase was indeed his own. 3. The US Centers for Disease Control warns about babies getting hypothermia in cold bedrooms, and in 2017 a healthy, middle-aged man in Thailand died in his bedroom after hypothermic shock, simply from leaving fans running on a cold night.

“Brain Function and Adaptive Systems: A Heterostatic Theory.” Bedford, MA: Air Force Cambridge Research Laboratories, 1972. Knox, W. Bradley, Peter Stone, and Cynthia Breazeal. “Training a Robot via Human Feedback: A Case Study.” In International Conference on Social Robotics, 460–70. Springer, 2013. Knuth, Donald E. “Computer Programming as an Art.” Communications of the ACM 17, no. 12 (1974): 667–73. ———. “The Errors of TeX.” Software: Practice and Experience 19, no. 7 (1989): 607–85. ———. “Structured Programming with Go to Statements.” Computing Surveys 6, no. 4 (1974): 261–301. Kobayashi, Hiromi, and Shiro Kohshima.

See curiosity interface design, 269 interference, 292 interpretability, 113–17 See also transparency interventions medical predictive models and, 84, 86, 352n12 risk-assessment models and, 80–81, 317–18, 351nn87, 90 intrinsic motivation addiction and, 205–8, 374n65 boredom and, 188, 201, 202, 203–04 knowledge-seeking agents, 206–07, 209–10, 374n73 novelty and, 189–94, 207, 370–71nn29–30, 32, 35 reinforcement learning and, 186–89, 370n12 sole dependence on, 200–03, 373n58 surprise and, 195–200, 207–08, 372nn49–50, 373nn53–54, 58 inverse reinforcement learning (IRL), 253–68 aspiration and, 386–87n55 assumptions on, 324 cooperative (CIRL), 267–68, 385nn40, 43–44 demonstration learning for, 256–61, 323–24, 383nn22–23, 398n30 feedback learning and, 262, 263–66, 384–85n37 gait and, 253–55 as ill-posed problem, 255–56 inference and, 251–53, 385n39 maximum-entropy, 260–61 inverse reward design (IRD), 301–02 irreversibility, 290–91, 292, 293, 320, 391n39, 397n22 Irving, Geoffrey, 344n86 Irwin, Robert, 326 Isaac, William, 75–77, 349n76 Jackson, Shirley Ann, 9 Jaeger, Robert, 184 Jain, Anil, 31 James, William, 121, 122, 124 Jefferson, Geoffrey, 329 Jefferson, Thomas, 278 Jim Crow laws, 344n83 Jobs, Steve, 98 Johns Hopkins University, 196–97 Jorgeson, Kevin, 220–21 Jurafsky, Dan, 46 Kabat-Zinn, Jon, 321 Kaelbling, Leslie Pack, 266, 371n30 Kage, Earl, 28 Kahn, Gregory, 288 Kalai, Adam, 6–7, 38, 41–42, 48, 316 Kálmán, Rudolf Emil, 383n15 Kant, Immanuel, 37 Kasparov, Garry, 205, 235, 242 Kaufman, Dan, 87–88 Kellogg, Donald, 214–15, 375n7 Kellogg, Luella, 214–15, 375n7 Kellogg, Winthrop, 214–15, 375n7 Kelsey, Frances Oldham, 315 Kerr, Steven, 163, 164, 168 Kim, Been, 112–17 kinesthetic teaching, 261 Kleinberg, Jon, 67, 69, 70, 73–74 Klopf, Harry, 127, 129, 130, 133, 138, 150 knowledge-seeking agents, 206–07, 209–10, 374n73 Knuth, Donald, 311, 395n2 Ko, Justin, 104, 356n55 Kodak, 28–29 Krakovna, Victoria, 292–93, 295 Krizhevsky, Alex, 21, 23–25, 285, 339n20 l0-norm, 354n47 Labeled Faces in the Wild (LFW), 31–32, 340n44 Lab for Analytical Sciences, North Carolina State University, 88 labor recruiting, 22 Landecker, Will, 103–04, 355n54 language models.

pages: 749 words: 92,104

Hacker's Delight by Henry S. Warren

In Papers of John von Neumann on Computing and Computing Theory, Volume 12 in the Charles Babbage Institute Reprint Series for the History of Computing, MIT Press, 1987. [Ken] Found in a GNU C compiler for the RS/6000 that was ported by Richard Kenner. He attributes this to a 1992 PLDI conference paper by him and Torbjörn Granlund. [Knu1] Knuth, Donald E. The Art of Computer Programming, Volume 1, Third Edition: Fundamental Algorithms. Addison-Wesley, 1997. [Knu2] Knuth, Donald E. The Art of Computer Programming, Volume 2, Third Edition: Seminumerical Algorithms. Addison-Wesley, 1998. [Knu3] The idea of using a negative integer as the base of a number system for arithmetic has been independently discovered by many people.

Single Cycle Merge/Logic Unit, US Patent No. 4,903,228, February 20, 1990. [GK] Granlund, Torbjörn and Kenner, Richard. "Eliminating Branches Using a Superoptimizer and the GNU C Compiler." In Proceedings of the 5th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), July 1992, 341-352. [GKP] Graham, Ronald L., Knuth, Donald E., and Patashnik, Oren. Concrete Mathematics: A Foundation for Computer Science, Second Edition. Addison-Wesley, 1994. [GLS1] Steele, Guy L., Jr. Private communication. [GLS2] Steele, Guy L., Jr. "Arithmetic Shifting Considered Harmful." AI Memo 378, MIT Artificial Intelligence Laboratory (September 1976); also in SIGPLAN Notices 12, 11 (November 1977), 61-69.

pages: 612 words: 187,431

The Art of UNIX Programming by Eric S. Raymond

Nevertheless, my approach has certainly been influenced by Christopher Alexander's work[3] (especially The Timeless Way of Building and A Pattern Language), and I owe the Gang of Four and other members of their school a large debt of gratitude for showing me how it is possible to use Alexander's insights to talk about software design at a high level without merely uttering vague and useless generalities. Interested readers should see Design Patterns: Elements of Reusable Object-Oriented Software [GangOfFour] for an introduction to design patterns. The title of this book is, of course, a reference to Donald Knuth's The Art of Computer Programming. While not specifically associated with the Unix tradition, Knuth has been an influence on us all. Editors with vision and imagination aren't as common as they should be. Mark Taub is one; he saw merit in a stalled project and skillfully nudged me into finishing it.

Get it working before you optimize it. The most basic argument for prototyping first is Kernighan & Plauger's; “90% of the functionality delivered now is better than 100% of it delivered never”. Prototyping first may help keep you from investing far too much time for marginal gains. For slightly different reasons, Donald Knuth (author of The Art Of Computer Programming, one of the field's few true classics) popularized the observation that “Premature optimization is the root of all evil”.[11] And he was right. Rushing to optimize before the bottlenecks are known may be the only error to have ruined more designs than feature creep.

But in the Unix tradition, profilers have a far more important function. They enable you not to optimize the other 90%! This is good, and not just because it saves you work. The really valuable effect is that not optimizing that 90% holds down global complexity and reduces bugs. You may recall that we quoted Donald Knuth observing “Premature optimization is the root of all evil” in Chapter 1, and that Rob Pike and Ken Thompson had a few pungent observations on the topic as well. These were the voices of experience. Do good design. Think about what's right first. Tune for efficiency later. Profilers help you do this.

pages: 615 words: 168,775

Troublemakers: Silicon Valley's Coming of Age by Leslie Berlin

The people who mattered to Taylor—the world’s leading academic computer scientists, not venture capitalists, shareholders, the buying public, or the press—knew he had won. Chaired professors at MIT, Stanford, and Carnegie Mellon were impressed by PARC’s work and stunned by the caliber of Taylor’s lab. In 1983, Stanford computer science professor Donald Knuth called the computer science lab “the greatest by far team of computer scientists ever assembled in one organization.”16 If Xerox was too shortsighted to turn top work into products, if the general public was so undiscerning as to want to buy a toy and call it a computer, that didn’t mean that Taylor’s team had lost.

To bring Taylor back to PARC with more resources and more power would have exacerbated the problems perceived by Xerox management. While the group was making its case to Kearns, other members of the lab contacted the world’s leading computer scientists to ask them to write to the CEO and pressure him not to let Taylor leave. Within days, the letters were on Kearns’s desk. “A mind-boggling event,” Donald E. Knuth, the distinguished computer scientist at Stanford, called it. “Bob has accomplished such miraculous things. I had always assumed he was considered one of Xerox’s most important people.” With Taylor gone, Knuth wrote, the world’s finest assembly of computer scientists would likely dissolve, which would “spell the end of Xerox’s leadership in computer systems.”26 Similar letters arrived from Dana S.

Smith, Fumbling the Future: How Xerox Invented, Then Ignored, the First Personal Computer (New York: iUniverse, 1999). 15. Though Gary Starkweather began working on the laser printer at Xerox’s Webster Research Center in Rochester, the work came to fruition only once he moved to PARC and began working with Butler Lampson and others on a digital control system and character generator. 16. Donald E. Knuth to David T. Kearns, Sept. 23, 1983, RWT. 17. Butler Lampson, interview by author, April 18, 2014. 18. Geschke, interview by author, April 21, 2014. Young Maniacs — Mike Markkula 1. Arthur Rock, interview by author, April 4, 2016. It could not have hurt matters that Richard B. Fisher, the leading senior executive at Morgan Stanley (he would be named president in 1984) had been one of Bill Hambrecht’s closest friends since college (Hambrecht ROHO interview).

pages: 315 words: 70,044

Learning SPARQL by Bob Ducharme

RDF lets you define custom datatypes for your own needs, and as this query demonstrates, SPARQL lets you query for them. (We’ll learn how to query for d:item2d, which has the @en tag to show that it’s in English, in Checking, Adding, and Removing Spoken Language Tags.) Note The Potrzebie System of Weights and Measures was developed by noted computer scientist Donald Knuth. He published it as a teenager in Mad Magazine in 1957, so it is not considered normative. A single potrzebie is the thickness of Mad magazine issue number 26. The use of non-XSD types in RDF is currently most common in data using the SKOS standard for controlled vocabularies. In SKOS, the skos:notation property names an identifier for a concept that is often a legacy value from a different thesaurus expressed as a cryptic numeric sequence (for example, “920” to represent biographies in the library world’s Dewey Decimal System), unlike the concept’s skos:prefLabel property that provides a more human-readable name.

pages: 619 words: 210,746

Reversing: Secrets of Reverse Engineering by Eldad Eilam

., 319 architecture compilers, 55–58 decompilers, 459 Windows operating system, 70–71 arithmetic flags carry flag (CF), 520–521 defined, 519 EFLAGS register, 519–520 overflow flag (OF), 520–521 parity flag (PF), 521 sign flag (SF), 521 zero flag (ZF), 521 arithmetic operations ADC instruction, 529 ADD instruction, 522, 529 DIV/IDIV instruction, 524 LEA instruction, 522 modulo, 527–528 MUL/IMUL instruction, 523–524 reciprocal multiplication, 524–527 SBB instruction, 529 64-bit arithmetic, 528–534 SUB instruction, 522, 529 arithmetic (pure), 510–512 array restructuring, 356 arrays, 31, 548–549 The Art of Computer Programming — Volume 2: Seminumerical Algorithms (Second Edition), Donald E. Knuth, 251 The Art of Computer Programming — Volume 3: Sorting and Searching (Second Edition), Donald E. Knuth, 177, 187 assembler program, 11 Index assemblies (.NET), 426, 453 assembly language AT&T Unix notation, 49 code examples, 52–53 defined, 10–11, 44 flags, 46–47 instructions, 47–51 Intel notation, 49 machine code, 11 operation code (opcode), 11 platforms, 11 registers, 44–46 AT&T Unix assembly language notation, 49 attacks copy protection technologies, 324 DoS (Denial-of-Service) attacks, 280 power usage analysis attacks, 319 audio, 321 Automatic Detection and Prevention of Buffer-Overflow Attacks, Crispin Cowan, Calton Pu, David Maier, Heather Hinton, Peat Bakke, Steve Beattie, Aaron Grier, Perry Wagle, and Qian Zhang, 252 B back end of decompilers, 476–477 backdoor access (with malicious software), 280 backdoors, 276 Bakke, Peat, Automatic Detection and Prevention of Buffer-Overflow Attacks, 252 base object, 29 BaseNamedObjects directory, 83 basic block (BB), 464–466 Beattie, Steve, Automatic Detection and Prevention of Buffer-Overflow Attacks, 252 beq instruction, 432 Best, Robert M., Microprocessor for Executing Enciphered Programs patent, 311, 318 bge instruction, 432 bgt instruction, 432 binary code, 11 binary file comparison programs, 242 binary search algorithm, 177 binary searching, 32 binary trees, 32, 552, 554 BIOS/firmware malware, 279–280 ble instruction, 432 blt instruction, 432 bne instruction, 432 Boomerang IA-32 decompiler, 477 box instruction, 432 br instruction, 432 branch prediction, 67–68 branchless logic conditional instructions, 513–515 defined, 509 pure arithmetic, 510–512 break conditions in loops, 506–507 breaking copy protection technologies attacks, 324 challenge response, 315–316 class breaks, 312–313 cracking, 357–358 crypto-processors, 318–319 Defender crackme program, 415–416 dongle, 316–317 encryption, 318 hardware-based, 316–317 media-based, 314–316 objectives, 312 online activation, 315–316 requirements, 313 ripping algorithms, 365–370 serial numbers, 315 563 564 Index breaking copy protection technologies (continued) server-based software, 317 StarForce suite (StarForce Technologies), 345 trusted components, 312 Uncrackable Model, 314 breakpoint interrupt, 331 BreakPoint Software Hex Workshop, 131–132 breakpoints, 331–332 brute-forcing the Defender crackme program, 409–414 BSA and IDC Global Software Piracy Study, Business Software Alliance and IDC, 310 bugs (overflows) heap overflows, 255–256 integer overflows, 256–260 stack overflows, 245–255 string filters, 256 Business Software Alliance, BSA and IDC Global Software Piracy Study, 310 Byte magazine, 311 bytecodes defined, 12 difference from binary code, 61 interpreters, 61–62 just-in-time compilers (JiTs), 62 reversing strategies, 62–63 virtual machines, 12–13, 61 C C programming language, 34–35 C# programming language, 36–37, 428 C++ programming language, 35 CALL instruction, 51, 487, 540 call instruction, 431 calling conventions cdecl, 540 defined, 540 fastcall, 541 stdcall, 541 thiscall, 541 calling functions, 487 carry flag (CF), 520–521 cases Felten vs.

The function is looping toward higher-valued elements by constantly moving to the next node on the right until it finds a node whose middle element is higher-valued than the element you’re looking for (which would indicate that the element is somewhere in the left node). Whenever that happens the function moves to the left node and then continues to move to the right from there until the element is found. This is the classic binary search algorithm defined in Donald E. Knuth. The Art of Computer Programming - Volume 3: Sorting and Searching (Second Edition). Addison Wesley. [Knuth3]. Of course, this function is probably not searching for an existing element, but is rather looking for a place to fit the new element. Callback Parameters Let’s take another look at the parameters passed to the callback and try to guess their meaning.

Volume 32 , Issue 3, July 1985, which is essentially a binary tree with a unique organization scheme. The problem of properly organizing a binary tree has been heavily researched and there are quite a few techniques that deal with it (If you’re patient, Knuth provides an in-depth examination of most of them in [Knuth3] Donald E. Knuth. The Art of Computer Programming—Volume 3: Sorting and Searching (Second Edition). Addison Wesley. The primary goal is, of course, to be able to reach elements using the lowest possible number of iterations. A splay tree (also known as a self-adjusting binary search tree) is an interesting solution to this problem, where every node that is touched (in any operation) is immediately brought to the top of the tree.

pages: 519 words: 142,646

Track Changes by Matthew G. Kirschenbaum

His colophon to the three books (just shy of 3,000 published pages of scientific and historical fiction) captures what I mean. He tells us there that the manuscript was drafted longhand, using a succession of boutique fountain pens. Stephenson then transcribed the text to his personal computer system using the venerable Emacs program and typeset it himself using TeX, the computer typesetting system to which Donald Knuth (perhaps our most famous living computer scientist) devoted nearly a decade of his career to perfecting. His publisher, however, wanted the manuscript set using what was then the industry standard, QuarkXPress, so Stephenson next took it upon himself to put together a conversion program written in LISP.90 Point for point, the brand names of the fountain pens—Waterman, Rotring, Jorg Hysek—balance out the technical particulars of the software programs and computing languages that follow.

See Amazon.com King, Stephen, xi, 42, 43, 59–62, 74–77, 83–86, 279n1, 279n9; On Writing, 83, 84; The Talisman, 59–62, 58, 76, 84; “The Word Processor,” 77–83, 85, 157, 186, 188; Under the Dome, 83–84 Kittler, Friedrich, 28, 48, 158, 160, 163, 209, 235, 243, 324n2 Kleinschrod, Walter, 34, 146 Kling, Thomas, 233 Knickerbocker, Conrad, 167 Knopf, 132, 133, 137 Knuth, Donald, 30, 128 Kokkonen, Kim, 112 Kopelson, Kevin, 75 Kosofsky Sedgwick, Eve, 3, 330n19 Krementz, Jill, 74–76, 83, 90 Kruse, Horst, 251n1 Labor: computers and, 25, 39, 50, 58, 71, 101, 142–144, 244; gender and, 140–143, 150 162, 167, 176; of writing, 97, 160, 243–244 Langford, David, 268n37 Lanham, Richard, 196, 197, 198 Lanier, 33, 44, 51, 117, 216 Larson, Jonathan, 26, 234 Larsson, Stieg, 216, 222 Le Guin, Ursula K., 113 Leiber, Fritz, 38, 192, 268n27, 279n10 Lem, Stanislaw, 38, 41, 192, 279n10 Levertov, Denise, 160 Levine, David, 253n16 Levy, Steven, 54, 140–141 Lexitron, 35, 46, 119, 164, 216, 221, 304n105 Licklider, J.

pages: 525 words: 142,027

CIOs at Work by Ed Yourdon

When I was working my way through school, I was spending a lot of time reading, guess what? I think it was classic computer science texts. Yourdon: [laughter] Fried: And everything from reading [Brian] Kernighan and [P.J.] Plauger’s Elements of Programming Style [McGraw-Hill, 1978], the books of the Bell Labs guys, [Donald] Knuth’s Art of Computer Programming [Addison-Wesley, 2011], and the stuff he did. Did you guys [Bell Labs team and Ed Yourdon] publish together? I thought I remembered. Yourdon: Well, because it took two years to get my books out—in fact, because of Bill Plauger, we had the first nonacademic UNIX license in the country.

Nobody wants to spend more than ten minutes focusing intellectually on anything. Nicholas Kristof wrote something saying that in today’s world you could never read War and Peace because who’s got time for a 1200-page book, whether it’s a novel or a computer science book? Fried: Yeah. Yourdon: Who’s going to read Donald Knuth’s four volumes? Fried: Yeah, I just got the new one, the 4A just came out, right? So, that’s interesting. There had been this period of time when many of us had thought or hoped that the prevalence of e-mail would lead to a second great, generation of letters, of people of letters. But of course, what happened instead was instant messaging and tweets and so on—more and more sharding of one’s attention.

pages: 326 words: 91,559

Everything for Everyone: The Radical Tradition That Is Shaping the Next Economy by Nathan Schneider

Less glamorously, the professional organizations for doctors, lawyers, real estate agents, and hairdressers have clung to the guild model, complete with monopoly powers recognized by governments and peers. As we talked on the rooftop, Prime Produce’s founders freely mixed medieval idiom with that of Silicon Alley. Taeyoung cited the computer programming guru Donald Knuth’s dictum, “Premature optimization is the root of all evil.” That is, if they decided too much ahead of time and in too much detail, they wouldn’t be as flexible or as iterative. Hsu described what Prime Produce was doing as “crafted social innovation,” a form of “slow entrepreneurship.” The guild’s appeal wasn’t just nostalgic to them but was a means of navigating an often lonely, attention-deficient economy, by cultivating habits of excellence and communizing resources like office space, companionship, and broadband.

Infospai, 118–119 Innocent IV (pope), 23 Institute for Cooperative Development, 66 Institute for Local Self-Reliance, 175 Institute for the Formation of Character, 47 insurance industry, 5, 8, 10, 14, 38, 54–56, 183, 185 Integral Cooperative, 119, 120 integral human development, 62 Integral Revolution, 119, 126 Integralism, 128–129 International Cooperative Alliance, 8–9, 11–12, 58, 233 International Ladies’ Garment Workers’ Union, 7 International Summit of Cooperatives, 11, 15 Internet, 147–148, 162, 212 investors, 80, 104, 233 Ipercoop store, 230 iStock, 148 Italy co-op laws in, 188–189, 232–233 co-ops in, 62–63, 229–230 Emilia-Romagna region, 62–63 Matera, 24–25, 28, 32 social co-ops in, 81 Jackson, Andrew, 192 Jackson Jambalaya (blog), 202 “Jackson Rising” (conference), 203–204, 215 Jackson-Kush Plan, 195, 196–198, 205 Jackson-Kush Plan: The Struggle for Black Self-Determination and Economic Democracy (pamphlet), 195 Jay Z, 34 Jefferson, Thomas, 43 Jesus Christ, 22 jobs as ideology, 45 technology and vulnerability of, 79, 225 Jobs, Steve, 79 Jobs of Our Own (Mathews), 61 Johnson, Derrick, 178 Johnson, Lyndon, 171 Johnstown, CO, 1 Joint Stock Companies Act (1856), 50 Joyce, James, 144 Juris, Jeffrey, 117 Jurowicz, Julek, 93 Kahle, Brewster, 158 Kauai Island Utility Cooperative, 174 Kazadi, Aleta, 184 Kelly, Marjorie, 151 Kelty, Christopher M., 135 Kenya, 65–67 King, Martin Luther, Jr., 199–200, 222 Kit Carson Electric Cooperative, 174 Kleiner, Dmytri, 160 Knights of Labor, 54–56, 61–62 Knuth, Donald, 35 Koch, Charles, 223 Koestler, Arthur, 139 König, Thomas, 131 Krause, Alanna, 95–96 Kunstler, James Howard, 97 Kurds, 207 Kush District, 190 labor unions, 6–7, 15, 34, 44, 53–54, 56, 76, 83–84, 85, 112, 124, 154, 224 Lander, Brad, 161 LaPlante, Rochelle, 144 Las Indias, 149–150 Laurini, Gianluca, 63 law school, 193 learning, lifetime of, 13 Lee, Jonathan, 196 Lee, Marcia, 73, 75 Legacoop, 63, 150, 231 Lehman Brothers, 119 Leo XIII (pope), 60 Leroux, Monique, 11 Lessig, Lawrence, 137 Liberty Distributors, 2, 3 (fig.), 6, 234–235 Lieder, Sheila, 85, 88 Lim, Leng, 33 Lincoln, Abraham, 44–45 Lincoln, Murray, 41, 57, 181 Lines Across the Land, 175 Linux software, 133–134 Lockwood, Jonathan, 186–187 Loconomics Cooperative, 150, 154 The Lone Ranger (radio dramas), 57 Long, Guillaume, 213 Loomio, 93–95, 104, 159, 167 Lopez, Alfredo, 135 Lumumba, Chokwe, 189–192, 197–198 mayoral campaign of, 196–197 Mississippi arrival of, 192–193 New Afrikan People’s Organization founded by, 194 Lumumba, Chokwe Antar, 190, 200–201, 203 (photo) mayoral election of, 205 Mississippi’s flag changed and, 204–205 Lumumba, Rukia, 195 Lundahl, Erika, 103 Lung Ta (farming commune), 123–124 Luther, Martin, 38 Magnolia Electric Power Association, 177 Malcolm X, 74, 189, 193, 194, 199 Malcolm X Grassroots Movement, 191, 194 Manna (Brain), 222–223 manufacturing cooperative, 63 (photo) Martin, Brendan, 82, 84 Marx, Karl, 53, 79 Matera, Italy, 24–25, 28, 32 Matheson, Jim, 171 Mathews, Race, 60–61 Maurin, Peter, 5 May First/People Link organization, 135–136 MBA programs, 69 McClelland, Jamie, 135–136 Mckesson, DeRay, 190 McKnight, Albert J., 62 McLean, Christopher, 174–175, 179–180 McRitchie, Jim, 166 Mead, Margaret, 20, 188 Mechanical Turk, 90, 92, 144 medieval guilds, 33–37, 212, 229 Megatrends (Naisbitt), 10 mendicant movement, 23 mercantilism, 215 Meredith, Greg, 157 migration, 216 Millet, Jean-François, 142 Mingo, Stephanie, 205 missing markets, 9, 52 Mississippi Sovereignty Commission, 193 Mississippi’s flag, 204–205 Modo cooperative, 152 monasteries, 22–23, 25–26, 32 Mondragon Corporation, 59–62, 124, 151, 156, 195, 206 money, as debt, 104–105 Moraa, Nyong’a Hyrine, 67–68 Mòrist, Joel, 123, 126 (photo) mortgage crisis, 119 movements, 9, 15, 23, 49–50 anti-globalization, 117 communal, 212–213 for co-ops, 12, 43–44, 225–226, 233 cryptocurrencies and, 130 free-software, 135, 137, 140–141 Malcolm X Grassroots, 191, 194 Mubarak, Hosni, 80 Müntzer, Thomas, 37–39 Musk, Elon, 79 Mussolini, Benito, 188 Mutual Broadcasting System, 57 MXGM organization, 194–197, 200–201, 204 Naisbitt, John, 10 Najm, Qinza, 36 (photo) Nakamoto, Satoshi, 106–107 Namasté Solar, 227 National Cooperative Business Association (NCBA), 41 National Domestic Workers Alliance, 151 National Grange of the Order of Patrons of Husbandry, 54 National Rural Electric Cooperative Association (NRECA), 171 National Security Agency, 135–136 National Trades Union, 44 NCBA.

pages: 332 words: 93,672

Life After Google: The Fall of Big Data and the Rise of the Blockchain Economy by George Gilder

In embryo, Google had at its disposal the full bandwidth of the university’s T-3 line, then a lordly forty-five megabits a second, and ties to such venture capital titans as John Doerr, Vinod Khosla, Mike Moritz, and Don Valentine. The computer theorists Terry Winograd and Hector Garcia Molina supervised the doctoral work of the founders. Rollerblading down the corridors of Stanford’s computer science pantheon in the madcap spirit of Claude Shannon, the Google founders consorted with such academic giants as Donald Knuth, the conceptual king of software, Bill Dally, a trailblazer of parallel computation, and even John McCarthy, the founding father of artificial intelligence. By 1998, Brin and Page were teaching the course CS 349, “Data Mining, Search, and the World Wide Web.” Sun founder Andy Bechtolsheim, Amazon founder Jeff Bezos, and Cisco networking guru Dave Cheriton had all blessed the Google project with substantial investments.

., 94 Google, xv, 2–5, 7–8 25–26, 146, 150, 153–54, 157, 164–69, 171–73, 176, 181–84, 187, 189, 191–98, 220, 222–25, 247 “system of the world,” 11–23, 276 philosophy, 25–35 use of advertising, 37–43 rule of communications, 45–46 compared to the cryptocosm, 48–50 data center, 51–61 machine learning/innovation, 63–71 influence of Andrey Markov, 75–92 work with AI, 93–108 cloud technology, 199–211 Internet regulation, 227–41 the “great unbundling,” 259–69 Google Brain, 67–68, 71, 94, 192, 223 Google Era, 13, 45, 49, 57, 63, 75–76, 78, 80, 89, 247, 261–62, 277 Gosling, James, 179 Grainger, Alissa, 205, 207, 209 Grigg, Ian, 153 H Harari, Yuval Noah, 4, 7 Harik, Georges, 196–98 HashCash, 123, 134 Hassabis, Demis, 41, 93, 99 Hearn, Mike, 153, 245 Hennessy, John, 26, 222 Heyting, Arend, 15 Hilbert, David, 14–17, 247 Hillenmeyer, Hunter, 271–74 Hillis, Danny, 71 Hinton, Geoffrey, 41, 93, 192 Hoffman, Reid, 274 Hölzle, Urs, 53–56, 58, 67, 71, 82, 195, 199–202, 209, 232, 241 Horowitz, Ben, 125, 162 Horowitz, David, 162 Hoskinson, Charles, 153–54, 264–65 How to Create a Mind, 79, 101 I Ibárgüen, Giancarlo, 215–16 Inception, 192 Industrial and Commercial Bank of China, 11 iTunes, 8 Ivan on Tech, 204 J James, Daniel Colin, 39–40 JavaScript, 48, 166, 176, 179–80, 185–86 Jelinek, Fred, 81, 88 Jobs, Steve, xv, 8, 64, 144 Jouppi, Norm, 65, 69 K Kelley, Nick, xi Kelly, Kevin, 184–85, 191 Kendall, Mike, 249–50, 253–58 Khosla, Vinod, 26 King, Mervyn, 263 Kleiman, David, 140, 145–46 Klugmann, Mark, 216 Knuth, Donald, 26 Kolmogorov, Anton, 73 Kowalski, Jeff, 186 Krauss, Lawrence, 93 Krugman, Paul, 126, 136, 243 Kubrick, Stanley, xi Kurzweil, Raymond, 25, 68, 79, 89, 93, 95–101, 103, 280 L Langley, Samuel P., 224 Langville, Amy, 75 Lanier, Jaron, xiv, 60, 82–83, 89, 104, 185, 272, 275 Larimer, Dan, 153, 245, 265–66 Laughlin, Robert, 87 LeCun, Yann, 93, 99 Leibniz, Gottfried Willhelm, 12 Levandowski, Anthony, 41 Levy, Steven, 30–31 Lewis, C.

pages: 665 words: 159,350

Shape: The Hidden Geometry of Information, Biology, Strategy, Democracy, and Everything Else by Jordan Ellenberg

He was a compulsive inventor of games, which he liked to give funny names to: Col, Snort, ono, loony, dud, sesqui-up, Philosopher’s Football. But fun was never just for fun. He made theory out of fun. We’ve met his mathematical gaming already in this book: it was Conway who developed the notion that a game like Nim is a kind of number, an idea his colleague Donald Knuth wrote about in a 1974 book with the extremely 1974 title Surreal Numbers: How Two Ex-Students Turned On to Pure Mathematics and Found Total Happiness. The book is styled as a dialogue between two students who come upon a sacred text outlining Conway’s theory: “In the beginning, everything was void, and J.

“the murder weapon”: István Hargittai, “John Conway—Mathematician of Symmetry and Everything Else,” Mathematical Intelligencer 23, no. 2 (2001): 8–9. He was a compulsive: R. H. Guy, “John Horton Conway: Mathematical Magus,” Two-Year College Mathematics Journal 13, no. 5 (Nov. 1982): 290–99. began to create numbers: Donald Knuth, Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness (Boston: Addison-Wesley, 1974). The Knuth book introduces Conway’s novel number system, but the connection of these numbers with games comes in Conway’s 1976 book On Numbers and Games. here are some: This is Figure 1 in John H.

See also intuition immunity, 219, 221–22, 221n independence of variables, 86–89, 89n, 91 Indo-European languages, 236n induction, mathematical, 119–20, 406n information theory, 93, 106 inherent value, 285 initial conditions, 239 Institute for Health Metrics and Evaluation, 257n, 259 integers, 273–74 integrals, 68 International Congress of Arts and Sciences, 59 International Congress of Mathematicians, 84, 212 International Mathematical Olympiad, 264 internet searching, 288–92 interpolation, 253–54 intuition and “compactness” of shapes, 367, 369 conceptualizing multidimensional space, 48 and exponential growth, 216 and gradient of confidence, 22 and Hudson, 213 and Kermack, 233 and linear algebra, 322 and multidimensional scaling, 193 and neutral networks, 206 and number theory, 110 and Pi (film), 276 and Poincaré, 39 and the pons asinorum, 24–26, 30 proofs as tools for, 416 and redistricting methods, 387 and strategy space, 165 and Sylvester, 323 invariance, 368–69 Inventional Geometry (Spencer), 15–16, 16–17 inverse assertions, 153 Iowa Baseball Confederacy, The (Kinsella), 160n Iran, 349 Ireland, 349 irrational numbers, 271–75 Isner, John, 160 isobutane, 316 isochrone maps, 189, 189–90, 302, 303n isometry, 52, 56 isoperimetric equality, 369 isosceles triangles, 26, 28–32, 191, 312, 412 Israel, 348 Isthmus of Panama, 304 Italy, 217 Izvestia, 85 Jeans, James, 154, 154n Jefferson, Thomas, 13–14, 48n, 319, 351, 414 Jefferson County, Alabama, 352 Jenner, Edward, 209 Jennings, Helen, 338 Jesuits, 413, 416 Jewish numerology, 276 Johns Hopkins University, 319 Johnson, Katherine, 3 Johnson, Ron, 341, 347 Jordan, Charles, 324–25, 330 Jordan Curve Theorem, 21 Journal of Prosthetic Dentistry, The, 278 Journal of the Royal Society of Medicine, 208 Jurin, James, 413 justiciability, 375, 404–5 Kagan, Elena, 402, 403, 405, 408–9 Karinthy, Frigyes, 338, 339 Kasich, John, 384 Kasiski examination, 133 Kasparov, Gary, 145 Kavanaugh, Brett, 404 Keats, John, 6 Keller, Helen, 59 Kempelen, Wolfgang von, 155 Kennedy, Anthony, 375, 384 Kepler, Johannes, 269–70, 277 Kerkman, Samantha, 344 Kermack, William Ogilvy, 233, 240, 286 Kerry, John, 346 Kinsella, W. P., 160n kin words, 190–91 Kirchoff, Gustav, 397 “Kittytron” (image recognition program), 169–70, 173–74 Kleitman, Daniel, 315n Knesset, 348 knot theory, 46, 205–6, 216, 223, 223–24, 331 Knuth, Donald, 223 Kochen, Manfred, 338 Kondlo, Lubabalo, 142 Lagerlöf, Selma, 339 laghu, 236 Lamb, Charles, 6 Lamone v. Benisek, 384 Láncszemek (Karinthy), 338 Langmuir, Alexander, 257 language and linguistics, 90–96, 191–99 Last Week Tonight, 408 Latifah, Queen, 315 latitude, 305–8 law of anti-averages, 72–74 law of conservation of area, 54 law of increase, 244, 248, 255, 333.

pages: 309 words: 65,118

Ruby by example: concepts and code by Kevin C. Baird

/usr/bin/env ruby # factorial1.rb class Integer def fact() return 1 if (self.zero?) or (self == 1) return self * (self-1).fact end end And here’s fibonacci1.rb: #!/usr/bin/env ruby # fibonacci1.rb class Integer def fib() return 0 if (self.zero?) 2 122 C h ap te r 7 Commonly attributed to Donald Knuth, a computer programming genius if there ever was one. return 1 if self == 1 return (self-1).fib + (self-2).fib end end How It Works For factorial1.rb and fibonacci1.rb, we add a new method to all Integers: either fact or fib, respectively. In both cases, we have our exit conditions that return either zero or one.

method (Builder::XmlMarkup), 255 Integer class, 3–4 get_base method, 200 round_to_base method, 86 to_roman method, 81–87 Integers, multiplying Strings by, 86 Interactive Ruby (irb), 1–2 information in prompt, 8 starting, 2 Internet connection, for opening URLs, 95 Internet protocols, end-of-line marker, 52 interpolation, 23 irb. See Interactive Ruby (irb) J Java, 262–263 JavaScript, 157 join method (Array), 37, 47 JRuby, 263 K Kasahara, Motoyuki, 39 Kay, Alan, 265 kelvins, vs. Celsius, 134 keys method (Hash), 44 keys of Hash, 42 King Crimson, 29–30, 192–193 Knuth, Donald, 122n L command, 43, 100–102 creating Procs with, 105, 115, 116 nesting, 111–112 lazy evaluation, 127, 262 Lerdorf, Rasmus, 265 letters_only method (String), 47 lib directory for Rails, 230 library file, 155, 156 line break, 18 in HTML source, 209 line feed character (newline), 15, 52 line numbers, 2 displaying, 57–59 line_num.rb script, 57–59 lines, definition, 2 Linux, starting irb on, 2 Lisp, 22, 263–264 as Ruby ancestor, 99 lists, making, 36–39 load_old_rates method (CurrencyConverter), 97 local method (Time), 15 Locomotive, 228 log directory for Rails, 230 logs messages by radio_player2.rb, 191 radio station need for, 186 long options, 39 lookup tables, Hashes for, 42–43 ls command (Unix), 192 lambda M Mac OS X and Apache, 206 starting irb on, 2 magic numbers, 15 make_exp example, 111 make_exp_proc Proc, 112 make_incrementer method, 101 make_incrementer.rb script, 100–102 map method, 66, 185, 203–204 filtering Proc via, 106 I N D EX 273 Mastering Regular Expressions (Friedl), 55, 64 matches_block method (Array), 105 matching_compound_members method (Array), 106 matching_compound_members.rb script, 103–108 matching_members method (Array), 105 matching_members.rb script, 102–103 McKay, Brendan, 162 memoization of results, 126–127, 131 merge method (Hash), 151 merge_totals method (Hash), 151 <meta> tag (HTML), 144 Meta_Mutator class best_num method, 180 creating, 180 get_children method, 180 get_no_better_count method, 180 initialize method, 180 mutate_mutations!

pages: 894 words: 190,485

Write Great Code, Volume 1 by Randall Hyde

The only problem is that certain operations may produce really large numerators or denominators (to the point where you get integer overflow in these values). Other than this problem, however, you can represent a wide range of fractional values using this scheme. 2.13 For More Information Donald Knuth’s The Art of Computer Programming, Volume Two: Seminumerical Algorithms is probably the seminal text on number systems and arithmetic. For more information on binary, decimal, fixed-point, rational, and floating-point arithmetic, you’ll want to take a look at that text. * * * [1] The “..” notation, taken from Pascal and other programming languages, denotes a range of values.

Inserting ThirdField into the Social Security packed type Here’s the C/C++ code that accomplishes the operation shown in Figure 3-10: packedValue = (packedValue & 0xFFc000FF) | (ThirdField << 8 ); You’ll note that $FFC000FF is the hexadecimal value that corresponds to all zeros in bit positions 8 through 21 and ones everywhere else. 3.8 For More Information My book, The Art of Assembly Language, provides additional information on bit processing, including several algorithms for counting bits, reversing the bits in an object, merging two bit strings, coalescing sets of bits, and spreading bits out across some value. Please see that text for more details on these low-level bit operations. Donald Knuth’s The Art of Computer Programming, Volume Two: Seminumerical Algorithms provides a discussion of various arithmetic operations (addition, subtraction, multiplication, and division) that you may find of interest. * * * [6] It’s also possible to set all the uninteresting bits to ones via the OR operation, but the AND operator is often more convenient . // Okay, assemble the final real32 value: shr( 8, eax ); // Move mantissa into bits 0..23. and($7f_ffff, eax ); // Clear the implied bit. or( ecx, eax ); // Merge mantissa & exponent into EAX. or( ebx, eax ); // Merge in the sign. Whew! This has been a lot of code. However, it’s worthwhile to go through all this just to see how floating-point operations work (so you can gain an appreciation of exactly what an FPU is doing for you). 4.8 For More Information Donald Knuth’s The Art of Computer Programming, Volume Two: Seminumerical Algorithms, provides an in-depth discussion of floating-point arithmetic and floating-point formats. This book is required reading for someone who wants to fully understand how floating-point arithmetic operates. Also, Intel’s documentation on its Pentium processors explains its floating-point formats, exceptional conditions, and other issues related to the use of its FPU.

pages: 893 words: 199,542

Structure and interpretation of computer programs by Harold Abelson, Gerald Jay Sussman, Julie Sussman

Syntactic extensions in the programming language Lisp. Ph.D. thesis, Indiana University. Konopasek, Milos, and Sundaresan Jayaraman. 1984. The TK!Solver Book: A Guide to Problem-Solving in Science, Engineering, Business, and Education. Berkeley, CA: Osborne/McGraw-Hill. Knuth, Donald E. 1973. Fundamental Algorithms. Volume 1 of The Art of Computer Programming. 2nd edition. Reading, MA: Addison-Wesley. Knuth, Donald E. 1981. Seminumerical Algorithms. Volume 2 of The Art of Computer Programming. 2nd edition. Reading, MA: Addison-Wesley. Kowalski, Robert. 1973. Predicate logic as a programming language. Technical report 70, Department of Computational Logic, School of Artificial Intelligence, University of Edinburgh.

List of Exercises 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.10 1.11 1.12 1.13 1.14 1.15 1.16 1.17 1.18 1.19 1.20 1.21 1.22 1.23 1.24 1.25 1.26 1.27 1.28 1.29 1.30 1.31 1.32 1.33 1.34 1.35 1.36 1.37 1.38 1.39 1.40 1.41 1.42 1.43 1.44 1.45 1.46 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 2.16 2.17 2.18 2.19 2.20 2.21 2.22 2.23 2.24 2.25 2.26 2.27 2.28 2.29 2.30 2.31 2.32 2.33 2.34 2.35 2.36 2.37 2.38 2.39 2.40 2.41 2.42 2.43 2.44 2.45 2.46 2.47 2.48 2.49 2.50 2.51 2.52 2.53 2.54 2.55 2.56 2.57 2.58 2.59 2.60 2.61 2.62 2.63 2.64 2.65 2.66 2.67 2.68 2.69 2.70 2.71 2.72 2.73 2.74 2.75 2.76 2.77 2.78 2.79 2.80 2.81 2.82 2.83 2.84 2.85 2.86 2.87 2.88 2.89 2.90 2.91 2.92 2.93 2.94 2.95 2.96 2.97 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19 3.20 3.21 3.22 3.23 3.24 3.25 3.26 3.27 3.28 3.29 3.30 3.31 3.32 3.33 3.34 3.35 3.36 3.37 3.38 3.39 3.40 3.41 3.42 3.43 3.44 3.45 3.46 3.47 3.48 3.49 3.50 3.51 3.52 3.53 3.54 3.55 3.56 3.57 3.58 3.59 3.60 3.61 3.62 3.63 3.64 3.65 3.66 3.67 3.68 3.69 3.70 3.71 3.72 3.73 3.74 3.75 3.76 3.77 3.78 3.79 3.80 3.81 3.82 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 4.16 4.17 4.18 4.19 4.20 4.21 4.22 4.23 4.24 4.25 4.26 4.27 4.28 4.29 4.30 4.31 4.32 4.33 4.34 4.35 4.36 4.37 4.38 4.39 4.40 4.41 4.42 4.43 4.44 4.45 4.46 4.47 4.48 4.49 4.50 4.51 4.52 4.53 4.54 4.55 4.56 4.57 4.58 4.59 4.60 4.61 4.62 4.63 4.64 4.65 4.66 4.67 4.68 4.69 4.70 4.71 4.72 4.73 4.74 4.75 4.76 4.77 4.78 4.79 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10 5.11 5.12 5.13 5.14 5.15 5.16 5.17 5.18 5.19 5.20 5.21 5.22 5.23 5.24 5.25 5.26 5.27 5.28 5.29 5.30 5.31 5.32 5.33 5.34 5.35 5.36 5.37 5.38 5.39 5.40 5.41 5.42 5.43 5.44 5.45 5.46 5.47 5.48 5.49 5.50 5.51 5.52 Index Any inaccuracies in this index may be explained by the fact that it has been prepared with the help of a computer. Donald E. Knuth, Fundamental Algorithms (Volume 1 of The Art of Computer Programming) ! in names " (double quote) λ calculus, see lambda calculus ⟼ notation for mathematical function π , see pi Σ (sigma) notation θ, see theta ' (single quote) read and, [2] * (primitive multiplication procedure) + (primitive addition procedure) , (comma, used with backquote) - (primitive subtraction procedure) as negation / (primitive division procedure) < (primitive numeric comparison predicate) = (primitive numeric equality predicate) =number?

., [2] read-eval-print loop intersection-set binary-tree representation ordered-list representation unordered-list representation interval arithmetic invariant quantity of an iterative process inverter inverter iteration contructs, see looping constructs iterative improvement iterative process as a stream process design of algorithm implemented by procedure call, [2], [3], see also tail recursion linear, [2] recursive process vs., [2], [3], [4] register machine for Jayaraman, Sundaresan Kaldewaij, Anne Karr, Alphonse Kepler, Johannes key key of a record in a data base in a table testing equality of Khayyam, Omar Knuth, Donald E., [2], [3], [4], [5], [6], [7] Kohlbecker, Eugene Edmund, Jr. Kolmogorov, A. N. Konopasek, Milos Kowalski, Robert KRC, [2] label (in register machine) simulating label-exp label-exp-label Lagrange interpolation formula λ calculus (lambda calculus) lambda (special form) define vs.

pages: 511 words: 111,423

Learning SPARQL by Bob Ducharme

RDF lets you define custom datatypes for your own needs, and as this query demonstrates, SPARQL lets you query for them. (We’ll learn how to query for d:item2d, which has the @en tag to show that it’s in English, in Checking, Adding, and Removing Spoken Language Tags.) Note The Potrzebie System of Weights and Measures was developed by noted computer scientist Donald Knuth. He published it as a teenager in Mad Magazine in 1957, so it is not considered normative. A single potrzebie is the thickness of Mad magazine issue number 26. The use of non-XSD types in RDF is currently most common in data using the SKOS standard for controlled vocabularies. In SKOS, the skos:notation property names an identifier for a concept that is often a legacy value from a different thesaurus expressed as a cryptic numeric sequence (for example, “920” to represent biographies in the library world’s Dewey Decimal System), unlike the concept’s skos:prefLabel property that provides a more human-readable name.

pages: 468 words: 137,055

Crypto: How the Code Rebels Beat the Government Saving Privacy in the Digital Age by Steven Levy

While Merkle was figuring out how to get exponential, Diffie and Hellman focused on finding their own means of implementing a public key cryptosystem. Without some way of actually putting their ideas into action—or at least proving that some feasible scheme could exist—the whole concept of public key cryptography would be merely a mathematical mind-trick. One path was suggested by Stanford computer scientist Donald Knuth, whose encyclopedic series of books in progress, The Art of Computer Programming, would earn him the reputation as the high guru of algorithms. Knuth reminded them of an interesting mathematical phenomenon: while it is child’s play to multiply a pair of prime numbers, reversing the process—a task known as factoring—is an assignment that could confound the devil himself.

., ref-1, ref-2 Gardner, Martin, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8 Gates, Bill, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Gauss, Carl Friedrich, ref-1, ref-2, ref-3, ref-4 Gejdenson, Sam, ref-1, ref-2, ref-3 General Communication Headquarters (GCHQ), ref-1, ref-2, ref-3, ref-4 Gersho, Alan, ref-1 Gill, John, ref-1 Gilmore, John, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Glaser, Edward, ref-1 Goen, Kelly, ref-1, ref-2, ref-3 Goldberg, Ian, ref-1, ref-2 Goodlatte, Robert, ref-1, ref-2 Gore, Al, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12 Graff, Michael, ref-1, ref-2 Graham, Sue, ref-1 groupware, ref-1 Haber, Stuart, ref-1 Hammond, Larry, ref-1 Harbert, Don, ref-1 Harmon, John, ref-1, ref-2 Heiman, Bruce, ref-1, ref-2 Hellman, Martin, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20, ref-21, ref-22, ref-23, ref-24 Diffie-Hellman algorithm, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8 Helsingius, Julf, ref-1, ref-2, ref-3, ref-4 heuristic qualifiers, ref-1 Hoffman, Lance, ref-1, ref-2, ref-3, ref-4 Homer, Mike, ref-1 Hughes, Eric, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 hybrid system, ref-1 IBM, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14 Identification Friend or Foe (IFF), ref-1, ref-2, ref-3, ref-4 identity proofs: digital signatures, see signatures, digital zero-knowledge, ref-1 Ingram, Tim, ref-1 Inman, Bobby Ray, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13 Intergraph, ref-1 International Data Encryption Algorithm (IDEA), ref-1, ref-2 Internet, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12 anonymity and, ref-1 browsers and, ref-1, ref-2, ref-3 factoring and, ref-1, ref-2 Iris Associates, ref-1, ref-2, ref-3, ref-4 ITAR, see export regulations Izen, Ted, ref-1 Jefferson, Thomas, ref-1 Kahn, David, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9 Kallstrom, James, ref-1, ref-2, ref-3 Kammer, Raymond, ref-1, ref-2, ref-3 Kapor, Mitch, ref-1, ref-2, ref-3, ref-4, ref-5 Karn, Phil, ref-1, ref-2 Kaufman, Charles, ref-1 Keane, William, ref-1 Kelly, Jack, ref-1, ref-2 Kerckhoffs, Auguste, ref-1 Kerry, Bob, ref-1 keys, ref-1, ref-2 escrow system and, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10 nonsecret, ref-1 pairs of, ref-1, ref-2, ref-3, ref-4 public, see public key cryptography secret sharing of, ref-1 size of, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12 symmetrical, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 knapsacks, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 multiple-iteration, ref-1 single-iteration, ref-1 superincreasing, ref-1 Knuth, Donald, ref-1, ref-2, ref-3, ref-4 Kocher, Paul, ref-1 Kolata, Gina, ref-1 Konheim, Alan, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8 Kravitz, David, ref-1, ref-2 Kreps, Juanita, ref-1 Landau, Susan, ref-1 Larry King Live, ref-1 law enforcement, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Law Enforcement Access Field (LEAF), ref-1, ref-2 Leahy, Patrick, ref-1, ref-2, ref-3 Lee, Ronald, ref-1 Lenstra, Arjen, ref-1, ref-2 Lenstra, Hendrick, ref-1 Leyland, Paul, ref-1, ref-2 Limbaugh, Rush, ref-1 linear cryptanalysis, ref-1 Lloyds of London, ref-1, ref-2, ref-3 Lofgren, Zoe, ref-1, ref-2 Lotus, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13 Lucifer, ref-1, ref-2, ref-3, ref-4 DSD-1, ref-1, ref-2, ref-3 see also Data Encryption Standard McCain, John, ref-1 McCarthy, John, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 McConnell, Mike, ref-1, ref-2, ref-3, ref-4, ref-5 McNulty, Lynn, ref-1, ref-2, ref-3 Mailsafe, ref-1, ref-2, ref-3, ref-4, ref-5 Mann, Bill, ref-1, ref-2, ref-3 Manzi, Jim, ref-1 Markoff, John, ref-1 May, Tim, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8 BlackNet, ref-1 Mead, Carver, ref-1, ref-2 Merkle, Ralph C., ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15 Merritt, Charlie, ref-1, ref-2, ref-3, ref-4 Metamorphic Systems, ref-1, ref-2 Meyer, Joseph A., ref-1, ref-2, ref-3, ref-4 Meyer, Karl, ref-1, ref-2, ref-3 Micali, Silvio, ref-1 Microsoft, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10 Access, ref-1 Moore’s Law, ref-1, ref-2 Morris, Lew, ref-1 Morris, Robert, Sr., ref-1, ref-2, ref-3 Mosaic, ref-1 “Multiuser Cryptographic Techniques” (Diffie and Hellman), ref-1, ref-2, ref-3 Murray, Patty, ref-1 Myhrvold, Nathan, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Mykotronx, ref-1, ref-2, ref-3 National Bureau of Standards (NBS), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 National Institute of Standards and Technology (NIST), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 National Research Council (NRC), ref-1, ref-2 National Science Foundation (NSF), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 National Security Access Field (NSAF), ref-1 National Security Agency (NSA), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20, ref-21, ref-22, ref-23, ref-24, ref-25, ref-26, ref-27, ref-28, ref-29, ref-30, ref-31, ref-32, ref-33 Clipper and, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 DES and, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9 Diffie and, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10 dual roles of, ref-1 GCHQ and, ref-1, ref-2 Kahn and, ref-1, ref-2 Lotus Notes and, ref-1, ref-2, ref-3, ref-4 NRC report and, ref-1 NSAF and, ref-1 Project Overtake of, ref-1 security failures at, ref-1 Snuffle and, ref-1 National Security Decision Directive, ref-1 Nelson, Mike, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Netscape, ref-1, ref-2, ref-3 Neukom, Bill, ref-1 “New Directions in Cryptography” (Diffie and Hellman), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 New York Times, ref-1, ref-2 Nicolai, Carl, ref-1, ref-2 nonrepudiation feature, ref-1 nonsecret encryption, ref-1 Notes, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8 NP-complete functions, ref-1, ref-2 O’Brien, Bart, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Odom, William E., ref-1 Omura, Jim, ref-1, ref-2 one-time pads, ref-1, ref-2, ref-3 one-way functions, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 factoring, ref-1, ref-2, ref-3 knapsacks, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 trapdoor, ref-1, ref-2, ref-3, ref-4 Ozzie, Ray, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 paranoia levels, ref-1 Parker, Donn, ref-1, ref-2 passwords, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Pasta, John R., ref-1 Patel, Marilyn, ref-1 patents, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20, ref-21, ref-22 Patterson, Nick, ref-1, ref-2, ref-3, ref-4 Penet, ref-1, ref-2, ref-3, ref-4, ref-5 Phasorphone, ref-1 Podesta, John, ref-1, ref-2 Poe, Edgar Allan, ref-1, ref-2, ref-3 pornography, ref-1 Press, Frank, ref-1 Pretty Good Privacy (PGP), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12 breaking of, ref-1, ref-2 Prime, Geoffrey, ref-1 prime numbers, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Project C43, ref-1, ref-2 Project Overtake, ref-1 public key cryptography, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20, ref-21, ref-22, ref-23, ref-24, ref-25, ref-26 certification of, ref-1 escrow and, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10 nonsecret encryption and, ref-1 Secure Sockets Layer, ref-1, ref-2, ref-3 security failures and, ref-1 Public Key Partners (PKP), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Puzzle Palace, The (Bamford), ref-1, ref-2 quantum computers, ref-1 Random Number Generator (RNG), ref-1 Ray, Charles, ref-1 RC-2, ref-1, ref-2, ref-3 RC-4, ref-1, ref-2, ref-3, ref-4 Reagan, Ronald, ref-1, ref-2 Reeds, Jim, ref-1 remailers (anonymous servers), ref-1, ref-2, ref-3, ref-4, ref-5 Penet, ref-1, ref-2, ref-3, ref-4, ref-5 Richardson, Elliot, ref-1 Ritner, Peter, ref-1, ref-2 Rivest, Ron, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20 Rizzo, Paul, ref-1 Roberts, Larry, ref-1 Robinson, William B., ref-1, ref-2 Rohrbacher, Dana, ref-1 Rosenblum, Howard, ref-1, ref-2 Rotenberg, Marc, ref-1, ref-2 RSA, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20, ref-21, ref-22, ref-23, ref-24, ref-25, ref-26, ref-27, ref-28, ref-29, ref-30, ref-31 Netscape and, ref-1 patents for, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 personal computers and, ref-1, ref-2 RSA Data Security, Inc., ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16 conference of, ref-1, ref-2, ref-3, ref-4 Sacco, Luigi, ref-1 Safire, William, ref-1 S-boxes (substitution boxes), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Schiller, Jeff, ref-1 Schneier, Bruce, ref-1, ref-2, ref-3 Schnorr, Claus, ref-1, ref-2 Schroeppel, Richard, ref-1, ref-2, ref-3, ref-4 Schwartz, John J., ref-1 Science, ref-1, ref-2, ref-3, ref-4 Scientific American, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8 Scientologists, ref-1, ref-2, ref-3 search warrants, ref-1, ref-2, ref-3, ref-4 secret sharing, ref-1 Secure Sockets Layer (SSL), ref-1, ref-2, ref-3 Security and Freedom through Encryption (SAFE) bill, ref-1, ref-2, ref-3 Security Dynamics, ref-1 Senate Bill ref-1, ref-2, ref-3, ref-4 servers, ref-1, ref-2 anonymous, see remailers Sessions, William, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Shamir, Adi, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17 Shannon, Claude, ref-1, ref-2, ref-3, ref-4, ref-5 shareware, ref-1, ref-2 signals intelligence, ref-1 signatures, digital, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13 blind, ref-1, ref-2 DSA, ref-1, ref-2, ref-3 Silver, Roland, ref-1, ref-2, ref-3, ref-4 Simmons, Gus, ref-1 Simons, Jim, ref-1, ref-2 Skipjack, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 Snefru, ref-1 Snow, Brian, ref-1 Snuffle, ref-1 stream ciphers, ref-1 Studeman, William O., ref-1, ref-2 substitution boxes (S-boxes), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 SWIFT, ref-1 T Attack (differential cryptanalysis), ref-1, ref-2, ref-3 telephones: cellular, ref-1 security devices for, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10 Tempest technology, ref-1 Tenet, George, ref-1 Tessera, ref-1 threshold scheme, ref-1 Time, ref-1 time-sharing, ref-1, ref-2 toll payments, ref-1 trapdoors, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9 knapsacks, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 one-way function, ref-1, ref-2, ref-3, ref-4 Senate bill and, ref-1, ref-2, ref-3 Tritter, Alan, ref-1, ref-2, ref-3, ref-4 Tuchman, Walter, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10 univectors, ref-1, ref-2 Usenet, ref-1, ref-2 vector space, ref-1 VeriSign, ref-1 Very Large Scale Integration (VLSI), ref-1 ViaCrypt, ref-1 virtual private networks, ref-1 Wagner, Dave, ref-1 Walker, Steve, ref-1 Wall Street Journal, ref-1, ref-2 Warren, Jim, ref-1, ref-2 Washington Post, ref-1 web of trust, ref-1 Weingarten, Fred, ref-1 Weldon, Curt, ref-1 Williamson, Malcolm, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Windows, ref-1 wiretapping, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Wise, William, ref-1 World Wide Web, ref-1, ref-2 browsers for, ref-1, ref-2, ref-3 Wormser, Dave, ref-1 Wylie, Shawn, ref-1 Xerox Corporation, ref-1, ref-2 xor operations, ref-1 Zero Knowledge, ref-1 zero-knowledge proofs of identity, ref-1 Zimmermann, Kacie, ref-1 Zimmermann, Phil, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 contents acknowledgments preface the loner the standard public key prime time selling crypto patents and keys crypto anarchy the clipper chip slouching toward crypto epilogue: the open secret notes bibliography glossary index VIKING Published by the Penguin Group Penguin Putnam Inc., 375 Hudson Street, New York, New York 10014, U.S.A.

pages: 560 words: 135,629

Eloquent JavaScript: A Modern Introduction to Programming by Marijn Haverbeke

Passing this string to console.log should show something like this: # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # When you have a program that generates this pattern, define a binding size = 8 and change the program so that it works for any size, outputting a grid of the given width and height. “People think that computer science is the art of geniuses but the actual reality is the opposite, just many people doing things that build on each other, like a wall of mini stones.” — Donald Knuth 3 FUNCTIONS Functions are the bread and butter of JavaScript programming. The concept of wrapping a piece of program in a value has many uses. It gives us a way to structure larger programs, to reduce repetition, to associate names with subprograms, and to isolate these subprograms from each other.

pages: 511 words: 139,108

The Fabric of Reality by David Deutsch

The largest number that has been factorized 'in anger', as it were - a number whose factors were secretly chosen by mathematicians in order to present a challenge to other mathematicians - had 129 digits. The factorization was achieved, after an appeal on the Internet, by a global cooperative effort involving thousands of computers. The computer scientist Donald Knuth has estimated that the factorization of a 250-digit number, using the most efficient known methods, would take over a million years on a network of a million computers. Such things are difficult to estimate, but even if Knuth is being too pessimistic one need only consider numbers with a few more digits and the task will be made many times harder.

pages: 828 words: 205,338

Write Great Code, Volume 2 by Randall Hyde

But unfortunately, if no thought is put into the performance of the application until the optimization phase, it’s unlikely that optimization will prove practical. The time to ensure that an application has reasonable performance characteristics is at the beginning, during the design and implementation phases. Optimization can fine-tune the performance of a system, but it can rarely deliver a miracle. Although the quote is often attributed to Donald Knuth, who popularized it, it was Tony Hoare who originally said, “Premature optimization is the root of all evil.” This statement has long been the rallying cry of software engineers who avoid any thought of application performance until the very end of the software-development cycle—at which point the optimization phase is typically ignored for economic or time-to-market reasons.

Higher-level data structure information is available in just about any decent college textbook on data structures and algorithm design. There are, literally, hundreds of these books available covering a wide range of subjects. For those interested in a combination of low-level and high-level concepts, a good choice is Donald Knuth’s The Art of Computer Programming, Volume 1 (Third Edition, Addison-Wesley Professional, 1997) This text is available in almost every bookstore that carries technical books. As noted in the previous chapter, textbooks on programming language design and compiler design and implementation are good sources of information about the low-level implementation of data types, including composite data types.

Higher-level data structure information is available in just about any decent college textbook on data structures and algorithm design. There are, literally, hundreds of these books available covering a wide range of subjects. If you are interested in a combination of low-level and high-level concepts, Donald Knuth’s The Art of Computer Programming, Volume I (Addison-Wesley Professional, 1997) is a good choice. This text is available in nearly every bookstore that carries technical books. As noted in the previous chapter, textbooks on programming language design and compiler design and implementation are another good source of information about the low-level implementation of data types, including composite data types such as records, unions, and classes.

pages: 792 words: 48,468

Tcl/Tk, Second Edition: A Developer's Guide by Clif Flynt

After reporting an order, it should be ready to start assembling a new order for that table. 301. Write a script that will accept multiple lines in the form “author, title, and so on.” Clif Flynt, Tcl/Tk: A Developer’s Guide Richard Stevens, TCP/IP Illustrated Donald Knuth, The Art of Computer Programming: Vol 1 Donald Knuth, The Art of Computer Programming: Vol 2 Donald Knuth, The Art of Computer Programming: Vol 3 John Ousterhout, Tcl and the Tk Toolkit Richard Stevens, Unix Network Programming Place this data in an associative array that would allow you to get lists of books by an author. 177 178 Chapter 6 Building Complex Data Structures with Lists and Arrays 302.

pages: 489 words: 117,470

Programming in Lua, Fourth Edition by Roberto Ierusalimschy

If our data file is in a predefined format, such as CSV (Comma-Separated Values) or XML, we have little choice. However, if we are going to create the file for our own use, we can use Lua constructors as our format. In this format, we represent each data record as a Lua constructor. Instead of writing in our data file something like Donald E. Knuth,Literate Programming,CSLI,1992 Jon Bentley,More Programming Pearls,Addison-Wesley,1990 we write this: Entry{"Donald E. Knuth", "Literate Programming", "CSLI", 1992} Entry{"Jon Bentley", "More Programming Pearls", "Addison-Wesley", 1990} Remember that Entry{code} is the same as Entry({code}), that is, a call to some function Entry with a table as its single argument.

For instance, the following program counts the number of entries in a data file: local count = 0 function Entry () count = count + 1 end dofile("data") print("number of entries: " .. count) The next program collects in a set the names of all authors found in the file, and then prints them: local authors = {} -- a set to collect authors function Entry (b) authors[b[1]] = true end dofile("data") for name in pairs(authors) do print(name) end Note the event-driven approach in these program fragments: the function Entry acts as a callback function, which is called during the dofile for each entry in the data file. When file size is not a big concern, we can use name-value pairs for our representation:[15] Entry{ author = "Donald E. Knuth", title = "Literate Programming", publisher = "CSLI", year = 1992 } Entry{ author = "Jon Bentley", title = "More Programming Pearls", year = 1990, publisher = "Addison-Wesley", } This format is what we call a self-describing data format, because each piece of data has attached to it a short description of its meaning.

pages: 1,387 words: 202,295

Structure and Interpretation of Computer Programs, Second Edition by Harold Abelson, Gerald Jay Sussman, Julie Sussman

THUNKS: A way of compiling procedure statements, with some comments on procedure declarations. Unpublished manuscript. (Also, private communication from Wallace Feurzeig.) Kaldewaij, Anne. 1990. Programming: The Derivation of Algorithms. New York: Prentice-Hall. Knuth, Donald E. 1973. Fundamental Algorithms. Volume 1 of The Art of Computer Programming. 2nd edition. Reading, MA: Addison-Wesley. Knuth, Donald E. 1981. Seminumerical Algorithms. Volume 2 of The Art of Computer Programming. 2nd edition. Reading, MA: Addison-Wesley. Kohlbecker, Eugene Edmund, Jr. 1986. Syntactic extensions in the programming language Lisp. Ph.D. thesis, Indiana University. –› Konopasek, Milos, and Sundaresan Jayaraman. 1984.

Producing Open Source Software: How to Run a Successful Free Software Project by Karl Fogel

Far from opposing proprietary software, the X license deliberately allowed proprietary extensions on top of the free core—each member of the consortium wanted the chance to enhance the default X distribution, and thereby gain a competitive advantage over the other members. X Windows[7] itself was free software, but mainly as a way to level the playing field between competing business interests and increase standardization, not out of some desire to end the dominance of proprietary software. Yet another example, predating the GNU project by a few years, was TeX, Donald Knuth's free, publishing-quality typesetting system. He released it under terms that allowed anyone to modify and distribute the code, but not to call the result "TeX" unless it passed a very strict set of compatibility tests (this is an example of the "trademark-protecting" class of free licenses, discussed more in Chapter 9, Legal Matters: Licenses, Copyrights, Trademarks and Patents).

Then they go further: if someone using software under the license initiates patent litigation against another party, claiming that the covered work infringes, the initiator automatically loses all the patent grants otherwise provided for that work by the license, and in the case of the GPL-3.0 loses their right to distribute under the license altogether. protection of "artistic integrity" Some licenses (the Artistic License, used for the most popular implementation of the Perl programming language, and Donald Knuth's TeX license, for example) require that modification and redistribution be done in a manner that distinguishes clearly between the pristine original version of the code and any modifications. They permit essentially the same freedoms as other free licenses, but impose certain requirements that make the integrity of the original code easy to verify.

pages: 504 words: 89,238

Natural language processing with Python by Steven Bird, Ewan Klein, Edward Loper

Computational Linguistics, 32: 485–525, 2006. [Kiusalaas, 2005] Jaan Kiusalaas. Numerical Methods in Engineering with Python. Cambridge University Press, 2005. [Klein and Manning, 2003] Dan Klein and Christopher D. Manning. A* parsing: Fast exact viterbi parse selection. In Proceedings of HLT-NAACL 03, 2003. [Knuth, 2006] Donald E. Knuth. The Art of Computer Programming, Volume 4: Generating All Trees. Addison Wesley, 2006. [Lappin, 1996] Shalom Lappin, editor. The Handbook of Contemporary Semantic Theory. Blackwell Publishers, Oxford, 1996. [Larson and Segal, 1995] Richard Larson and Gabriel Segal. Knowledge of Meaning: An Introduction to Semantic Theory.

Since the calling function simply has to find the maximum value—the word that comes latest in lexicographic sort order—it can process the stream of data without having to store anything more than the maximum value seen so far. 4.3 Questions of Style Programming is as much an art as a science. The undisputed “bible” of programming, a 2,500 page multivolume work by Donald Knuth, is called The Art of Computer Programming. Many books have been written on Literate Programming, recognizing that humans, not just computers, must read and understand programs. Here we pick up on some issues of programming style that have important ramifications for the readability of your code, including code layout, procedural versus declarative style, and the use of loop variables.

pages: 574 words: 164,509

Superintelligence: Paths, Dangers, Strategies by Nick Bostrom

It turned out to be possible to build a perfectly fine chess engine around a special-purpose algorithm.58 When implemented on the fast processors that became available towards the end of the twentieth century, it produces very strong play. But an AI built like that is narrow. It plays chess; it can do no other.59 In other domains, solutions have turned out to be more complicated than initially expected, and progress slower. The computer scientist Donald Knuth was struck that “AI has by now succeeded in doing essentially everything that requires ‘thinking’ but has failed to do most of what people and animals do ‘without thinking’—that, somehow, is much harder!”60 Analyzing visual scenes, recognizing objects, or controlling a robot’s behavior as it interacts with a natural environment has proved challenging.

pages: 923 words: 516,602

The C++ Programming Language by Bjarne Stroustrup

Englewood Cliffs, New Jersey. 1988. ISBN 0-13-110362-8. Andrew Koenig and Bjarne Stroustrup: C++: As close to C as possible – but no closer. The C++ Report. Vol. 1 No. 7. July 1989. Andrew Koenig and Barbara Moo: Ruminations on C++. Addison Wesley Longman. Reading, Mass. 1997. ISBN 1-201-42339-1. Donald Knuth: The Art of Computer Programming. Addison-Wesley. Reading, Mass. Barbara Liskov et al.: Clu Reference Manual. MIT/LCS/TR-225. MIT Cambridge. Mass. 1979. Robert C. Martin: Designing Object-Oriented C++ Applications Using the Booch Method. Prentice-Hall. Englewood Cliffs, New Jersey. 1995. ISBN 0-13-203837-4.

If a ‘‘maintenance crew’’ is left guessing about the architecture of the system or must deduce the purpose of system components from their implementation, the structure of a system can deteriorate rapidly under the impact of local patches. Documentation is typically much better at conveying details than in helping new people to understand key ideas and principles. 23.4.7 Efficiency [design.efficiency] Donald Knuth observed that ‘‘premature optimization is the root of all evil.’’ Some people have learned that lesson all too well and consider all concern for efficiency evil. On the contrary, efficiency must be kept in mind throughout the design and implementation effort. However, that does not mean the designer should be concerned with micro-efficiencies, but that first-order efficiency issues must be considered.

– D– #, preprocessing 813 template instantiation 866 discrimination of exception 188 disguised pointer 844 dispatch, double 326 distance() and - 551, 554 distribution exponential 685 uniform 685 div() 661 divide and conquer, complexity 693 divides / 517 div_t 661 do statement 114, 137 documentation 714– 715 do_it() example 777 domain error 661 dominance 401 Donald Knuth 713 dot product 684 double dispatch 326 quote 830 double 74 output 626 double-ended queue deque 474 doubly-linked list 470 down cast 408 draw_all() example 520 Duff’s device 141 dynamic memory 127, 576, 843 store 34 type checking 727 type checking, mis-use of 439 dynamic_cast 407– 408 and ambiguity 412 and polymorphism 409 and static_cast 413 bad_cast and 384 implementation of 409 to reference 410 use of 774 E eatwhite() 620 eback() 645 EDOM 661 efficiency 8, 713 and coupling 768 and generality 431 of operation 464 egptr() 645 element access 445 Index access, list 472 access, map 482 address of 454 constructor for array 250 first 445 from sequence, delete 529, 534 last 445 object, array 244 requirements for 466 to sequence, add 529 eliminate_duplicates() example 534 eliminating programmers 730 elimination of copying 675 of temporary 675 ellipse, circle and 703 ellipsis ... 154 else 134 emphasis, examples and 5 Employee example 302 empty string 585 empty() 455, 489 string 598 encapsulation 754 complete 283 end, seekdir and end() 54, 481 basicstring 584 iterator 444 #endif 162 endl 634 ends 634 engineering, viewgraph 704 enum 76 and integer 77 bitset and 492 conversion, undefined 77 difference from C 817 member 249 sizeof 78 user-defined operator and 265 enumeration 76 switch on 77 enumerator 76 EOF 620, 653 eof() 616 char_traits 581 eofbit 617 epptr() 645 epsilon() 659 eq(), char_traits 581 eq_int_type(), char_traits 581 equal() 527 equality and comparison 457 hash_map 497 The C++ Programming Language, Third Edition by Bjarne Stroustrup.

Software Design for Flexibility by Chris Hanson, Gerald Sussman

Oxford: Oxford University Press, 2001. [132]Ramin Zabih, David McAllester, and David Chapman; “Non-deterministic Lisp with dependency-directed backtracking,” in AAAI-87. (1987): 59–64. Index Any inaccuracies in this index may be explained by the fact that it has been prepared with the help of a computer. Donald E. Knuth, Fundamental Algorithms (Volume 1 of The Art of Computer Programming) Page numbers for Scheme procedure definitions are in italics. Page numbers followed by n indicate footnotes. % naming convention, 152 ! naming convention, 393 n λ (lambda) calculus, 1 n λ expression. See lambda λ notation, 380 n π (pi), 381 +->interval, 333 ’ (quote in Scheme), 390 ‘ (backquote in Scheme), 391 , (comma) in backquote, 391 - (negation or subtraction), 390 pattern-directed, 168 . in formal parameters, 267 (ex. 5.12), 389 . in printed representation of pair, 387 / in rational constant, 47 ;.

, 72 Integrated Development Environment (IDE), 321 (ex. 6.4) Integrating differential equations, 68–70, 256 (ex. 5.8) Internal definitions in Scheme, 24, 383, 385 Interpreter, 233–254 Intervals in measurements, 332–336 merging, 352 invert-address, 219 iota, 112 n Iteration in Scheme, 385 Java, 1 n, 6, 22 n chaining, 146 combinators, 65 interfaces, 6 n Jonge, Joost Kiewiet de, 334 n Justification, annotation of, 322 Kahn, Louis Isadore, 5 Kanizsa, Gaetano, 328 Kanizsa's triangle illusion, 328, 328 (fig. 7.1) Kirschner, Marc W., 9 n, 14 n Knuth, Donald E., 409 Kowalski, Robert M., 271 Kutsia, Temur, 203 n lambda ’.’ or symbol for rest parameters, 248 n, 267 (ex. 5.12), 389 in evaluator, 239 in Scheme, 380 lambda (λ) calculus, 1 n lambda?, 239 lambda-body, 239 lambda-parameters, 239 layer-accessor, 305 layered-datum, 303 layered-extender, 310 Layered arithmetic, 309–310 Layered data, 302–305 Layered procedure, 301, 305–309, 352 Layering, 4, 299.

pages: 230

Purely Functional Data Structures by Chris Okasaki

In Glasgow Workshop on Functional Programming, pages 141-150, September 1994. (pp. 29, 82) Chan Meng Khoong and Hon Wai Leong. Double-ended binomial queues. In International Symposium on Algorithms and Computation, volume 762 of LNCS, pages 128-137. SpringerVerlag, December 1993. (p. 169) Donald E. Knuth. Searching and Sorting, volume 3 of The Art of Computer Programming. Addison-Wesley, 1973. (pp. 18, 29) Donald E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison-Wesley, 1973. (p. 116) Haim Kaplan and Robert E. Tarjan. Persistent lists with catenation via recursive slow-down. In ACM Symposium on Theory of 212 Bibliography Computing, pages 93-102, May 1995.

The Art of Computer Programming: Fundamental Algorithms by Donald E. Knuth

DONALD E. KNUTH Stanford University :']¦ ADDISON-WESLEY An Imprint of Addison Wesley Longman, Inc. Volume 1 / Fundamental Algorithms THE ART OF COMPUTER PROGRAMMING THIRD EDITION Reading, Massachusetts • Harlow, England • Menlo Park, California Berkeley, California • Don Mills, Ontario • Sydney Bonn • Amsterdam • Tokyo • Mexico City is a trademark of the American Mathematical Society METflFONT is a trademark of Addison-Wesley Library of Congress Cataloging-in-Publication Data Knuth, Donald Ervin, 1938- The art of computer programming : fundamental algorithms / Donald Ervin Knuth. — 3rd ed. xx,650 p. 24 cm.

Kirchhoff, Gustav Robert, 406, 583. law of conservation of flow, 97, 170-171, 268, 278, 364-370, 380. Kirkman, Thomas Penyngton, 408. Kirschenhofer, Peter, 506. Klarner, David Anthony, 86. Kleitman, Daniel J (Isaiah Solomon), 547, 596. Knopp, Konrad Hermann Theodor, 48, 498. Knotted lists, 459. Knowlton, Kenneth Charles, 462. Knuth, Donald Ervin (]^^^), ii, iv, xi, 11, 33, 66, 120, 193, 201, 202, 296, 297, 395, 457, 461, 471, 484, 499, 504, 523, 525, 565, 579, 580, 584, 592, 596, 631, 650. Knuth, Nancy Jill Carter (Tti^jf B Kolmogorov, Andrei Nikolaevich (KojiMoropoB, AHflpe 104, 105, 464. Konig, Denes, 382, 406, 588. Koster, Cornelis (= Kees) Hermanus Antonius, 461.

The Art of Computer Programming: Sorting and Searching by Donald Ervin Knuth

DONALD E. KNUTH Stanford University TT ADDISON-WESLEY An Imprint of Addison Wesley Longman, Inc. Volume 3 / Sorting and Searching THE ART OF COMPUTER PROGRAMMING SECOND EDITION Reading, Massachusetts • Harlow, England • Menlo Park, California Berkeley, California • Don Mills, Ontario • Sydney Bonn • Amsterdam • Tokyo • Mexico City is a trademark of the American Mathematical Society METRFONT is a trademark of Addison-Wesley Library of Congress Cataloging-in-Publication Data Knuth, Donald Ervin, 1938- The art of computer programming / Donald Ervin Knuth. — 2nd ed. xiv,780 p. 24 cm. Includes bibliographical references and index.

Wijngaarden, Adriaan van, 1916- Remarks Initials are like one-letter words Ignore initial article Ignore punctuation in titles Ignore initial "al-" in Arabic names Respell it "Labor" Cross-reference card Ignore apostrophe in English Me = Mac Treat hyphen as space Ignore designation of rank "Mrs." = "Mistress" Don't ignore British royalty "St." = "Saint", even in German Treat hyphen as space Sainte (a book by Donald Ervin Knuth) (a book by Harriet Beecher Stowe) "U. S." = "United States" Ignore space after prefix in surnames Ignore initial article Ignore apostrophe in English Surname begins with upper case letter (Most of these rules are subject to certain exceptions, and there are many other rules not illustrated here.)

Kislitsyn, Sergei Sergeevich (KncjiimbiH, Cepreii CepreeBHn), 197, 209, 210, 212, 217, 661. Klarner, David Anthony, 585. Klein, Christian Felix, 745. Klein, Rolf, 714. Kleitman, Daniel J (Isaiah Solomon), 452, 454, 669, 744. Klerer, Melvin, 297, 388. Knockout tournament, 141-142, 207, 210, 212. Knott, Gary Don, 21, 434, 519, 529, 709, 710. _^ Knuth, Donald Ervin (i§)@^), ii, iv, vii, 8, 58, 152, 226, 297, 385, 389, 395, 398, 420, 422, 454, 478, 536, 585, 594, 600, 604, 627, 634, 658, 670, 696, 702, 713, 722, 734, 736, 741, 742, 760, 780. Koch, Gary Grove, 578. Koester, Charles Edward, 390. Kohler, Peter, 669. Kollar, Lubor, 656, 660. Komlos, Janos, 228, 549, 673, 740.

pages: 666 words: 181,495

In the Plex: How Google Thinks, Works, and Shapes Our Lives by Steven Levy

Soon after arriving at Stanford, he knocked off all the required tests for a doctorate and was free to sample the courses until he found a suitable entree for a thesis. He supplemented his academics with swimming, gymnastics, and sailing. (When his father asked him in frustration whether he planned to take advanced courses, he said that he might take advanced swimming.) Donald Knuth, a Stanford professor whose magisterial series of books on the art of computer programming made him the Proust of computer code, recalls driving down the Pacific coast to a conference with Sergey one afternoon and being impressed at his grasp of complicated issues. His adviser, Hector Garcia-Molina, had seen a lot of bright kids go through Stanford, but Brin stood out.

pages: 728 words: 182,850

Cooking for Geeks by Jeff Potter

Have fun! I was talking with a friend of mine, a fellow geek who was just starting to learn to cook, when he said: I was never that curious about cooking, so I thought that buying The Joy of Cooking and going through it would be the right approach. That’s probably like sitting down with Donald Knuth’s The Art of Computer Programming in order to learn to program, when really all you should be doing at first is trying to make something you like. He’s right: make something you like, give yourself enough time to enjoy the process, and have fun doing it. Slaving through the Joy or Knuth will work, but it’s not the way most people learn to cook or write code.

pages: 203 words: 14,242

Ship It!: A Practical Guide to Successful Software Projects by Jared R. Richardson, William A. Gwaltney

Regular expressions are the most powerful way to process text we’ve ever come across, but the “Here Be Dragons” factor is extremely high. This book handily slays the little beasties. The Mythical Man-Month by Frederick Brooks. Will realized after reading this book (the ﬁrst edition, in college no less!) how much more there is to software development than simply coding up a program. The Art of Computer Programming by Donald Knuth. There are multiple volumes in this set. They are a comprehensive introduction to classical computer science. Death March: The Complete Software Developer’s Guide to Surviving “Mission Impossible” Projects by Edward Youdon. Death March projects are famous in the software industry. Understand them so you don’t get swept along by them.

pages: 303 words: 57,177

Hands-On Functional Programming in RUST by Andrew Johnson

In this chapter, we will learn the following: Recognizing and applying good performant code practices Diagnosing and improving performance bottlenecks Recognizing and applying good defensive coding practices Diagnosing and resolving software bugs Recognizing and applying metaprogramming techniques Technical requirements A recent version of Rust is necessary to run the examples provided: https://www.rust-lang.org/en-US/install.html This chapter's code is available on GitHub: https://github.com/PacktPublishing/Hands-On-Functional-Programming-in-RUST Specific installation and build instructions are also included in each chapter's README.md file. Writing faster code Premature optimization is the root of all evil – Donald Knuth A good software design tends to create faster programs, while a bad software design tends to create slower programs. If you find yourself asking, "Why is my program slow?, then first ask yourself, Is my program disorderly?" In this section, we describe some performance tips. These are generally good habits when programming in Rust that will coincidentally lead to improved performance.

pages: 292 words: 62,575

97 Things Every Programmer Should Know by Kevlin Henney

For example, if the problem domain dictates that there can never be more than five items (like the number of dice in a Yahtzee game), you know that you always have to sort at most five items. In that case, bubble sort might actually be the most efficient way to sort the items. Every dog has its day. So, read some good books—and make sure you understand them. And if you really read Donald Knuth's The Art of Computer Programming (Addison-Wesley Professional), well, you might even be lucky: find a mistake by the author, and you'll earn one of Don Knuth's hexadecimal dollar ($2.56) checks. Chapter 90. Verbose Logging Will Disturb Your Sleep Johannes Brodwall WHEN I ENCOUNTER A SYSTEM that has already been in development or production for a while, the first sign of real trouble is always a dirty log. pages: 262 words: 65,959 The Simpsons and Their Mathematical Secrets by Simon Singh However, on average, the number of random numbers required to exceed 1 is 2.71828..., which, of course, is e. There are numerous other examples demonstrating that e plays a diverse and fundamental role in several areas of mathematics. This explains why so many number lovers have a particularly emotional attachment to it. For example, Donald Knuth, professor emeritus at Stanford University and a godlike figure in the world of computing, is an e enthusiast. After authoring Metafont, his font-creation software, he decided to release updates with version numbers that relate to e. This means that the first version was Metafont 2, then Metafont 2.7, then Metafont 2.71, and so on up to the current Metafont 2.718281. pages: 525 words: 149,886 Higher-Order Perl: A Guide to Program Transformation by Mark Jason Dominus One string commonly used when a zero-but-true value is desired is "0 but true". Perl’s warning system has a special case in it that suppresses the usual “isn’t numeric” warning for this string. (back) Chapter 4 1 The Perl Journal, Vol 1, #2 (Summer 1996) pp. 5–9. (back) 2 The Art of Computer Programming, Volume II: Seminumerical Algorithms, Donald E. Knuth, Addison–Wesley. (back) 3 There are, unfortunately, very few good robots. (back) Chapter 5 1 Stay away from the windows if you’re ever in Prague; the city is famous for its defenestrations. Probably the most important was on 23 March, 1618, when Bohemian nobles flung two imperial governors out the window into a ditch, touching off the Thirty Years’ War. Joseph Raphson discovered the technique independently and published it in 1671. (back) 6 Actually they’re alternating between 1.414213562373094923430016933708 and 1.414213562373095145474621858739, but who’s counting? (back) 7 It may not be obvious that the hare will necessarily catch the tortoise, but it is true. For details, see Donald Knuth, The Art of Computer Programming: Volume 2, Seminumerical Algorithms, exercise 3.1.6. (back) 8 It also requires a bit of a trick. Say S = 1 + k + k2 + ··· + kn − 1. Multiplying both sides by k gives Sk = k + k2 + ··· + kn − 1 + kn. These two equations are almost the same, and if we subtract one from the other almost everything cancels out, leaving only Sk − S = kn − 1 and so S = (kn − 1) / (k − 1). pages: 598 words: 183,531 Hackers: Heroes of the Computer Revolution - 25th Anniversary Edition by Steven Levy They didn’t make it in time, and Woods remembered what that misty dawn looked like and wrote it into the description of that scene in the game, which he conceived of over breakfast that morning. It was at Stanford that gurus were as likely to be faculty people as systems hackers (among Stanford professors was the noted computer scientist Donald Knuth, author of the multivolume classic The Art of Computer Programming). It was at Stanford that, before the Adventure craze, the casual pleasures of Spacewar were honed to a high art (Slug Russell had come out with McCarthy, but it was younger hackers who developed five-player versions and options for reincarnation, and ran extensive all-night tournaments). Greenblatt was still hacking away, as was Knight, and a few newer hackers were proving themselves masters at systems work . . . but others were leaving, or gone. Now, Bill Gosper headed West. He arranged to stay on the AI lab payroll, hacking on the ninth-floor PDP-6 via the ARPAnet, but he moved to California to study the art of computer programming with Professor Donald Knuth at Stanford. He became a fixture at Louie’s, the best Chinese restaurant in Palo Alto, but was missing in action at Tech Square. He was a mercurial presence on computer terminals there but no longer a physical center of attention, draped over a chair, whispering, “Look at that,” while the 340 terminal pulsed insanely with new forms of LIFE. pages: 931 words: 79,142 Concepts, Techniques, and Models of Computer Programming by Peter Van-Roy, Seif Haridi Prentice Hall, Englewood Cliﬀs, NJ, 1988. [113] Gregor Kiczales, Jim des Rivières, and Daniel G. Bobrow. The Art of the Metaobject Protocol. MIT Press, Cambridge, MA, 1991. Donald E. Knuth. The Art of Computer Programming: Seminumerical Algorithms, volume 2. Addison-Wesley, Reading, MA. [114] [115] Donald E. Knuth. The Art of Computer Programming: Fundamental Algorithms, volume 1. Addison-Wesley, Reading, MA, 1973. [116] Donald E. Knuth. Structured programming with go to statements. Computing Surveys, 6(4):261–301, December 1974. Leif Kornstaedt. Gump–a front-end generator for Oz. Technical report, Mozart Consortium, 2003. ., 441, 621 fold operation, 185 FoldL, 187, 465, 829 FoldR, 187 stream objects, 258 for statement, 188 for loop, 447 ForAll operation, 829 formal language, 33 forward chaining, 674 forwarding, 512 foundational calculus, xvii framework computation model, 844 software reuse, 492 France, 411 free identiﬁer occurrence, 58, 64, 633 free memory, 75 freeze/2 operation (in Prolog), 662 French, Michael, 569 fresh name, 203 variable, 787 full adder, 268 fun statement, 84 function, 84 generating, 170 incremental, 296 introduction, 2 lazy, 797 monolithic, 296 monotonic, 849 partially applied, 194 876 Index state transition, 351 functional decomposition, 135, 542 functional look, 196 functor, 221, 454 distributed resource, 709, 730 interactive use, 816 main, 222 Oz 3, 809 functor statement, 223 future, 336 future operation (in Multilisp), 336 Gamma, Erich, 534 garbage collection, 74, 75 copying dual-space, 78 distributed, 734 external references, 480 ﬁnalization, 481 generational, 78 lease-based, 734, 738 program pause, 76, 308 real-time, 76 root set, 76 weighted reference counting, 734 Gardner, Martin, 774 gate statement, 272 gate (digital logic), 267 Gaussian distribution, 476, 477 Gelernter, David, 586 generalization, 568 generate-and-test, 629, 758 generating function, 170 genericity, 180–182 object-oriented programming, 524 static and dynamic, 526 global condition ordered binary tree, 154 producer/consumer throughput, 261 reachability, 75 GlobalStore, 743 glue (in GUI), 687 Glynn, Kevin, 308 Gödel’s completeness theorem, 634 Gödel’s incompleteness theorem, 634 Gödel, Kurt, 634 Goodman, Nathan, 600 Gosling, James, 537 grammar, 31–36 ambiguous, 34, 166 context-free, 33 context-sensitive, 33 deﬁnite clause (DCG), 140, 650 disambiguation, 34 EBNF (Extended Backus-Naur Form), 32, 671 left-recursive, 644 natural language, 643 nonterminal symbol, 32, 163 terminal symbol, 32, 163 uniﬁcation, 649–650 graph bushy, 461 component, 461 distribution model, 735 Haskell expression, 310 hierarchical, 461 implementation, 464 inheritance, 502 nonlocal, 461 path, 463, 658 small world, 461 Gray, Jim, 582, 600 green cut (in Prolog), 669 Gregorian calendar, 693 Grolaux, Donatien, 689, 691 grue cut (in Prolog), 669 guard ask operation, 782 concurrent logic programming, 397 CSP, 619 Erlang, 388 Haskell, 309 list comprehension, 302 monitor, 595 Prolog, 669 quiet (in Prolog), 669 Index 877 receive expression (in Erlang), 391, 402 guarded method, 595 guardian, 481 GUI (Graphical User Interface) AWT (Abstract Window Toolkit) package, 679 component-based programming, 461 design, 679 Haskell fudgets, 679 model-based, 695 Prototyper tool, 689 QTk, 213, 680, 729 interactive use, 214, 684 use in application, 225 read-only view, 695 Swing components, xxi, 679 text input/output, 213 Visual Studio, 679 Hadzilacos, Vassos, 600 halting problem, 209, 681 Hamming problem, 293, 342 Hamming, Richard, 293 handler event, 563 exception, 90, 91 ﬁnalization, 481 GUI design, 213, 683, 682–688 HasFeature operation, 826 hash table, 438, 439 Haskell, 308–313 Helm, Richard, 534 Herbert, Frank, 749 heuristic best ﬁrst, 672 distribution strategy, 755, 766 Hewitt, Carl, 345 hexadecimal integer, 820 higher-order programming, 113, 177– 194 introduction, 13 iteration abstraction, 123 library operations, 830 relation to OOP, 538 history ADT language, 420 computer technology, 176 concurrent constraint programming, 663, 808 dangers of concurrency, 21 declarative concurrency, 337 functional programming, 96 incremental development, 451 object-oriented programming, 489 Oz, xxiv, 809 programming languages, 406 Prolog, 661 remote invocation, 709 Hoare, Charles Antony Richard, 232, 441, 592 Horn clause, xxi, 635, 640, 650, 663 hot spot, 177 HTML (Hypertext Markup Language), 115, 679 Hudak, Paul, 96, 314 IBM Corporation, 41 IDE (Interactive Development Environment), xxix IDE (interactive development environment), 815 identiﬁer, 2, 44 bound occurrence, 64 escaped, 509 free occurrence, 58, 64, 633 IEEE ﬂoating point standard, 544, 820 if statement, 66, 790 IID (Iterative and Incremental) software development, 451 ILOG Solver, 663 impedance matching, 324 concurrency, 576 event manager example, 567 imperative, 406 implementation, 410 878 Index import clause (in functor), 221 inactive memory, 75 incompleteness, 634 inconsistency, 787 incremental function, 295 incremental software development, 451 independence components, 363, 455 compositional design, 461 concepts, xvii concurrency, 14, 20, 89, 233 declarative loop, 189 declarative programming, 111 Erlang processes, 386 garbage collection, 76 message passing, 387 modularity, 319 multiple inheritance, 533 open programming, 105, 326, 714 polymorphism, 429 principle, 457 put and get (in queue), 381 reasoning with invariant assertions, 441 search and distribution strategies, 761 software deployment, 221 India, xiii inﬁnite precision arithmetic, 3 inﬁnity (ﬂoating point), 822 informatics, xxi curriculum, xxii success of object-oriented programming, 489 usefulness of computation models, xiv Information Cities project, 412 information systems, xxi inheritance, 19, 413, 420, 491 avoiding method conﬂicts, 511 cautionary tale, 521 design patterns, 534 directed and acyclic, 503 event manager, 564 factoring, 492 generalization, 568 graph, 502 implementation, 550 implementation-sharing problem, 533 Java, 551 multiple, 503, 527 rules of thumb, 533 simple, 503 single, 503, 531 software reuse, 492 static and dynamic binding, 504 structure view, 519 thread priority, 253 type view, 518 upward, 568 inherited argument, 161 Inject operation, 772 instantiation, 182–183, 411 integer arbitrary precision, 3, 821 arithmetic, 821 number, 819 tilde ˜ as minus sign, 820 interactive interface, 87 interactive system GUI design, 213 Mozart IDE, 815 pedagogical use, xix reaction time guarantees, 174 interface, 419 general concept, 221 inheritance, 492 Java, 551 Runnable (in Java), 616 interface builder, 679 interleaving semantics, 237, 780 Internet, 207, 345, 353, 707, 711, 717 simulation of Web use, 476 interoperability, 106 interpreter, 42 approach to deﬁne semantics, 41 Index 879 generic parser, 650 GUI description, 703 meta, 654, 676 metacircular, 42 original Erlang, 388 Prolog arithmetic, 664 QTk module, 703 intractable problems, 176 IntToFloat operation, 822 invariant, 134, 382, 412, 441 IP (Internet Protocol), 206 IsAtom operation, 824 IsChar operation, 823 IsDet operation, 319, 321, 333, 394, 660, 803, 849 IsFailed operation, 803 IsLock operation, 583 ISO 8859-1 character code, 820, 824 isolation, 600 IsProcedure function, 55 IsRecord operation, 826 I-structure, 336, 469, 811 IsTuple operation, 827 iterative software development, 451 Janson, Sverker, xxvi, 663 Japan, 397 Java, 551–556, 615–617 monitor semantics, 592 JavaBeans, 462 Jeﬀerson, Thomas, 9 Johnson, Ralph, 534 journaling, 532 Kahn, Gilles, 337 kernel language, see computation model kernel language approach, xvi, 36–42 choice of formalism, xix keywords (table of), 839 Knuth, Donald Ervin, 170, 472 Kowalski, Robert A., 406 Kurzweil, Raymond, 176 KWIC (keyword in context) index, 666 Label operation, 54, 826 label (record identiﬁcation), 19, 52 λ calculus, xvii, 41, 97, 331, 344, 792, 805, 811, 846 LAN (local area network), 353, 717, 739 language AKL, xxvi, 661, 809 Absys, 406, 621 Ada, 432, 619 Algol, 406, 432, 489 declarative concurrent, 337 nondeterministic, 622 Alice, 106 C++, 43, 48, 75, 180, 334, 445, 486, 489, 504, 508–510, 535, 540, 545, 551, 663, 761 C-Linda, 586 CLOS (Common Lisp Object System), 516 CLU, 420 CSP (Communicating Sequential Processes), 619 Clean, 313 Cobol, 544 Common Lisp, 59, 190 Concurrent Haskell, xx Concurrent ML, xx, 851 Concurrent Prolog, 397 C, 75, 179, 661 Eiﬀel, 519, 521, 850 Erlang, 75, 98, 326, 345, 386–394, 429, 456, 545, 563, 582, 807, 851 E, 208 FCP (Flat Concurrent Prolog), 397, 807 FP, 329 Flat GHC, 397 Fortran, 406, 642 parsing problem, 642 GHC (Guarded Horn Clauses), 397 Haskell, xiv, xvi, 43, 75, 98, 116, 880 Index 137, 194, 272, 279, 286, 308– 313, 329, 331, 334, 337, 342, 457, 545, 679, 807 IC-Prolog, 397 Id, 337, 811 Java, xiv, xvi, 41, 43, 48, 75, 180, 334, 356, 428, 430, 445, 462, 486, 489, 504, 508–510, 535, 540, 543–545, 551–556, 567, 581, 592, 615–617, 679, 807, 850 monitor, 592 Leda, xvii Linda extension, 586, 619, 808 Lisp, xiv, 5, 39, 59, 75, 76, 129, 406, 544, 650, 664, 828 ML, see Standard ML, Concurrent ML, Objective Caml Mercury, xiv, 116, 313, 663, 807 Miranda, 279, 342 Multilisp, 336, 811 Objective Caml, 543 Obliq, 722 Oz 1, Oz 2, Oz 3, 809 Oz, xix, xxvi, 313, 507, 545, 663, 807, 844, 851 PL/I, 642 parsing problem, 642 Parlog, 397 Pascal, 161, 179, 430, 807 Prolog, xiv, xvi, xxi, 5, 29, 48, 75, 116, 140, 142, 272, 287, 329, 334, 388, 397, 406, 545, 621– 623, 635, 640, 642, 649, 654, 656–660, 660–671, 807, 851 pure, 640 SICStus, 190, 663 Scheme, xiv, xvi, xvii, xx, 29, 43, 59, 97, 98, 286, 545, 807 Simula, 406, 489 Smalltalk, xiv, 43, 75, 334, 489, 507, 509, 510, 516, 540, 543, 544, 850 Standard ML, xiv, xx, 29, 43, 97, 98, 116, 137, 194, 286, 313, 330, 807 Visual Basic, 461 pH (parallel Haskell), 337, 811 tcl/tk, 679, 680, 703 assembly, 209, 313, 406, 551, 622 coordination, 586 ﬁrst-order, 177 formal, 33 higher-order, 177 multiparadigm, xvii natural, xiii, 31, 38, 641 nonstrict, 331 popular computation models, 807 practical, 31 secure, 208 speciﬁcation, 116 symbolic, 53, 545 language design abstraction life cycle, 40 declarative, 329 golden age, 406 layered, 850 lazy execution, 329 object properties, 543 trade-oﬀs, 811 Lao-tzu, 278 last call optimization, 72 latch (digital logic), 270 late error detection (at run time), 503 latency, 263 tolerance, 335 LATEX 2ε typesetting system, 459 Latin-1, 458 law Clarke’s second, 104 Clarke’s third, 314 contrapositive, 632 De Morgan’s, 632 Moore’s, 176, 622 stack ADT, 195 layered language design, 850 lazy evaluation, 98 coroutining, 574 Index 881 explicit, 183 Haskell, 310 relation to call by need, 433, 485 relation to nonstrict evaluation, 331 schedule, 343 strictness analysis, 289, 310, 342 lazy execution, 278 bounded buﬀer, 263 ﬂow control, 261 Hamming problem, 293 higher-order programming, 193 incremental, 295 introduction, 11 monolithic, 296, 342 needs ﬁnalization, 481 relation to synchronization, 334 lazy failure detection, 739 Lea, Doug, 581 legal program, 31 Length operation, 829 lex/yacc parsing, 642 lexical analyzer, 32 lexical scope, see scope, lexical lexical syntax (of Oz), 839 lexically scoped closure, see procedure value lexicographic order (of atoms), 55, 824 Ley, Willy, 621 library, 229 MOGUL (Mozart Global User Library), 222 Mozart Base and System modules, 229 Mozart Standard Library, 214, 225, 685, 690 universal, 621 life cycle abstraction, 40 memory block, 75 LIFO (last-in, ﬁrst-out), 491 lift control system, 365 lifting booleans to streams, 271 serializability, 600 synchronization, 358 lightweight transaction, 601 Linda (tuple space), 586 linguistic abstraction, 38–39, 124 case (pattern matching), 790 class, 548 conc (concurrent composition), 278 delegation, 514 for loop, 188, 447 fun (function), 84 functor (software component), 223 gate (logic gate), 271 local vs. global translation, 844 macro (in Lisp), 39 monitor, 593 parameter passing, 434 protected scope (Java), 567 while loop, 447 linking, 211, 222, 224, 229, 455, 817 component, 223, 459 dynamic, 284 failure detection in Erlang, 387 Linux operating system, xxvi, 201, 471, 499 Liskov, Barbara, 420 list, 52, 128, 828 circular, 829 complete, 53, 829 diﬀerence, 141 advantage, 145 ﬂattening, 143 incomplete, 440 introduction, 4 nested, 135 partial, 440, 829 usage trade-oﬀs, 439 list comprehension, 301 list pair, 52, 828 literal, 824 liveness, 602 882 Index local statement, 56, 63, 786 lock, 579, 582–583 distributed, 721 get-release, 598 implementation, 590 introduction, 21 Java, 616 read, 620 simple, 591 thread-reentrant, 591 transaction, 602 write, 620 lock statement, 22, 583 locus of control, 274 logic combinational, 267 gate, 267 predicate calculus, 633 propositional, 632 sequential, 269 temporal, 603 logic program, 634 logic programming, 44, 406, 632 diﬀerence list, 142 process model, 395, 807 uniﬁcation, 101 logical equivalence, 243, 785 conﬁguration, 805 logical formula, 633 logical semantics, 38, 631–641 logical sentence, 633 assertion, 441 invariant, 441 Louis XIV, 405, 410 Loyd, Sam, 774 Lully, Raymond (Llull, Ramón), 621 Lynch, Nancy, 353 Mac OS X operating system, xxiv, xxvi, 254 Macintosh computer, xxvi MacQueen, David, 337 macro alias (in QTk), 680 Lisp, 39, 544 loop (in Common Lisp), 190 Maher, Michael, 662, 808 mailbox, 456 Erlang, 386 implementation, 391 maintainability, 458 inheritance, 492 polymorphism, 425 MakeRecord operation, 165, 549, 695, 826 MakeTuple operation, 373, 827 Manchester Mark I, 36 Manna, Zohar, 441 many-to-one communication, 351 Map operation, 190, 466, 829 Mariner I (software error), 643 marshaling, 709 master-slave, 732 mathematical induction, 9 matrix graph representation, 464 list of lists implementation, 232 Max operation, 194 McCloud, Scott, 482 Member operation, 829 memoization, 417, 457 calendar example, 694 call by need, 434 declarative programming, 315 explicit state, 25, 694 uniﬁcation, 102 memory address in abstract machine, 56 consumption, 172 content-addressable, 587 leak, 75 choice point, 668 Prolog, 668 life cycle, 75 memory management, 72–78, 480– 482 C, 180 garbage collection, 75 Index 883 Pascal, 180 Merge operation, 771 message, 499 message-passing concurrency, see object, active, see object, port meta-interpreter, 654, 676 meta-object protocol, see protocol, meta-object method object, 19, 497 wrapping, 516 methodology, see software development Meyer, Bertrand, 450, 491, 521, 527 Microsoft Corporation, 462, 679 middle-out software development, 451 mind of programmer capabilities (atoms vs. names), 510 diﬀerence list, 145 enforcing encapsulation, 420 language design trade-oﬀs, 811 order-determining concurrency, 273 state (implicit vs. explicit), 408 use of constraints, 274 minus sign (use of tilde ˜), 820 Mnesia (Erlang database), 387 mod (integer modulo) operation, 54, 821 model computation, 29, see computation model dialog (in GUI), 695 domain (in GUI), 695 GUI formalism, 695 logical semantics, 633 presentation (in GUI), 695 programming, 29 model-based GUI design, 695 modularity, xxi, 315, 409, 458 encapsulated search, 625 inadequacy of declarative model, 315 reengineering, 522 relation to concurrency, 239, 252, 319 relation to explicit state, 315 relational model, 660 system decomposition, 457 module, 183, 220, 454 Array, 436 Atom, 824 Browser, 224 Char, 821, 823 Compiler, 690, 815 Connection, 715, 732 Dictionary, 437 Distribution (supplement), 718 FD, 775 Fault, 739, 743 File (supplement), 211, 292, 564 Finalize, 481 Float, 821 Int, 821 List, 258, 385, 829 Module, 224, 413, 455, 730, 817 MyList (example), 222 Number, 14, 54, 182, 821 OS, 371, 609, 692, 699, 730 ObjectSupport, 517 Open, 564, 729 Pickle, 216, 223, 717 Port, 673 Property, 93, 253, 255 QTk, 213, 680, 729 interactive use, 214, 684 use in application, 225 Record, 826 Remote, 255, 732 Search, 776 Space, 654, 763 String, 824 Thread, 255, 276 Time, 304 Tk, 703 Tuple, 827 Value, 328, 830 884 Index Base, 222, 229, 729 compilation unit, 454 dynamic linking, 285 failure, 329 dynamic typing, 105 Erlang, 389 importing, 224 interface, 455 library, 229 resource, 729, 746 speciﬁcation, 221 System, 222, 229, 729 MOGUL (Mozart Global User Library), 222 monad, xxi, 309, 332 monitor, 579, 592–600 condition variable, 598 guarded method, 595 implementation, 597 Java language, 616 Java semantics, 592 monolithic function, 296 stateful programming, 471 monotonicity, 849 constraint programming, 766 dataﬂow variable, 336, 570 need(x) predicate, 796 need property, 283 store, 781 thread reduction, 239, 781, 782 Moore’s law, 176, 622 Moore, Gordon, 176 Morrison, J. pages: 462 words: 172,671 Clean Code: A Handbook of Agile Software Craftsmanship by Robert C. Martin He stopped an old man on the corner and asked him how to get to Carnegie Hall. The old man looked at the violinist and the violin tucked under his arm, and said: “Practice, son. Practice!” Bibliography [Beck07]: Implementation Patterns, Kent Beck, Addison-Wesley, 2007. [Knuth92]: Literate Programming, Donald E. Knuth, Center for the Study of Language and Information, Leland Stanford Junior University, 1992. 2 Meaningful Names by Tim Ottinger Introduction Names are everywhere in software. We name our variables, our functions, our arguments, classes, and packages. We name our source files and the directories that contain them. This abstraction isolates all of the specific details of obtaining such a price, including from where that price is obtained. Bibliography [RDD]: Object Design: Roles, Responsibilities, and Collaborations, Rebecca Wirfs-Brock et al., Addison-Wesley, 2002. [PPP]: Agile Software Development: Principles, Patterns, and Practices, Robert C. Martin, Prentice Hall, 2002. [Knuth92]: Literate Programming, Donald E. Knuth, Center for the Study of language and Information, Leland Stanford Junior University, 1992. 11 Systems by Dr. Kevin Dean Wampler “Complexity kills. It sucks the life out of developers, it makes products difficult to plan, build, and test.” —Ray Ozzie, CTO, Microsoft Corporation How Would You Build a City? The Art of Computer Programming by Donald Ervin Knuth DONALD E. KNUTH Stanford University TT ADDISON-WESLEY An Imprint of Addison Wesley Longman, Inc. Volume 2 / Seminumerical Algorithms THE ART OF COMPUTER PROGRAMMING THIRD EDITION Reading, Massachusetts • Harlow, England • Menlo Park, California Berkeley, California ¦ Don Mills, Ontario • Sydney Bonn • Amsterdam • Tokyo ¦ Mexico City is a trademark of the American Mathematical Society METRFONT is a trademark of Addison-Wesley The quotation on page 61 is reprinted by permission of Grove Press, Inc. Library of Congress Cataloging-in-Publication Data Knuth, Donald Ervin, 1938- The art of computer programming / Donald Ervin Knuth. — 3rd ed. xiv,762 p. 24 cm. Library of Congress Cataloging-in-Publication Data Knuth, Donald Ervin, 1938- The art of computer programming / Donald Ervin Knuth. — 3rd ed. xiv,762 p. 24 cm. Includes bibliographical references and index. Contents: v. 1. Fundamental algorithms. — v. 2. Seminumerical algorithms. ISBN 0-201-89683-4 (v. 1) ISBN 0-201-89684-2 (v. 2) 1. Electronic digital computers—Programming. 2. Computer algorithms. I. Title. QA76.6.K64 1997 005.1—DC21 97-2147 CIP Internet page http://www-cs-faculty.stanford.edu/~knuth/taocp.html contains current information about this book and related books. Copyright © 1998 by Addison Wesley Longman All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form, or by any means, electronic, mechanical, photo- photocopying, recording, or otherwise, without the prior consent of the publisher. Khinchin, Alexander Yakovlevich (Xhhhhh, AjieKcaH^p ^KOBJieBHH), 356, 652. Kinderman, Albert John, 130-131, 135. Klarner, David Anthony, 213. Klem, Laura, 27. Knop, Robert Edward, 136. Knopfmacher, Arnold, 345, 686. Knopfmacher, John Peter Louis, 345. Knopp, Konrad Hermann Theodor, 364. Knorr, Wilbur Richard, 335. Knott, Cargill Gilston, 627. Knuth, Donald Ervin (ifi) fi^}), ii, iv, vii, 2, 4, 30, 89, 138, 145, 159, 196, 205, 226, 242, 316, 335, 372, 378, 384, 435, 491, 584, 595, 599, 606, 636, 659, 661, 686, 694, 697, 722, 739, 762. Knuth, Jennifer Sierra (M'h^), xiy- Knuth, John Martin tS Kohavi, Zvi (viTQ >33), 498. Koksma, Jurjen Ferdinand, 161. pages: 680 words: 157,865 Beautiful Architecture: Leading Thinkers Reveal the Hidden Beauty in Software Design by Diomidis Spinellis, Georgios Gousios A number of critically important software design decisions, based purely on how the JVM behaves, are also outlined where they had a significant performance benefit. * * * [46] This apocryphal rule of thumb was actually verified using JPC during the boot sequence of DOS and when playing numerous DOS games. With the total control of an emulator, it is easy to compile such statistics on program execution. See also Donald E. Knuth’s “An empirical study of FORTRAN programs.” (Software Practice and Experience, 1: 105-133. Wiley, 1971.) The PC Architecture The modern PC is a very complicated beast. Its hardware has been optimized and iterated over many times to produce a highly effective and generalized computing platform. There we see that Wright, Le Corbusier, and Mies van der Rohe are all criticized because they were unyielding; they were criticized for being adamant, for their lack of compromise. Their strident views gave us beautiful buildings, but not buildings that would provide us with material comfort. Being adamant is not necessarily a flaw. In an interview in Doctor Dobb’s Journal in April 1996, Donald Knuth was asked his opinion on Edsger Dijkstra. “His great strength,” he replied, “is that he is uncompromising. It would make him physically ill to think of programming in C++.” Uncompromising to the point of not touching a computer for years, and writing “his really terrific essay on the Humble Programmer discussing this.” pages: 834 words: 180,700 The Architecture of Open Source Applications by Amy Brown, Greg Wilson [Hor05] Cay Horstmann: Object-Oriented Design and Patterns. Wiley, 2 edition, 2005. [HR83] Theo Haerder and Andreas Reuter: "Principles of Transaction-Oriented Database Recovery". ACM Computing Surveys, 15, December 1983. [Kit10] Kitware: VTK User's Guide. Kitware, Inc., 11th edition, 2010. [Knu74] Donald E. Knuth: "Structured Programming with Go To Statements". ACM Computing Surveys, 6(4), 1974. [LA04] Chris Lattner and Vikram Adve: "LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation". Proc. 2004 International Symposium on Code Generation and Optimization (CGO'04), Mar 2004. I have run into many bottlenecks along the way but each time I look for improvements in design rather than speed-ups in performance. I have been asked many times why I wrote Graphite in Python rather than Java or C++, and my response is always that I have yet to come across a true need for the performance that another language could offer. In [Knu74], Donald Knuth famously said that premature optimization is the root of all evil. As long as we assume that our code will continue to evolve in non-trivial ways then all optimization6 is in some sense premature. One of Graphite's greatest strengths and greatest weaknesses is the fact that very little of it was actually "designed" in the traditional sense. pages: 317 words: 101,074 The Road Ahead by Bill Gates, Nathan Myhrvold, Peter Rinearson Why would you want to create such a profile? I certainly don't want to reveal everything about myself, but it would be helpful if an agent knew I wanted to see any safety features the new model Lexus might have added. Or, it could alert me to the publication of a new book by Philip Roth, John Irving, Ernest J. Gaines, Donald Knuth, David Halberstam, or any of my other longtime favorite writers. I would also like to have it signal me when a new book appears on some topic that interests me: economics and technology, learning theories, Franklin Delano Roosevelt, and biotechnology, to name a few. I was quite stimulated by a book called The Language Instinct, written by Steven Pinker, a professor at MIT, and I'd like to know about new books or articles on its ideas. Possiplex by Ted Nelson I have shown him XanaduSpace and ZigZag several times. He is always wonderfully appreciative and his reactions are clever. ‘What are you doing to publicize this?’ he recently asked. 'Only everything in my whole life,' I said. ‘We should hold a big meeting,’ said Doug. That is Doug’s way. The last thing I want is a big meeting. What would Donald Knuth have said? 1957-current “I saw nothing flaky.” After the Wired attack I asked Don Knuth, the world authority on algorithms, if he would please go through the Xanadu algorithms with me and state, as an objective observer, whether they were based on ‘ignorance’ or otherwise deficient, as alleged by Gory Jackal in that foul piece. pages: 313 words: 101,403 My Life as a Quant: Reflections on Physics and Finance by Emanuel Derman I was naively proud to be doing real math. There were helpful resources wherever I turned. I found that Chris Van Wyk, an MTS in Computer Science in Area 10, had written a set of UNIX tools for solving simultaneous equations. He had started this project while working on his PhD thesis at Stanford under Donald Knuth, the famous author of the four-volume The Art of Computer Programming and the inventor of TeX, a widely used language for mathematical typesetting and word processing that has become standard among scientists. Steve Blaha, my particle-physicist friend at the Labs, told me that Knuth had been his college roommate. The Art of Readable Code by Dustin Boswell, Trevor Foucher Smalltalk Best Practice Patterns, by Kent Beck (Prentice Hall, 1996) Although the examples are in Smalltalk, the book has many good programming principles. The Elements of Programming Style, by Brian Kernighan and P.J. Plauger (Computing McGraw-Hill, 1978) One of the oldest books dealing with the issue of “the clearest way to write things.” Most of the examples are in Fortran and PL1. Literate Programming, by Donald E. Knuth (Center for the Study of Language and Information, 1992) We agree wholeheartedly with Knuth’s statement, “Instead of imagining that our main task is to instruct a computer what to do, let us concentrate rather on explaining to human beings what we want a computer to do” (p. 99). But be warned: the bulk of the book is about Knuth’s WEB programming environment for documentation. pages: 377 words: 110,427 The Boy Who Could Change the World: The Writings of Aaron Swartz by Aaron Swartz, Lawrence Lessig And they both run pretty much exactly as Bernstein first wrote them. One bug—one bug!—was found in qmail. A second bug was recently found in djbdns, but you can get a sense of how important it is by the fact that it took people nearly a decade to find it. No other programmer has this kind of track record. Donald Knuth probably comes closest, but his diary about writing TeX (printed in Literate Programming) shows how he kept finding bugs for years and never expected to be finished, only to get closer and closer (thus the odd version numbering scheme). Not only does no one else have djb’s track record, no one else even comes close. pages: 423 words: 21,637 On Lisp: Advanced Techniques for Common Lisp by Paul Graham Thanks also to Mona Pompili, Shirley Michaels, and Shirley McGuire for their organization and good humor. The incomparable Gino Lee of the Bow and Arrow Press, Cambridge, did the cover. The tree on the cover alludes specifically to the point made on page 27. This book was typeset using LaTeX, a language written by Leslie Lamport atop Donald Knuth's TeX, with additional macros by L. A. Carr, Van Jacobson, and Guy Steele. The diagrams were done with Idraw, by John Vlissides and Scott Stanton. The whole was previewed with Ghostview, by Tim Theisen, which is built on Ghostscript, by L. Peter Deutsch. Gary Bisbee of Chiron Inc. produced the camera-ready copy. pages: 404 words: 43,442 The Art of R Programming by Norman Matloff Graphics 283 13 D EBUGGING Programmers often ﬁnd that they spend more time debugging a program than actually writing it. Good debugging skills are invaluable. In this chapter, we’ll discuss debugging in R. 13.1 Fundamental Principles of Debugging Beware of bugs in the above code; I have only proved it correct, not tried it. —Donald Knuth, pioneer of computer science Though debugging is an art rather than a science, it involves some fundamental principles. Here, we’ll look at some debugging best practices. 13.1.1 The Essence of Debugging: The Principle of Conﬁrmation As Pete Salzman and I said in our book on debugging, The Art of Debugging, with GDB, DDD, and Eclipse (No Starch Press, 2008), the principle of conﬁrmation is the essence of debugging. pages: 566 words: 122,184 Code: The Hidden Language of Computer Hardware and Software by Charles Petzold Those numbers aren't prime. The final for loop prints out all the prime numbers, which are the values of i where a[i] is true. Sometimes people squabble over whether programming is an art or a science. On the one hand, you have college curricula in Computer Science, and on the other hand, you have books such as Donald Knuth's famous The Art of Computer Programming series. "Rather," wrote physicist Richard Feynman, "computer science is like engineering—it is all about getting something to do something." If you ask 100 different people to write a program that prints out prime numbers, you'll get 100 different solutions. pages: 706 words: 120,784 The Joy of Clojure by Michael Fogus, Chris Houser Presented at the ACM Workshop on Java for High-Performance Network Computing. This paper provides more information on the cyclopian nightmares awaiting you in Java floating point. Keene, Sonya. 1989. Object-Oriented Programming in Common Lisp: A Programmer’s Guide to CLOS. Boston: Addison-Wesley. The best book on CLOS ever written. Knuth, Donald. 1997. The Art of Computer Programming: Volume 1 - Fundamental Algorithms. Reading, MA: Addison-Wesley. This book goes into exquisite detail about the primary characteristics of FIFO queues and is highly recommended reading. _____. 1998. The Art of Computer Programming, Vol. 3: Sorting and Searching. pages: 624 words: 127,987 The Personal MBA: A World-Class Business Education in a Single Volume by Josh Kaufman In this chapter, you’ll learn the secrets of Optimization, how to remove unnecessary Friction from critical processes, and how to build Systems that can handle Uncertainty and Change. SHARE THIS CONCEPT: http://book.personalmba.com/improving-systems/ Optimization Premature optimization is the root of all evil. —DONALD KNUTH, COMPUTER SCIENTIST AND FORMER PROFESSOR AT STANFORD UNIVERSITY Optimization is the process of maximizing the output of a System or minimizing a specific input the system requires to operate. Optimization typically revolves around the systems and processes behind your Key Performance Indicators , which measure the critical elements of the system as a whole. How I Became a Quant: Insights From 25 of Wall Street's Elite by Richard R. Lindsey, Barry Schachter ., 29–47, 308 Kalman filter, usage, 188, 239 Kani, Iraj, 123–124 Kapner, Ken, 333 Katz, Gary, 336–337 Kazhdan, David, 119–120 Kazhdan-Lusztig result, 120 Kealhofer, Stephen, 211–225 Kelvin, Lord, 67 Kennecott Copper-Carborundum merger, 290 reporting system, design (foresight), 72–73 risk-controlled stock/bond funds, offering, 71 Kieschnick, Michael, 213 P1: OTE/PGN JWPR007-Lindsey P2: OTE January 1, 1904 6:33 384 KMV Corporation, 218 Knuth, Donald, 171 Kohn, Robert, 132 Kottwitz, Robert, 120 Krail, Bob, 202 Krell, David, 336–337 Kritzman, Mark, 251–261 Kurzweil, Ray, 27–28 Kusuda, Yasuo, 168, 170 Kyle, Peter, 214 Landlands, Robert, 119 Landlands Program, 119–120 Lang, Serge, 287 Lanstein, Ron, 307 Large-cap securities, comparison, 267 Large-scale data analysis, 218 Large-scale matrix inversion, 257 Lattice Trading, 75–76 sale, 79–81 “Law of One Alpha, The,” 274 Lawrence, Colin, 232 LECG, litigation counseling, 218 LeClair, Ray, 82 Leeson, Nick, 194 Lefevre, Edwin, 321 Leinweber, David, 9–28 Leinweber & Co., 9 Leland, Hayne, 158 Leland O’Brien Rubinstein Associates, 278 Leptokurtosis, 193–194 Levy, Kenneth N., 263–283 Levy processes, 169 Lewis, Harry, 13 Lexis database, 146–148 Li, David, 240 Liability Driven Investment (LDI), 148 Liew, John, 201, 202 Lindsey, Rich, 157, 162 Lintner, John, 34 Linux, 18 LISP-based trading systems, flaw, 20 LISP Machines, Inc. pages: 1,331 words: 183,137 Programming Rust: Fast, Safe Systems Development by Jim Blandy, Jason Orendorff For those situations, Rust has traits, the topic of our next chapter. Chapter 11. Traits and Generics [A] computer scientist tends to be able to deal with nonuniform structures—case 1, case 2, case 3—while a mathematician will tend to want one unifying axiom that governs an entire system. Donald Knuth One of the great discoveries in programming is that it’s possible to write code that operates on values of many different types, even types that haven’t been invented yet. Here are two examples: Vec<T> is generic: you can create a vector of any type of value, including types defined in your program that the authors of Vec never anticipated. pages: 968 words: 224,513 The Art of Assembly Language by Randall Hyde You'll also want to check out the source code for several of the HLA Standard Library routines to see how to do various extended-precision operations (that properly set the flags once the computation is complete). The HLA Standard Library source code also covers the extended-precision I/O operations that do not appear in this chapter. Donald Knuth's The Art of Computer Programming, Volume Two: Seminumerical Algorithms contains a lot of useful information about decimal arithmetic and extended-precision arithmetic, though that text is generic and doesn't describe how to do this in x86 assembly language. Chapter 9. MACROS AND THE HLA COMPILE-TIME LANGUAGE This chapter discusses the HLA compile-time language. Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems by Martin Kleppmann Chapter 12 concludes the book by exploring ideas about how we might use these tools to build reliable, scalable, and maintainable applications in the future. CHAPTER 10 Batch Processing A system cannot be successful if it is too strongly influenced by a single person. Once the initial design is complete and fairly robust, the real test begins as people with many different viewpoints undertake their own experiments. —Donald Knuth In the first two parts of this book we talked a lot about requests and queries, and the corresponding responses or results. This style of data processing is assumed in many modern data systems: you ask for something, or you send an instruction, and some time later the system (hopefully) gives you an answer. pages: 1,237 words: 227,370 Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems by Martin Kleppmann Chapter 12 concludes the book by exploring ideas about how we might use these tools to build reliable, scalable, and maintainable applications in the future. Chapter 10. Batch Processing A system cannot be successful if it is too strongly influenced by a single person. Once the initial design is complete and fairly robust, the real test begins as people with many different viewpoints undertake their own experiments. Donald Knuth In the first two parts of this book we talked a lot about requests and queries, and the corresponding responses or results. This style of data processing is assumed in many modern data systems: you ask for something, or you send an instruction, and some time later the system (hopefully) gives you an answer. Why Things Bite Back: Technology and the Revenge of Unintended Consequences by Edward Tenner Computerization turns this manifesto on its ancient head. Software can devour highly complex tasks with ease if they fit well into its existing categories. But even a simple change illustrates the revenge effect of recomplicating. The scientific typesetting program TEX, developed by the computer scientist Donald S. Knuth and now the standard in many branches of physics and mathematics, makes short work of the most fearsomely complex equations that once cost publishers up to$6o per page to typeset. An author proficient in TEX—and I have had the good fortune to work with several of them—can prepare camera-ready copy that stands up to most commercially available systems.

From Airline Reservations to Sonic the Hedgehog: A History of the Software Industry by Martin Campbell-Kelly

Blair Smith, “The IBM 701—Marketing and Customer Relations,” Annals of the History of Computing 5 (1983): 170–172. 13. Ibid. Notes to pp. 33–39 317 14. Armer, “SHARE—A Eulogy to Cooperative Effort,” p. 122. 15. Akera, “The IBM User Group, Share,” p. 725. 16. The best general account of early programming systems is Paul E. Ceruzzi, A History of Modern Computing (MIT Press), especially chapter 3. 17. Donald E. Knuth and Luis Trabb Pardo, “The Early Development of Programming Languages,” in A History of Computing in the Twentieth Century, ed. N. Metropolis, J. Howlett, and G.-C. Rota (Academic Press, 1980). 18. The best historical account of FORTRAN is Annals of the History of Computing 6 (1984), no. 1 (25th-anniversary special issue). 19.

Applied Cryptography: Protocols, Algorithms, and Source Code in C by Bruce Schneier

If you are depending on your random-number generator for security, weird correlations and strange results are the last things you want. The problem is that a random-number generator doesn’t produce a random sequence. It probably doesn’t produce anything that looks even remotely like a random sequence. Of course, it is impossible to produce something truly random on a computer. Donald Knuth quotes John von Neumann as saying: “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin” [863]. Computers are deterministic beasts: Stuff goes in one end, completely predictable operations occur inside, and different stuff comes out the other end.

Engineering Security by Peter Gutmann

“A Killer Adversary for Quicksort” Douglas McIlroy, Software — Practice and Experience, Vol.29, No.4 (April 1999), p.341. “Quicksort killer”, Igor Ostrovsky, 4 May 2008, http://igoro.com/archive/quicksort-killer/. “Data Structures and Efficient Algorithms, Volume 1: Sorting and Searching”, Kurt Mehlhorn Springer Verlag, 1984. “The Art of Computer Programming, Volume 3: Sorting and Searching (2 nd ed)”, Donald Knuth, Addison-Wesley, 1997. “Algorithms in C: Fundamentals, Data Structures, Sorting, Searching (3rd ed)”, Robert Sedgewick, Addison-Wesley, 1998. “Introduction to Algorithms (2nd ed)”, Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, MIT Press, 2001. “Designing and Attacking Port Scan Detection Tools”, Solar Designer, Phrack Magazine, Vol.8, No.53 (8 July 1998), Article 13.