tag:blogger.com,1999:blog-60089092648330348992015-03-15T17:15:12.525-07:00The Great Knuth ReadDamianhttp://www.blogger.com/profile/12279087272033708352noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-6008909264833034899.post-56329674020134012652008-11-29T14:36:00.000-08:002008-11-29T14:37:00.197-08:001.2.6. Binomial CoefficientsDamianhttp://www.blogger.com/profile/12279087272033708352noreply@blogger.com0tag:blogger.com,1999:blog-6008909264833034899.post-14618911178085431332008-11-10T18:02:00.000-08:002008-11-29T14:35:48.319-08:001.2.5. Permutations and FactorialsPermutations are of huge importance in computer science for the analysis of algorithms. A <i>permutation</i> of objects is an arrangement of those objects in a row. This leads to the concept of <i>factorials</i> which is the product of a given number and all the natural numbers below that to the number one.<br /><br />Knuth notes that it is helpful to remember that 10! is equal to 3,628,800, which represents an approximate dividing line between things that are practical to compute and and things that are not.Damianhttp://www.blogger.com/profile/12279087272033708352noreply@blogger.com0tag:blogger.com,1999:blog-6008909264833034899.post-55104755661072613562008-11-10T17:56:00.000-08:002008-11-10T18:02:17.908-08:001.2.4. Integer Functions and Elementary Number TheoryAn explaination of <i>floor</i> and <i>ceiling</i> are presented. Then laws associated with <i>mod</i> and <i>modulo</i> are presented.Damianhttp://www.blogger.com/profile/12279087272033708352noreply@blogger.com0tag:blogger.com,1999:blog-6008909264833034899.post-4228453590858094552008-11-10T17:41:00.001-08:002008-11-10T17:56:14.887-08:001.2.3. Sums and ProductsThe section begins by explaining what a sum is, and then explores four simple algebraic operations on sums;<ol><br /><li>The distributive law, for products of sums<br /><li>Change of variable<br /><li>Interchanging order of submission<br /><li>Manipulating the domain<br /></ol><br />Following this a notation for products is discussed.Damianhttp://www.blogger.com/profile/12279087272033708352noreply@blogger.com0tag:blogger.com,1999:blog-6008909264833034899.post-72323360652860695572008-11-10T17:21:00.001-08:002008-11-10T17:41:03.682-08:001.2.2. Numbers, Powers, and LogarithmsThis section discusses integers, rationals and real numbers. A complex number is explained. The definition of a logarithm is given, and discussed.Damianhttp://www.blogger.com/profile/12279087272033708352noreply@blogger.com0tag:blogger.com,1999:blog-6008909264833034899.post-45485806835356884652008-11-10T16:54:00.000-08:002008-11-10T17:21:12.663-08:001.2.1. Mathematical InductionMathematical induction is explained, and it is distinguished from inductive reasoning. Proving that an algorithm is valid using this method usually consists of inventing the correct assertions to put into a flow chart.Damianhttp://www.blogger.com/profile/12279087272033708352noreply@blogger.com0tag:blogger.com,1999:blog-6008909264833034899.post-44559738787931778302008-11-10T16:36:00.000-08:002008-11-10T16:59:52.081-08:001.2. Mathematical PreliminariesMathematical notations are used for two reasons in the book; first to describe portions of the algorithms, and second to analyse the performance characteristics of the algorithms.<br /><br />The mathematical calculations will draw from nearly every branch of mathematics, but the majority of calculations can be understood by an average college student.<br /><br />Knuth recommends for the sake of motivation that <i>all readers skim read the rest of section 1.2 lightly at first and return to it later for more intensive study</i>.Damianhttp://www.blogger.com/profile/12279087272033708352noreply@blogger.com0tag:blogger.com,1999:blog-6008909264833034899.post-53781040043486917532008-11-10T16:22:00.000-08:002008-11-10T17:24:02.138-08:001.1. AlgorithmsThis section begins with an investigation of the etymology of the word “algorithm”. <br /><br />Knuth defines the following characteristics for an algorithm;<ol><br /><li><i>Finiteness</i>. An algorithm must always terminate after a finite number of steps.<br /><li><i>Definiteness</i>. Each step must be carried out rigorously and unambiguously.<br /><li><i>Input</i>. An algorithm has zero or more inputs.<br /><li><i>Outputs</i>. An algorithm has one or more outputs.<br /><li><i>Effectiveness</i>. Steps must be sufficiently basic so that they could be done using a pen and paper.<br /></ol>Damianhttp://www.blogger.com/profile/12279087272033708352noreply@blogger.com0tag:blogger.com,1999:blog-6008909264833034899.post-68148515577532270242008-11-10T16:21:00.000-08:002008-11-10T16:59:20.990-08:00VOLUME ONE, CHAPTER ONE. BASIC CONCEPTSThe following postings cover the main points of volume one, chapter one.Damianhttp://www.blogger.com/profile/12279087272033708352noreply@blogger.com0tag:blogger.com,1999:blog-6008909264833034899.post-91593115971482947372008-11-10T16:13:00.000-08:002008-11-29T14:27:56.486-08:00VOLUME ONE PREFACEMost importantly Knuth expresses the view that programming can be "an aesthetic experience much like composing poetry or music”.<br /><br />The book is not an introduction to computer programming; the reader needs to have written some programs already to fully understand it. The main theme of the book can be considered “non-numerical analysis” or “analysis of algorithms” as it focuses on decision-making problems as opposed to mathematical problems.<br /><br />To help make clear the techniques presented in the book Knuth has created his own “ideal” computer with simple rules of operation. <br /><br />Knuth considers Volume I as being still under construction, Knuth hopes to create a final, 4th Edition, in 2012.<br /><center><br /><img src="http://tex.loria.fr/historique/knuth.gif" height=200><br /></center>Damianhttp://www.blogger.com/profile/12279087272033708352noreply@blogger.com0tag:blogger.com,1999:blog-6008909264833034899.post-2536114686193389532008-11-09T04:56:00.000-08:002008-11-29T14:18:08.267-08:00Welcome to the Great Knuth Read<center><img src="http://upload.wikimedia.org/wikipedia/en/6/62/ArtOfComputerProgramming.jpg" height=230></center><br /><b>The Art of Computer Programming</b> is a multi-part monograph written by Donald Knuth, which describes a range of computer algorithms. It is considered the most important collection of books in the field of computer sceince, and the most comprehensive treatment of algorithms. So far, three complete volumes have been released;<br /><ul><br /><li>Volume 1 - Fundamental Algorithms (1968)<br /><li>Volume 2 - Seminumerical Algorithms (1969)<br /><li>Volume 3 - Sorting and Searching (1973)<br /></ul><br />Forthcoming volumes will include;<br /><ul><br /><li>Volume 4 - Combinatorial Algorithms<br /><li>Volume 5 - Syntactic Algorithms<br /><li>Volume 6 - Theory of Context-Free Languages<br /><li>Volume 7 - Compiler Techniques<br /></ul><br /><br />Sections (or fascicles) of Volume 4 are currently being released for beta testing. For more information pop over to Knuth's website;<br /><a href="http://www-cs-faculty.stanford.edu/~knuth/taocp.html">http://www-cs-faculty.stanford.edu/~knuth/taocp.html</a><br /><p><br />This blog will document my reading of these mongraphs, think of this blog as a piece of preformance art, building up slowly into something that will hopefully be both interesting and unexpected.<br /><br /><img src="http://www.ibiblio.org/Dave/Dr-Fun/df200002/df20000210.jpg" height=390>Damianhttp://www.blogger.com/profile/12279087272033708352noreply@blogger.com0