Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Computer science : an interdisciplinary approach
Sedgewick R., Wayne K., Addison-Wesley Professional, Upper Saddle River, NJ, 2016. 1168 pp.  Type: Book (978-0-134076-42-3)
Date Reviewed: Dec 2 2016

I’ve decided to say here at the beginning that this book is outstanding and that it has my highest recommendation, both for self-study and as a text for undergraduate students who are serious about computing. The book’s content, organization, various levels of abstraction, and pedagogy are perfect for the authors’ aim “to teach programming to those who need or want to learn it, in a scientific context . . . [as an] essential part of the education of every student in the sciences and engineering.” And it is certainly not just programming that the book teaches, but also well-treated samples of the entire gamut of computing science, including abstract machines and the essence of real-life computer architecture.

My (relatively) early acquaintance, and complete enthrallment, with Dijkstra’s A discipline of programming [1] established a mindset of whose robustness I was unaware. There was, in addition, an even earlier acquaintance with Knuth’s (still) emerging magnum opus [2]. Though arguably less purist than Dijkstra, Knuth nevertheless shares Mount Olympus with Dijkstra. Add to that the positive experience that judicious use of formal methods has contributed to realizing safety-critical projects in which I continue to be involved, and the result is my approximation of Eric Hoffer’s True believer [3].

This book is a powerful antidote (perhaps vaccination, since it is largely aimed at a young audience) against self-inflicted dogmatism, even if born of appropriate but early-in-life admiration of the giants of our field. One more thing by way of meta-review: The title’s “interdisciplinary” is realized most rigorously in this book, as the referred-to disciplines are “applications in science and engineering” that use state-of-the-art computing science notions.

The book’s broad divisions are: chapters 1 to 4, programming; chapters 5 to 7, computer science.

Chapters 1 and 2 introduce Java as a, possibly first (!), programming language. The choice of this complex, object-oriented procedural language is deliberate, and the expressed trade-offs in the selection of Java are convincing and congruent with the goal of being interdisciplinary. The book visits both the deeper recesses and the upper reaches of Java’s semantics without leaving the reader in the dust. Downloading and using Java per the book’s website works like a charm.

Chapter 3, on object-oriented programming (OOP), is in my view a great course on OOP: this from one who has always been lukewarm regarding OOP (or perhaps OOP’s C++ realization). The sections on genomic string processing and on color processing are breathtaking in their sophistication. My old friends, the quaternions, are treated well, though these 4-tuples should not be called “vectors” because Gibbs and Heaviside independently invented vector analysis in treating the last three components of a quaternion as today’s ubiquitous 3-vector.

Chapter 4’s topic is algorithms and data structures, where one of the book’s several mantras is brought to life: “Pay attention to the cost [execution time].” Concise computation-cost models (linear, n log n, polynomial, and exponential) are clearly explicated. The coverage is broad and includes stacks, queues, and such applications as Poisson processes and search algorithms. Enumeration of Dijkstra’s 1960s two-stack, reverse-Polish-notation algorithm is the clearest I’ve encountered, and so is the authors’ equivalent single-stack version.

Chapter 5, “Theory of Computing,” expounds “careful [mathematical] reasoning about simplified and idealistic [sic] abstract machines that still retain the essential properties of real modern computers.” This chapter comes very close to being a substitute for specialized works on the theory of computing. Its coverage includes formal language; regular expressions (REs), including Java RE tools; deterministic and non-deterministic finite-state automata (DFAs and NFAs); Kleene’s theorem regarding equivalence among REs, DFAs, and NFAs; Turing machines and the universal Turing machine; the halting problem; and the notorious P = NP challenge.

Chapter 6 explicates the time-honored von Neumann architecture that we assembly language programmers learned about bottom-up. It is a masterly exposition and omits nothing essential; this machine is called TOY, but it’s not a toy. We are reminded that the “Apollo Guidance Computer that took men to the moon on six occasions had merely 1,024 16-bit words, the equivalent of just four TOY machines.”

Chapter 7, on Boolean algebra and combinational and sequential circuits, shows how remarkable it is “that we can move from switch to processor . . . with just two levels of abstraction.” Having perused some books on this chapter’s subject, I marveled at how easy it was made in this book. There is a typographical error regarding the OR gate; the sentence should read, “The output is 0 if and only if both inputs are 0.”

Other inessential errata in the book at large are the spelling of Dijkstra’s and Church’s first names, which should be Edsger and Alonzo; the year of the Ariane 5 disaster, which should be 1996; “When happens when” should be “What happens when”; and LSC should be LCS.

To restate my initial message: Don’t miss this book; it is excellent and eminently practical.

More reviews about this item: Amazon

Reviewer:  George Hacken Review #: CR144955 (1702-0082)
1) Dijkstra, E. W. A discipline of programming. Prentice-Hall, Englewood Cliffs, NJ, 1976.
2) Knuth, D. E. The art of computer programming. Addison Wesley, Reading, MA, 1968.
3) Hoffer, E. The true believer. Harper, New York, NY, 1951.
Bookmark and Share
  Editor Recommended
Featured Reviewer
Object-Oriented Programming (D.1.5 )
Java (D.3.2 ... )
Reference (A.2 )
Would you recommend this review?
Other reviews under "Object-Oriented Programming": Date
Object-orientation, abstraction, and data structures using Scala (2nd ed.)
Lewis M., Lacher L.,  Chapman & Hall/CRC, Boca Raton, FL, 2017. 660 pp. Type: Book (978-1-498732-16-1)
Nov 27 2017
Reactive programming with Angular and ngrx: learn to harness the power of reactive programming with RxJS and ngrx extensions
Farhi O.,  Apress, New York, NY, 2017. 148 pp. Type: Book (978-1-484226-19-3)
Nov 9 2017
How to use objects: code and concepts
Gast H.,  Addison-Wesley Professional, New York, NY, 2016. 832 pp. Type: Book (978-0-321995-54-4)
Feb 21 2017

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2017 ThinkLoud, Inc.
Terms of Use
| Privacy Policy