Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
Algorithms and Data Structures: The Science of Computing embodies several distinctive ideas about what computer science is and how it is best learned. Understanding the authors’ philosophies regarding these issues will help both students and instructors best use the book. The book’s preface presents the most important philosophical bases; this document delves further into issues not covered in the preface.
The most distinctive thing about Algorithms and Data Structures: The Science of Computing is its emphasis on computer science’s methods of inquiry. Briefly, the methods of inquiry are…
The book’s foremost goal is to introduce readers to these methods, to give readers rudimentary ability to use all three, and to demonstrate the methods as mutually supporting necessities for “doing computer science.” For more on the importance of these methods to the computer science student, see the preface to the book. The methods themselves are described in detail in part I.
To many students, algorithms are simply the abstract outlines of programs, preliminaries to writing “real” code. Algorithms are much more than that in Algorithms and Data Structures: The Science of Computing — they are the main subjects of study in their own right, far more important than programs. This is because the thought processes surrounding algorithms are the important end result of studying computer science. A student who understands the insights and invariants on which an algorithm is based, the process by which it was developed, and the reasons why it works and why it works efficiently (or not) can reproduce the algorithm in any programing language he or she wishes, and can even invent new or better algorithms based on similar insights, processes, and analyses. On the other hand, a student who understands only the code for the algorithm in a particular language can do little more than regurgitate that code in its original form.
This book therefore devotes considerable time to each algorithm it presents, discussing a process by which the algorithm could be discovered, developing its design through multiple iterations, analyzing its performance and correctness, and, almost as an after-thought, presenting it in Java. Both instructors and students must appreciate that the design processes and analyses are the heart of the book, and therefore are the things that should receive the most study.
Two features characterize the book’s presentation of algorithms: object oriented abstraction and recursion. Abstraction in some form is essential to making computing intellectually manageable, and object oriented design and programming seem to be particularly powerful abstraction mechanisms. The book thus takes an object oriented view of all algorithms and data structures. For an in-depth introduction to object oriented programming and abstraction, see Chapter 2. Recursion is perhaps the ultimate control structure for algorithms (it can express everything iteration can, and more). Recursion also provides a key connection between algorithms and mathematics, and is a definitional mechanism applicable far beyond algorithms. Recursion thus reappears many times in this book — chapters 6 and 7 introduce it and its related math, it figures prominently in the definition of a number of data structures in part III, and it is an essential ingredient in the exponential behaviors studied in chapter 15.
Many of the ideas (particularly mathematical and experimental techniques) presented in Algorithms and Data Structures: The Science of Computing are not ones introductory students are naturally motivated to study. This is not because the ideas are unimportant, but simply because they are not prominent in the public perception of computing. In order to encourage readers to study things that they may not initially consider part of computer science, material in the book is ordered, as far as possible, so that no important idea appears until after some motivation for studying it has been presented. The motivations are often problems raised in chapter introductions or earlier chapters.
Algorithms and Data Structures: The Science of Computing is a second course in computer science (CS 2). The authors wrote the book in order to expose students to computer science’s methods of inquiry as early as possible in the computer science program. This early introduction prevents students from forming the impression that computer science is fundamentally about programming, and that other methods are peripheral. Recognizing that students must be able to program in order to do the exercises and laboratories associated with this book, however, “as early as possible” realistically means the second course.
Traditionally, CS 2 introduces many classic data structures and some rudimentary analysis of algorithms, and it may introduce recursion, pointers, object oriented programming, elements of software engineering, etc. Algorithms and Data Structures: The Science of Computing does indeed cover many of these topics, but it is not a traditional CS 2 textbook. Its focus on methods of inquiry, particularly mathematical and experimental ones, means that it goes far deeper into analysis of algorithms and discrete math than is usual in CS 2, and correspondingly less deeply into data structures and software.
To use Algorithms and Data Structures: The Science of Computing in a traditional two-course introductory sequence, one should be willing to put more math and analysis of algorithms into CS 2 than is usual, and to cover data structures and programming in less depth. Any deficit in programming ability thus produced should be made up in later courses. Many curricula have an intermediate-level analysis of algorithms course that would be a good candidate for making up these deficits, as some of the material normally covered in that course is already covered in Algorithms and Data Structures: The Science of Computing.
Another way to use Algorithms and Data Structures: The Science of Computing, which is more consistent with modern curricular recommendations (e.g., Computing Curricula 2001), and which is also the context in which the book was developed, is to view it as one course in a three-course introductory sequence. The first course in such a sequence would be a fairly traditional introduction to object oriented programming, the second would be Algorithms and Data Structures: The Science of Computing, and the third would be an in-depth study of data structures, program design, etc.
Regardless of how Algorithms and Data Structures: The Science of Computing fits into a program, subsequent courses must use all three methods of inquiry. This drives home to students that facility with all three methods is important beyond this one course, and allows students to develop that facility further. Just as most computer science programs expect students to practice programming in ever more sophisticated forms for four years, students should also practice ever-more sophisticated forms of mathematical thinking and experimentation throughout their studies of computer science.
The papers below discuss some of the ideas on which Algorithms and Data Structures: The Science of Computing is based, or define the general curricular context within which the book exists:
D. Baldwin, G. Scragg, and J. A. G. M. Koomen, “A Three-Fold Introduction toComputer Science.” Twenty-Fifth SIGCSE Technical Symposium on Computer Science Education, Mar. 1994. pp. 290 - 294.
D. Baldwin and J. A. G. M. Koomen, “Using Scientific Experiments in Early Computer Science Laboratories.” Twenty-Third SIGCSE Technical Symposium on Computer Science Education, Mar. 1992. pp. 102 - 106.
P. Denning et al., “Computing as a Discipline.” Communications of the ACM, Jan. 1989 (32:1). pp 9 - 23.
IEEE-CS and ACM, Computing Curricula 2001: Computer Science Volume. Available at http://www.sigcse.org/cc2001/
H. Walker and G. M. Schneider, “A Revised Model Curriculum for a Liberal Arts Degree in Computer Science.” Communications of the ACM, Dec. 1996 (39:12). pp. 85 - 95.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 9, 2005 by Doug Baldwin