Orcmid's Lair

Computer Science


2004-12-13 -07:24 -0800

see also:
Readings in Personal Computing
Readings in Software Tools
          Readings in Information Processing
Readings in Software Engineering
Readings in System Architecture and Design
Readings in Programming Systems and Languages
Readings in Functional Programming Systems (Miser Project)

Ashenhurst, Robert L., Graham, Susan L. (eds.).  ACM Turing Award Lectures: The First Twenty Years 1966-1985.  ACM Anthology Series.  ACM Press (New York: 1987).  ISBN 0-201-07794-9.
     The complete list is maintained on the ACM web site.
     Author's Biographies
     Introduction to Part I Programming Languages and Systems (Susan L. Graham)
          1966 The Synthesis of Algorithmic Systems (Alan J. Perlis)
          1972 The Humble Programmer (Edsger W. Dijkstra)
          1974 Computer Programming as an Art (Donald E. Knuth [1974])
          1976 Logic and Programming Languages (Dana S. Scott)
          1977 Can Programming Be Liberated from the von Neumann Style? (John Backus)
          1978 The Paradigm of Programming (Robert W. Floyd)
          1980 The Emperor's Old Clothes (Charles Anthony Richard Hoare)
          1983 Reflections on Trusting Trust (Ken Thompson)
          1984 From Programming Language Design to Computer Construction (Niklaus Wirth)
     Introduction to Part II Computers and Computing Methodologies (Richard L. Ashenhurst)
          1967 Computers Then and Now (Maurice V. Wilkes)
          1968 One Man's View of Computer Science (R. W. Hamming [1969])
          1969 Form and Content in Computer Science (Marvin Minsky)
          1970 Some Comments from a Numerical Analyst (J. H. Wilkinson)
          1971 Generality in Artificial Intelligence [Postscript] (John McCarthy)
          1973 The Programmer as Navigator (Charles W. Bachman)
          1975 Computer Science as Empirical Inquiry: Symbols and Search (Allen Newell and Herbert A. Simon)
          1976 Complexity of Computations (Michael O. Rabin)
          1979 Notation as a Tool of Thought (Kenneth E. Iverson)
          1981 Relational Database: A Practical Foundation for Productivity (E. F. Codd [1982])
          1982 An Overview of Computational Complexity (Stephen A. Cook)
          1985 Combinatorics, Complexity, and Randomness (Richard M. Karp)
                   Piecing Together Complexity [Postscript] (Karen Frenkel)
                   Complexity and Parallel Processing: An Interview with Richard Karp [PostScript] (Karen Frenkel)
     Index According to ACM Computing Reviews Classification Scheme
     Name Index
     Subject Index
Biermann, Alan W.  Great Ideas in Computer Science: A Gentle Introduction.  ed.2.  MIT Press (Cambridge, MA: 1990, 1997).  ISBN 0-262-52223-3 pbk. alk. paper
     "This is a book about computers--what they are, how they work, what they can do, and what they cannot do.  It is written for people who read about such topics as computers networks or artificial intelligence and want to understand them, for people who need to have data processed on the job and want to know what can and cannot be done, and for people who see the proliferation of computers throughout society and ask about the meaning of it all.  It is written for doctors, lawyers, preachers, teachers, managers, students, and all others who have a curiosity to learn about computing.  It is also written for computer science students and professionals whose education may not have covered all the important areas, and who want to broaden themselves." -- from the Preface, p.xv.
     "This book was written on the assumption that intelligent people can understand every fundamental issue of computer science if the preparation and explanation are adequate. ...
     "Because casual readers may not wish to read all the chapters, the book is designed to encourage dabbling.  Readers are encouraged to jump to any chapter at any time and read as much as is of interest. ...
     "... Chapter sections labeled A include only introductory material and make few demands on the reader.  One can get an overview of the book in a single evening by reading them.  The B sections are the primary material of the book and may require substantial time and effort, but the reader who completes them will have a deep understanding of the major lessons on that topic.  The C material answers questions that careful readers may ask and supplements the main portions of the book."  -- from the Introduction, p.xxiv.
     I just became aware of this book out of recent discussions of my experience seeing how programming languages are taught and on how the principles of computing (as opposed to the technology du jour) are introduced.  I am very much in favor of this approach and the proposal that computing be made accessible to anyone to the degree that they choose to explore it.  I strongly favor any approach that promotes readers and students distilling out the ideas behind the practices and concrete examples.
     This book offers a practical approach that encourages the reader to sit down at a computer and explore and confirm what is presented.  The book is not a programming text -- programs and programming are introduced as vehicles of demonstration.  I am keenly interested in this hands-on approach and in how that can be used to illustrate principles without having the principle associated too tightly (or even be confused with) the technology that is applied as the instrument of illustration.
     A subset of Pascal is used, in the spirit of [Sedgewick1989], and the examples are developed in Turbo Pascal.  There is a single page devoted to what is needed and how to get started, including the following wonderful paragraph: "The [computer system] manual is necessary because it will tell you which buttons to push on your computer to turn it on and to get your program typed in and running.  Finally, you need an instructor or friend to tell you what the manual did not.  Computer Science, like many disciplines, has an oral tradition, and some of the most important facts are passed only by word of mouth.  You may be able to get along without this help, but learning is usually easier if it is there (p.11)."
     The recognition of the amount of tacit knowledge that is assumed in even the most elementary treatment of computing, as far as hands-on treatment goes, is very welcome.  My experience is that more is called for here, though I can accept the author not choosing to take on that task as part of his project.  Now that Pascal has gone out of favor and economical implementations are no longer commonplace, it will take more work to apply the examples.  This has me wondering whether there is an advantage to two levels of exposition -- something like design plus representative implementation -- if there is going to be provision for hands-on confirmation, demonstration, and exploration that can endure technology fashions while also accentuating how the ideas are manifest in the concrete examples. -- dh:2003-07-31
     Preface to the Second Edition
     Studying Academic Computer Science: An Introduction

     1. An Introduction to Programming: Coding Decision Trees
     2. Text Manipulation and Algorithm Design
     3. Numerical Computation and a Study of Functions
     4. Top-Down Programming, Subroutines, and a Database Application
     5. Simulation
     6. Software Engineering
     7. Electric Circuits
     8. Machine Architecture
     9. Language Translation
     10. Virtual Environments for Computing
     11. Computer Communications
     12. Program Execution Time
     13. Parallel Computation
     14. Noncomputability
     15. Artificial Intelligence
     Appendix A.  The Rules for the Subset of Pascal Used in this Book
     Appendix B.  Two Simulation Programs

Biermann, Alan W., Ramm, Dietolf.  Great Ideas in Computer Science with Java.  MIT Press (Cambridge, MA: 2002).  ISBN 0-262-02497-7 pbk. alk. paper.
     There is an errata at http://www.cs.duke.edu/~dept/Great_Ideas_with_Java/errata.html.
     "This book is written for people who find themselves on the outside of a high-technology world and who want to find a way in. ...
     "This book presents the story of computer science organized around the theme of the 'great ideas' of the field.  These are the discoveries, the paradigms, the simplifying equations that attract the attention of everyone who comes near, and they provide the best-known paths to understanding. ...
     "The method of teaching is by doing rather than just by reading and talking.  The theory is that if you personally go through the steps of creating a program to do something or if you hand-simulate a process, that mechanism and the related ideas will get built into your body as well as your mind.  They will become instinctive as well as intellectually known. ... This is the problems-oriented approach to teaching that has been so successful in the traditional quantitative sciences." -- from the Preface, pp. xiii-xiv.
     A number of alterations have appeared since the previous version [Biermann1997].  First, scholarly publishing is losing its memory -- there is no recognition of prior editions in the history of the book and certainly not in the copyright notice -- a recent practice about which I have my suspicions and my doubts.
  And the Preface completely disregards the possibility that we have been here before.
      Secondly, the language of choice for illustration of computer science is now Java.  With regard to availability, support, and high interest, that is difficult to fault.  It is also an avenue to the currently-favored approach for GUI and graphics work as well as a way of exploring an object-oriented technology (OOT).
      The "gentle introduction" isn't quite so gentle, and the immediate support for hands-on experience does not come across so well nor so early as in the previous chapters 1-2.  It seems that this book is seriously intended as a textbook with a companion laboratory or instructional support for the nitty-gritty, working-at-a-keyboard parts.  I miss the promise of an introduction for anyone with the interest and curiosity.  
      There is something less situated about the introduction of Java and starting with applets so unceremoniously.  I am also concerned with having to deal with OOT so early just because there is no other way to accomplish anything useful in Java.  Here the neophyte may never know, in a clear way, whether we are doing OOP or simply using the OOT to accomplish some straightforward OOP-indifferent task by idiomatic application of the object-oriented technology (e.g., as with main(), or java.lang.Math, or init()-as-main()).  And identifying what we are actually doing when we extend a GUI-component class, and how that ties to OOP, takes some masterful explication (not included here -- where interface ActionListener implementation begins on p.86 and is nowhere addressed that I can find.) That it cost the readers of this book an introduction to text processing and algorithm design is unfortunate.
     Having said all of that, I strongly favor a hands-on, experience-it and demonstrate-it-yourself approach.  There is much value here.  And, I think, there's more to accomplish in execution on the promise to demonstrate the great ideas in a way that brings them to life for people.
  It would be useful to not have the tool be in the way. --dh:2003-07-31
     An updated, extended version of this précis appears on amazon.com. --dh:2003-10-17
     Studying Academic Computer Science: An Introduction
     1. The World Wide Web
    2. Watch Out: Here Comes Java
     3. Numerical Computation and a Study of Functions
     4. Top-Down Programming, Subroutines and a Database Application
     5. Graphics, Classes, and Objects
     6. Simulation
     7. Software Engineering
     8. Machine Architecture
     9. Language Translation
     10. Virtual Environments for Computing
     11. Security, Privacy, and Wishful Thinking
     12. Computer Communication
     13. Program Execution Time
     14. Parallel Computation
     15. Noncomputability
     16. Artificial Intelligence
     Appendix: The IntField and DoubleField Classes
Bird, Richard., de Moor, Oege.  Algebra of Programming.  Prentice-Hall (Harlow, England: 1997).  ISBN 0-13-507245-X.
     "[This book] codifies the basic laws of algorithmics, and shows how they can be used to classify many ingenious and important programs into families related by the algebraic properties of their specifications.  The formulae and equations that you will see here share the elegance of those which underlie physics or chemistry or any other branch of basic science; and like them, they inspire our interest, enlarge our understanding, and hold out promise of enduring benefits in application."  From the Foreword by Tony Hoare, p. ix.

     1. Programs
     2. Functions and Categories
     3. Applications
     4. Relations and Allegories
     5. Datatypes in Allegories
     6. Recursive Programs
     7. Optimisation Problems
     8. Thinning Algorithms
     9. Dynamic Programming
     10. Greedy Algorithms
Brookshear, J.Glenn.  Computer Science: An Overview.  ed.7.  Addison-Wesley (Boston: 2003).  ISBN 0-201-78130-1 pbk.
     2002-11-18: This book is designed and promoted as a textbook for module CS0, Introduction to Computer Science
.  The traditional designation (introduced in Computer Science Curriculum 78) of courses CS1, CS2, ... commences with programming.  In breadth-first approaches, there is an overview of computer science topics that precedes the first collegiate programming course.   The overview can be designed for non-majors as well.  This is apparently CS0, or, in the terminology for Computing Curriculum 2001, CS100b.  Providing this breadth-first overview for non-majors and majors alike is the express purpose of this book.
     "I wrote this text for both computer science majors and students from other disciplines.  As for computer science majors, most begin their studies with the illusion that computer science is programming and Web browsing since that is essentially all they have seen.  Yet computer science is much more than this." -- From the preface, p.v.
     2002-11-02, -11-28: When I first learned that this book is used for the mandatory Computer Structures course of the University of Liverpool M.Sc in Information Technology on-line degree, I checked it out on amazon.com.  I was a little surprised at the cross-section of the reader reviews.  There were those -- apparently practitioners -- who disliked the book for the absence of programming and software approaches.  Many of these dismissed it as too elementary.  There was a second group who found it valuable in preparation for examinations in introductory computer science.  And then there were those who raved about the book because it gave them grounding and insights that they had been seeking.  It would seem that some did not check to see what the author's intention is.  I expect to be satisfied.  One odd thing though.  As soon as I ordered the book, amazon.com began recommending other books of an elementary nature that are considered good study guides for various introductory-subject examinations.  Their recommendations have lately returned to something more like my typical interests, however.
     The author's web site provides an errata for this edition.
     The publisher has a web site for the book, with links, PowerPoint slides, and supplementary materials.
          0. Introduction
     Part One: Machine Architecture
          1. Data Storage
          2. Data Manipulation
     Part Two: Software
          3. Operating Systems and Networks
          4. Algorithms
          5. Programming Languages
          6. Software Engineering
     Part Three: Data Organization
          7. Data Structures
          8. File Structures
          9. Database Structures
     Part Four: The Potential of Machines
          10. Artificial Intelligence
          11. Theory of Computation
          A. ASCII
          B. Circuits to Manipulate Two's Complement Representations
          C. A Simple Machine Language
          D. High-Level Language Program Examples
          E. The Equivalence of Iterative and Recursive Structures
          F. Answers to Questions/Exercises
Codd, E.F.  A Relational Model of Data for Large Shared Data Banks.  Comm. ACM 13, 6 (June 1970), 377-387.  Available on the web as an ACM Classic (without Section 2).  A PDF of the complete paper is available here.
Codd, E.F.  Normalized Data Base Structure: A Brief Tutorial.  Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access, and Control.  San Diego, California, November 11-12, 1971.
Codd, E.F.  Further Normalization of the Data Base Relational Model.  in Rustin, Randall J.(ed.).  Data Base Systems.   Courant Computer Symposia Series, vol. 6.  Prentice-Hall (Englewood Cliffs, NJ: 1972).
     This is is where the second and third normal forms were introduced.  Ron Fagin introduced the fourth and fifth normal forms.  Chris Date has introduced a sixth, but it is clear that the the fifth is complete.  
Codd, E.F.  Relational Completeness of Data Base Sublanguages in Data Base Systems.  pp. 65-98 in Rustin, Randall J.(ed.).  Data Base Systems.   Courant Computer Symposia Series, vol. 6.  Prentice-Hall (Englewood Cliffs, NJ: 1972).
Codd, E.F.  Interactive Support for Nonprogrammers:  The Relational and Network Approach.  in Proc. ACM SIGMOD Workshop on Data Description, Access and Control, vol. II.  Ann Arbor, Michigan, May, 1974.
Codd, E.F.  Extending the Data Base Relational Model to Capture More MeaningACM Trans. on Database Systems 4, 4 (December 1979), 397-434.  A PDF is available here.
Codd, E.F.  Data Models in Database Management.  ACM SIGMOD Record 11, 2 (Feb. 1981).
Codd, E.F.  The 1981 ACM Turing Award Lecture: Relational Databases -- A Practical Foundation for Productivity.  Comm. ACM 25, 2 (February, 1982).
Date, C.J.  The Database Relational Model: A Retrospective Review and Analysis. Addison-Wesley (Reading, MA: 2001).  ISBN 0-201-61294-1 pbk.  A historical account and assessment of E. F. Codd's contribution to the field of database technology.
     "This book consists in essence of a series of twelve articles, originally published in the print and online portions of the Miller Freeman magazine Intelligent Enterprise (Vol. 1, Nos. 1-3, and vol.2, Nos. 1-9, October 1998 onward).  The overall title for the series was '30 Years of Relational,' ... to celebrate the relational model's 30th birthday ... [and] to serve as a historical account and impartial analysis of E. F. Codd's (huge!) contribution to the field of database technology ... with a view to assessing their true significance and restating (and reinforcing) their message for a new generation of database professionals."  -- from the Preface.
     1. The Birth of the Relational Model, Part 1 [October 1998]
     2. The Birth of the Relational Model, Part 2
     3. The Birth of the Relational Model, Part 3 [December 1998]
     4. Codd's Relational Algebra [January 5, 1999]
     5. Codd's Relational Calculus
     6. Data Sublanguage ALPHA, Part 1 [February 16, 1999]
     7. Data Sublanguage ALPHA, Part 2 [March 9, 1999]
     8. The First Three Normal Forms, Part 1 [March 30, 1999]
     9. The First Three Normal Forms, Part 2 [April 20, 1999]
     10. Relational Really Is Different [May 11, 1999]
     11. Extending the Relational Model [June 1, 1999]
     12. Relational Forever! [June 22, 1999]
     Appendix A. A Definition of the Relational Model
     Appendix B. References and Bibliography
Dawson, Christian W.  The Essence of Computing Projects: A Student's Guide.  Pearson Education (Harlow, England: 2000).  ISBN 0-13-021972-X pbk.
          1. Introduction: What Are Computing Projects?
     Part I: Setting Your Project's Foundation
          2. Choosing a Project and Writing a Proposal
          3. Project Planning
     Part II: Conducting Your Project
          4. Literature Searching and Literature Reviews
          5. Doing Your Project
     Part III: Presenting Your Project
          6. Presenting Your Project in Written Form
          7. Presentation Skills
          8. Final Considerations

Bird, Richard., de Moor, Oege.  Algebra of Programming.  Prentice-Hall (Harlow, England: 1997).  ISBN 0-13-507245-X.  See [Bird1997]
Ershov, Andrei P.  Aesthetics and the Human Factor in Programming.  Comm. ACM 15, 7 (July 1972), 501-505.  Archived on-line at http://doi.acm.org/10.1145/361454.361458.
     This is a wonderful find in the references of [Knuth1974].  I had read the article when it first appeared, but it lands much more clearly for me on rereading it now.  Andrei Ershov was a renowned computer scientist in Novosobirsk.  That he could observe this about the situation of programmers worldwide over 30 years ago demonstrates to me how out-of-balance our progress has been.  I don't want to diminish the substantial ground we have covered, yet it is valuable to notice that we are dealing with essentially the same issues and that our tools don't save us. -- dh:2003-03-22
Ashenhurst, Robert L., Graham, Susan L. (eds.).  ACM Turing Award Lectures: The First Twenty Years 1966-1985.  ACM Anthology Series.  ACM Press (New York: 1987).  ISBN 0-201-07794-9.  See [Ashenhurst1987]
Graham, Ronald L., Knuth, Donald E., Patashnik, Oren.  Concrete Mathematics: A Foundation for Computer Science.  Addison-Wesley (Reading, MA: 1989).  ISBN 0-201-14236-8.
     A Note on Notation

     1. Recurrent Problems
     2. Sums
     3. Integer Functions
     4. Number Theory
     5. Binomial Coefficients
     6. Special Numbers
     7. Generating Functions
     8. Discrete Probability
     9. Asymptotics
     Appendix A.  Answers to Exercises
     Appendix B. Bibliography
     Appendix C. Credits for Exercises
     List of Tables
Gulutzan, Peter., Pelzer, Trudy.  SQL-99 Complete, Really: An Example-Based Reference Manual of the New Standard.  R&D Books Miller Freeman (Lawrence KS: 1999).   ISBN 0-87930-568-1 pbk + CD-ROM.  See [Gulutzan1999] under Information Processing.
Hamming, R.W.  One Man's View of Computer Science.  J. ACM 16, 1 (Jan. 1969), 3-12.  Archived on-line at http://doi.acm.org/10.1145/321495.321497.  Reprinted in [Ashenhurst1987: pp.207-218].
     "A number of observations and comments are directed toward suggesting that more than the usual engineering flavor be given to computer science. The engineering aspect is important because most present difficulties in this field do not involve the theoretical question of whether certain things can be done, but rather the practical question of how can they be accomplished well and simply.
     "The teaching of computer science could be made more effective by various alterations, for example, the inclusion of a laboratory course in programming, the requirement for a strong minor in something other than mathematics, and more practical coding and less abstract theory, as well as more seriousness and less game playing." -- from the Abstract
Kent, William.  A Simple Guide to Five Normal Forms in Relational Database Theory. Comm. ACM 26, 2 (Feb. 1983), 120-125. Also IBM Technical Report TR03.159, Aug. 1981. Also presented at SHARE 62, March 1984, Anaheim, California. Also in A.R. Hurson, L.L. Miller and S.H. Pakzad, Parallel Architectures for Database Systems, IEEE Computer Society Press, 1989.
Kent, William.  Data and Reality.  ed.2.  The International Online Library.  (Bloomington, IN: 1978; 1998, 2000).  ISBN 1-58500-970-9.
     Preface to the Second Edition
     1. Entities
     2. The Nature of an Information System
     3. Naming
     4. Relationships
     5. Attributes
     6. Types and Categories and Sets
     7. Models
     8. The Record Model
     9. The Other Three Popular Models
     10. The Modeling of Relationships
     11. Elementary Concepts: Another Model?
     12. Philosophy
     Detailed Contents
Knuth, Donald E.  Minimizing Drum Latency Time.  J. ACM 8, 2 (April 1961), 119-150.  Archived on-line at http://doi.acm.org/10.1145/321062.321063.
Knuth, Donald E.  Computer Programming as an Art.  1974 Turing Award Lecture.  Comm. ACM 17, 12 (Dec. 1974), 667-673.  Reprinted in pp. 33-46 of [Ashenhurst1987] and in Chapter 1 of [Knuth1992].  Archived on-line at http://doi.acm.org/10.1145/361604.361612.
Graham, Ronald L., Knuth, Donald E., Patashnik, Oren.  Concrete Mathematics: A Foundation for Computer Science.  Addison-Wesley (Reading, MA: 1989).  ISBN 0-201-14236-8.  See [Graham1989]
Knuth, Donald E. «Literate Programming».  CSLI Lecture Notes Number 27.  Center for the Study of Language and Information (Palo Alto: 1992).  ISBN 0-937073-80-6 pbk.

     1. Computer Programming as an Art [A.M. Turing Award Lecture, 1974]
     2. Structured Programming with goto Statements [1974]
     3. A Structured Program to Generate All Topological Sorting Arrangements [with Jayme L. Szwarcfiter, 1974]
     4. Literate Programming [1984]
     5. Programming Pearls, by Jon Bentley: Sampling [1986]
     6. Programming Pearls, Continued: Common Words [1986]
     7. How to Read a
WEB [1986]
     8. Excerpts from the Programs for ΤΕΧ and METAFONT [1986]
     9. Mathematical Writing [1987]
     10. The Errors of ΤΕΧ [1989]
     11. The Error Log of ΤΕΧ [1991]
     12. An Example of
CWEB [1990]
     Further Reading
Knuth, Donald E.  Artistic :Programming.  This Week's Citation Classic.  Current Contents, Physical, Chemical & Earth Sciences 33, 34 (23 August 1993), 8.  Reprinted in [Knuth1996: Chapter 15].
     This short article provides some interesting context on the writing of the Art of Computer Programming [ACP: now [Knuth1997], [Knuth1998], [Knuth1998b], and subsequent volumes and revisions to appear].   In the summer of 1962 I was on the Univac team for which Don developed a small Fortran compiler using the small-compiler techniques that he and others had mastered.  There is also a hint of the degree to which Knuth pursues beauty in his work and as something to preserve in the world, including his 11-year effort to restore mathematical typography, an ultimate tool-building act.  -- dh:2003-03-22
Knuth, Donald E. Selected Papers on Computer Science. CSLI Lecture Notes Number 59.  Center for the Study of Language and Information (Palo Alto: 1996). ISBN 1-881526-91-7 pbk.
     I opened this up because it contains Don's appreciation of the IBM 650. There is more here, including an example from Bishop's Constructive Analysis (almost on p.100) that put me over the top on the purchase decision.  There is much said here about algorithms, and that matters in The Miser Project, too.  dh:2000-07-18.
     For a related discussion, see my note, Do Programs Teach Algorithms? -- dh.

     0. Algorithms, Programs, and Computer Science [1966; 1992]
     1. Computer Science and its Relation to Mathematics [1973; 1974]
     2. Mathematics and Computer Science: Coping with Finiteness [1976]
     3. Algorithms [1977]
     4. Algorithms in Modern Mathematics and Computer Science [1981]
     5. Algorithmic Themes [1988]
     6. Theory and Practice, I [1977]
     7. Theory and Practice, II [1985]
     8. Theory and Practice, III [1986]
     9. Theory and Practice, IV [1989]
     10. Are Toy Problems Useful [1977]
     11. Ancient Babylonian Algorithms [1972; 1976]
     12. Von Neumann's First Computer Program [1970]
     13. The IBM 650: An Appreciation from the Field [1986]
     14. George Forsythe and the Development of Computer Science [1972]
     15. Artistic Programming [1993]
Knuth, Donald E.  The Art of Computer Programming, vol.1: Fundamental Algorithms. ed.3.  Addison Wesley Longman (Reading, MA: 1968, 1973, 1997).  ISBN 0-201-89683-4.
     Preface to the Third Edition
     Procedure for Reading This Set of Books
     Notes on the Exercises

     Chapter 1 - Basic Concepts
          1.1 Algorithms
          1.2 Mathematical Preliminaries
          1.4 Some Fundamental Programming Techniques
     Chapter 2 - Information Structures
          2.1 Introduction
          2.2 Linear Lists
          2.3 Trees
          2.4 Multilinked Structures
          2.5 Dynamic Storage Allocation
          2.6 History and Bibliography
     Answers to Exercises
     Appendix A - Tables of Numerical Quantities
     Appendix B - Index to Notations
     Index and Glossary
Knuth, Donald E.  The Art of Computer Programming, vol.2: Seminumerical Algorithms.  ed.3.  Addison Wesley Longman (Reading, MA: 1969, 1981, 1998).  ISBN 0-201-89684-2.
     Preface to the Third Edition
     Notes on the Exercises

     Chapter 3 - Random Numbers
          3.1 Introduction
          3.2 Generating Uniform Random Numbers
          3.3 Statistical Tests
          3.4 Other Types of Random Quantities
          3.5 What Is a Random Sequence?
          3.6 Summary
     Chapter 4 - Arithmetic
          4.1 Positional Number Systems
          4.2 Floating Point Arithmetic
          4.3 Multiple Precision Arithmetic
          4.4 Radix Conversion
          4.5 Rational Arithmetic
          4.6 Polynomial Arithmetic
          4.7 Manipulation of Power Series
     Answers to Exercises
     Appendix A - Tables of Numerical Quantities
     Appendix B - Index to Notations
     Index and Glossary
Knuth, Donald E.  The Art of Computer Programming, vol.3: Sorting and Searching.  ed.2.  Addison Wesley Longman (Reading, MA: 1973, 1998).  ISBN 0-201-89685-0.
     Preface to the Second Edition
     Notes on the Exercises
     Chapter 5
- Sorting
          5.1 Combinatorial Properties of Permutations
          5.2 Internal Sorting
          5.3 Optimum Sorting
          5.4 External Sorting
          5.5 Summary, History, and Bibliography
     Chapter 6 - Searching
          6.1 Sequential Searching
          6.2 Searching by Comparison of Keys
          6.3 Digital Searching
          6.4 Hashing
          6.5 Retrieval on Secondary Keys
     Answers to Exercises
     Appendix A
- Tables of Numerical Quantities
     Appendix B - Index to Notations
     Index and Glossary
Knuth, Donald E.  Selected Papers on Analysis of Algorithms.  CLSI Lecture Notes Number 102.  Center for the Study of Language and Information (Palo Alto: 2000).  ISBN 1-57586-212-3 pbk.
Kurose, James F., Ross, Keith W.  Computer Networking: A Top-Down Approach Featuring the Internet.  ed.2, International.  Addison-Wesley (Boston, MA: 2003).  ISBN 0-321-17644-8 pbk.
This is a textbook.  I will be using it for my M.Sc module on Computer Communication beginning 2004-02-05.  There is a companion web site that provides links, errata, and other materials.  It includes additional student resources available to purchasers of the book (via a scratch-off access code bound into the book).  The companion material includes self-assessment, some programming assignments, and material from the previous edition. 
     I am also interested in this book with regard to the treatment of abstractions involving computer communication and networking.  These are pertinent to nfoWare and I want to use consistent terminology and concepts where I am able to do so.  I will see how that works as I dig into the course.  -- dh:2004-01-11
     Although communication and networking texts don't start at the fundamental level that I see called for in Situating Data, this book is rewarding in how it points to meaningful toolcraft for having confirmable experiences with operations of computer communications.  I find high value in the gentleness of the progression and in the provision of concrete examples that can be used in experimental confirmation of networking and communication operations.  [dh:2004-02-13]
     1. Computer Networks and the Internet
     2. Application Layer
     3. Transport Layer
     4. Network Layer and Routing
     5. Link Layer and Local Area Networks
     6. Multimedia Networking
     7. Security in Computer Networks
     8. Network Management

Graham, Ronald L., Knuth, Donald E., Patashnik, Oren.  Concrete Mathematics: A Foundation for Computer Science.  Addison-Wesley (Reading, MA: 1989).  ISBN 0-201-14236-8.  See [Graham1989]
Gulutzan, Peter., Pelzer, Trudy.  SQL-99 Complete, Really: An Example-Based Reference Manual of the New Standard.  R&D Books Miller Freeman (Lawrence KS: 1999).   ISBN 0-87930-568-1 pbk + CD-ROM.  See [Gulutzan1999] in Information Processing.
Biermann, Alan W., Ramm, Dietolf.  Great Ideas in Computer Science with Java.  MIT Press (Cambridge, MA: 2002).  ISBN 0-262-02497-7 pbk. alk. paper.  See [Biermann2002]
Kurose, James F., Ross, Keith W.  Computer Networking: A Top-Down Approach Featuring the Internet.  ed.2, International.  Addison-Wesley (Boston, MA: 2003).  ISBN 0-321-17644-8 pbk.  See [Kurose2003]
Sedgewick, Robert.  Algorithms.  Second edition.  Addison-Wesley (Reading, MA: 1983, 1988).  1989 reprint with authors corrections.  ISBN 0-201-06673-4.
     "This book is intended to survey the most important computer algorithms in use today and to teach fundamental techniques to the growing number of people in need of knowing them.  ... The broad perspective taken in the book makes it an appropriate introduction to the field." -- from the Preface, p.v.
     "The orientation of the book is toward algorithms likely to be of practical use.  ... Full implementations of the methods discussed (in an actual programming language) are included in the text, along with descriptions of the operations of these programs on a consistent set of examples.
     "Properties of the algorithms and situations in which they might be useful are discussed in detail.  Though not emphasized, connections to the analysis of algorithms and theoretical computer science are not ignored.  When appropriate, empirical and analytical results are discussed to illustrate why certain algorithms are preferred.  When interesting, the relationship of the practical algorithms being discussed to purely theoretical results is described."  -- from the Preface, p.vii.
     "To learn an algorithm well, one must implement and run it.  Accordingly, the recommended strategy for understanding the programs present in this book is to implement and test them, experiment with variants, and try them out on real problems.  We will use the Pascal programming language to discuss and implement most of the algorithms; since, however, we use a relatively small subset of the language, our programs can easily be translated into many other modern programming languages." -- from the Introduction, p.3.
     There is more discussion of my concerns about the actual execution of this approach under "Do Programs Teach Algorithms?" -- dh.
          1. Introduction
          2. Pascal
          3. Elementary Data Structures
          4. Trees
          5. Recursion
          6. Analysis of Algorithms
          7. Implementation of Algorithms
     Sorting Algorithms
          8. Elementary Sorting Methods
          9. Quicksort
          10. Radix Sorting
          11. Priority Queues
          12. Mergesort
          13. External Sorting
     Searching Algorithms
          14. Elementary Searching Algorithms
          15. Balanced Trees
          16. Hashing
          17. Radix Searching
          18. External Searching
     String Processing
          19. String Searching
          20. Pattern Matching
          21. Parsing
          22. File Compression
          23. Cryptology
     Geometric Algorithms
          24. Elementary Geometric Methods
          25. Finding the Convex Hull
          26. Range Searching
          27. Geometric Intersection
          28. Closet-Point Problems
     Graph Algorithms
          29. Elementary Graph Algorithms
          30. Connectivity
          31. Weighted Graphs
          32. Directed Graphs
          33. Network Flow
          34. Matching
     Mathematical Algorithms
          35. Random Numbers
          36. Arithmetic
          37. Gaussian Elimination
          38. Curve Fitting
          39. Integration
     Advanced Topics
          40. Parallel Algorithms
          41. The Fast Fourier Transform
          42. Dynamic Programming
          43. Linear Programming
          44. Exhaustive Search
          45. NP-Complete Problems
Skiena, Steven S.  The Algorithm Design Manual.  Springer-Verlag TELOS (New York: 1998).  ISBN 0-387-94860-0 (book & CD-ROM).
     I. Techniques
          1. Introduction to Algorithms
          2. Data Structures and Sorting
          3. Breaking Problems Down
          4. Graph Algorithms
          5. Combinatorial Search and Heuristic Methods
          6. Intractable Problems and Approximations
          7. How to Design Algorithms
     II. Resources
          8. A Catalog of Algorithmic Problems
          9. Algorithmic Resources

Construction Zone (Hard Hat Area) You are navigating Orcmid's Lair

created 2000-07-18-18:06 -0700 (pdt) by orcmid
$$Author: Orcmid $
$$Date: 05-02-11 16:47 $
$$Revision: 60 $