Copyright 1994 by the Association for Computing
Machinery, Inc. Permission to make digital or hard copies of part or
all of this work for personal or classroom use is granted without fee
provided that copies are not made or distributed for profit or
commercial advantage and that copies bear this notice and the full
citation on the first page. Copyrights for components of this work
owned by others than ACM must be honored. Abstracting with credit is
permitted. To copy otherwise, to republish, to post on servers, or to
redistribute to lists, requires prior specific permission and/or a
fee. Request permissionsfrom Publications Dept, ACM Inc., fax +1
(212) 869-0481, orpermissions@acm.org.
The computing profession continues to debate what computer science is. The perspective ranges from the mathematical abstractionists to the "down-to-earth" programmers. As computer science educators we are faced with the dilemma that one cannot do computer science well without being a good programmer, nor can one understand the underpinnings of computer science without a strong background in mathematics.
We propose a three tiered model for curricular design in computer science education. We emphasis teaching the languages of both programming and mathematics within this framework so that students become proficient solvers of computational problems. At the highest level students must be exposed to the
Whether by accident or intent, if a curriculum is designed so that the above levels have a disjoint nature, the results are less than optimal. For example, if a course in Discrete Mathematics is not taught in conjunction with a computer science experience, or it is taught long before the concepts and theory are applied in a computer science course, then the effectiveness of this course is lost. This is a problem at the theory level: students do not see an integration of theory with practice. If exposure to a functional programming language is not provided before an elective in AI is taken, then the advanced course may degenerate into a functional programming course using Lisp rather than a course on AI concepts. This is a problem with implementation issues: the AI course becomes concerned with implementation of AI concepts rather than the concepts themselves. If students become dependent upon a single language and computing platform in their first few years (for example MS-DOS based Pascal), precious time is wasted in an advanced course on Operating Systems or Software Engineering that requires a different platform and language (for example UNIX based C). This is a problem at the mechanical trivia level: students do not develop the adaptability to master new environments. Our model carefully integrates the three identified levels into the early part of the first experience of the computer science major, and alleviates these kinds of curricular problems.
This paper describes an ongoing project to radically change the initial experience of undergraduates in computer science. Specifically we show how to thoroughly integrate students' exposure to mathematics with their first formal courses in computer science. We describe a learning experience in which theory and practice are mutually reinforcing components, rather than competitors. Our goal is for students to learn to use the languages of mathematics and programming to become proficient users of the concepts of computer science. Students should begin their study through three experiences. The first isolates abstract expression of algorithms from the details of implementation through the use of a functional programming language. The second addresses the implementation of the abstract concepts in an imperative framework. Finally, we create a fully integrated learning environment in which real learning is fostered. These goals are achieved through three new courses taken during the first year of study at the undergraduate level in the Computer Science major. In the first semester students take "Computational Problem Solving" (CS1) and Discrete Structures of Computer Science" (DS). In the second semester they take "Implementation and Analysis of Abstract Data Types" (CS2.)
The next section provides a brief summary of problems surrounding current introductory sequences. Sections 3 - 5 describe CS1, DS and CS2 respectively. Section 6 presents results of our work to date and provides a summary.
Our three tiered approach helps articulate the problems with the current introductory curriculum as identified by studies of programmer preparedness[7]. All too often introductory programming courses focus primarily on the minutia, and mix, or worse, confuse theory and implementation.
The current core curriculum at many institutions across the country is typical of those emphasized in both the old ACM '78 and new ACM '91 guidelines[1,2]. Students begin with a rigorous course in problem solving and programming in Pascal that covers traditional topics included in standard texts. However, this course often degenerates into one with an emphasis on Pascal syntax as can be evidenced from textbook chapter summaries and suggested exam questions in instructor support manuals. The course is usually followed by a second Pascal-based course in introductory data structures and algorithms. However, this course tends to emphasize the implementation of abstract data types in Pascal, via arrays and pointers, diminishing the critical importance of developing sound problem solving skills. These two courses are generally taken in parallel with a calculus sequence even though the calculus has little relevance to the computer science topics. Worse, although the calculus is intended to teach rigorous mathematics, it too is often a cookbook course of disjoint techniques.. An introduction to Discrete Mathematics may also be provided but is not well integrated with the computer science curriculum, for example it is taken long after an ntroductory Data Structures and Algorithms course, where it is needed.
In our new curriculum, the first semester courses, CS1 and DS, establish a tight coupling between mathematical foundations and their role in problem solving and analysis in computer science. Curricula are articulated to enhance learning at the theory level. A lab experience is used to address the levels of mechanical trivia and algorithm implementation. Both of the courses involve programming experiences in functional languages like Scheme and Mathematica, which insulates students from the minutia associated with procedural languages like Pascal or C. In the second semester CS2 focuses on taking the concepts and theory covered in the first semester and examining complexity and efficiency issues associated with implementation in the procedural languages C and C++. Because of our approach, the minutia surrounding these languages does not interfere with the students' learning, since underlying concepts have previously been mastered.
In recent years there has been increasing dissatisfaction with the predominant "Pascal language features-driven" model as an introduction to foundations of computer science. The dilemma is that introductory computer science must focus simultaneously on the theoretical and the practical. Students should develop a firm grounding in the basic concepts of computer science, but must learn to exploit those concepts when writing programs on real machines.
Nationally, there is an accelerating shift away from Pascal. Hilburn[6] substituted Ada for Pascal because of Pascal's unsuitability for problem solving via modular programming. At Stanford, Roberts[11] found Pascal inadequate for teaching modern programming concepts, overly restrictive in design, and of limited usefulness in more advanced work, and opted instead for C. Decker and Hirshfeld [4] teach the object-oriented approach via Object Pascal. A number of institutions have adopted such languages as Scheme and Smalltalk[3, 10, 12] for CS1.
The CS1 introductory course is ideally a course in algorithmic problem solving. However, most textbooks are strongly influenced in organization and emphasis by a particular language and the presentation of the features of that language. Programming language constructs are useful only to the extent that they contribute to the effective description of algorithms. A successful experience in CS1 should give students the ability to design and implement algorithmic solutions for a wide variety of problems.
The classic introductory approach assumes that students must first learn the "primitive" constructs of a programming language before proceeding to the more abstract. For example, pointers are taught before lists. It is an historical artifact that data types such as queues, stacks, lists, trees and graphs are not considered primitive data types within a language. There is no reason that students in a first course can't learn to use these constructs before learning how they are implemented. Our new CS1 - CS2 sequence first teaches the use of data structures regardless of whether they are traditionally thought of as primitive or abstract and then later shows how they are implemented within an imperative paradigm.
Our innovative approach is to introduce abstractions of all kinds, including object oriented programming (OPP), in CS1 using a language such as Scheme (with SCOOPS) that is suited to "hiding" implementation. The emphasis in the first course is not on algorithmic design and implementation from a functional perspective. Instead we exploit the high level nature of a functional language in order to avoid dealing with the low level syntactic minutia required to understand the constructs such as lists. Students should not have to deal with the details of pointers when learning about lists, stacks, trees, etc. They ought to be able to experiment with these structures at a level that allows them to express their ideas naturally.
We emphasize the important concepts of problem specification and solution through three means. First, the CS1 course provides an abstract conceptual framework through formal lecture and off-computer problem solving activities. Second, the course is articulated with DS so that the strong ties between the mathematical formalisms and the computational expression of those formalisms is made clear to students. Finally, extensive experience in developing solutions to small programs is provided in both open and closed laboratory activities. Our current choice of language is Scheme. It allows us to dispense with much of the syntactic minutia associated with Pascal (or C) because it does not require data typing, it has a simple syntactic form and because functions can be expressed more naturally as individual entities within its interpreted environment.
The emphasis in CS1 is on the practical illustration of top-down design via bottom-up implementation. The functional paradigm is used to stress the fundamental components of a computational process: input (via parameters), output (the returned value), and process (the body of the code.) Small programs (functions) can be designed, coded, tested and debugged as autonomous units. Once verified they can be combined into larger procedures, which themselves eventually form a fully working program. This is bottom-up implementation.
A stumbling block in many introductory computer science courses is to convince students that bottom-up implementation alone is not sufficient. Top-down design must precede it. The contribution of the Discrete Structures course is critical here. By viewing a solution to a computational process as a static function, rather than an imperative process, students learn to think of the composing function and its parts, regardless of how the details of the parts are constructed. We believe this will lead students to view top-down design as a natural evolution, rather than a form required by the instructor.
Closed laboratory sessions are used to guide important working strategies: program organization, incremental testing, and use of the debugger and other features of the programming environment. Student projects are submitted electronically on a rolling basis, with resubmission allowed within reasonable deadlines. Collaborative work is encouraged and at times demanded. For example, at least one exam will be given as a programming contest in which teams of students compete under time constraints to produce implemented and tested solutions to problems.
The course begins with an introduction to functions and their use as simple operations on numbers and symbols. Both primitive and user defined functions are used to construct solutions to large problems. Correctness is stressed through the relationship between the denotational semantics of Scheme and the model of the problem.
The concept of program control is introduced via recursion and conditional branching. Again, the emphasis is on a strong association with a mathematical (and thus declarative) specification of a solution to a problem.
Data organization and typing are introduced via nested list. The distinctions between sequences and collections is shown. Primitive and user defined operations on these structures is stressed. Data abstractions (including stacks, queues and trees) are shown to be an extension of nested lists. Operators on defined data structures is stressed. Data types (integers, reals, Booleans, strings) and procedures are presented as specializations of first class objects. Object-oriented techniques are addressed, both through functions as first class objects (within Scheme itself) and through SCOOPS (an inheritance extension)
Traditional imperative techniques are intorduced. Iteration is presented with an explanation of its correct use. Iteration is shown to be a special case of recursion; the recursion's precondition is precisely the loop invariant. Non-sequential structures, arrays and records (vectors and structures) are shown within the context of efficiency. I/O is initially introduced via a discussion of the read/eval/print loop as a means of creating customized environments. More traditional perspectives on interfaces is then discussed and simple file processing is introduced.
Standard discrete mathematics courses do not meet appropriate goals for computer science. "Discrete Structures of Computer Science" presents mathematics relevant to problem solving by computer so that students can apply the theory level in diverse contexts in later courses.
While it is generally accepted that a course in discrete mathematics ought to be a requirement in the computer science curriculum, there is considerable variation in the definition of such a course. Recent years have seen proposals for several alternatives to the mainstream discrete mathematics course. Henderson[5] argues for a primary emphasis on problem solving, supported by appropriate laboratory experience. The text of Maurer and Ralston[8] minimizes mathematical formalism and is centered on algorithms and problem solving via induction and recursion. Neff[9] has supplemented relational topics with laboratory experience using Prologb .
The content of DS is innovative because it places particular emphasis on the mathematics that relate closely to modern programming concepts, while the standard Discrete Mathematics course covers a more diffuse collection of topics tailored to aspiring mathematics majors. For example, we believe that lists, trees, and word algebras should be given just as much early emphasis as sets.
The methodology of DS is innovative for several reasons. First, theoretical concepts are initially presented by way of concrete examples, with subsequent student laboratory work. The laboratory work involves exploration of concrete examples of structures, using various declarative programming systems and custom course software. Second, DS is articulated with the concurrent course CS1. Third, careful reasoning and accurate expression are emphasized, but mathematical formalism is minimized. In addition to traditional notations, we use notation from Scheme.
The problem of non transferability of discrete mathematics is attacked by the inclusion of laboratory exercises in declarative programming and by the contiguity with CS1. Freshmen are capable of understanding complex concepts and relationships, but often lack the motivation or experience necessary for following formal textbook mathematics. The new DS course uses a strategy of involvement by example, via declarative programming. We believe that this strategy will reach the students more efficiently, and will also tacitly present mathematics as a useful tool with many applications, rather than as a necessary requirement disjoint from computer science.
A small set of mathematical topics, closely related to the core of computer science, is presented in depth. Topics include: functions on lists, trees, and word algebras, the relational database model, polymorphic type inference, decompositions of digraphs, and formal languages. Each topic is presented as an application of general foundational principles, such as recursively defined sets and functions, structural and numerical induction, properties of relations, and informal predicate logic.
Concrete examples are explored. This includes both paper and pencil and laboratory work in Scheme. Functional programs within this course will be viewed as equational specifications of the desired solution function. Software packages such as ISETL will be used to introduce abstract mathematics such as sets and predicate logic. Logic programming will be introduced via Prolob[9], a pure logic subset of the Prolog syntax that uses a breadth-first search strategy to guarantee solution for all valid queries, regardless of the ordering of clauses or goals.
While CS2 is traditionally thought of as course in Data Structures and Algorithms, the current standard suffers from three shortcomings. First, because it is typically taught in Pascal it degenerates into an advanced programming course on Pascal with an emphasis on recursion, pointers and parameterized procedures. Second, it tends to be a cookbook course in which the "classic" abstract data structures and algorithms (stacks, queues, linked lists, trees and graphs, search and sort algorithms) are presented. Third, good software engineering practice is emphasized, but given the demands of the language and the data structures and algorithms, this aspect often gets little attention.
Taken together these problems create a course that is often a smattering of superficial ideas that do not form a cohesive whole. As the extension of CS1, the CS2 course is generally the place where the price is paid for the flaws in CS1. As computer science has evolved, the curriculum has collapsed downward, so that the typical CS2 course now contains not only intermediate programming, but also topics in data structures, algorithm analysis, and abstract data types. If the CS1 experience was in the classic "Pascal language features" driven form, the students do not have the tools to cope with all of this material in one semester. Because the typical CS1 course excessively emphasized low-level details, the students lack experience in procedural organization of medium-sized programs. Because the discrete mathematics was not integrated with the CS1 experience, they must suddenly absorb new mathematical notions, such as recursion and abstract data types.
Another major problem is that the presentation of data structures and algorithms occurs in a cookbook fashion even in the best CS2 books. When the "classic" algorithms and data structures are presented as fully flushed out Pascal code, there is little incentive to do much else but study the completed solutions. A more important goal (lost in the cookbook) is to understand the circumstances under which a data structure is appropriate, and why.
A third problem is that formal methods for analyzing efficiency of algorithms is introduced, but in an informal and superficial way. Students do not develop intuitions about time complexity. Instead, time complexity becomes a topic that is a bit of esoterica thrown in to make the course more "formal." While students may memorize the method for analyzing simple iterative algorithms with polynomial time complexity, few books present logarithmic or exponential analysis well. The treatment is usually extremely superficial, providing neither mathematical rigor (which is not appropriate) nor good intuitive models (which is.) Yet the emphasis in studying efficiency should be on the distinction between logarithmic, polynomial and exponential algorithms.
The major goal of our CS2 is the implementation and efficiency of the structures and algorithms that were learned in CS1. The course addresses the question of how the "big ideas" presented in the first course are implemented within an imperative framework. While a high level, functional language is appropriate for studying abstractions, it is less appropriate for considering the implementation issues. In order to optimally implement algorithms, we need a model of computation that is closer to that of the actual hardware; hence an imperative framework is critical.
Within this context, the notion of efficiency, both of time and space, has special relevance. While the first course emphasized how to construct an algorithm, the second course continues with the theme of implementation, but addresses the cost of a particular implementation. Within this framework the approach emphasizes trade-offs both in efficiency and style. The focus need not be fanatically rigorous. We do not expect students to be able to solve recurrence relations to prove nlog2n time complexity. However, within CS2 we will expect students to be able to articulate the trade-offs between algorithm implementations.
The final consideration is how to give students practical experience in efficient implementation. An imperative language that has strong ties to the underlying machine is more appropriate. Commercial programming is firmly entrenched in imperative languages and is rapidly adopting C as its standard. We therefore have chosen to use C rather than Pascal as a second language.
In order to reinforce these concepts, students will be exposed to small to medium sized programming problems through extensive use of closed lab sessions. Finally, the course introduces C++ in order to demonstrate the implementational of OOP.
It should be stressed that the goal of CS2 is not merely to teach an imperative language. Implementation and analysis of the trade-offs between implementations is the focus. The major innovation is that this course is not merely an extension of CS1, but that it explicitly changes the focus from mastery of abstract concepts to consideration of implementation. This approach is exactly the opposite of the traditional curriculum in which language primitives are taught first (in CS1) and abstractions are considered later.
The course begins with an introduction to the constructs of an imperative language compared to those of a functional language (sequential nature of code, relationship between procedures, parameter passing, structure of a complete program.) The implementation of abstract data types in a strongly typed imperative language is hown, using both static and dynamic techniques Analysis of trade-offs between implementations is emphasized.
The course then considers the distinctions between iterative and recursive solutions and informally introduces algorithm efficiency. Comparison of implementations of problems such as Fibonacci is shown, for example, solutions that are either purely recursive or exploite local storage. Trade-offs between clarity and efficiency are stressed.
The combination of algorithm and data structure selection will be addressed; for example the trade-offs between exploiting binary search on an array or binary tree. The course will include reinforcing exposure to the object-oriented paradigm, again with an emphasis on implementation and efficiency. The emphasis will be on how OOP affects coding time and transferability to other problems. The mechanics of OOP will be shown by comparing the transparency of SCOOPS in Scheme with less abstract object definitions required in C++.
Clean program organization, which is an issue of style and efficiency will be considered. Students will build medium-sized programs (approximately 30 procedures of approximately 20 lines each) with the intent to produce tight elegant code that is space and time efficiency.
Machine transportability will be studied by coding solutions to run on more than one machine architecture. Language trade-offs will be considered through problem solutions implementation in both C and Scheme.
Between the Summer of '92 and Spring '93 each of the new courses were offered at least once. Average enrollment was approximately 25 students per class. Although most students were computer science majors, the courses also drew students from other majors. During the academic year 92-93, all entering Computer Science majors were placed in a special section of CS1 (Fall) and CS2 (Spring) to track course continuity. Full integration of the CS1 and CS2 sequence with DS is taking place in academic year 93-94.
To date, we have seen a marked improvement in performance among students in the new DS, CS1/CS2 sequence. They have demonstrated the ability to articulate a problem solution both in English and in Scheme. Quick mastery of a second programming language occurred in CS2, but more importantly, students employed a programming style based on the procedural emphasis from their experience with Scheme. We believe this was the result of a firmer grasp of the fundamental abstractions, and because we could separate the abstractions from the implementation and the minutia. Our results to date have been informal and anecdotal. Course notes and laboratory exercises have been prepared, and will be formally tested and evaluated during the 93-94 academic year.
We expect that the new courses will contribute to a redefinition of the objectives of the initial core courses in computer science and related mathematics. In mathematics, we moved from a "grab bag" of isolated topics to a package of concepts particularly useful to computer science. In computing, we moved from courses with syntax-centered emphasis to ones focused on the application of theory and high level computing concepts to problem solving.
Because of the superior theoretical background provided by DS and CS1, the CS2 course is able to more successfully meet its objectives . The potential impact of the new DS, CS1, CS2 sequence is to demonstrate a teaching methodology that provides students with strong conceptual foundations, while simultaneously providing practical experience in developing efficient implementations of those concepts. Our course sequence demonstrates that by emphasizing this three part model, students gain a better appreciation for and grasp of the core of Computer Science.
This project is supported by National Science Foundation Grant DUE-9254108. Norman Neff is a senior investigator on this project and is primarily responsible for the content of the DS course. Peter Henderson, Jim Dunne and Eugene Spafford have provided valuable advice on course content and evaluation
[1] ACM Curriculum Committee on Computer Science. Computing Curricula 1991, Report of the ACM/IEEE-CS Joint Curriculum Task Force , ACM Press, 1991.
[2] ACM Curriculum Committee on Computer Science. Curriculum 78: Recommendations for the undergraduate program in computers. Communications of the ACM, 22(3):147-166, March 1979.
[3] Conjura, E., U. Wolz and N. Neff, "An Integrated Approach to Teaching the Languages of Programming and Mathematics in the Computer Science Curriculum. NSF UCC Proposal", June, 1992. Contract Number: DUE-9254108, Federal Category 47.076NSF.
[4] Decker, R. and S. Hirshfeld, "Top-Down Teaching: Object-Oriented Programming in CS 1" SIGCSE Bulletin 25, (1), March 1993.
[5] Henderson, P. B., "Discrete Mathematics as a Precursor to Programming", SIGCSE Bulletin 21(1), 1990.
[6] Hilburn, T., "A Top-Down Approach to Teaching an Introductory Computer Science Course", SIGCSE Bulletin , 25, (1), March 1993.
[7] Koffman, E. B., D. Stemple, and C.E. Wardle, "Recommended Curriculum for CS2, 1984: A Report of the ACM Curriculum Committee Task Force for CS2", Communications of the ACM , 28, (8). August, 1985.
[8] Maurer , S. B. and A. Ralston. Discrete Algorithmic Mathematics , Addison-Wesley, Reading MA, 1991.
[9] Neff, N., "A Logic Programming Environment for Teaching Mathematical Concepts of Computer Science", SIGCSE Bulletin 25, (1), March 1993.
[10] Reid, R., "The Object-Oriented Paradigm in CS 1," SIGCSE Bulletin , 25 (1), March 1993, pp 265-269.
[11] Roberts, E., "Using C in CS 1 - Evaluating the Stanford Experience", SIGCSE Bulletin 25 (1), March 1993.
[12] Skubles, S.and P. White, "Teaching Smalltalk as a First Programming Language", SIGCSE Bulletin , 23 (1), February 1991, pp 231-234.