# 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

John Backus, “Programming in America in the 1950s: Some Personal Impressions,” in A History of Computing in the Twentieth Century: A Collection of Essays, ed. 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.

“Cybernetics, Management Science, and Technology Policy: The Emergence of ‘Information Technology’ as a Keyword, 1948–1985.” 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. New York: Springer-Verlag, 1977.

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

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. 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.

"Optimization: Your Worst Enemy." May 2000, http://www.flounder.com/optimization.htm. 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. They can be somewhat intimidating. In addition to the English description of the algorithms, they're described in mathematical notation or MIX, an assembly language for the imaginary MIX computer.

[bib36entry38] Beck,LelandL., and ThomasE.Perkins. 1983. “"A Survey of Software Engineering Practice: Tools, Methods, and Results."” IEEE Transactions on Software Engineering SE-9, no. 5 (5): 541–61. [bib36entry39] Beizer,Boris. 1990. Software Testing Techniques, 2d ed. New York, NY: Van Nostrand Reinhold. [bib36entry40] Bentley,Jon, and Donald Knuth. 1986. “"Literate Programming."” Communications of the ACM 29, no. 5 (5): 364–69. [bib36entry41] Bentley,Jon, Donald Knuth, and Doug McIlroy. 1986. “"A Literate Program."” Communications of the ACM 29, no. 5 (5): 471–83. [bib36entry42] Bentley,Jon. 1982. Writing Efficient Programs. Englewood Cliffs, NJ: Prentice Hall. [bib36entry43] Bentley,Jon. 1988. More Programming Pearls: Confessions of a Coder. Reading, MA: Addison-Wesley. [bib36entry44] Bentley,Jon. 1991.

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. In 1973, Knuth ran a poll via postal mail. He famously doesn’t use email today, but back in 1973 neither did anyone else.

Knuth was not entirely happy with this choice but was willing to live with it. 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. But terminology gets embedded in the culture over the decades, and at this point it would be difficult to change, even if we had great alternatives.

The third (interior point) works well both in theory and practice. Not bad for a problem still considered unresolved into the late 1970s. * 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. But Knuth and others in America couldn’t so easily look toward Russia.

pages: 523 words: 143,139

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

In academia, holding office hours is a way of coalescing interruptions from students. 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. His report ends with the cheery sign-off “Stay tuned for The TeX Tuneup of 2021!”

a quarter of the computing resources of the world: Knuth, The Art of Computer Programming, p. 3. “unit cost of sorting, instead of falling, rises”: Hosken, “Evaluation of Sorting Methods.” 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. This is a Radix Sort, and is related to the Bucket Sort algorithm we discuss later in the chapter.

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. Some of my subjects scoffed at the notion that formal proofs could be useful in improving the quality of software, but Guy Steele gave a very nice illustration of both their power and their limitations.

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. The sample label is given as 99 since a two-digit number produces sufficient indentation for the standard form of \bibitem.

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 { }. The very first entry is the key 312 Chapter 14. Bibliographic Databases and BIBTEX for the whole reference by which it is referred to in the \cite command.

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.” A short extract: “5.

using Lisp and comments on its suitability as the language that was developed for artificial intelligence, thus encapsulating the imagined ability of machines to speak like humans. (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. Heinz von Foerster, Cybernetics of Cybernetics (Urbana: University of Illinois, 1974). 33.

“Protected Mode.” In Ute Bernhardt and Ingo Ruhmann, eds., Computer, Macht und Gegenwehr. 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. Latour, Bruno. Reassembling the Social: An Introduction to Actor-Network-Theory.

pages: 255 words: 76,834

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

However, the quotation I cite is part of a lengthy back-and-forth with a reporter who was questioning Edison on the occasion of his birthday in 1929, and I doubt the author had a notebook to take down what Edison said. 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. W. Dijkstra in his article “Go To Statement Considered Harmful.”

As we untangled those columns of text from news sites, and fixed e-commerce shopping carts so they always remembered your items, and improved compatibility with banking sites so you could manage your money online, we had to change the code to make these features and functions perform correctly while avoiding making the browser any slower. There could be no exceptions to the PLT speed rule—Don wouldn’t allow it. 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.

This is where Kant returns to the discussion, and this notion suggests how his philosophy might figure into creative work. 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. What does this have to do with QWERTY? This keyboard arrangement is also a part of our cultural inheritance, even if it’s not as high-minded as Kant’s philosophical musings on taste.

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. “A longer attention span is needed”: Ibid., p. 145. The information about the Piet Hein poem over Knuth’s entrance is from Ditlea, “Rewriting the Bible,” in Technology Review.

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.

To shape it so that people can learn it easily, and to render it flexible so people can bend it to their needs? Is it just a matter of time and experience? 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. The full explanation for this habit lies in the esoteric realm of the design of the registers inside a computer’s central processing unit and the structure of data arrays.

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. Debunking the "Expensive Procedure Call" Myth or, Procedural Call Implementations Considered Harmful or, LAMBDA: The Ultimate GOTO.

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. A program has to live up to mathematical truth in the same way that a building has to live up to the laws of physics. But the architect's aim is not simply to make a building that doesn't fall down. Almost always the real aim is to make something beautiful. Many programmers feel, like Donald Knuth, that this is also the real aim of programming. Almost all Lisp hackers do. The spirit of Lisp hacking can be expressed in two sentences.

Thanks also to the staff at Aiken Lab, including Tony Hartman, Dave Mazieres, Janusz Juda, Harry Bochner, and Joanne Klys. 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.

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. More than anyone else, he understands the paradox that programmers write code for other humans, not for machines: “Let us change our traditional attitude to the construction of programs: 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.”7 In 1984, therefore, he famously formalized the notion of “literate programming”: The practitioner of literate programming can be regarded as an essayist, whose main concern is with exposition and excellence of style.

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. Even a simple software requirement for a small company that, say, provides secretarial services for the medical insurance industry—“We need an application that makes it easier for our scribes to write up reports from doctors’ examinations of insurance claimants”—will always reveal a swirling hodgepodge of exceptions and special cases.

pages: 351 words: 123,876

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

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. In that case, if the uniform RNG is trustworthy, then the nonuniform generator is trustworthy. Of course it is possible that a bug could still slip through the process, but this is unlikely. If the K-S test fails, examining the values of x that determine K+ and K− could help developers locate the bug in the RNG. † Knuth, Donald E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Third Edition.

How do you know when χ2 is too large or too small? First we consider the number of buckets. 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. The empirical distribution is defined as: and the theoretical distribution function F(x) is the theoretical probability of the RNG returning a value no greater than x.

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

Some of these strategies will deploy simple heuristics to hijack your brain’s motivation center while others are designed to recharge your willpower reserves at the fastest possible rate. You could just try to make deep work a priority. 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. Chappell told me that his first encounter with the idea of deep work was “an emotional moment.”

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.

He would then meditate and walk in the woods to clarify his thinking in preparation for the next day’s writing. 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

[KLM+97] Gregor Kiczales, John Lamping, Anurag Mendhekar, Chris Maeda, Cristina Videira Lopes, Jean-Marc Loingtier, and John Irwin. 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. Kernighan and Rob Pike. The Practice of Programming. Addison Wesley Longman, Reading, MA, 1999.

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? Exercises 34.

At best it is an unfortunate necessity; at worst it is treated as a low-priority task in the hope that management will forget about it at the end of the project. 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. Tip 67 Treat English as Just Another Programming Language There are basically two kinds of documentation produced for a project: internal and external.

pages: 394 words: 108,215

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

Moreover, other important companies such as Digital, Lucasfilm, and Intel received important technological boosts from SAIL innovations. 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.

He was able to visit the Menlo Park laboratory and had a good conversation with a number of the members of the Augment team. He liked them, and they liked him. 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. The doors of Augment were opened not only to a small technical elite of software designers like Duvall and Lehtman.

In his senior year, he began experimenting with electronic devices and built several electronic slide rules, assembling them from components that he dredged out of scavenging expeditions to a electronic-surplus shop in Cambridge. 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. The Knuth course also led to Ingalls’s first entrepreneurial venture and his first business failure when he launched a one-man consulting firm that sought to speed up programs written in Fortran.

pages: 285 words: 86,853

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

Throughout this evolution, the algorithm retained an essential feature that will soon become central to the story: it just works. 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.

“You’re Allowed to Tip Your Uber Driver (And Maybe You Should).” 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.” Forbes, January 21, 2013. http://www.forbes.com/sites/anthonykosner/2013/01/21/facebook-is-recycling-your-likes-to-promote-stories-youve-never-seen-to-all-your-friends/#410fca25777c.

Algorithms Unlocked by Thomas H. Cormen

Freeman, 1979. [Gri81] David Gries. The Science of Programming. Springer, 1981. [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. [Mac12] John MacCormick. Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today’s Computers.

John MacCormick’s book Nine Algorithms That Changed the Future [Mac12] describes several algorithms and related aspects of computing that affect our everyday lives. 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. Be warned, however: the material in TAOCP is intense. By the way, if you’re wondering where the word “algorithm” comes from, Knuth says that it derives from the name “al-Khowârizmı̂,” a ninth-century Persian mathematician.

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

In Object-Oriented Programming Systems, Languages, and Applications Conference Proceedings, pages 63-76, Vancouver, British Columbia, Canada, October 1992. 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. Journal of Object-Oriented Programming, 1(3):26–49, August/September 1988.

(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. The Domain Specific Software Architecture program sponsored by the U.S.

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. [Artificial intelligence pioneer and Stanford Professor John] McCarthy used to make up the problems.

p 56 The issue tracker isn’t just for fixing bugs, it’s also used to propose and implement new features: In fact, the issue tracker is just one of several ways in which Firefox developers can propose new features. 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.” I haven’t been able to find a verifiable source for the Picasso quote, but compare T.

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. T. Clanchy, From Memory to Written Record, England, 1066-1307 (Cambridge, Mass.: Harvard University Press, 1979), 202

To demonstrate this, Otto Neugebauer, the leading twentieth-century historian of ancient mathematics, had to reassemble tablets whose fragments had made their way to opposite sides of the Atlantic Ocean. 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. The height is 3,20, and a volume of 27,46,40 has been excavated. The length exceeds the width by 50.

Out of Control: The Rise of Neo-Biological Civilization. Reading, Mass.: Addison-Wesley, 1994. Kendall, David G. “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. N. Kolmogorov. Vol. 3, Information Theory and the Theory of Algorithms. Translated by 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. Perhaps most significantly, what have come to be known as the “encryption wars” in the mid-1990s were waged over the right to freely publish and use software cryptography in the face of governmental restrictions that classified strong forms of encryption as munitions.

Mother Jones, July 20. http://motherjones.com/politics/2001/07/peace-love-and-marketing (accessed August 24, 2011). Kidder, Tracy. 1981. The Soul of a New Machine. 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. Lancashire, David. 2001. Code, Culture, and Cash: The Fading Altruism of Open Source Development.

., 200–203; definition of, 9, 84, 118; expansion of, 84–86; history of, 9–10, 62–64; and international treaties, 71, 72, 84; relationship of to free speech, 9, 10, 183, 200 International Intellectual Property Alliance (IIPA), 71, 87 Internet, 26, 30, 32–33, 39, 46, 58, 73, 75, 83, 88, 169, 189, 207 Internet Relay Chat (IRC), 6, 23, 33, 51, 107, 128, 140, 194, 213n9 Jackson, Michael, 27 Jaffe, Adam, 66, 67 jazz poetics. 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: 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. The earliest reference given by Knuth is to Vittorio Grünwald in 1885. Knuth himself submitted a paper on the subject in 1955 to a "science talent search" for high-school seniors.

[GGS] Gregoire, Dennis G., Groves, Randall D., and Schmookler, Martin S. 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. [GM] Granlund, Torbjörn and Montgomery, Peter L.

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. Copy editors with a good ear for prose style and enough ability to improve writing that isn't like theirs are even less common, but Mary Lou Nohr makes that grade.

(We cover these techniques in Chapter 9.) Rule of Optimization: Prototype before polishing. 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. From tortured code to incomprehensible data layouts, the results of obsessing about speed or memory or disk usage at the expense of transparency and simplicity are everywhere.

Profilers are tools that help you identify the 10% of hot spots that constrain the speed of your program. This is a good thing for making it faster. 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. If you get in the good habit of using them, you can get rid of the bad habit of premature optimization.

pages: 615 words: 168,775

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

Altos were being used in many parts of Xerox, and Taylor’s lab had already moved on to new contests: faster machines, smaller machines, ever-more-interactive machines that would understand speech commands. 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. What did those people know? The mind-set of Taylor and other leaders in the lab was fundamentally different from the traditional Silicon Valley way of thinking.

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

p "two"^^mt:potrzebies . } It’s an interesting case, because it has the ^^ in it to indicate that the value is of a specific type, but it’s not an xsd type. 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. We already know what the first parameter is—it is read from EDI, which is the root data structure.

It turns out that the generic table is implemented using a splay tree [Tarjan] Robert Endre Tarjan, Daniel Dominic Sleator. Self-adjusting binary search trees. Journal of the ACM (JACM). 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: 525 words: 142,027

CIOs at Work by Ed Yourdon

I think I’ve been lucky in that in every job I’ve been in, there’s been one or more people I’ve been able to look up to and learn from. Yourdon: Hmm. Fried: Kind of different depending on the situation. 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. Fried: Really? Yourdon: And I said, “Is it free?” And [Plauger] said, “Of course not, it’s 10,000.” Of course, you have access to whatever you want on the Internet, but it’s something I’ve noticed having written a whole bunch of books: nobody wants to read a book anymore. 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. ., 87 Arizona Public Service (APS) Company, 66, 211, 223 Arizona State University, 227 ARPANET, 19, 117, 135 Art of Computer Programming, 2 Atlanta-based Southern Company, 191 AT&T, 191, 249 B Ballmer, Steve, 39 Bank of Boston, 47 Baylor-Grapevine Board of Trustees, 47 Bedrock foundation, 249 Bell Atlantic Mobile, 231 Bell Labs, 2, 249 BlackBerry, 60, 96, 116, 121, 171, 184, 246, 261, 296, 317 Blalock, Becky, 182, 191, 215 adaptability, 192 Air Force brat, 191, 192 Atlanta-based Southern Company, 191 banking industry, 203 Boucher, Marie, 196 brainstorm, 202 24/7 business, 199 business intelligence, 204 cloud computing, 205 cognitive surplus, 206 cognitive time, 206 Coker, Dave, 196 communication and education, 200 Community and Economic Development, 194 consumer market, 202 cybersecurity, 207, 209 data analytics, 204, 205 disaster recovery, 209 distributed generation, 204 distribution organization, 201 Egypt revolution, 198 farming technology, 206 finance backgrounds/marketing, 200, 209 Franklin, Alan, 193 Georgia Power, 191 Georgia Power Management Council, 193 global society, 206 Google, 198 incredible technology, 195 Industrial Age, 206 Information Age, 206 InformationWeek's, 196 infrastructure, 202 intellectual property, 196 intelligence and redundancy, 207 Internet, 198, 206 leapfrog innovations, 205 mainframe system, 207 marketing and customer service, 193, 200 MBA, finance, 192 microfiche, 207 microwave tower, 207 mobile devices, 203 mobility and business analytics, 205 Moore's Law, 205 new generation digital natives, 197 flexible and adaptable, 199 innovation and creativity, 199 superficial fashion, 198 Olympic sponsor, 193 out pushing technology, 202 reinforcement, 201 sense of integrity, 200 Southern Company, 194, 198, 201, 207 teamwork survey, 201 technology lab, 202 undergraduate degree, marketing, 192 virtualization, 205 VRU, 203 Ward, Eileen, 196 wire business, 201 world-class customer service, 203 Bohlen, Ken, 211 American Production Inventory Control Society, 211 Apple, 217 APS, 211, 223 ASU, 227 benchmarking company, 216 chief innovation officer, 229 Citrix, 217 cloud computing, 218, 219 cognitive surplus, 220 DECnet, 212 Department of Defense, 222 distributed computing, 217 energy industry, 214 gizmo/whiz-bang show, 216 GoodLink, 217 hard-line manufacturing, 218 home computing, 219 home entertainment, 219 Honeywell, 219 HR generalists, 215 information technology department, 211 Intel machines, 217 John Deere, 213 just say yes program, 223 Lean Six Sigma improvement process, 211 Linux, 220 MBA program, 214 mentors, 213 national alerts, 224 North American universities, 228 paradigm shifts, 218, 220 PDP minicomputers, 212 Peopleware, 226 prefigurative culture, 221 R&D companies, 218 Rhode Island, 226 role models, 213 San Diego Fire Department, 224 security/privacy issues, 217 skip levels, 223 smart home concepts, 219 smartphone, 217 social media, 225 Stead, Jerry, 214 Stevie Award, 211 Storefront engineering, 212 traditional management, 219, 226 Twitter, 224 vocabulary, 221 Waterloo operations, 213 Web 2.0 companies, 227 Web infrastructure, 215 wikipedia, 220 Y2K, 222 Botnets, 23 Brian's and Rob Pike's, 2 Bristol-Myers Squibb, 33 Broadband networks, 241 Brown, 227 Bryant, 227 BT Global Services, 253 BT Innovate & Design (BTI&D), 253 Bumblebee tuna, 130 C Career writing technology, 67 CASE tools, 232 Cash, Jim, 50 Christensen, Clyde, 212 Chrome, 14, 18 Chrysler Corporation, 175 Citibank, 337 Citicorp, 313 Citrix, 217 Client-server-type applications, 59 Cloud computing, 218, 219, 239, 240, 261, 262, 310, 311, 313 Cloud technology, 62 CNN, 54 COBOL, 250 Cognitive surplus, 20, 79, 206, 291 College of Engineering, University of Miami, 113 Columbia University, 1 Community and Economic Development, 194 Computer Sciences Corporation, 35 Computerworld magazine, 196 Consumer-oriented technology, 22 Content management system, 133 Corporate information management (CIM) program, 309 Corporate Management Information Systems, 87 Corvus disk drive, 36 Customer Advisory Boards of Oracle, 191 Customer-relationship management (CRM), 56 Cutter Business Technology Council, 173 D Dallas Children's Medical Center Development Board, 48 DARPA, 19 DDoS attacks and security, 81 DECnet, 212 Dell Platinum Council, 113 DeMarco, Tom, 16, 226 Department of Defense, 222, 329, 332 Detroit Energy, 252 Digital books, 30 Digital Equipment, 48 Distributed computing, 217 Dodge, 189 Dogfooding, 11, 37, 38, 236 DTE Energy, 173 DuPont Dow Elastomers, 151 E Educational Testing Service (ETS), 151 E-government, 282, 285 Electrical distribution grid, 182 Elementary and Secondary Education Strategic Business Unit, 151 Elements of Programming Style, 2 Ellyn, Lynne, 173 advanced technology software planning, 175 Amazon, 184 artificial intelligence group, 175 Association for Women in Computing, 173 benchmark, 180, 181 BlackBerries, 184 Burns, Ursula, 175 Chrysler, 176 Cisco, 186 cloud computing, 183, 184 component-based architecture, 186 corporate communications customer service, 185 Crain's Detroit Business, 173 cyber security threats, 177 degree of competence, 187 diversity and sophistication, 182 DTE Energy, 173 energy trading, 176 engineering and science programs, 188 enterprise business systems policy, 186 executive MBA program, 176 Facebook, 185 fresh-out-of-the-university, 187 General Electric, 174 Google, 184 Grace Hopper, 174 grid re-automation, 182 Henry Ford Hospital, 174 internal social media, 185 International Coaching Federation, 178 iPads, 184 IP electrical grids, 182 iPod applications, 182 IT budgets, 186 IT responsibilities, 176 Java, 186 level of sophistication, 179 lobbying efforts, 181 medical computing, 175 Miller, Joan, 174 Mulcahey, Anne, 175 Netscape, 175 neuroscience leadership, 189 object-oriented programming, 186 Oracle, 186 peer-level people, 179 people system, 177 policies and strategies, 180 Radio Shack, 180 remote access capacity, 189 security tool and patch, 183 sense of community, 180 Shipley, Jim, 174 smart grid, 177, 182 smart meters, 182 smart phone applications, 183 swarming, 179 technical competence, 178, 179 Thomas, Marlo, 174 Twitter, 185 UNITE, 181 vendor community, 186 virtualization, 183, 184 Xerox, 175 E-mail, 9 Employee-relationship management (ERM), 56 Encyclopedia, 115 Encyclopedia Britannica, 292 ERP, 123 F Facebook, 244 Ellyn, Lynne, 185 Sridhara, Mittu, 73, 84 Temares, Lewis, 116, 121, 131 Wakeman, Dan, 169 Federal information technology investments, 299 Flex, 236 Ford, 102 Ford, Monte, 47 agile computing, 59 agile development, 62, 66 airplanes, 51 American Airlines, 47 Arizona Public Services, 66 Bank of Boston, 47 Baylor-Grapevine Board of Trustees, 47 BlackBerry, 60 board of Chubb, 51 board of Tandy, 51 business organizations, 63 business school, dean, 50 career writing technology, 67 client-server-type applications, 59 cloud technology, 62 CNN, 54 common-sense functionality, 49 consumer-based technology, 60 CRM, 56 Dallas Children's Medical Center Development Board, 48 Digital Equipment, 48 ERM, 56 financial expert, 69 frequent-flier program, 57 frontal lobotomy, 57 Harvard Business Review, 50 HR policies, 65 IBM, 48 information technology, 47, 52 Internet, 54 Internet-based protocol, 59 iPhone, 52 IT stuff, 58 Knight Ridder, 51 legacy apps, 59 mainframe-like applications, 59 management training program, 64 marketing and technical jobs, 48 Maynard, Massachusetts mill, 48 MBA program, 50 mentors, 49 Microsoft, 50 mobile computing, 62 New York Times, 53 operations center, 54 PDP-5, 49 PDP-6, 49 Radio Shack, 51 revenue management, 57 role models, 49 security paradigms, 62 self-service machine, 57 Silicon Valley companies, 68 smartphones, 54 social networking, 51, 53, 56, 58 stateful applications, 59 techie department, 48 The Associates First Capital Corporation, 47 transmission and distribution companies, 47 wireless network, 59 YouTube, 65 Fort Worth, 226 Free software foundation, 19 Fried, Benjamin, 1, 241 agile development, 25 agile methodologies, 26 Apple Genius Bar, 8 ARPANET, 19 Art of Computer Programming, 2 Bell Labs, 2 books and records, accuracy, 25 botnets, 23 Brian's and Rob Pike's, 2 cash-like principles, 29 CFO, 4 check writers, 18 chrome, 14, 18 classic computer science text, 1 cognitive surplus, 20 Columbia University, 1 compensation management, 7 competitive advantage, 9, 18 computer science degree, 1 computer scientists, 6 consumer-driven computing, 12 consumer-driven software-as-a-service offerings, 12 consumer-driven technology, 12 consumer-oriented technology, 14, 22 corporate leadership, 25 cost centers, 4 DARPA, 19 decision makers, 17 decision making, 13 360-degree performance management, 7 detroit energy, 30 digital books, 30 document workbench, 2 dogfooding, 11 e-books, 29 Elements of Programming Style, 2 e-mail, 9 end-user support, 7 engineering executive group, 4 European vendors, 6 file servers and print servers, 17 Folger Library editions, 30 free software foundation, 19 German company, 13 German engineering, 13 Gmail, 15 Godot, 26 Google, 1 books, 29 products, 5, 10 software engineers, 6 hiring managers, 6 HR processes and technologies, 6 IBM model, 13 instant messaging, 9 Internet age, 6 interviewers, training, 6 iPad, 29 iPhone, 29 IPO, 3 IT, engineering and computer science parts, 4 Knuth's books, 2 Linux machine, 8 Linux software, 19 machine running Windows, 8 Macintosh, 8 Mac OS, 9 macro factors, 11 Managing Director, 1 mentors, 1 microcomputers, 18 Microsoft, 5 Minds for Sale, 20 Morgan Stanley, 1–3, 5, 16 nonacademic UNIX license, 2 nontechnical skills, 5 oil exploration office, 17 open-source phone operating system, 20 outlook, 15 PARC, 19 performance review cycles, 7 personal computer equipment, 15 post-Sarbanes-Oxley world, 25 project manager, 13 quants, 24 rapid-release cycle, 26 R&D cycle, 24 regression testing, 27 role models, 1 shrink-wrapped software, 14 signature-based anti-virus, 22 smartphone, 20, 27 social contract, 8 society trails technology, 21 software engineering tool, 13 software installation, 14 supply chain and inventory and asset management, 10 SVP, 4 telephony, 17 ten things, 13 TMRC, 19 TROFF, 2 typesetter workbench, 2 UI designer, 14 university computing center, 28 videoconferencing, 12 Visicalc, 24 Wall Street, 23 Walmart, 6 waterfall approach, 25 XYZ widget company, 5 YouTube video, 20 G Gates, Bill, 39, 50 General Electric, 134 General Foods, 309, 326–328 General Motors, 33, 321, 329, 332 George Mason School of Information Technology, 309 Georgia Power Company, 191–193, 196 Georgia Power Management Council, 193 German company, 13 German engineering, 13 German manufacturing company, 232 Gizmo/whiz-bang show, 216 Gmail, 15 GoodLink, 217 Google, 1, 84, 85, 117, 217, 219, 220, 222, 235, 241, 263, 302, 319 apps, 314 books, 29 commercial products, 10 model, 293 Government Accountability Office (GAO), 305 4G program, 250 4G smartphone, 235 GTE, 231 Gupta, Ashish aspiration, organization, 256 bandwidth and network infrastructure, 267 BlackBerry, 261 business and customer outcomes, 274 capital investment forums, 269 career progression, 255 cloud-based shared infrastructure model, 263 cloud computing, 261, 262 collaboration, 272 communications infrastructure, 258 compute-utility-based model, 262 control and integrity, 268 core competency, 255 core network infrastructure, 267 core strengths, 256 cost per unit of bandwidth, 267 customer demands, 268 data protection, 261, 262 decision-making bodies, 269 demographics, 272, 273 device convergence, 263 dogfooding, 259 employee flexibility, 260, 264 engagement and governance, 269 enterprise market segment, 261 equipment management, 260 executive MBA, 256 fourth-generation LTE networks, 267 functional service departments, 270 Global Services, distributed organization, 257 Google, 263, 275 Google Apps, 266 handheld devices, 265 hastily formed networks, 258 IMF, 266 innovation and application development, 265 iPad, 257, 260, 261, 266,267 iPhone, 266 Japan, 257, 258 London Business School, 253 management functions, 257 management sales functions, 257 market segments, 259 MBA, General Management, 253 measurements, 271 messaging with voice capability, 264 mini-microcomputer model, 261 mobile communications network, 258 mobile-enabling voice, 259 mobile phone network, 260 mobile traffic explosion, 265 network infrastructures, 265 network IT services, 254 network quality, 257 new generation digital natives, 271 disadvantages, 273 Google, 273 opportunities, 273 Olympics, 263 opportunities, 275 organizational construct, 272 outsourced network IT services, 259 outsourcing, 271 per-use-based model, 262 portfolio and business alignment, 274 Portfolio & Service Design (P&SD), 253 primary marketing thrust, 264 product development thrust, 264 product management team, 259 project and program management, 255 resource balance, 270 scalability, 262 security, 262 Selley, Clive, 254, 255 service delivery organization, 254 single-device model, 264 smart devices, 267 smart phones, 266 telecommunications capability, 259 upward-based apps, 264 virtualization, 261 voice-over-IP connections, 258 Windows platform, 261 Gurnani, Roger, 231 accounting/finance department, 233 analog cellular networks, 250 AT&T, 249 bedrock foundation, 249 Bell Atlantic Mobile, 231 Bell Labs, 249 blogs, 244 broadband networks, 241 business benefits, 237 business device, 240 business executives, 238 business leaders, 248, 249 business relationship management, 248 buzzword, 239 CASE tools, 232 cloud computing, 239, 240 COBOL, 250 consumer and business products, 231 consumer electronics devices, 241 consumer telecom business, 233 customer-engagement channel, 244 customer forums, 244 customer support operations, 251 customer-touching channels, 236 degree of control, 246 distribution channel, 250 dogfooding, 236 ecosystem, 243, 249 enterprise business, 233 ERP systems, 236 face-to-face communications, 244 FiOS product, 235 flex, 236 "follow the sun" model, 239 German manufacturing company, 232 4G program, 250 4G smartphone, 235 hardware/software vendors, 247 information assets, 245 information technology strategy, 231 intellectual property rights, 244 Internet, 235, 239 iPhone, 243 Ivan, 232 Lowell, 232 LTE technology-based smartphone, 235 marketing, 251 MIT, 246 mobile technology, 234 Moore's law, 242 MP3 file, 235 network-based services, 240 Nynex Mobile, 233 P&L responsibility, 251 PDA, 238 personal computing, 235 product development, 234, 251 role models, 232 sales channels, 251 smartphones, 238 state-level regulatory issues, 251 state-of-the-art networks, 243 telecom career, 232 telephone company, Phoenix, 234 Verizon Communication, 231, 232 virtual corporations, 241 Web 2.0, 244 Williams Companies, 232, 233 WillTell, 233 wireless business, 233 H Hackers, 19 Harmon, Jay, 213 Harvard Business Review, 50 Harvard Business School, 331 Heller, Martha, 171 Henry Ford Hospital, 174 Hewlett-Packard piece, 129 Home computing, 219 Honda, 102 Honeywell, 219 Houghton Mifflin, 134, 136 I IBM, 48, 250 manpower, 311 model, 13 Indian IT outsourcing company, 255 Information technology, 52 Intel machines, 217 International Coaching Federation, 178 Internet, 9, 44, 54, 117, 235, 239, 316, 322 Internet-based protocol, 59 Interoperability, 341 iPads, 2, 94, 97, 184, 257, 260, 264, 267, 288, 289, 295, 296 IP electrical grids, 182 iPhones, 43, 52, 96, 101, 170, 181, 260, 264,296 iPod, 101 IT lifecycle management process, 37 Ivan, 232 J John Deere, 213 K Kansas, 226 Kernigan, Brian, 2 Knight Ridder, 51 Knuth, Donald, 2, 29 Kraft Foods Inc, 309 Krist, Nicholas, 28 Kundra, Vivek Clever Commute, 305 cognitive surplus, 303 command and control systems, 301 consumerization, 302 consumption-based model, 300 cyber-warfare, 301 Darwinian pressure, 302 desktop core configuration, 306 digital-borne content, 301 digital oil, 300, 307 digital public square, 304 enterprise software, 303 entrepreneurial startup model, 306 frugal engineering, 306 Google, 302 government business, 302 innovator's dilemma, 307 iPad, 302 IT dashboard, 302 leapfrog technology, 306 massive consumerization, 301 megatrends, 301 parameter security, 302 Patent Office, 305 pharmaceutical industry, 304 phishing attacks, 301 policy and strategic planning, 299 security and privacy, 301 server utilization, 300 social media and technology, 300, 306 storage utilization, 300 Trademark Office, 305 Wikipedia, 303 L LAN, 259 Lean Six Sigma improvement process, 211 Levy, Steven (Hackers), 19 Linux, 220 machine, 8 open-source software, 19 Lister, Tim, 226 London Business School, 73, 253, 256 Long-term evolution (LTE), 235 Lowell, 232 M MacArthur's intelligence officer, 327 Macintosh, 8 Mainframe computers, 118 Mainframe-like applications, 59 Marriott's Great America, 35 McDade, 327 McGraw-Hill Education, 133, 147, 150 Mead, Margaret, 221 Mendel, 311 Microcomputers, 18 Microsoft Corporation, 5, 11, 33, 36, 38, 41, 44, 46, 50, 156, 217, 223, 236, 250, 293 Microsoft Higher Education Advisory Group, 113 Microsoft's operational enterprise risk management, 33 Middlesex University, 189 Miller, Joan Apple products, 295 authority and accuracy, 292 award-winning ICT programs and services, 277 back locked-down information, 289 big-scale text issues, 294 big-time computing, 279 BlackBerry, 296 business management training, 281 business skills, 281 central government, 283 cognitive surplus, 291 community care project, 278 community development programs, 277, 278 computers, constituency office, 294 confidential information, 284 data management, 281 decision making, 286 democratic process, 288 economics degree, 278 e-government, 282, 285 electronic communication, 289 electronic-enabled public voice, 286 electronic information, 288 electronic media, 286 electronic records, 280, 284 electronic services, 294 e-mail, 289, 290, 295 forgiving technology, 296 front-office service, 282, 283 Google, 292 Google's cloud service, 290 Government 2, 287 Health and Social Care, 284 House business, 294 House of Lords, 288 ICT strategy, 289, 290 information management, 278 insurance company, 278 Internet information, 285 iPad, 288, 289, 296 IT data management, 279 management principle, 280 local government, 283 mainframe environment, 289 member-led activity, 287 messages, 289 Microsoft, 293 Microsoft's cloud service, 290 mobile electronic information, 284 mobile technology, 289 national organization, 284 network perimeters, 290 official government information, 285 on-the-job training, 281 organizational planning, 278 Parliamentary ICT, 277 project management, 279 public sector, 282 public transportation, 285 quango-type organizations, 283 representational democracy, 286 security, 290, 291 social care organization, 279 social care services, Essex, 278 social care systems, 284 social networking, 285 sovereignty, 291 sustainability and growth, 293 technical language, 294 technology skills, 281 transactional services, 285 transferability, 291 Web-based services, 285 Wikipedia, 291, 292 X-factor, 286 Minds for Sale, 20 Mitchell & Co, 333 MIT Media Labs, 149 Mobile computing, 62 Mobile technology, 234 Mooney, Mark, 133 artificial intelligence, 134 back-office legacy, 136 balancing standpoint, 145 BBC, 140 Bermuda Triangle, 135 BlackBerry shop, 142 Bureau of National Standards, 136 business model, 140 career spectrum, 144 cloud computing, 148 competitive intelligence and knowledge, 143 Connect, 141 customer-facing and product development, 135 customer-facing product space, 137 customer space and product development, 136 digital products development, 144 digital space and product, 146 educational and reference content, 139 educational products, 141 entrepreneur, 150 General Electric, 134 GradeGuru, 140 handheld devices, 142 hard-core technical standpoint, 146 hardware servers, 142 Houghton Mifflin, 134, 136 HTML, 138 industrial-strength product, 141 intellectual content, 148 Internet, 148 iPad, 138, 139, 142 iPhone, 142, 143 iTunes, 138 Klein, Joel, 147 learning management systems, 137 long-term production system, 141 Marine Corps, 134 McGraw-Hill Education, 133, 147 media development, 144 media space, 138, 142 mobile computing, 139 MOUSE, 150 online technology, 138 open-source capabilities, 142 Oracle quota-management system, 143 people's roles and responsibilities, 137 Phoenix, 149 product development, 149 publishing companies, 142 publishing systems, 137 Reed Elsevier, 133, 136 Salesforce.com, 144, 149 scalability testing, 145 senior business leaders, 146 social network, 148 soft discipline guidelines, 141 solar energy, 149 Strassmann, Paul, 135 technical skill set, 143, 144 testing systems integration, 145 The Shallows, 139 transactional systems, 142 trust and integrity, 145 TTS, QuickPro, and ACL, 144 Vivendi Universal, 134 War and Peace today, 139 Moore's law, 242 Morgan Stanley, 2, 3, 16 N NASA, 309, 333, 334 National Institute of Standards and Technology (NIST), 173 Naval Postgraduate School, 134 Netscape, 175 New Brunswick model, 282 News Corp., 147 New York Stock Exchange (NYSE), 87, 116, 223, 278 New York Times, 53 North American universities, 228 NSA/CIA software, 134 Nynex Mobile, 233 O Oil exploration office, 17 Open-source phone operating system, 20 Outlook, 15 P Pacer Software, 135 Paradigm shifts, 218, 220 Parks and Recreation Department, 126 PDP minicomputers, 212 Peopleware, 226 Personal computing, 235 Personal digital assistant (PDA), 238 Petri dish, 44 Phoenix, 211 Plauger, Bill, 2 Q Quants, 24 R Radio Shack, 51 Reed Elsevier, 133, 136 Reed, John, 335 Rubinow, Steve, 87 AdKnowledge, Inc., 87 agile development, 110 Agile Manifesto, 110 Archipelago Holdings Inc., 87 attributes, 108 capital market community, 91 cash/actual trading business, 88 channel marketing departments, 92 cloud computing, 97 CNBC, 89 collaborative technology, 95 collective intelligence, 95 communication skills, 102, 106 conference organizations, 99 consumer marketplace, 94 data center, 90 decision making, 105, 108 economy standpoint, 100 e-mail, 100 Fidelity Investments, 105 financial services, 92 IEEE, 101 innovative impression, 94 Internet, 98 iPad, 97 iPod device, 91 labor laws, 110 listening skills, 106 logical progression, 104 Mac, 96 mainframe, 104 management and leadership, 104, 105 market data system, 89 micro-second response time, 89 mobile applications, 94 multidisciplinary approach, 103 multimedia, 97 multi-national projects, 110 multiprocessing options, 99 network operating system, 103 NYSE Euronext, 87 open outside system, 88 parallel programming models, 99 personal satisfaction, 109 PR function, 106 proclaimed workaholic, 109 real estate business, 88 regulatory and security standpoint, 96 Rolodex, 94 Rubin, Howard, 99 server department, 97 software development, 89 sophisticated technology, 101 technology business, 88 technology integration, 91 trading engines, 90 typewriter ribbon, 94 virtualization, 98 Windows 7, 96 younger generation video games, 93 visual interfaces, 93 Rumsfeld, Donald, 222 S San Diego Fire Department, 224 Santa Clara University, 36 SAS programs, 131 Scott, Tony, 10, 33, 236 Android, 43 Apple Computer, 35 architectural flaw, 44 BASIC and Pascal, 35 Bristol-Myers Squibb, 33 Bunch, Rick (role model), 34 business groups, 42 COO, 39 Corporate Vice President, 33 Corvus disk drive, 36 CSC, 35 Defense department, 45 dogfooding, 37, 38 games and arcades, 35 General Motors, 33 IBM's role, 37 information systems management, 36 integrity factor, 40 Internet, 44 iPhone, 43 IT lifecycle management process, 37 leadership capability, 40 leisure studies, 34 macro-architectural threats, 44 Marriott's Great America, 35 math models, 36 Microsoft Corporation, 33, 36, 38, 41, 44, 46 Microsoft's operational enterprise risk management, 33 parks and recreation, 34 Petri dish, 44 playground leader, 42 product groups, 42 quality and business excellence team, 33 Santa Clara University, 36 Senior Vice President, 33 smartphone, 43 social computing, 38 Sun Microsystems, 36 theme park industry, 35 University of Illinois, 34 University of San Francisco, 36 value-added business, 33 Walt Disney Company, 33 Senior Leadership Technology and Product Marketing, 71 Shakespeare, 30 Shirky, Clay, 220 Sierra Ventures, 191 Silicon Valley companies, 68 Silicon Valley software factories, 323 Skype, 118 Smart Grid Advisory Committee, 177 Smartphones, 20, 27, 43, 54, 217, 238 Social care computer electronic record system, 279 Social computing, 38, 320 Social networking, 51, 53, 56, 58 Society trails technology, 21 SPSS programs, 131 Sridhara, Mittu, 71 Amazon, 76 American Airlines, 72 back-end computation and presentation, 80 banking, 77 B2B and B2C, 85 business/product departments, 82 business work context, 74 buzzword, 77 career aspiration, 73 career spans, 73 coders, 72 cognitive surplus, 79 competitive differentiation, 74 computing power, 78 contribution and energy, 85 convergence, 75 CPU cycles, 78 cross-channel digital business, 71 cultural and geographic implementation, 72 customer experience, 84, 85 customer profile, 76 data visualization, 79, 80 DDoS protection, 81 economies of scale, 77 elements of technology, 72 encryption, 82 end customer, 83 entertainment, 75 ERP system, 72 Facebook, 84 finance and accounting, 73 foster innovation and open culture, 81 friends/mentors/role models, 74 FSA, 76 gambling acts, 81 games, 79 gaming machines, 80 GDS, 72 global organization, 71 Google, 75, 84, 85 Group CIO, Ladbrokes PLC, 71 industry-standard technologies, 77 integrity and competence, 83 IT, 74, 82 KickOff app, 71 land-based casinos, 79 live streaming, 78 London Business School, 73 mobile computing, 78 multimedia, 84 new generation, 84 on-the-job training, 73 open-source computing, 79 opportunity, 80, 83 PCA-compliant, 81 personalization, 76 real-time systems, 74 re-evaluation, 81 reliability and availability, 77 security threats, 80 smart mobile device, 75 technology-intense customer, 85 top-line revenue, 74 trader apps, 82 true context, 73 underpinning business process, 76 virtualization, 78 Visa/MasterCard transactions, 78 Web 3.0 business, 76 web-emerging web channel, 76 Wikipedia, 79, 85 Word documents and e-mail, 82 work-life balance, 84 young body with high miles, 72 Zuckerberg, Mark, 73 Stead, Jerry, 214 Storefront engineering, 212 Strassmann, Paul, 228, 309 agile development, 340 Amazon EC2, 314 America information processors, 322 Annapolis, 340 AT&T, 332 backstabbing culture, 339 BlackBerry, 317 block houses, 319 CFO/CEO position, 337 CIM program, 309 Citibank, 337 Citicorp, 313, 339 cloud computing, 310, 311, 313 coding infrastructure, 341 communication infrastructure, 341 corporate information management, 329 Corporate Information Officer, 309 counterintelligence, 320 cyber-operations, 338 Dell server, 314 Department of Defense, 329, 332 Director of Defense Information, 309 employee-owned technology, 316 enterprise architecture, 316 exfiltration, 313 financial organizations, 320 firewalls and antiviruses, 312 General Foods, 309, 326–328 General Motors, 321, 329, 332 George Mason School of Information Technology, 309 Google apps, 314 government-supported activities, 326 Harvard Business School, 331 HR-related issues, 331 IBM manpower, 311 infiltration, 313 Internet, 316, 322 interoperability, 315, 317, 341 Kraft Foods Inc, 309 MacArthur's intelligence officer, 327 Machiavellian view, 327 mash-up, 316 military service, 331 NASA, 309, 333, 334 police department, economics, 312 powerpoint slides, 324 Radio Shack, 319 senior executive position, 334 service-oriented architecture, 316 Silicon Valley software factories, 323 social computing, 320 Strassmann's concentration camp, 318 structured methodologies, 342 U.S. 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. Though the Jobs visit is the one that will remain inscribed in legend, there were many outsiders who came through PARC, and the Alto, Bravo, and Gypsy teams did many demos. A year or so before the group from Apple, a young Hollywood screenwriter named Bonnie MacBird showed up. She had an unusual background: she had read about PARC in Ted Nelson’s book Computer Lib / Dream Machines (1974) and had studied with Donald Knuth, one of the world’s foremost computer scientists, at Stanford. She was also working on a rather unusual script. MacBird had recently left a writing position at Universal Studios for a new production company run by Steven Lisberger specializing in animated films and computer graphics. Lisberger had an idea for a movie about video games, which were quickly becoming the rage in coin-operated arcades (Space Invaders had just been released in the United States by Midway). ., 52 Keats, John, 36, 227 Kedit (program), 12 Keep, Christopher, 297n9 Kellerman, Jesse, 188–189 Kenner, Hugh, 27, 28, 29 Kerouac, Jack, 13, 17 Kindle. 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: 326 words: 91,559 Everything for Everyone: The Radical Tradition That Is Shaping the Next Economy by Nathan Schneider In the twentieth century, Charlie Chaplin and his friends formed United Artists to produce their own films, and photographers such as Henri Cartier-Bresson and Robert Capra formed Magnum, a cooperative syndication guild. 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: 309 words: 65,118 Ruby by example: concepts and code by Kevin C. Baird The Code For this chapter, we’ll be looking at some short scripts in pairs. Here’s factorial1.rb: #!/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. For factorials, we return 1 when self is either 0 or 1, testing for 0 with the predicate zero? 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 In theory, arithmetic is quite easy; you use the same algorithms to add, subtract, multiply, and divide fractional values that you learned in grade school when dealing with fractions. 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. For example, “a..z” denotes all the lowercase alphabetic characters between a and z 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 thatFFC000FF 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. [7] Actually, they could count down to zero as well, but usually they count up

. // 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 New York: Prentice-Hall. Kohlbecker, Eugene Edmund, Jr. 1986. 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. Kowalski, Robert. 1979. 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. with dotted-tail notation lambda expression as operator of combination value of lambda-body lambda-parameters lambda? pages: 511 words: 111,423 Learning SPARQL by Bob Ducharme p "two"^^mt:potrzebies . } It’s an interesting case because it has the ^^ in it to indicate that the value has a specific type, but it’s not an xsd type. 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. ., Adding Data to a Dataset integer datatype, Datatypes and Queries IRI, Glossary IRI(), Node Type Conversion Functions, Solution isBlank(), Node Type and Datatype Checking Functions isIRI(), Node Type and Datatype Checking Functions isLiteral(), Node Type and Datatype Checking Functions isNumeric(), Node Type and Datatype Checking Functions isURI(), FILTERing Data Based on Conditions, Node Type and Datatype Checking Functions J Java, SPARQL and Web Application Development JavaScript, SPARQL Query Results JSON Format, SPARQL and Web Application Development Jena, Defining Rules with SPARQL, Getting Started with Fuseki, Getting Started with Fuseki, Standalone Processors join (SPARQL equivalent), Searching Further in the Data JSON, The SPARQL Specifications, SPARQL and Web Application Development ARQ and, Working with SPARQL Query Result Formats, Standalone Processors defined, SPARQL Query Results JSON Format query results, SPARQL Query Results JSON Format results from a SPARQL engine, SPARQL Query Results JSON Format K Knuth, Donald, Datatypes and Queries L lang(), Checking, Adding, and Removing Spoken Language Tags langMatches() vs., Checking, Adding, and Removing Spoken Language Tags langMatches(), Checking, Adding, and Removing Spoken Language Tags language codes, Making RDF More Readable with Language Tags and Labels, Checking, Adding, and Removing Spoken Language Tags–Checking, Adding, and Removing Spoken Language Tags adding, Checking, Adding, and Removing Spoken Language Tags checking, Checking, Adding, and Removing Spoken Language Tags filtering on, Using the Labels Provided by DBpedia removing, Checking, Adding, and Removing Spoken Language Tags LCASE(), String Functions, Discussion LIMIT, Retrieving a Specific Number of Results, Federated Queries: Searching Multiple Datasets with One Query Linked Data, What Exactly Is the “Semantic Web”? Eloquent JavaScript 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. The most obvious application of functions is defining new vocabulary. Creating new words in prose is usually bad style. ., 82 Hooke’s law, 395 hooligan, 375 Host header, 313 hot code, 392 href attribute, 222, 232, 235 HTML, 221, 312, 326, 369 notation 221 structure 227 html (HTML tag), 223, 228 HTTP, 219–221, 311–317, 366, 367, 369, 373, client, 361, 367, 372 server, 360, 363, 375, 381 http package, 360–361 HTTPS, 221, 317, 361 https package, 361 human language, 23 Hypertext Markup Language, see HTML Hypertext Transfer Protocol, see HTTP hyphen character, 13, 147, 238 I id attribute, 232, 239, 323 idempotence, 189, 366, 425 identifier, 204 identity, 65 if keyword, 28, 162 chaining, 29, 34, 408 If-None-Match header, 374, 380, 385 image, 233, 258, 287, 313 imagination, 265 IME (input method editor), 252 img (HTML tag), 222, 233, 237, 258, 287, 295, 296, 345 immutable, 65, 120, 270, 335, 336, 342, 346, 423 implements (reserved word), 26 import keyword, 173 in operator, 64, 105 includes method, 68, 69, 399, 411 indentation, 32 index, 61 index property, 149 index.html file, 381 index.js file, 355 indexOf method, 71, 73, 94, 113, 146, 158, 411 infinite loop, 33, 47, 139, 409 infinity, 14 infrastructure, 169 inheritance, 100, 111–112, 139, 365 INI file, 160 ini package, 169, 173, 175, 356 initialization, 258 inline caching, 403, 404 inline element, 235, 237 inlining, 400 inner function, 44, 418 inner loop, 154 innerHeight property, 257 innerWidth property, 257 input, 134, 247, 266, 319, 353, 378 input (HTML tag), 257, 318, 322, 323, 325, 341, 345 input event, 322 insertBefore method, 232, 233 installation, 169 instance, 101 instanceof operator, 112, 139 instructions, 3, 391 integers, 13 integration, 145, 230 interface, 98 canvas, 287, 289 design, 54, 145, 150, 155, 158, 229, 230, 272, 290 HTTP, 316, 373 module, 168–172, 175, 315, 356 object, 105, 106, 109, 114, 126, 189, 269, 301, 322, 335 interface (reserved word), 26 internationalization, 162 internet, 160, 220, 221, 224 Internet Explorer, 225 interpolation, 15 interpretation, 7, 170, 207–208, 212, 391 interview question, 37 inversion, 147 invoking (of functions), see function application IP address, 221, 311, 313 isDirectory method, 366, 425 isEven (exercise), 56, 408 isolation, 97, 167, 170, 224 iterable interface, 107, 412 iterator, 196 iterator interface, 106, 107, 114, 398 J Jacques, the weresquirrel, 60 Java, 5 JavaScript, 5 availability of, 2 flexibility of, 6 history of, 5, 219 in HTML, 223 syntax, 23 uses of, 6 versions of, 6 weaknesses of, 6 JavaScript console, 7, 16, 27, 134, 138, 330, 354 JavaScript Object Notation, see JSON join method, 94, 104, 356 journal, 60, 62, 64, 66, 69 JOURNAL data set, 68 journalEvents function, 69 JSON, 77, 175, 184, 193, 315, 328, 373, 386, 425 json method, 315 JSON.parse function, 77, 426 JSON.stringify function, 77 JSX, 384 jump, 4 jump-and-run game, 265 jumping, 266, 282 just-in-time compilation, 392 K Kernighan, Brian, 128 key code, 282 key property, 252, 418, 423 keyboard, 26, 247, 251, 266, 281, 282, 285, 319, 320, 322, 349 keyboard bindings (exercise), 349, 423 keyboard focus, see focus keydown event, 251, 260, 282, 349, 418, 423 keyup event, 251, 282 keyword, 24, 26, 235 Khasekhemwy, 322 kill process, 360 Knuth, Donald, 40 L label, 295, 307 label (HTML tag), 323, 341 labeling, 323 landscape example, 44 Laozi, 180 lastChild property, 230 lastIndex property, 158–160 lastIndexOf method, 71 Last-Modified header, 313 latency, 174 lava, 266, 267, 275, 278, 280, 305 Lava class, 270, 280 layering, 194, 220 layout, 235–237 laziness, 236 Le Guin, Ursula K., 2 leaf node, 229 leak, 225, 285 learning, 2, 6, 371 left (CSS), 240–242, 244 LEGO, 168 length property for arrays, 61, 336 for strings, 53, 56, 61, 74, 409 less than, 16 let keyword, 24, 25, 43, 65, 75, 76, 130 level, 266, 267, 273, 275, 284 Level class, 267 lexical scoping, 44 library, 230, 334, 356, 357 license, 169 line, 24, 32, 161, 287, 289–294, 307, 420 line break, 14, 161 line comment, 35, 156 line drawing, 350, 424 line width, 290, 297 lines of code, 211 lineTo method, 290–291 lineWidth property, 290 link (HTML tag), 277 linked list, 79, 410, 426 links, 222, 230–231, 251, 252, 344 linter, 173 Liskov, Barbara, 96 list (exercise), 79, 410 listen method, 360 listening (TCP), 220, 360 literal expression, 23, 146, 206, 208 live data structure, 227, 233, 240, 419 live view, 372, 373, 387, 426 lives (exercise), 285 load event, 258, 295–296, 303, 326, 421 LoadButton class, 344 local binding, 48, 215, 409 local scope, 43, 212 localhost, 360 localStorage object, 326–327, 383 locked box (exercise), 141, 413 logging, 133 logical operators, 17 long polling, 372–374, 378, 380, 385 loop, 4, 30, 32, 37, 38, 50, 69, 85, 90, 91, 160, 189, 408, 409, 420 termination of, 33 loop body, 31, 85 lycanthropy, 60, 66 M machine code, 3, 213, 391 macro-optimization, 406 magic, 99, 203 mailRoute array, 123 maintenance, 169 malicious script, 224 man-in-the-middle, 317 map, 272, 321 map (data structure), 104 Map class, 105, 109, 195 map method, 88, 91, 94, 99, 104, 120, 191, 268, 340 Marcus Aurelius, 246 match method, 149, 159 matching, 146, 151, 152, 158, 164 algorithm, 152–154 Math object, 56, 61, 75 Math.abs function, 76, 424 Math.acos function, 75 Math.asin function, 75 Math.atan function, 75 Math.ceil function, 76, 278, 302–303 Math.cos function, 75, 241, 242, 421 mathematics, 50, 86 Math.floor, 76, 122, 278, 302–303 Math.max function, 27, 61, 74, 75, 302 Math.min function, 27, 56, 75, 302 Math.PI constant, 75, 293 Math.random function, 75, 122, 271, 330, 404 Math.round function, 76 Math.sin function, 75, 241, 242, 271, 281 Math.sqrt function, 68, 75, 411 Math.tan function, 75 Matrix class, 107–108, 335 matrix example, 107–108, 111 MatrixIterator class, 108 max-height (CSS), 275–276 maximum, 27, 75, 90 max-width (CSS), 275–276 McConnell, Steve, 390 Meadowfield, 117 measurement, 397 measuring, 399 measuring a robot (exercise), 125, 412 media type, 317, 329, 365 meetups, JavaScript, 371 memory, 3, 11 call stack, 24 organization, 12, 47, 60, 65, 77 persistence, 387 speed, 181, 213, 400, 402, 406 structure sharing, 79 mesh, 221 message event, 259 meta key, 252 metaKey property, 252, 349 method, 62, 100, 101 array, 71 HTTP, 312, 317, 360, 367, 373, 375 interface, 98 method attribute, 313 method call, 98 method property, 315 methods object, 363 micro-optimization, 397, 399, 406 Microsoft, 225 Middle East, graph of, 393 mime package, 365 MIME type, 329, 365 mini application, 326 minifiers, 175 minimalism, 265 minimum, 27, 56, 75 minimum (exercise), 56, 408 minus, 13, 165 Miró, Joan, 332 mirror, 298, 308, 421 mirroring, 297–298 MKCOL method, 368–369, 425 mkdir function, 368–369, 425 modification date, 366 modifier key, 252 modular robot (exercise), 177, 414 modularity, 97, 334 module, 168, 169, 177, 272, 355, 356, 375 design, 175 module loader, 355 module object, 172 module system, 169 modulo (remainder) operator, 14, 33, 297, 407, 408, 418, 420 Mongolian vowel separator, 162 monster (exercise), 285, 419 Mosaic, 225 motion, 266 mouse, 26 button, 249, 250, 253 cursor, 253 mouse trail (exercise), 262, 418 mousedown event, 250, 253, 255, 337, 338, 422 mousemove event, 254, 260–262, 338, 350, 418 mouseup event, 253–255 moveTo method, 290, 293 Mozilla, 225 multiple attribute, 324, 325 multiple-choice, 318–319, 323, 324 multiplication, 13, 269–270, 280 multiplier function, 49 music, 265 mutability, 63, 65, 120 N name attribute, 320, 324 namespace, 75 naming, 4, 5, 25–26 NaN (not a number), 14, 17, 18, 130 negation, 16, 17 neighbor, 330, 422 neighbors property, 190 nerd, 158 nesting of arrays, 67 of expressions, 23, 205 of functions, 44 of loops, 38, 408 of objects, 228, 231 in regular expressions, 154 of scope, 44 Netscape, 5, 225 network, 182, 219, 372 abstraction, 194, 316 protocol, 220 reliability, 188 security, 317 speed, 174, 181, 353 network function, 194 new operator, 101 newline character, 14, 38, 147, 156, 161, 268, 422 next method, 107, 197, 412 nextSibling property, 230 Nietzsche, Friedrich, 226 node, 228, 229 node program, 354 node-fetch package, 361 Node.js, 6, 7, 27, 171, 183, 353–369, 372, 373, 375, 387, 398 NodeList type, 230, 239 node_modules directory, 355, 356 nodeName property, 243 nodeType property, 229, 418, 419 nodeValue property, 231 nonbreaking space, 162 normalizing, 396 not a number (NaN), 14, 17, 18, 129 notation, 173 note-taking example, 327 notification, 372 NPM, 169, 171, 173, 174, 176, 177, 355–358, 365, 375, 376, 387, 415 npm program, 356, 357, 365 null, 18, 19, 51, 61, 77, 80, 134 number, 12, 65, 146, 165, 414 conversion to, 19, 28 notation, 12–13 precision of, 13 representation, 12 special values, 14 Number function, 28, 35 number puzzle example, 50–52 Number.isNaN function, 29 O object, 59, 63–65, 97, 112 creation, 77, 101, 328, 401, 403 identity, 65 as map, 272 as module, 169 mutability, 65 property, 27, 61, 75, 76, 99 representation, 77 Object prototype, 99, 100 object shape, 404 Object.assign function, 328, 336 Object.create function, 100, 104, 211 Object.keys function, 64, 80, 195, 410, 417 object-oriented programming, 97, 101, 105, 106, 111, 119, 175 Object.prototype, 104 observation, 399 obstacle, 277, 278 offsetHeight property, 235, 236 offsetWidth property, 235 on method, 362 onclick attribute, 224, 248 onclick property, 337 OpenGL, 289 opening tag, 222 operator, 13, 16, 19, 204, 210, 404 application, 13 optimization, 50, 55, 236, 260, 266, 275, 306, 308, 359, 392, 398–400, 403, 406, 426 option (HTML tag), 319, 324, 425 optional, in pattern, 148 optional arguments, 48, 78 options property, 324 ordering, 220 ordinal package, 171–172 organic growth, 167 organization, 167 outline, 289 output, 16, 26, 27, 133, 134, 211, 353, 422 overflow (CSS), 275–276 overflow, with numbers, 12 overlap, 278 overlay, 238 overriding, 103, 105, 111, 415 overwriting, 367, 369, 378 P p (HTML tag), 222, 235 package, 168, 171, 355, 357 package (reserved word), 26 package manager, 169 package.json file, 357 padding (CSS), 274 page reload, 258, 321, 326 pageX property, 253, 255 pageXOffset property, 236 pageY property, 253, 255 pageYOffset property, 236, 257 Palef, Thomas, 265 panning, 339 paragraph, 222 parallelism, 182, 313 parameter, 27, 42, 43, 46–48, 74, 76, 99, 131, 172 parent node, 249 parentheses arguments, 23, 41, 46, 85, 204 expression, 13 in regular expressions, 149, 151, 152, 162, 413 statement, 27, 29, 31, 33 parentNode property, 230 parse function, 207 parseApply function, 206 parseExpression function, 205 parseINI function, 161, 168 parsing, 77, 129, 161, 203–206, 208, 211, 223, 227, 364, 380 password, 317 password field, 318 path canvas, 290–293, 420 closing, 291 file system, 355, 363 URL, 312, 315, 363, 364, 373, 375 path package, 365 pathfinding, 123, 176, 193, 343 pathfinding (exercise), 405, 406, 426 patience, 350 pattern, 145–147, 157 pausing (exercise), 285, 419 pea soup, recipe analogy, 84 peanuts, in weresquirrel example, 70–71 percent sign, 314 percentage, 94, 257 performance, 154, 174, 212, 236, 266, 306, 359, 391, 393, 397, 399 period character, 27, 61, 74, 147, 156, 165, 336 persistence, 326, 372, 387, 425 persistent data structure, 119, 120, 126, 132, 335, 342, 346, 419 persistent group (exercise), 126 persistent map (exercise), 413 PGroup class, 126, 413 phase, 271, 281 phi coefficient, 66–68 phi function, 68, 76 phone, 252 physics, 277, 281, 393, 418 physics engine, 278 pi, 13, 75, 241, 271, 293 PI constant, 75, 242 pick function, 343 picture, 287, 288, 296, 306, 334, 346 Picture class, 335, 345 picture property, 335 PictureCanvas class, 337, 349 pictureFromImage function, 345 pie chart example, 294, 295, 307, 420 ping request, 190 pink, 336 pipe analogy, 220 pipe character, 152, 414 pipe method, 364, 367 pipeline, 175 pixel, 235, 242, 253, 267, 273, 288, 289, 295, 296, 302, 306, 308, 333, 335, 339, 342, 343, 345, 350, 423 pixel art, 296 PixelEditor class, 340, 347, 349 pizza, in weresquirrel example, 67 platform game, 265, 285 Plauger, P.J., 128 player, 265–267, 275, 278, 281, 284, 296, 303, 305 Player class, 270, 281 plus character, 13, 148, 165 pointer, 230 pointer events, 253–256, 337 pointerPosition function, 338 polling, 247 pollTalks function, 385 polymorphism, 105–106 pop method, 62, 71 Popper, Karl, 234 port, 220, 311, 360 pose, 296 position, of elements on screen, 236 position (CSS), 240, 244, 257, 266, 275 POST method, 313, 314, 321, 374 postMessage method, 259 power example, 42, 48, 50 precedence, 13, 17, 239 predicate function, 88, 92, 95 Prefer header, 374, 380, 385 premature optimization, 50 preventDefault method, 251, 256–258, 282, 321, 339, 423 previousSibling property, 230 primitiveMultiply (exercise), 141, 413 privacy, 225 private (reserved word), 26 private properties, 98, 141–142 process object, 354–355, 364–365 processor, 181, 400 profiling, 50, 399 program, 2, 23, 28 program size, 83, 84, 164, 272 programming, 1 difficulty of, 2 history of, 3 joy of, 1, 2 Programming Is Terrible, 166 programming language, 1–2 creating, 203, 213 DOM, 229 history of, 3 machine language and, 391 Node.js and, 354 power of, 5 programming style, 3, 24, 32, 35, 272 progress bar, 256 project chapter, 117, 203, 265, 333, 371 promise, 200, 416 Promise class, 186, 187, 189, 195, 197, 198, 200, 315, 326, 359, 361, 363, 386, 416 Promise.all function, 190, 199, 200, 416 Promise.reject function, 187 Promise.resolve function, 186, 190 promises package, 359 promptDirection function, 139 promptInteger function, 134 propagation, of events, 249, 250, 257, 258 proper lines (exercise), 350, 424 property access, 27, 61, 129, 348, 403 assignment, 63 definition, 63, 66, 109 deletion, 63, 98 inheritance, 99, 101, 103 model of, 63 naming, 105–107 testing for, 64 protected (reserved word), 26 protocol, 220, 221, 311–312 prototype, 99–104, 111, 211, 215, 417, 426 diagram, 103 prototype property, 101 pseudorandom numbers, 75 public (reserved word), 26 public properties, 98 public space (exercise), 369, 425 publishing (packages), 358 punch card, 3 pure function, 55, 79, 88, 175, 330, 422 push method, 62, 69, 71, 411, 426 pushing data, 372 PUT method, 312–313, 363, 367, 373, 378, 425 Pythagorean theorem, 411, 423 Python, 391 Q quadratic curve, 292 quadraticCurveTo method, 292, 420 query string, 314, 374, 380 querySelector method, 240, 417 querySelectorAll method, 239, 324 question mark, 18, 148, 157, 314 queue, 198 quotation mark, 14, 165 quoting in JSON, 77 of object properties, 63 quoting style (exercise), 165, 413 R rabbit example, 98, 100–102 radians, 242, 293, 298 radio buttons, 318, 323 radius, 350, 423 radix, 11 raising (exceptions), 135 random numbers, 75, 271 random-item package, 414 randomPick function, 122 randomRobot function, 122 range, 88, 147, 148 range function, 5, 78, 409 Range header, 316 ray tracer, 306 readability, 4, 5, 35, 50, 54, 135, 167, 208, 276, 307 readable stream, 361, 362, 364, 378 readAsDataURL method, 345 readAsText method, 326 readdir function, 359, 366, 425 readdirSync function, 425 read-eval-print loop, 354 readFile function, 172, 358, 425 readFileSync function, 359, 424 reading code, 6, 117 readStorage function, 184 readStream function, 378, 379 real-time events, 247 reasoning, 17 recipe analogy, 84 record, 62 rect (SVG tag), 288 rectangle, 266, 278, 289, 307, 342 rectangle function, 342, 423 recursion, 47, 50, 56, 80, 189, 195, 205, 206, 208, 231, 243, 300, 394, 408, 410, 413, 416, 418 reduce method, 89, 91, 94, 95, 340, 411 redundancy, 397 ReferenceError type, 215 RegExp class, 146, 157, 424 regexp golf (exercise), 164 regular expressions, 145–165, 206, 368, 375, 376, 417, 424 alternatives, 152 backtracking, 153 boundary, 151 creation, 146, 157 escaping, 146, 158, 414 flags, 149, 155, 157, 414 global, 155, 158, 159 grouping, 149, 155 internationalization, 162 matching, 152, 158 methods, 146, 150, 158 repetition, 148 rejecting (a promise), 187, 189, 198 relative path, 172, 224, 355, 363, 425 relative positioning, 240, 241 relative URL, 315 remainder (modulo) operator, 14, 33, 297, 407, 408, 418, 420 remote access, 363 remote procedure call, 316 removeChild method, 232 removeEventListener method, 248, 419 removeItem method, 326 rename function, 359 rendering, 289 renderTalk function, 384 renderTalkForm function, 385 renderUserField function, 383 repeat method, 73, 257 repeating key, 251 repetition, 52, 148, 154, 157, 260 replace method, 155, 165, 413 replaceChild method, 233, 418 replaceSelection function, 322 reportError function, 383 repulsion, 393, 395 request, 185, 189, 220, 312, 313, 321, 360, 361, 367, 372 request function, 189, 361, 362 request type, 185 requestAnimationFrame function, 241, 258, 260, 283, 308, 418 requestType function, 190 require function, 171, 172, 178, 355, 356, 365, 375 reserved words, 26 resolution, 172, 355 resolve function, 364 resolving (a promise), 186, 187, 189, 198 resource, 220, 221, 312, 313, 317, 363, 377 response, 185, 189, 312, 313, 316, 360, 364, 366 Response class, 315 responsiveness, 247, 353, rest parameters, 74 restore method, 299, 300 result property, 326 retry, 189 return keyword, 42, 47, 101, 196, 408, 411 return value, 27, 42, 134, 185, 410 reuse, 54, 112, 167–169, 356 reverse method, 79 reversing (exercise), 79, 409 rgb (CSS), 274 right-aligning, 243 rmdir function, 366, 368 roadGraph object, 118 roads array, 117 roads module (exercise), 177, 415 robot, 117, 119, 121, 123, 125, 177 robot efficiency (exercise), 125, 412 robustness, 373 root, 229 rotate method, 298, 300 rotation, 307, 420 rounding, 76, 134, 278, 279, 302, 424 router, 372, 375 Router class, 375, 376 routeRequest function, 194 routeRobot function, 123 routing, 192 rows, in tables, 243 Ruby, 391 rules (CSS), 238, 239 run function, 211 runAnimation function, 283, 285 runGame function, 284, 285 runLayout function, 396 runLevel function, 283, 285 running code, 7 runRobot function, 121, 412 run-time error, 132–134, 140, 417 Rust (programming language), 391 S Safari, 225 sandbox, 7, 59, 224, 227, 316 save method, 299, 300 SaveButton class, 344 scalar replacement of aggregates, 400, 402 scale constant, 337–339 scale method, 297, 299 scaling, 273, 296, 297, 303, 421 scalpel (exercise), 200, 416 scheduling, 197, 354 scientific notation, 13, 165 scope, 43, 44, 48, 168, 170–173, 208, 210, 214, 215, 417 script (HTML tag), 223, 224, 258 SCRIPTS data set, 87, 89, 92, 93, 95 scroll event, 256, 260 scrolling, 251, 256–257, 275–276, 282, 301 search method, 158 search problem, 124, 152, 154, 232, 368, 405 search tool (exercise), 368, 424 section, 161 Secure HTTP, 221, 317, 361 security, 224, 225, 316, 317, 325, 327, 364, 375 select (HTML tag), 319, 324, 327, 334, 340, 425 selected attribute, 324 selection, 322 selectionEnd property, 322 selectionStart property, 322 selector, 239 self-closing tag, 222 semantic versioning, 357 semicolon, 23, 24, 33, 237 send method, 185, 188 sendGossip function, 191 sep binding, 364–365 sequence, 148 serialization, 77 server, 220, 221, 311–313, 315, 316, 353, 360, 362, 363, 372, 375 session, 328 sessionStorage object, 328 set, 146, 147, 229 Set (data structure), 113, 126 Set class, 113, 126, 413 set method, 105 setAttribute method, 235, 337 setInterval function, 260, 296 setItem method, 326 setter, 110 setTimeout function, 184, 197, 259, 260, 380, 386 shape, 287, 290, 291, 293, 295, 307 shapes (exercise), 307, 420 shared property, 100, 103 SHIFT key, 252, 423 shift method, 71 shiftKey property, 252 short-circuit evaluation, 20, 51, 209, 411 SICP, 202 side effect, 24, 27, 34, 42, 54, 65, 79, 88, 159, 175, 199, 230, 232, 233, 236, 290, 299, 314, 334, 335 sign, 12, 165, 414 sign bit, 12 signal, 11 simplicity, 213 simulation, 119, 121, 265, 270, 330, 393, 418 sine, 75, 241, 271, 281 single-quote character, 14, 165, 224 singleton, 126 skill, 333 SkillShareApp class, 386 skill-sharing project, 371–373, 375, 381 skipSpace function, 206, 214 slash character, 13, 35–36, 146, 156, 315, 364, 425 slice method, 72, 73, 88, 233, 409, 416 slope, 424 sloppy programming, 261 smooth animation, 241 SMTP, 220 social factors, 349 socket, 372–373 some method, 92, 95, 191, 376, 426 sorting, 229 source property, 158 special form, 203, 208 special return value, 134, 135 specialForms object, 208 specificity, 239 speed, 1, 2, 308, 421 SpiderMonkey, 400 spiral, 307, 420 split method, 118, 268 spread, 74, 336 spread operator, 274 spring, 393, 395 sprite, 296, 303–304 spy, 256 square, 28 square brackets, 60, 61, 74, 76, 107, 147, 324, 328, 409 square example, 41–42, 45, 46 square root, 68, 75, 411 src attribute, 222, 224 stack, see call stack stack overflow, 47, 50, 56, 408 stack trace, 136 staged compilation, 392 standard, 5, 26, 35, 88, 136, 162, 349, 354, 355 standard environment, 26 standard output, 354, 362–363 standards, 219, 225 star, 307, 420 Star Trek insignia, 292 startPixelEditor function, 347 startState constant, 347 startsWith method, 364 stat function, 359, 365, 366, 425 state of application, 275, 334, 342, 346, 347, 388 in binding, 24, 31, 32, 34, 400 of canvas, 289, 299 in iterator, 197 in objects, 119, 268, 301 transitions, 198, 336, 337 statement, 23, 24, 28, 31, 32, 42, 63 static (reserved word), 26 static file, 373, 376 static method, 110, 113, 268, 413 static typing, 403 Stats type, 366 statSync function, 425 status code, 312, 354–355 status property, 315, 383 stdout property, 362–363 stopPropagation method, 250 storage function, 187 stream, 220, 361–363, 364, 367, 378 strict mode, 130 string, 14, 60, 62, 65, 92 indexing, 56, 72, 74, 92, 149 length, 37, 92 methods, 73, 149 notation, 14 properties, 72 representation, 15 searching, 73 String function, 28, 105 stroke method, 290–292 strokeRect method, 289, 421 strokeStyle property, 290 strokeText method, 295 stroking, 289, 290, 295, 306 strong (HTML tag), 235, 237 structure, 168, 222, 227, 334 Structure and Interpretation of Computer Programs, 202 structure sharing, 79 style, 237 style (HTML tag), 238, 239 style attribute, 237–239, 273 style sheet, see CSS subclass, 111 submit, 318, 320, 321 submit event, 321, 384, 425 substitution, 54 subtraction, 13, 113 sum function, 5, 78 summing (exercise), 78, 409 summing example, 4, 83, 89, 211 superclass, 111 survey, 294 Sussman, Gerald, 202 SVG, 287–289, 305, 306 swapping bindings, 424 swipe, 342 switch keyword, 34 symbiotic relationship, 183 symbol, 106 Symbol function, 106 Symbol.iterator symbol, 107 SymmetricMatrix class, 111 synchronization, 387, 426 synchronous programming, 182, 195, 359, 368 syncState method, 335, 338, 340, 341, 349, 426 syntax of Egg, 203, 204 error, 26, 129, 130 expression, 23 function, 42, 45 identifier, 26 number, 12, 165 object, 63 operator, 13 statement, 24, 26, 28–34, 135 string, 14 syntax tree, 204–205, 207, 228–229 SyntaxError type, 206 T tab character, 14, 32 TAB key, 320 tabbed interface (exercise), 262, 419 tabindex attribute, 252, 320, 349 table (HTML tag), 243, 266, 274, 422 table example, 417 tableFor function, 68 tables, 67, 68, 274 tags, 221–222, 227, 239, see also names of specific tags talk, 371, 372, 377–379 talkResponse method, 380 talksAbout function, 231 talkURL function, 383 Tamil, 87 tampering, 317 tangent, 75 target property, 250 task management example, 71 TCP, 220, 221, 311, 373 td (HTML tag), 243, 274 Tef, 166 temperature example, 110 template, 171, 388, 426 template literals, 15 tentacle (analogy), 25, 63, 65 terminal, 354 termite, 183 ternary operator, 18, 20, 209 test method, 146 test runners, 132 test suites, 132 testing, 125, 132 text, 14, 221, 222, 227, 229, 295, 305–307, 322, 324, 358, 422 text field, 257, 318, 319, 322 text method, 315 text node, 229, 231, 233, 419 text wrapping, 305 text-align (CSS), 243 textAlign property, 295, 420 textarea (HTML tag), 260, 318, 322, 327, 330, 425 textBaseline property, 295, 420 textContent property, 418, 422 TEXT_NODE code, 229, 419 textScripts function, 94, 411 th (HTML tag), 243 then method, 186–188, 191, 416 theory, 133 this binding, 62, 98–99, 101, 130 thread, 182, 183, 198, 259 throw keyword, 135, 136, 139, 141, 413 tile, 303 time, 147, 148, 150, 184, 241, 261, 277, 278, 280, 283, 303, 346 time zone, 150 timeline, 182, 197, 223, 241, 247, 258 timeout, 188, 259, 373, 374, 380 Timeout class, 189 times method, 269 timing, 396 title, 382 title (HTML tag), 222, 223 toDataURL method, 344 toLowerCase method, 62, 243 tool, 145, 164, 175, 334, 339, 340, 342–344, 347, 350, 357 tool property, 335 ToolSelect class, 340 top (CSS), 240–242, 244 top-level scope, see global scope toString method, 99, 100, 103–105, 346, 362 touch, 255, 334 touchend event, 255 touches method, 278 touches property, 255, 339 touchmove event, 255, 339, 350 touchstart event, 255, 337, 339 toUpperCase method, 62, 132, 243, 362 tr (HTML tag), 243, 274 trackKeys function, 282, 285 transform (CSS), 287 transformation, 297–299, 308, 420 translate method, 298, 299 Transmission Control Protocol, 220, 221, 311, 373 transparency, 289, 296, 346 transpilation, 213 trapezoid, 307, 420 traversal, 152 tree, 100, 204, 229 treeGraph function, 394 trial and error, 133, 282, 293 triangle (exercise), 37, 407 trigonometry, 75, 241 trim method, 73, 268 true, 16 trust, 224 try keyword, 136, 137, 190, 413, 422 type, 12, 16, 112 type attribute, 318, 321 type checking, 131, 174 type coercion, 18, 19, 28 type observation, 392, 401, 403 type property, 204, 249 type variable, 131 typeof operator, 16, 80, 410 TypeScript, 131–132 typing, 260 typo, 129 U Ullman, Ellen, xx unary operator, 16, 23 uncaught exception, 138, 188 undefined, 18, 19, 25, 42, 47, 61, 63, 77, 129, 130, 134 underline, 237 underscore character, 26, 35, 98, 151, 157 undo history, 346, 347 UndoButton class, 347 Unicode, 15, 17, 87, 92, 147, 162, 163 unicycling, 371 Uniform Resource Locator, see URL uniformity, 204 uniqueness, 239 unit (CSS), 242, 257 Unix, 366–368 Unix time, 150 unlink function, 359, 366 unshift method, 71 unwinding the stack, 135 upcasing server example, 362 updated method, 378, 381, 425 updateState function, 336 upgrading, 169 upload, 325 URL, 221, 224, 288, 313, 315, 317, 360, 373, 383 URL encoding, 314 url package, 364, 380 urlToPath function, 364 usability, 251 use strict, 130 user experience, 247, 320, 372, 383 user interface, 138, 334 users’ group, 371 UTF-8, 358, 359 UTF-16, 15, 92 V V8, 398 validation, 134, 140, 203, 277, 321, 378, 379 value, 12, 186 value attribute, 318, 322, 324 var keyword, 25, 43, 76 variables, see also binding Vec class, 113, 268, 269, 280, 394, 396, 421 vector, 394, 400 vector (exercise), 113, 411 vector graphics, 295 verbosity, 46, 182 version, 169, 222, 312, 357, 398 viewport, 275–277, 301, 302, 305 VillageState class, 119 virtual keyboard, 252 virtual world, 117, 119, 121 virus, 224 vocabulary, 41, 84 void operator, 26 volatile data storage, 12 W waitForChanges method, 380 waiting, 184 walking, 303 warning, 357 wave, 271, 280, 281 web, see World Wide Web web application, 5, 326, 333 web browser, see browser web page, 174 web worker, 259 WebDAV, 369 webgl (canvas context), 289 website, 224, 225, 313, 353, 369, 371 WebSockets, 373 weekDay module, 169–170 weekend project, 369 weresquirrel example, 60, 62, 64, 66, 69, 71 while loop, 4, 30, 32, 53, 160 whitespace in HTML, 231, 340, 419 indentation, 32 matching, 147, 162 syntax, 204, 206, 214, 417 trimming, 73, 268 in URLs, 373–374 Why’s (Poignant) Guide to Ruby, 22 width property, 350, 423 window, 250, 255, 258 window object, 248 with statement, 131 word boundary, 151 word character, 147, 151, 162 work list, 124, 343 workbench (exercise), 330, 422 world, of a game, 265 World Wide Web, 5, 77, 219, 221, 224, 225, 311 writable stream, 360–363, 364 write method, 360, 361 writeFile function, 359, 361, 425 writeHead method, 360 writing code, 6, 117 writing system, 87 WWW, see World Wide Web X XML, 230, 288 XML namespace, 288 xmlns attribute, 288 Y yield (reserved word), 26 yield keyword, 197 your own loop (example), 95 Yuan-Ma, 10, 352 Z Zawinski, Jamie, 144 zero-based counting, 56, 61, 150 zeroPad function, 54 zigzag shape, 420 zooming, 305 Eloquent JavaScript, 3rd Edition is set in New Baskerville, Futura, Dogma, and TheSansMono Condensed. 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. Could this phenomenon be the basis for a devilishly challenging one-way function? ., 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: 792 words: 48,468 Tcl/Tk, Second Edition: A Developer's Guide by Clif Flynt The kitchen in an automated restaurant might receive orders as patrons select items from a menu via a format such as the following: {{Table 2} {{Table {{Table {{Table {{Table {{Table {{Table {burger} {ketchup mustard}} 3} {drink} {medium}} 2} {fries} {large}} 1} {BLT} {no mayo}} 3} {Complete} {} } 1} {drink} {small}} 1} {Complete} {} } Write a script that will accept data in a format such as this, collecting the items ordered at a table and reporting a table’s order when the Complete message is received. 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. A tree data structure can be implemented as nested lists. 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. However, Hoare did not say, “Concern about application performance during the early stages of an application’s development is the root of all evil.” The Art of Assembly Language (No Starch Press, 2003) is a good place to begin that journey. 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. The Art of Assembly Language (No Starch Press, 2003) is a good place to begin that journey. If you want to learn high-level implementations, you can find a wealth of information. 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: 1,387 words: 202,295 Structure and Interpretation of Computer Programs, Second Edition by Harold Abelson, Gerald Jay Sussman, Julie Sussman Ingerman, Peter, Edgar Irons, Kirk Sattley, and Wallace Feurzeig; assisted by M. Lind, Herbert Kanner, and Robert Floyd. 1960. 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. The TK!Solver Book: A Guide to Problem-Solving in Science, Engineering, Business, and Education. Next: Exercises, Prev: 5.5, Up: Top [Contents] Next: Figures, Prev: References, Up: Top [Contents] List of Exercises Chapter 1 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 Chapter 2 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 Chapter 3 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 Chapter 4 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 Chapter 5 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 Next: Figures, Prev: References, Up: Top [Contents] Next: Term Index, Prev: Exercises, Up: Top [Contents] List of Figures Chapter 1 1.1 1.2 1.3 1.4 1.5 Chapter 2 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 Chapter 3 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 Chapter 4 4.1 4.2 4.3 4.4 4.5 4.6 Chapter 5 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 Next: Term Index, Prev: Exercises, Up: Top [Contents] Next: Colophon, Prev: Figures, Up: Top [Contents] Term 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) Jump to: A B C D E F G H I K L M N O P Q R S T U V W Z Index Entry Section A abstract models: 2.1.3 abstract syntax: 4.1.1 abstraction barriers: Chapter 2 abstraction barriers: 2.1.2 accumulator: 2.2.3 accumulator: 3.1.1 acquired: 3.4.2 action: 5.1.1 additive: 2.4.3 additively: Chapter 2 additively: 2.4 address: 5.3.1 address arithmetic: 5.3.1 agenda: 3.3.4 algebraic specification: 2.1.3 aliasing: 3.1.3 and-gate: 3.3.4 applicative-order: 4.2.1 applicative-order evaluation: 1.1.5 arbiter: 3.4.2 arguments: 1.1.1 assembler: 5.2.1 assertions: 4.4.1 assignment operator: 3.1 atomically: 3.4.2 automatic storage allocation: 5.3 average damping: 1.3.3 B B-trees: 2.3.3 backbone: 3.3.3 backquote: 5.5.2 backtracks: 4.3.1 balanced: 2.2.2 barrier synchronization: 3.4.2 base address: 5.3.1 Bertrand’s hypothesis: 3.5.2 bignum: 5.3.1 bindings: 3.2 binds: 1.1.8 binomial coefficients: 1.2.2 block structure: 1.1.8 bound variable: 1.1.8 box-and-pointer notation: 2.2 breakpoint: 5.2.4 broken heart: 5.3.2 bugs: Chapter 1 C cache-coherence: 3.4.1 call-by-name: 3.5.1 call-by-name: 4.2.2 call-by-name thunks: 3.5.1 call-by-need: 3.5.1 call-by-need: 4.2.2 call-by-need thunks: 3.5.1 capturing: 1.1.8 Carmichael numbers: 1.2.6 case analysis: 1.1.6 cell: 3.4.2 chronological backtracking: 4.3.1 Church numerals: 2.1.3 Church-Turing thesis: 4.1.5 clauses: 1.1.6 closed world assumption: 4.4.3 closure: Chapter 2 closure property: 2.2 code generator: 5.5.1 coerce: 2.5.2 coercion: 2.5.2 combinations: 1.1.1 comments: 2.2.3 compacting: 5.3.2 compilation: 5.5 compile-time environment: 5.5.6 composition: 1.3.4 compound data: Chapter 2 compound data object: Chapter 2 compound procedure: 1.1.4 computability: 4.1.5 computational process: Chapter 1 concurrently: 3.4 congruent modulo: 1.2.6 connectors: 3.3.5 consequent expression: 1.1.6 constraint networks: 3.3.5 constructors: 2.1 continuation procedures: 4.3.3 continued fraction: 1.3.3 control structure: 4.4.3 controller: 5.1 conventional interfaces: Chapter 2 conventional interfaces: 2.2.3 current time: 3.3.4 D data: Chapter 1 data: 2.1.3 data abstraction: Chapter 2 data abstraction: 2.1 data paths: 5.1 data-directed: 2.4 data-directed programming: Chapter 2 data-directed programming: 2.4.3 deadlock: 3.4.2 deadlock-recovery: 3.4.2 debug: Chapter 1 deep binding: 4.1.3 deferred operations: 1.2.1 delayed argument: 3.5.4 delayed evaluation: Chapter 3 delayed evaluation: 3.5 delayed object: 3.5.1 dense: 2.5.3 dependency-directed backtracking: 4.3.1 depth-first search: 4.3.1 deque: 3.3.2 derived expressions: 4.1.2 digital signals: 3.3.4 dispatching on type: 2.4.3 displacement number: 5.5.6 dotted-tail notation: 2.2.1 driver loop: 4.1.4 E empty list: 2.2.1 encapsulated: 3.1.1 enclosing environment: 3.2 entry points: 5.1.1 enumerator: 2.2.3 environment: 1.1.2 environment model: Chapter 3 environments: 3.2 Euclid’s Algorithm: 1.2.5 Euclidean ring: 2.5.3 evaluating: 1.1.1 evaluator: Chapter 4 event-driven simulation: 3.3.4 evlis tail recursion: 5.4.1 execution procedure: 4.1.7 explicit-control evaluator: 5.4 expression: 1.1.1 F failure continuation: 4.3.3 FIFO: 3.3.2 filter: 1.3.1 filter: 2.2.3 first-class: 1.3.4 fixed point: 1.3.3 fixed-length: 2.3.4 forcing: 4.2.2 forwarding address: 5.3.2 frame: 4.4.2 frame coordinate map: 2.2.4 frame number: 5.5.6 framed-stack: 5.4.1 frames: 3.2 free: 1.1.8 free list: 5.3.1 front: 3.3.2 full-adder: 3.3.4 function boxes: 3.3.4 functional programming: 3.1.3 functional programming languages: 3.5.5 G garbage: 5.3.2 garbage collection: 5.3 garbage collection: 5.3.2 garbage collector: 3.3.1 garbage-collected: 4.2.2 generic operations: Chapter 2 generic procedures: 2.3.4 generic procedures: 2.4 glitches: Chapter 1 global: 1.2 global: 3.2 global environment: 1.1.2 golden ratio: 1.2.2 grammar: 4.3.2 H half-adder: 3.3.4 half-interval method: 1.3.3 Halting Theorem: 4.1.5 headed list: 3.3.3 hiding principle: 3.1.1 hierarchical: 2.2 hierarchy of types: 2.5.2 higher-order procedures: 1.3 Horner’s rule: 2.2.3 I imperative programming: 3.1.3 indeterminates: 2.5.3 index: 5.3.1 indexing: 4.4.2 instantiated with: 4.4.1 instruction counting: 5.2.4 instruction execution procedure: 5.2.1 instruction sequence: 5.5.1 instruction tracing: 5.2.4 instructions: Chapter 5 instructions: 5.1.1 integerizing factor: 2.5.3 integers: 1.1 integrator: 3.5.3 interning: 5.3.1 interpreter: Chapter 1 interpreter: Chapter 4 invariant quantity: 1.2.4 inverter: 3.3.4 iterative improvement: 1.3.4 iterative process: 1.2.1 K k-term: 1.3.3 key: 2.3.3 L labels: 5.1.1 lazy evaluation: 4.2.1 lexical address: 5.5.6 lexical addressing: 4.1.3 lexical scoping: 1.1.8 linear iterative process: 1.2.1 linear recursive process: 1.2.1 linkage descriptor: 5.5.1 list: 2.2.1 list: 2.2.1 list: 2.2.1 list structure: 2.2.1 list-structured: 2.1.1 list-structured memory: 5.3 local evolution: 1.2 local state variables: 3.1 location: 5.3.1 logic-programming: Chapter 4 logical and: 3.3.4 logical deductions: 4.4.1 logical or: 3.3.4 M machine language: 5.5 macro: 4.1.2 map: 2.2.3 mark-sweep: 5.3.2 memoization: 1.2.2 Memoization: 3.3.3 memoize: 4.2.2 merge: 3.5.5 message passing: 2.1.3 message passing: 2.4.3 message-passing: 3.1.1 metacircular: 4.1 Metalinguistic abstraction: Chapter 4 Miller-Rabin test: 1.2.6 modular: Chapter 3 modulo: 1.2.6 modulo: 1.2.6 modus ponens: 4.4.3 moments in time: 3.4 Monte Carlo integration: 3.1.2 Monte Carlo simulation: 3.1.2 mutable data objects: 3.3 mutators: 3.3 mutex: 3.4.2 mutual exclusion: 3.4.2 N n-fold smoothed function: 1.3.4 native language: 5.5 needed: 5.5.1 networks: Chapter 4 Newton’s method: 1.3.4 nil: 2.2.1 non-computable: 4.1.5 non-strict: 4.2.1 nondeterministic: 3.4.1 nondeterministic choice point: 4.3.1 nondeterministic computing: Chapter 4 nondeterministic computing: 4.3 normal-order: 4.2.1 normal-order evaluation: 1.1.5 normal-order evaluation: Chapter 4 O obarray: 5.3.1 object program: 5.5 objects: Chapter 3 open-code: 5.5.5 operands: 1.1.1 operator: 1.1.1 operator: 4.1.6 or-gate: 3.3.4 order of growth: 1.2.3 ordinary: 2.5.1 output prompt: 4.1.4 P package: 2.4.3 painter: 2.2.4 pair: 2.1.1 pair: 2.1.1 parse: 4.3.2 Pascal’s triangle: 1.2.2 pattern: 4.4.1 pattern matcher: 4.4.2 pattern matching: 4.4.2 pattern variable: 4.4.1 pipelining: 3.4 pointer: 2.2 poly: 2.5.3 power series: 3.5.2 predicate: 1.1.6 predicate: 1.1.6 prefix: 2.3.4 prefix code: 2.3.4 prefix notation: 1.1.1 pretty-printing: 1.1.1 primitive constraints: 3.3.5 probabilistic algorithms: 1.2.6 procedural abstraction: 1.1.8 procedural epistemology: Preface 1e procedure: 1.2.1 procedure definitions: 1.1.4 procedures: Chapter 1 process: 1.2.1 program: Chapter 1 programming languages: Chapter 1 prompt: 4.1.4 pseudo-random: 3.1.2 pseudodivision: 2.5.3 pseudoremainder: 2.5.3 Q quasiquote: 5.5.2 queries: 4.4 query language: 4.4 queue: 3.3.2 quote: 2.3.1 R Ramanujan numbers: 3.5.3 rational functions: 2.5.3 RC circuit: 3.5.3 read-eval-print loop: 1.1.1 reader macro characters: 4.4.4.7 real numbers: 1.1 rear: 3.3.2 recursion equations: Chapter 1 Recursion theory: 4.1.5 recursive: 1.1.3 recursive: 1.1.8 recursive process: 1.2.1 red-black trees: 2.3.3 referentially transparent: 3.1.3 register machine: Chapter 5 register table: 5.2.1 registers: Chapter 5 released: 3.4.2 remainder of: 1.2.6 resolution principle: 4.4 ripple-carry adder: 3.3.4 robust: 2.2.4 RSA algorithm: 1.2.6 rules: 4.4 rules: 4.4.1 S satisfy: 4.4.1 scope: 1.1.8 selectors: 2.1 semaphore: 3.4.2 separator code: 2.3.4 sequence: 2.2.1 sequence accelerator: 3.5.3 sequences: 1.3.1 serializer: 3.4.2 serializers: 3.4.2 series RLC circuit: 3.5.4 shadow: 3.2 shared: 3.3.1 side-effect bugs: 3.1.3 sieve of Eratosthenes: 3.5.2 smoothing: 1.3.4 source language: 5.5 source program: 5.5 sparse: 2.5.3 special forms: 1.1.3 stack: 1.2.1 stack: 5.1.4 state variables: 1.2.1 state variables: 3.1 statements: 5.5.1 stop-and-copy: 5.3.2 stratified design: 2.2.4 stream processing: 1.1.5 streams: Chapter 3 streams: 3.5 streams: 3.5 strict: 4.2.1 subroutine: 5.1.3 substitution: 1.1.5 substitution model: 1.1.5 subtype: 2.5.2 success continuation: 4.3.3 summation of a series: 1.3.1 summer: 3.5.3 supertype: 2.5.2 symbolic expressions: Chapter 2 syntactic sugar: 1.1.3 syntax: 4.1 systematically search: 4.3.1 systems: Chapter 4 T tableau: 3.5.3 tabulation: 1.2.2 tabulation: 3.3.3 tagged architectures: 5.3.1 tail-recursive: 1.2.1 tail-recursive: 5.4.2 target: 5.5.1 thrashing: UTF thunk: 4.2.2 thunks: 4.2.2 time: 3.4 time segments: 3.3.4 tower: 2.5.2 tree accumulation: 1.1.3 tree recursion: 1.2.2 trees: 2.2.2 truth maintenance: 4.3.1 Turing machine: 4.1.5 type field: 5.3.1 type tag: 2.4.2 type tags: 2.4 type-inferencing: 3.5.4 typed pointers: 5.3.1 U unbound: 3.2 unification: 4.4 unification: 4.4.2 unification: 4.4.2 unification algorithm: 4.4 univariate polynomials: 2.5.3 universal machine: 4.1.5 upward-compatible extension: 4.2.2 V value: 1.1.2 value of a variable: 3.2 values: 2.3.1 variable: 1.1.2 variable-length: 2.3.4 vector: 5.3.1 W width: 2.1.4 wires: 3.3.4 wishful thinking: 2.1.1 Z zero crossings: 3.5.3 Jump to: A B C D E F G H I K L M N O P Q R S T U V W Z Next: Colophon, Prev: Figures, Up: Top [Contents] Prev: Term Index, Up: Top [Contents] Colophon On the cover page is Agostino Ramelli’s bookwheel mechanism from 1588. 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). Knuth wasn't taking a stand one way or the other on the question of free-versus-proprietary software; he just needed a better typesetting system in order to complete his real goal—a book on computer programming—and saw no reason not to release his system to the world when done. 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. These licenses have not caught on much beyond the specific programs they were made for, and will not be discussed in this chapter; they are mentioned here only for the sake of completeness. pages: 504 words: 89,238 Natural language processing with Python by Steven Bird, Ewan Klein, Edward Loper [Kiss and Strunk, 2006] Tibor Kiss and Jan Strunk. Unsupervised multilingual sentence boundary detection. 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. MIT Press, Cambridge, MA, 1995. [Levin, 1993] Beth Levin. English Verb Classes and Alternations. In , the data is streamed to the calling function. 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. Python Coding Style When writing programs you make many subtle choices about names, spacing, comments, and so on. 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. Nevertheless, a fair amount of progress has been made and continues to be made, aided by steady improvements in hardware. J. 4 Gorbachev, Mikhail 86 graceful degradation 7 graphical models 11 growth 1–7, 48–55, 69–75, 83, 163, 261, 281 H Hail Mary approach 198–200, 207, 293, 294 Hanson, Robin 2, 160, 261, 270, 271, 287 hardware overhang 73, 240–243, 274, 289, 301, 302 hedonism 140, 210 hedonium 140, 219 Helsinki Declaration 188 heuristic search 6 Hill, Benny 105 hippocampus 47 HLMI, see machine intelligence, human-level Hodgkin–Huxley model 25 human baseline 62–77, 82 human extinction, see existential risk Human Genome Project 86, 253, 276 human intelligence 5–14, 24–58, 98–99, 159–184, 242–254, 255–257 human–machine interface, see cyborg I impersonal perspective 228–246 in vitro fertilization, see embryo selection incentive methods 131–143 cryptographic reward tokens 133 social integration 131–132, 156–158, 159, 202, 283 indirect normativity 141–150, 209–227, 262, 298 indirect reach 58 inductive bias 9–10 Industrial Revolution 2, 80, 161–163 infrastructure profusion 123–125, 153, 187, 226, 282 institution design 202–208 instrumental convergence thesis 105–116 intelligence explosion 2–5, 22–51, 62–77, 78–90, 95–104, 108, 115–126, 127–128, 136, 151, 160, 165, 178, 198, 205, 227, 228–254, 256–260, 274, 276, 282, 284, 289, 300, 301–302 Internet 16, 45–49, 67–77, 85, 94–98, 130, 146, 241, 271 inventory control systems 16 IVF, see embryo selection J Jeopardy!13 K Kasparov, Garry 12 Kepler, Johannes 14 Knuth, Donald 14, 264 Kurzweil, Ray 2, 261, 269 L Lenat, Douglas 12, 263 Logic Theorist (system) 6 logicist paradigm, see Good Old-Fashioned Artificial Intelligence (GOFAI) Logistello 12 M machine intelligence; see also artificial intelligence human-level (HLMI) 4, 19–21, 27–35, 73–74, 207, 243, 264, 267 revolution, see intelligence explosion machine learning 8–18, 28, 121, 152, 188, 274, 290 machine translation 15 macro-structural development accelerator 233–235 malignant failure 123–126, 149, 196 Malthusian condition 163–165, 252 Manhattan Project 75, 80–87, 276 McCarthy, John 5–18 McCulloch–Pitts neuron 237 MegaEarth 56 memory capacity 7–9, 60, 71 memory sharing 61 Mill, John Stuart 210 mind crime 125–126, 153, 201–208, 213, 226, 297 Minsky, Marvin 18, 261, 262, 282 Monte Carlo method 9–13 Moore’s law 24–25, 73–77, 274, 286; see also computing power moral growth 214 moral permissibility (MP)218–220, 297 moral rightness (MR)217–220.296, 297 moral status 125–126, 166–169, 173, 202–205, 268, 288, 296 Moravec, Hans 24, 265, 288 motivation selection 29, 127–129, 138–144, 147, 158, 168, 180–191, 222 definition 138 motivational scaffolding 191, 207 multipolar scenarios 90, 132, 159–184, 243–254, 301 mutational load 41 N nanotechnology 53, 94–98, 103, 113, 177, 231, 239, 276, 277, 299, 300 natural language 14 neural networks 5–9, 28, 46, 173, 237, 262, 274 neurocomputational modeling 25–30, 35, 61, 301; see also whole brain emulation (WBE) and neuromorphic AI neuromorphic AI 28, 34, 47, 237–245, 267, 300, 301 Newton, Isaac 56 Nilsson, Nils 18–20, 264 nootropics 36–44, 66–67, 201, 267 Norvig, Peter 19, 264, 282 O observation selection theory, see anthropics Oliphant, Mark 85 O’Neill, Gerard 101 ontological crisis 146, 197 optimality notions 10, 186, 194, 291–293 Bayesian agent 9–11 value learner (AI-VL) 194 observation-utility-maximizer (AI-OUM) 194 reinforcement learner (AI-RL) 194 optimization power 24, 62–75, 83, 92–96, 227, 274 definition 65 oracle AI 141–158, 222–226, 285, 286 definition 146 orthogonality thesis 105–109, 115, 279, 280 P paperclip AI 107–108, 123–125, 132–135, 153, 212, 243 Parfit, Derek 279 Pascal’s mugging 223, 298 Pascal’s wager 223 person-affecting perspective 228, 245–246, 301 perverse instantiation 120–124, 153, 190–196 poker 13 principal–agent problem 127–128, 184 Principle of Epistemic Deference 211, 221 Proverb (program) 12 Q qualia, see consciousness quality superintelligence 51–58, 72, 243, 272 definition 56 R race dynamic, see technology race rate of growth, see growth ratification 222–225 Rawls, John 150 Reagan, Ronald 86–87 reasons-based goal 220 recalcitrance 62–77, 92, 241, 274 definition 65 recursive self-improvement 29, 75, 96, 142, 259; see also seed AI reinforcement learning 12, 28, 188–189, 194–196, 207, 237, 277, 282, 290 resource acquisition 113–116, 123, 193 reward signal 71, 121–122, 188, 194, 207 Riemann hypothesis catastrophe 123, 141 robotics 9–19, 94–97, 117–118, 139, 238, 276, 290 Roosevelt, Franklin D.85 RSA encryption scheme 80 Russell, Bertrand 6, 87, 139, 277 S Samuel, Arthur 12 Sandberg, Anders 265, 267, 272, 274 scanning, see whole brain emulation (WBE) Schaeffer, Jonathan 12 scheduling 15 Schelling point 147, 183, 296 Scrabble 13 second transition 176–178, 238, 243–245, 252 second-guessing (arguments) 238–239 seed AI 23–29, 36, 75, 83, 92–96, 107, 116–120, 142, 151, 189–198, 201–217, 224–225, 240–241, 266, 274, 275, 282 self-limiting goal 123 Shakey (robot) 6 SHRDLU (program) 6 Shulman, Carl 178–180, 265, 287, 300, 302, 304 simulation hypothesis 134–135, 143, 278, 288, 292 singleton 78–90, 95–104, 112–114, 115–126, 136, 159, 176–184, 242, 275, 276, 279, 281, 287, 299, 301, 303 definition 78, 100 singularity 1, 2, 49, 75, 261, 274; see also intelligence explosion social signaling 110 somatic gene therapy 42 sovereign AI 148–158, 187, 226, 285 speech recognition 15–16, 46 speed superintelligence 52–58, 75, 270, 271 definition 53 Strategic Defense Initiative (“Star Wars”) 86 strong AI 18 stunting 135–137, 143 sub-symbolic processing, see connectionism superintelligence; see also collective superintelligence, quality superintelligence and speed superintelligence definition 22, 52 forms 52, 59 paths to 22, 50 predicting the behavior of 108, 155, 302 superorganisms 178–180 superpowers 52–56, 80, 86–87, 91–104, 119, 133, 148, 277, 279, 296 types 94 surveillance 15, 49, 64, 82–85, 94, 117, 132, 181, 232, 253, 276, 294, 299 Szilárd, Leó 85 T TD-Gammon 12 Technological Completion Conjecture 112–113, 229 technology race 80–82, 86–90 203–205, 231, 246–252, 302 teleological threads 110 Tesauro, Gerry 12 TextRunner (system) 71 theorem prover 15, 266 three laws of robotics 139, 284 Thrun, Sebastian 19 tool-AI 151–158 definition 151 treacherous turn 116–119, 128 Tribolium castaneum 154 tripwires 137–143 Truman, Harry 85 Turing, Alan 4, 23, 29, 44, 225, 265, 271, 272 U unemployment 65, 159–180, 287 United Nations 87–89, 252–253 universal accelerator 233 unmanned vehicle, see drone uploading, see whole brain emulation (WBE) utility function 10–11, 88, 100, 110, 119, 124–125, 133–134, 172, 185–187, 192–208, 290, 292, 293, 303 V value learning 191–198, 208, 293 value-accretion 189–190, 207 value-loading 185–208, 293, 294 veil of ignorance 150, 156, 253, 285 Vinge, Vernor 2, 49, 270 virtual reality 30, 31, 53, 113, 166, 171, 198, 204, 300 von Neumann probe 100–101, 113 von Neumann, John 44, 87, 114, 261, 277, 281 W wages 65, 69, 160–169 Watson (IBM) 13, 71 WBE, see whole brain emulation (WBE) Whitehead, Alfred N.6 whole brain emulation (WBE) 28–36, 50, 60, 68–73, 77, 84–85, 108, 172, 198, 201–202, 236–245, 252, 266, 267, 274, 299, 300, 301 Wigner, Eugene 85 windfall clause 254, 303 Winston, Patrick 18 wire-heading 122–123, 133, 189, 194, 207, 282, 291 wise-singleton sustainability threshold 100–104, 279 world economy 2–3, 63, 74, 83, 159–184, 274, 277, 285 Y Yudkowsky, Eliezer 70, 92, 98, 106, 197, 211–216, 266, 273, 282, 286, 291, 299 pages: 923 words: 516,602 The C++ Programming Language by Bjarne Stroustrup Brian W. Kernighan and Dennis M. Ritchie: The C Programming Language (Second Edition). Prentice-Hall. 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. George Orwell: 1984. Secker and Warburg. London. 1949. Graham Parrington et al.: The Design and Implementation of Arjuna. 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. ISBN 0-201-88954-4. All rights reserved. – 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. pages: 230 Purely Functional Data Structures by Chris Okasaki (p. 118) David J. King. Functional binomial queues. 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. (pp. 5,130,169,170,171, 184,212) [KT96a] Haim Kaplan and Robert E. 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. Includes bibliographical references and index. ISBN 0-201-89683-4 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. Kepler, Johann, 80, 81. Kilmer, Alfred Joyce, 232. King, James Cornelius, 20. 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. Kozelka, Robert Marvin, 544. Kramp, Christian, 49. Krattenthaler, Christian, 39. 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. Contents: v. 1. Fundamental algorithms. — v. 2. Seminumerical algorithms. — v. 3. Sorting and Searching. ISBN 0-201-03809-9 (v. 1) ISBN 0-201-03822-6 (v. 2) ISBN 0-201-89685-0 (v. 3) 1. 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.) If you were given the job of sorting large quantities of catalog cards by computer, and eventually maintaining a very large file of such cards, and if you had no chance to change these long-standing policies of card filing, how would you arrange the data in such a way that the sorting and merging operations are facilitated? Kirkpatrick, David Galer, 213, 218, 663. Kirschenhofer, Peter, 576, 634, 644, 726, 726. 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. Konheim, Alan Gustave, 376, 505, 548, 732, 740. Koornwinder, Tom Hendrik, 601. pages: 666 words: 181,495 In the Plex: How Google Thinks, Works, and Shapes Our Lives by Steven Levy But the professors understood that behind the goofiness was a formidable mathematical mind. 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. “He was brilliant,” Garcia-Molina says. ., 236, 331, 344–47, 364, 365–66 Kahle, Brewster, 362, 365 Kamangar, Salar, 71–72, 74, 233, 235 and advertising, 86, 89, 91–92, 109, 113 and business plan, 72, 75, 201 and Google motto, 143–44 and YouTube, 248, 260–65 Karen, Alana, 97–98 Karim, Jawed, 243, 247, 250 Kay, Erik, 207 Keyhole, 239–40, 340 Keyword Pricing Index, 118 Khosla, Vinod, 28, 29 Kim, Jini, 166 Klau, Rick, 312, 318 Kleinberg, Jon, 24–26, 34, 38, 292 Knol, 240 Knuth, Donald, 14 Kohl, Herb, 332 Koogle, Timothy, 44 Kordestani, Omid, 75–76, 78, 81, 96, 97, 130, 155, 242 Krane, David, 69–70, 143, 144–45, 150, 156 Kraus, Joe, 28, 136, 201, 374–75 Kundra, Vivek, 322, 326 Kurzweil, Raymond, 66 language, translations, 55, 62–65 Lantos, Tom, 285–87 Larson, Mark, 208 Leach, Jim, 286 Lee, Kai-Fu: and China office, 4, 281–83, 289–90, 291, 292, 293, 294, 296, 298, 302, 303, 305, 307–8, 313 departure of, 307–8, 312 Lee, Steve, 338–39 Lenat, Douglas, 47 Leonard, Herman, 117 Lessig, Lawrence, 359, 360, 363 Levick, Jeff, 96, 110–11, 112–13 Levinson, Arthur, 218, 237 Li, Mark, 293, 298–99 Li, Robin (Yanhong), 26–27, 278, 292, 293, 298 Library of Congress, 352, 361 Liebman, Jason, 103–5 LinkAds, 102–3 Linux, 78, 182, 210 Litvack, Sanford “Sandy,” 345, 347 Liu, John, 296 Liu, Jun, 294, 303–4 long-tail businesses, 85, 105, 107, 118, 243, 334 Lu, Qi, 380 Lucovsky, Mark, 283 Luk, Ben, 290, 302 Maarek, Yoelle, 272 MacDonald, Brian, 380 Macgillivray, Alex “AMac,” 353–55 machine learning, 64–66, 100–101, 385 Malone, Kim (Scott), 107–8, 135 Manber, Udi, 44, 45, 57–58, 68, 240, 355, 380 MapReduce, 199–200 Marconi International Fellowship Award, 278 Markoff, John, 193 Matias, Yossi, 272 Mayer, Marissa, 36, 41, 381 and advertising, 78–79 and APM program, 1, 4, 5, 161–62, 259 and books, 348–50, 358, 365 and Gmail, 170–71 and Google culture, 121, 122, 126–27, 141, 142, 163, 164, 365 and Google motto, 143–44 and Google’s look, 206–7 and management structure, 160, 235 and social networking, 371–73, 375 and stock price, 155, 156–57 McCaffrey, Cindy, 3, 76, 77, 145, 150, 153, 164 McCarthy, John, 127 McLaughlin, Andrew: and China, 276–79, 283–84, 303, 304 and Obama administration, 316, 321, 322–23, 325–26, 327 and privacy, 176–78, 379 memex, 15, 44 Merrill, Douglas, 183 Mi, James, 276 Microsoft: and antitrust issues, 331–32, 344–45 and aQuantive, 331 Bing search engine, 186, 380–81 and books, 361, 363 and browser wars, 206, 283 and China, 281, 282, 283, 284, 285, 304 and competition, 70, 191, 197, 200–212, 218, 220, 266, 282–83, 331, 344–47, 363, 380–81 and Danger, 214 data centers of, 190 and disclosure, 108 and email, 168, 169, 179–80 Excel, 200 and Facebook, 370 Hotmail, 30, 168, 172, 180, 209 IE 7, 209 Internet Explorer, 204–7 and mapping, 342 monopolies of, 200, 331–32, 364 Office, 200, 202, 203 Outlook, 169 PowerPoint, 200, 203 and user data, 335 and values, 144 WebTV, 217 Windows, 200, 210, 212, 219, 331 Windows Mobile, 220 Word, 200 and Yahoo, 343–44, 346, 380 of yesterday, 369 MIDAS (Mining Data at Stanford), 16 Milgrom, Paul, 90 Miner, Rich, 215, 216 Mobile Accord, 325 mobile phones, 214–17, 219–22, 251 Moderator, 323–24 Mohan, Neal, 332, 336 Monier, Louis, 19, 20, 37 Montessori, Maria, 121, 124, 166 Montessori schools, 121–25, 129, 138, 149 Moonves, Leslie, 246 Moore’s Law, 169, 180, 261 Morgan Stanley, 149, 157 Moritz, Mike, 32, 73–74, 80, 147, 247–48, 249 Morozov, Evgeny, 379 Morris, Doug, 261 Mossberg, Walt, 94 Mowani, Rajeev, 38 Mozilla Firefox, 204, 206, 207–8, 209 Murdoch, Rupert, 249, 370 MySpace, 243, 375 name detection system, 50–52 Napier’s constant, 149 National Federation of the Blind, 365–66 National Institute of Standards and Technology (NIST), 65 National Science Digital Library, 347 National Security Agency (NSA), 310 Native Client, 212 navigation, 229, 232, 338 Nelson, Ted, 15 net neutrality, 222, 326–27, 330, 383–84 Netscape, 30, 75, 78, 147, 204, 206 Nevill-Manning, Craig, 129 Newsweek, 2, 3, 20, 179 New York Public Library, 354, 357 Nexus One, 230, 231–32 95th Percentile Rule, 187 Nokia, 341, 374 Norman, Donald, 12, 106 Norvig, Peter, 47, 62, 63, 138, 142, 316 Novell, 70 Obama, Barack, 315–21, 322, 323–24, 329, 346 Obama administration, 320–28 Ocean, 350–55 Och, Franz, 63–65 Oh, Sunny, 283, 297, 298 OKR (Objectives and Key Results), 163–64, 165, 186, 209, 325 Open Book Alliance, 362 Open Handset Alliance, 221–22 OpenSocial, 375–76 operating systems, 210–12 optical character recognition (OCR), 53, 349–50 Oracle, 220 Orkut, 371–73, 375 Otellini, Paul, 218 Overture, 89, 90, 91, 95, 96, 98–99, 103, 150 Oxford University Press, 354, 357 Page, Larry, 3, 5 achievements of, 53, 383 and advertising, 84, 86–87, 90, 92, 94, 95–97, 114, 334, 336–37 ambition of, 12, 39, 73, 127–28, 139, 198, 215, 238, 362, 386–87 and applications, 205, 206, 207, 208, 210, 240–42, 340 and artificial intelligence, 62, 100, 246, 385–86 and BackRub/PageRank, 17, 18, 21–24, 26 and birth of Google, 31–34 and Book Search, 11, 347–52, 355, 357, 359, 361, 362, 364 on capturing all the web, 22–24, 52, 58, 63 on changing the world, 6, 13, 33, 39, 97, 120, 125, 146, 173, 232, 279, 316, 327, 361, 384–85 childhood and early years of, 11–13 and China, 267, 276, 277–78, 279–80, 283, 284, 305, 311 and data centers, 182–83 and eco-activism, 241 and email, 169–72, 174, 179 and Excite, 28–29 and funding, 32, 33–34, 73–75 and hiring practices, 139–40, 142, 182, 271, 386 imagination of, 14, 271 and IPO, 146–47, 149–54, 157 and machine learning, 66, 67 and management, 74, 75–77, 79–82, 110, 143, 158–60, 162–66, 228, 231, 235, 252–53, 254, 255, 260, 272, 273, 386–87 marriage of, 254 as Montessori kid, 121–25, 127–28, 149, 331, 387 and Obama, 315–16 and philanthropy, 257–58 and privacy, 174, 176–77, 337 and robots, 246, 385 and secrecy, 31–32, 70, 72–73, 106, 218 and smart phones, 214–16, 224, 225, 226–30, 234 and social networking, 372 and speed, 184–85, 207 and Stanford, 12–13, 14, 16–17, 28, 29, 34 and trust, 221, 237 values of, 127–28, 130, 132, 135, 139–40, 146, 196, 361, 364 and wealth, 157 and web links, 51 and YouTube, 248 PageRank, 3, 17, 18, 21–24, 27, 34, 38, 48–49, 53, 55, 56, 294 Palm, 216, 221 Park, Lori, 235, 258 Pashupathy, Kannan, 270–72, 277, 282 Passion Device, 230 Patel, Amit, 45–46, 82 and Google motto, 143–44, 146 patents, 27, 39, 89, 102, 221, 235, 237, 350 PayPal, 242, 243 peer-to-peer protocols, 234–35 Peters, Marybeth, 352 Phil, 99–103 Philip, Prince, 122 Picasa, 185–86, 187, 239 Pichai, Sundar, 205–6, 207–8, 209–12 Pichette, Patrick, 120, 150, 254–56 Pike, Rob, 241 Pittman, R. pages: 728 words: 182,850 Cooking for Geeks by Jeff Potter Take time to taste things, both to adjust seasoning and to learn how the taste changes during cooking. Don’t be afraid to burn dinner! 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. It’d be like picking up a dictionary to learn how to write. kitchen organization, Kitchen Organization calibrating instruments, Approaching the Kitchen cleanability considerations, Counter Layout counter layout, Uniform Storage Containers functional grouping, 0(1) Retrieval importance of, 356°F / 180°C: Sugar Begins to Caramelize Visibly kitchen equipment, Prepping Ingredients kitchen pruning, Kitchen Pruning prepping ingredients, Calibrating Your Instruments retrieval and, Kitchen Organization Ried on, Kitchen Pruning storage containers, 0(1) Retrieval kitchen scales, Measuring cups and scales kitchen shears, Spoons & co. kneading (mechanical agitation), Gluten, Mozzarella spheres knives, Kitchen Equipment "failure mode", Knives alloyed steels, Knives bacteria and, Knives basic skills, Knives forged blades, Kitchen Equipment heat treatment, Knives holding, Knives Raper on, Knives repurposing, Knives sharpening, Knives stamped blades, Kitchen Equipment types of, Kitchen Equipment Knuth, Donald, Tips for Newbies Kurti, Nicholas, Sugar L lactic acid, Salty, Yeast in breads lactisole, Combinations of Tastes and Smells, Anti-Sugar: Lactisole Lahey, Jim, Yeast in breads Laiskonis, Michael, 356°F / 180°C: Sugar Begins to Caramelize Visibly Latin American cuisine, Regional/Traditional Method Le Creuset, Pots and pans leaveners, Biological Leaveners biological, Biological Leaveners chemical, Kitchen Pruning, Chemical Leaveners mechanical, Mechanical Leaveners multiple, Egg Yolks Lebovitz, David, Whipped Cream lecithin, Playing with Chemicals, Making Foams: Lecithin Lego ice cream maker, Smell (Olfactory Sense) Lemon Lentil Soup, Reading Between the Lines Lemon Meringue Pie, Making gels: Starches Lemony Quinoa and Asparagus with Shrimp Scampi, Kitchen Pruning Lersch, Martin, Gluten, Yeast in breads Leucippus, Smell + Taste = Flavor Lime Marmalade, Sugar limonin, Sugar lipase (enzyme), Acids and Bases liquid nitrogen "cooking" with, Fun with Hardware, "Cooking" with Cold: Liquid Nitrogen and Dry Ice experimenting with, 158°F / 70°C: Vegetable Starches Break Down parasites and, How to Prevent Foodborne Illness Caused by Parasites liquid smoke, Liquid Smoke: Distilled Smoke Vapor listeria, How to Prevent Foodborne Illness Caused by Parasites, Foodborne Illness and Sous Vide Cooking Listeria monocytogenes, How to Prevent Foodborne Illness Caused by Bacteria listeriosis, How to Prevent Foodborne Illness Caused by Bacteria locus coeruleus, Taste == Feedback lye (sodium hydroxide), Acids and Bases lysine, Meat Glue: Transglutaminase M Mac ‘n Cheese, Adapt and Experiment Method macronutrients, A Few Words on Nutrition Maillard reaction defined, Time and Temperature: Cooking’s Primary Variables grilled meat and, Heat Transfer and Doneness temperature for, Reading Between the Lines, Pots and pans, Cooked = Time * Temperature, 310°F / 154°C: Maillard Reactions Become Noticeable Maillard, Louis Camille, 310°F / 154°C: Maillard Reactions Become Noticeable main dishes Bacon-Wrapped Scallops, Meat Glue: Transglutaminase Beef Steak Tips, Beef and other red meats Beef Stew, Unitaskers Brisket, 48-Hour, Beef and other red meats Cheeseburger, How to Prevent Foodborne Illness Caused by Bacteria Chicken, Broiled and Roasted, 310°F / 154°C: Maillard Reactions Become Noticeable Crepes, Unitaskers Duck Confit, 154°F / 68°C: Collagen (Type I) Denatures Duck Confit Sugo, Reading Between the Lines Grilled Fish with Bayou Sauce or Mustard Sauce, Adapt and Experiment Method Hot Dog, Electrocuted, Making ice cream Lemony Quinoa and Asparagus with Shrimp Scampi, Kitchen Pruning Mac ‘n Cheese, Adapt and Experiment Method Oven-Cooked Barbeque Ribs, Liquid Smoke: Distilled Smoke Vapor Pork Chops Stuffed with Cheddar Cheese and Poblano Peppers, Wet brining Salmon Poached in Olive Oil, 104°F / 40°C and 122°F / 50°C: Proteins in Fish and Meat Begin to Denature Salt-Roasted Fish, Wet brining Scallop Ceviche, Acids and Bases Seared Scallops, 310°F / 154°C: Maillard Reactions Become Noticeable Seared Steak, Temperature gradients Seared Tuna with Cumin and Salt, 104°F / 40°C and 122°F / 50°C: Proteins in Fish and Meat Begin to Denature Seitan, Gluten Shrimp Roll-up, Liquid Smoke: Distilled Smoke Vapor Slow-Cooked Short Ribs, 154°F / 68°C: Collagen (Type I) Denatures Squid Bruschetta, 154°F / 68°C: Collagen (Type I) Denatures maltodextrin, "Melts" in your mouth: Maltodextrin mandolins, Mixers & co. 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. A PPENDIX G. S UGGESTED R EADING L IST Refactoring: Improving the Design of Existing Code by Martin Fowler. 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. If your program is slow, then first check to see whether you are violating one of these principles. pages: 292 words: 62,575 97 Things Every Programmer Should Know by Kevlin Henney A good programmer should also know when to use an abominable algorithm. 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

Sometimes it will require two random numbers, usually three, and occasionally four or more numbers to reach a total bigger than 1. 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. Each new version number is a closer approximation to the true value of e.

pages: 525 words: 149,886

Higher-Order Perl: A Guide to Program Transformation by Mark Jason Dominus

, however, will generate an “Argument isn’t numeric” warning if warnings are enabled. 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. Other notable defenestrations have occurred in 1419 and 1948.

(back) 5 Isaac Newton discovered and wrote about the method first, but his write-up wasn’t published until 1736. 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

For instance, Woods’ vision of a mist-covered toll bridge protected by a stubborn troll came during a break in hacking one night, when Woods and some other hackers decided to watch the sun rise at a mist-shrouded Mount Diablo, a substantial drive away. 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). It was at Stanford that hackers would actually leave their terminals for a daily game of volleyball.

The AI lab began to look for teachers as well as researchers, and the hackers were seldom interested in the bureaucratic hassles, social demands, and lack of hands-on machine time that came with teaching courses. 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. He was in California, and he had bought a car. With all these changes, some of the hackers sensed that an era was ending.

pages: 931 words: 79,142

Concepts, Techniques, and Models of Computer Programming by Peter Van-Roy, Seif Haridi

[112] B. W. Kernighan and D. M. Ritchie. The C Programming Language (ANSI C), 2nd edition. 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. Available at http://www.mozart-oz.org/. [117] 858 References [118] S. Rao Kosaraju.

pages: 462 words: 172,671

Clean Code: A Handbook of Agile Software Craftsmanship by Robert C. Martin

Remember the old joke about the concert violinist who got lost on his way to a performance? 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. We name our jar files and war files and ear files. We name and name and name.

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? Could you manage all the details yourself? Probably not.

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. 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.

Kermack, William Ogilvy, 74. Kerr, Leslie Robert, 699. Kesner, Oliver, 226. 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. Kolmogorov, Andrei Nikolaevich (KoJiMoropoB, AH 56, 169, 178, 183. Kolmogorov-Smirnov distribution, 57-60. table, 51.

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. However, it also carries with it legacy components and functionality designed to maintain its backward compatibility.

It is more interesting to look deeper into the criticism of the masters themselves. 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.” Dijkstra was one of the most influential computer scientists; his writings are still alive with valuable advice, and they make a salutary reading when attacked by the latest fashion or silver bullet in programming.

pages: 834 words: 180,700

The Architecture of Open Source Applications by Amy Brown, Greg Wilson

[Gra81] Jim Gray: "The Transaction Concept: Virtues and Limitations". Proc. Seventh International Conference on Very Large Data Bases, pages 144–154, 1981. [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. [LCWB+11] H. Andrées Lagar-Cavilla, Joseph A. Whitney, Roy Bryant, Philip Patchin, Michael Brudno, Eyal de Lara, Stephen M.

Design Reflections My experience in working on Graphite has reaffirmed a belief of mine that scalability has very little to do with low-level performance but instead is a product of overall design. 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. By and large Graphite evolved gradually, hurdle by hurdle, as problems arose.

pages: 313 words: 101,403

My Life as a Quant: Reflections on Physics and Finance by Emanuel Derman

Stimulated by the courses on computer science I had taken at the Labs, I realized that I could represent each variable in the set of equations by a node in a directed graph, and that reordering the equations was equivalent to decomposing the graph into its strongly connected components. 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. As we worked together I was impressed by Chris's professional programming skills; I was an amateur, living by my wits, while Chris was the real thing, a researcher working in his area of expertise.

pages: 317 words: 101,074

Needless to say, there will be lots of controversy and negotiation about who can get access to your profile information. It will be crucial that you have such access. 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

(2) (2004-current) Doug has been having difficulty with his memory, but his mind is still great. 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. By that time I had known Knuth for nearly forty year, in a way. (In fact we had both been first published nationally in the same journal.*) I read his first published piece when I was in college, though years later when I was aware of him as a computer professional I did not know it was the same person. * Mad.

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. WEB is effectively a language for writing your programs as works of literature, with code on the sidelines.

pages: 377 words: 110,427

The Boy Who Could Change the World: The Writings of Aaron Swartz by Aaron Swartz, Lawrence Lessig

They accomplish all sorts of complicated functions, work under incredibly high loads, and confront no end of unusual situations. 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. But far more important are the subjective factors. djb’s programs are some of the greatest works of beauty to be comprehended by the human mind.

pages: 423 words: 21,637

On Lisp: Advanced Techniques for Common Lisp by Paul Graham

I feel fortunate to have worked with Alan Apt, a good editor and a good guy. 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. I owe thanks to many others, including Paul Becker, Phil Chapnick, Alice Hartley, Glenn Holloway, Meichun Hsu, Krzysztof Lenk, Arman Maghbouleh, Howard Mullings, NancyParmet, Robert Penny, Gary Sabot, Patrick Slaney, Steve Strassman, Dave Watkins, the Weickers, and Bill Woods.

pages: 404 words: 43,442

The Art of R Programming by Norman Matloff

For more information, refer to the books cited in footnote 1 at the beginning of this chapter. 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

If the number is prime, which means that a[i] is true, another for loop sets all the multiples of that number to false. 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. Even those programmers who use the Sieve of Eratosthenes won't implement it in precisely the same way that I did.

pages: 706 words: 120,784

The Joy of Clojure by Michael Fogus, Chris Houser

Kahan, William, and Joseph Darcy. 1998. “How Java’s Floating-Point Hurts Everyone Everywhere.” 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. Reading, MA: Addison-Wesley. Running quick-sort on a sorted sequence is an O(n2) operation, which for our implementation in chapter 6 completely defeats its laziness.

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: 624 words: 127,987

The Personal MBA: A World-Class Business Education in a Single Volume by Josh Kaufman

The purpose of understanding and analyzing systems is to improve them, which is often tricky—changing systems can often create unintended consequences. 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. Improve your KPIs, and your system will perform better.

pages: 1,331 words: 183,137

Programming Rust: Fast, Safe Systems Development by Jim Blandy, Jason Orendorff

For example, when an enum is used in a compiler to represent the various operators of a programming language, adding a new operator should involve touching all code that handles operators. But sometimes more flexibility is needed. 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. Many things have .write() methods, including Files and TcpStreams.

pages: 968 words: 224,513

The Art of Assembly Language by Randall Hyde

See Write Great Code, Volume 1 (No Starch Press) or the electronic version of The Art of Assembly Language at http://webster.cs.ucr.edu/ or http://www.artofasm.com/ for details concerning the operation of cache memory and how you can optimize your use of cache memory. 8.5 For More Information The HLA Standard Library reference manual contains lots of information about the HLA Standard Library's extended-precision arithmetic capabilities. 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. This discussion includes what is perhaps the most important component of the HLA compile-time language, macros.

Martin Kleppmann-Designing Data-Intensive Applications. The Big Ideas Behind Reliable, Scalable and Maintainable Systems-O’Reilly (2017) by Unknown

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. Databases, caches, search indexes, web servers, and many other systems work this way.

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. Databases, caches, search indexes, web servers, and many other systems work this way.

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. John Backus, “The History of FORTRAN I, II, and III,” Annals of the History of Computing 1 (1979): 21–37. 20.

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

Use a poor random-number generator and you start getting weird correlations and strange results [1231,1238]. 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. Put the same stuff in on two separate occasions and the same stuff comes out both times. Put the same stuff into two identical computers, and the same stuff comes out of both of them.

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. “Denial of Service via Algorithmic Complexity Attacks”, Scott Crosby and Dan Wallach, Proceedings of the 12th Usenix Security Symposium (Security’03), August 2003, p.29.