The following is the November 29, 1994 draft of an article that appeared in the December 1996 issue of the Communications of the ACM. The final version was abbreviated somewhat because of space limitations. This paper, together with its predecessor, "A Model Curriculum for a Liberal Arts Degree in Computer Science" by Norman Gibbs and Alan Tucker, come out of extensive discussions of the Liberal Arts Computer Science Consortium. The sidebar at the end of this article provides additional information concerning this Consortium and the development of the following paper. -------------------------------------------------------------------------- A Revised Model Curriculum for a Liberal Arts Degree in Computer Science by Henry Walker, Grinnell College G. Michael Schneider, Macalester College Abstract This report updates 1986 recommendations for a high-quality undergraduate degree program in computer science. This curriculum provides a coherent model for colleges and universities of all sizes, where the goal is a strong computer science program within a liberal arts setting. 1. INTRODUCTION This report presents recommendations for a high quality undergraduate computer science major within a liberal arts setting. These recommendations build upon the traditional strengths of a liberal arts education, while ensuring reasonable depth in fundamental areas of computer science. The report updates the 1986 ``Model Curriculum for a Liberal Arts Degree in Computer Science'' by Norman Gibbs and Allen Tucker [8]. (See the sidebar for a discussion of this revision process.) In doing so, it draws upon important new educational and technological developments in the discipline as well as the recommendations of Curricula 1991 of the ACM/IEEE-CS Joint Curriculum Task Force [1]. The revisions lead to a four layer hierarchical curriculum which provides in-depth coverage of fundamental areas of computer science and which can be staffed by the limited number of faculty typically available at smaller liberal arts institutions. 2. THE LIBERAL ARTS ENVIRONMENT A liberal arts education strives to maintain balance between a breadth of study in a variety of fields and a depth of understanding within a major field. Exposure to a number of disciplines encourages students to understand and practice problem-solving skills from different perspectives. For example, computer science majors may gain an appreciation of social and ethical issues through courses in philosophy or sociology. A psychology course may provide insight into issues of artificial intelligence or the human-computer interface. At the same time, a liberal arts education involves the investigation of a major at a reasonable level of depth. The recommendations given later in this report demonstrate that a carefully chosen sequence of courses can provide a rigorous program of study in computer science. While a major in a liberal arts environment may not involve a large number of computer science courses, the core areas of the discipline can be carefully and fully covered. This emphasis on the core of the discipline, rather than applications, means that a liberal arts programs will emphasize principles, with details and applications following from and building upon these basic ideas in a hierarchical fashion. While liberal arts programs exist at all sized schools, from tiny to very large, a great many liberal arts programs are located at small undergraduate colleges. In this environment, the number of FTE faculty available to teach computer science is very limited, frequently only 3, 4, or 5 FTE. Therefore, an important challenge to this revised curriculum is to create a high quality computer science program in the presence of potentially very limited resources. 3. EXISTING CURRICULAR RECOMMENDATIONS In preparing this report, we have drawn upon two sets of curricular recommendations: Curricula 1991 from ACM/IEEE-CS and the original 1986 `Model Curriculum' authored by Norm Gibbs and Allen Tucker. Curricula 1991 [1], published by a joint ACM/IEEE task force in March, 1991, was a complete rethinking of the undergraduate computer science curriculum when compared to earlier recommendations described in Curriculum 78 [2], and it identified many important contemporary issues. Ironically the strengths of Curricula 1991 also create some of its difficulties. Curricula 1991 is based upon the 1989 report, Computing as a Discipline, by Peter Denning et al [7]. That report identifies nine basic subareas within the field of computer science. Curricula 1991 added two additional areas in introductory programming and social, ethical, and professional issues. It then expanded the view of these eleven topics and labeled them `subject areas', which encompass research, teaching, and laboratory activities. In order to encourage curricular experimentation, the material contained in these subject areas was organized into curriculum modules called knowledge units rather than the more traditional sequences of courses. The volume of information contained in a knowledge unit varied from enough for a few days to several weeks. Appendices to Curricula 1991 presented different sets of courses which show how these knowledge units can be combined in various ways. Altogether, Curricula 1991 identifies 56 separate knowledge units involving 283 hours of lectures as well as an unspecified number of laboratory sessions. This material represents the core of computer science that, in the opinion of the committee, must be part of all undergraduate majors in computer science. The 11 subject areas and the approximate amount of time spent on each one are shown in Table 1. Subject Area Total Lecture Hours Algorithms and Data Structures 47 Architecture 59 AI and Robotics 9 Database and Info Retrieval 9 Human-Computer Communication 8 Introduction to a Programming Language 12 Numerical and Symbolic Computation 7 Operating Systems 31 Programming Languages 46 Software Methodology and Engineering 44 Social and Ethical Issues 11 TOTAL 283 Table 1. Curriculum 1991 Subject Areas and the Total Time Spent per Subject Area While Curricula 1991 does an excellent job listing topics and defining the core of computer science, the knowledge unit approach requires faculty to analyze their current course offerings with regard to these 11 areas and 56 modules. In principle, the sample programs from the Appendix of Curricula 1991 may help this process, and the knowledge unit approach permits great experimentation and flexibility. In practice, however, the review and redesign of an entire curriculum is a tremendous job, and it seems that few colleges and universities have been willing to undertake this task. More importantly, the listing of individual knowledge units obscures a vital element of any curriculum. A curriculum involves a sequencing of courses, as topics progress from an introductory level to advanced material. Later courses build upon earlier ones as students gain specific knowledge and thinking skills. A computer science major should develop a depth of understanding and a maturity of thinking in addition to a repertoire of specific algorithms, facts, and details. A focus on individual units obscures this need for depth. As with any broadly-based committee report, Curricula 1991 also reflects a series of compromises among people representing different types of institutions, e.g., engineering schools, colleges of arts and sciences, and liberal arts institutions. Therefore, while the final report identifies many worthwhile topics, some themes important to the liberal arts are explicitly deemphasized. For example, a liberal arts curriculum typically emphasizes high-level abstractions and theory. Therefore, one would expect to see considerable discussion of such topics as theory of computation, computational complexity, and program verification. Similarly, while liberal arts institutions would be expected to cover the basic principles of hardware and computer architecture, these discussions might not extend beyond a single course and probably not to the level of the 59 lecture hours suggested by Curricula 1991. Regarding pedagogy, both Computing as a Discipline and Curricula 1991 make strong statements about the importance of laboratories within the undergraduate curriculum. For example, Computing as a Discipline recommends that laboratories should be used to demonstrate principles, emphasize processes, and introduce experimentation [7, p. 14]. Curricula 1991 `supports a similar view' [1, p. 19]. Many of these difficulties (grouping of topics into courses, sequencing of courses, liberal arts orientation) were addressed in the paper entitled `Model Curriculum for a Liberal Arts Degree in Computer Science' [8]. This 1986 report refined Curriculum 78 [2], taking into account the then-recent recommendations for CS 1 [9] and CS 2 [10], and basing curricular decisions on liberal arts principles and realities. For several years, it served as virtually the only comprehensive and timely model for a four-year computer science curriculum, and consequently the 1986 Model Curriculum had a considerable impact upon computer science offerings on many campuses. Today, literally dozens of schools have a curricular structure based on these original 1986 recommendations. To complete this review of existing curricular recommendations, the current accreditation standards of the Computer Science Accreditation Board (CSAB) [4] should be noted. In general, CSAB requirements are based upon the notion of a concentrated focus within the undergraduate curriculum. CSAB guidelines mandate that a minimum of one and one-third years of an accredited program must be courses in computer science, along with an additional one year of required study in mathematics and the laboratory sciences. Thus, to meet CSAB requirements, an undergraduate program must devote a minimum of 2 and 1/3 years of study, or 58%, to computer science and required mathematics and laboratory science courses. In contrast, a liberal arts education emphasizes breadth as well as reasonable depth in a major, but not to the exclusion of other subjects and ways of thinking. Thus, within a liberal arts setting, a computer science major, including supporting mathematics and science courses, would typically require no more than 40-45% of a student's undergraduate program, significantly lower than CSAB requirements. Since arguments over the relative merits of these two approaches have been going on for many years, resolution of this debate is obviously beyond the scope of this paper. It is clear, however, that the principles motivating CSAB requirements and a liberal arts education are quite different, and very few liberal arts institutions have applied for or received accreditation in computer science. Because of this, CSAB requirements will not be considered relevant to the recommendations that are presented in this paper. 4. PROPOSED REVISIONS TO THE 1986 MODEL CURRICULUM Even today, eight years after it was released, many elements of the 1986 Model Curriculum are still highly appropriate: the division of courses into levels (introductory, core, and electives) provides the appropriate hierarchical framework for the overall curriculum; the size of the major program represents an appropriate balance between a computer science major and the requirements of other liberal arts courses; the introduction of appropriate mathematics at an early stage allows adequate depth and sophistication in succeeding courses; the core program still identifies fundamental areas of the discipline: computer systems, algorithms, computability, and programming languages. However, in the eight years since the appearance of that original 1986 report the discipline has changed greatly. A number of important curricular improvements and enhancements are possible based upon both advances in the discipline and new teaching techniques. For example, today there is an increased awareness of the importance of different programming paradigms--procedural, object-oriented, functional, and logic-- and more emphasis on these topics is appropriate at an early stage. Similarly, greater treatment is needed of important technological developments such as distributed computing and parallel processing. Just as recursion was once viewed as an "advanced topic" but is now part of virtually every course, so too must the issues of parallel algorithms, languages, and architectures become a recurring theme throughout the curriculum. Furthermore, a discussion of these complex architectures leads quite naturally to the equally important issue of how to access and manage this huge collection of resources. Thus, issues such as resource management, virtual environments, and distributed operating systems must also become a core topics in computer science. The last few years have seen a great deal of work with formal laboratories in the first year program, and a modern curriculum must reflect this [1, 7, 11]. Formal laboratories demonstrate the scientific method of inquiry and teach such important skills as data collection and data analysis. At a minimum, formal labs must become a required part of the first year of computer science. If additional resources are available, then other courses could benefit from the addition of formal, scheduled laboratoies. Both Computing as a Discipline and Curricula 1991 observe that theory is best considered as a recurring theme that touches many courses, rather than viewed as a single course with little effect on the remained of the curriculum. In addition, those reports recognize the importance of a strong mathematical foundation for any CS program, and they encourage the inclusion of a significant mathematics requirement as part of any liberal arts computer degree. The growing concern over the use and misuse of computers and information systems argues for a significantly increased treatment of social and ethical issues in computers and an early discussion of professional standards and conduct. Finally, with the increased interest in undergraduate research and development and with today's understanding of the value of such experiences within the curriculum, it is highly appropriate to include a required project at the upper levels of the program. In summary then, this report updates the 1986 curriculum proposal entitled "A Model Curriculum For A Liberal Arts Degree in Computer Science". The eight major changes in this proposal are: 1. Recognition of the importance of different language and problem solving paradigms and their early inclusion into the curriculum, 2. A significant increase in the coverage of parallelism and distributed systems in the intermediate and core courses, 3. Addition of modern topics drawn from the areas of operating systems and architecture into introductory and core courses, 4. The addition of required formal laboratories into the first two computer science courses, 5. The integration of theory as a recurring theme throughout the core, 6. An increase in the number of mathematics courses required for completion of the program, 7. The explicit inclusion of social and ethical issues into introductory and intermediate level courses, and 8. The addition of a required senior project The next section of the report will describe in detail the courses in this revised curriculum. However, the notion of a `course' may vary from one institution to another. For example, courses may be designated as 3 credits or 4 credits, or all courses may be treated as being equal. The following recommendations are based on the simple system where a student typically takes four courses per semester. Graduation then is based upon the completion of eight full semesters or 32 courses. In this context, one course is considered to be about one-fourth of a student's load over a semester or about 1/32nd of the graduation requirement. 5. FOUR MAIN CURRICULUM LEVELS One of the most important characteristics of any curriculum is hierarchy -- a sequence of courses that build on each other in a spiral fashion. Each layer of the hierarchy expands and enriches ideas presented in earlier courses, giving the student a deeper understanding of the material. The 1986 Model Curriculum described in [8] was based on the idea of a three layer curriculum, using layers called Introductory, Core, and Electives. This revision expands and refines these layers in several ways. First, a new level of computer science courses is inserted between the introductory and core levels so that elements of computer architecture, organization, networks, and systems will be introduced relatively early and can be assumed in the core courses. Second, mathematics is introduced as early as possible, and additional mathematics courses are included so suitable concepts and techniques can be presented in both the core and elective courses. Third, a research or development project is included as a required component of at least one elective within each student's major. The overall structure of the Revised Model Curriculum is shown in Table 2. -------------------------------------------------------------------------- Required: 9 computer science 1 introductory, 2 intermediate, 3 core, 3 electives 3 required mathematics courses 12 required courses in total Organization: Level 1. Introductory Level -- CS 1: Computer Science I (with formal laboratory) -- MA 1: Discrete Mathematics Level 2. Intermediate Level -- CS 2: Computer Science II (with formal laboratory) -- CS 3: Computer Organization and Architecture Integral Mathematics Component -- Two courses selected by the student and advisor to support core courses and electives Level 3. Core Level -- CO 1: Sequential and Parallel Algorithms -- CO 2: Foundations of Computing -- CO 3: Programming Languages and Systems Level 4. Computer Science Electives and Project -- Three computer science elective courses building upon core topics -- An independent research or development project with library, written, and oral components Table 2. The Revised Model Curriculum. Levels and Courses -------------------------------------------------------------------------- The following sections will describe the content and structure of each layer of this four level curriculum. 5.1 The Introductory and Intermediate Levels (Levels 1 and 2) The revised introductory course sequence (level 1) is composed of two courses, referred to as CS 1 and MA 1. They introduce fundamental concepts of computer science and discrete mathematics and give students a broad overview of the discipline. Subsequent courses, referred to as CS 2 and CS 3 (level 2), build upon this introduction to provide a broader understanding of computer science and its various subareas and lay the foundations for further study. The presentation of this basic material could follow two distinct and quite different paths--the traditional model and the breadth first model. In the traditional model, the four courses CS 1, CS 2, CS 3, and MA 1 would be viewed as separate and distinct entities which generally address a single coherent topic, e.g., programming, data structures, computer organization and systems, and discrete mathematics. This is the model used in the 1986 curriculum and the majority of schools today. In the breadth first model, the topics are more intertwined, and the four courses are not seen as distinct and independent classes, but as a single, integrated introduction to the discipline extending over three or four semesters. CS 1 Computer Science I/CS 2 Computer Science II Regardless of which of these two approaches is taken, the first two computer science courses should cover the following topics: -- algorithms and algorithmic problem solving -- two fundamental problem-solving paradigms chosen from: procedural, object-oriented, functional Examples: + a procedural language (C, Pascal) in CS 1 and an object- oriented model (C++, Object Pascal, Modula-3, Turing) in CS 2 + a functional language (Scheme, LISP, ML, Miranda) in CS 1 and either a procedural or object-oriented language for CS 2 + a hybrid language (C++, LISP) to integrate the coverage of two models (object-oriented/procedural, functional/procedural) over two-semesters -- control structures, recursion and iteration -- classical computer science algorithms: e.g., sorting, searching, pattern matching -- time and space analysis, including O- and/or -notation -- concepts of modularity, decomposition, procedural and data abstraction, program libraries -- the formal specification of abstract data types -- major data structures: arrays, records, stacks, queues, lists, simple trees and examples of their use in computer science -- software development, including program specifications, design, coding, debugging, testing, verification, and documentation -- brief introduction to internal representation of information -- social issues: intellectual property, liability, privacy, ethical behavior, access In the traditional approach, this range of topics would be introduced using the courses called Computer Science I (CS 1) and Computer Science II (CS 2) described in [8, 9, 10]. In this plan, CS 1 is offered at the introductory level, while CS 2 has CS 1 as a prerequisite and therefore is at a somewhat higher, intermediate level. While there is a good deal of similarity between the 1986 report and this introductory sequence, these new proposals also reflect important new directions in computer science education which have occurred since 1986. First is the question of which language models to use. The 1986 curriculum made the following statement regarding language issues: [One of the objectives of CS 1 is] to teach a block structured programming language. To do justice to the concept of procedural and data abstraction, it would be helpful for students to study a language that directly supports this concept, e.g., Modula-2, CLU, or Ada. Thus, it may be necessary to introduce a different language than the one learned in CS 1. [8] Even in 1986, the designers of the Model Curriculum realized that it may be necessary to consider a set of languages, rather than one, to meet the needs of the introductory sequence. However, rather than stating this to be a desirable option, it now seems mandatory that the courses CS 1 and CS 2 introduce at least two of the fundamental problem solving paradigms currently in use in computer science--procedural, object oriented, and functional. By introducing at least two different world views and models of thinking early in the curriculum, students will be less likely to develop tunnel vision -- the belief that there is only a single model of computation, a single way of doing things. They will be exposed to alternative paradigms, each with its own unique strengths and weaknesses. The second difference between the current proposals and the 1986 report is the explicit requirement of formal laboratories for the courses CS 1 and CS 2. In the last few years, it has become widely accepted that computer science is both a theoretical and an empirical discipline based on formal lecture material and experimental laboratory work. Therefore, there must be a formal laboratory component associated with both CS 1 and CS 2. (Laboratories for other courses in the computer science curriculum are certainly possible and highly beneficial, but due to staffing limitations, they are not required.) These regularly scheduled laboratory sessions should be staffed by faculty or teaching assistants, meet weekly for at least 1 hour (longer, if possible), have a prearranged sequence of activities to be carried out by the student, and require the completion of written exercises. They should not be limited to skills acquisition labs, (e.g., learning to use a debugger or editor), but should be based on the principles of the scientific method, including experimentation, observation, data collection, data analysis, and hypothesis confirmation or rejection. For a discussion of the format and structure of introductory computer science laboratories along with their benefits to the student, see [1] and [11]. The third difference is the inclusion of some theoretical topics in CS 1 and CS 2, such as the time/space complexity of algorithms and the formal specification of abstract data types. As mentioned earlier, it is important that formal ideas drawn from mathematics and logic not be compartmentalized into a one course "theory ghetto". Wherever possible, these concepts should be introduced, even if only at a simple level, and made a part of the introductory and intermediate levels of the curriculum. Students should appreciate early on that mathematical ideas such as proof, counting, and formal models are not simply academic exercises but an essential part of the discipline. Finally, we have included in the introductory sequence an explicit discussion of ethical and social issues. For many students CS 1 and CS 2 will be their only computer science courses. Topics such as ownership of intellectual property, liability, constitutional right of privacy, ethical behavior, and professional standards can influence the behavior of students during class and beyond and can help identify some of the social consequences of computing. MA 1: Discrete Mathematics Computer science draws upon mathematics in many ways, and computer science students need to gain both a mastery of specific topics as well as a general level of mathematical insight and maturity. Unfortunately, such mastery and maturity require time to develop. Further, some mathematical analysis is appropriate in computer science courses from the very beginning (e.g., CS 1). Thus, as a practical matter, some mathematical material should be included as a part of introductory computer science courses, regardless of what mathematics courses students can take. For example, an introduction to conditional statements in CS 1 could include a discussion of Boolean expressions, simplification, and Boolean manipulations, such as DeMorgan's Laws. While such a folding of mathematical material into early computer science courses can be an effective mechanism for developing mathematical maturity, a computer science program should also ensure that students cover the fundamental concepts of discrete mathematics as early as possible, so that these ideas and techniques can be used in subsequent courses. In many colleges and universities, this material will be covered in a separate discrete mathematics course, which should include the following topics: -- sets -- functions -- relations, including partial order -- methods of propositional logic -- introduction to predicate logic -- counting -- recurrence relations -- asymptotic analysis -- proof, including induction -- introduction to probability -- graphs CS 3: Computer Organization and Architecture While students in CS 2 work with high-level abstractions such as objects, functions, and abstract data types, there is also the need to expose students at an early stage to lower level abstractions such as digital logic, machine language, computer architecture, data representation, and elements of distributed systems. CS 3 provides this perspective as it covers the following topics: -- introduction to digital logic and/or microcode -- conventional Von Neumann architectures -- the internal representation of information -- instruction formats and addressing, instruction sets, machine and assembly language programming -- the fetch/execute model of computation -- alternative architectures: RISC/CISC, SIMD/MIMD parallel -- memory architectures and algorithms: cache, virtual memory, paging, segmentation -- I/O architectures: interrupts, memory-mapped I/O -- overview of distributed systems, multiprocessors, networks, massively parallel systems Overall, CS 3 provides low-level hardware and system models which complement the high-level abstractions discussed in CS 2. To summarize, the four courses contained in the first two levels of the Revised Model Curriculum are sequenced as shown in Table 3. ------------------------------------------------------------------------------- CS 1 Computer Science 1 MA 1 Discrete Mathematics (with formal laboratory) \ / \ \ / \ \| |/ \| CS 2 Computer Science 2 CS 3 Computer Organization (with formal laboratory) and Architecture Table 3. Organization of the Four Introductory and Intermediate Courses in the Curriculum ------------------------------------------------------------------------------ 5.2 Integral Mathematics Component In addition to the introductory and intermediate courses listed in Table 3 above, students must develop their reasoning ability, sophistication, and mathematical background. Thus, the 1986 report recommended a two course mathematics requirement--a one semester Discrete Mathematics course and a second course chosen from a set which included a second discrete mathematics course, linear algebra, and calculus. While this recommendation increased the students' mathematical foundation, it did not allow students the opportunity to fully develop the reasoning skills associated with mathematical maturity. Thus, these revised recommendations specify three required mathematics courses, two beyond Discrete Mathematics. This will begin to provide appropriate background for the core courses and/or electives and help to develop reasoning skills and mathematical maturity. Since different areas of computer science draw upon different mathematical topics and since students may have widely varying interests, it is unrealistic to believe that a single requirement will fill the needs of every student. Instead, the Revised Model Curriculum suggests that specific courses be selected by students in consultation with an advisor and with the intent of providing appropriate background for later work. For example, a linear algebra course might be appropriate for students planning to take a course in graphics. Other likely mathematics course options might include calculus I and II, discrete mathematics II, probability and statistics, and mathematical modeling. While this recommendation does not reach the four courses required for accreditation by the Computing Science Accreditation Board, a three course requirement makes sense within the context of the liberal arts, where emphasis is placed on developing sophistication in many disciplines beyond the major. Further, the flexibility of choosing courses that support later work provides support for a wide range of student abilities and interests. 5.3 The Core Courses (Level 3) The introductory and intermediate courses just described address wide ranging themes that impact all of computing and computer science -- themes such as algorithms, problem solving, data types, abstractions, proof, and the Von Neumann architecture. The purpose of these initial courses is to give the student a broad overview of the central concepts of computer science, mathematics, and logic. The third level of the curriculum, called the core, focuses on individual subareas of the discipline and demonstrates to the student that computer science, like any scientific discipline, is divided into separate and distinct areas of study. The core is composed of the following three courses which can be taken in any order: CO 1. Sequential and Parallel Algorithms CO 2. Foundations of Computing CO 3. Programming Languages and Systems The following paragraphs describe each of these redesigned core courses. CO 1. Sequential and Parallel Algorithms This course examines the design and efficiency of algorithms from both a sequential and a parallel perspective. It also investigates problem-solving strategies and the relative difficulty of various classes of problems and problem solving techniques. A list of possible topics would include the following: -- algorithmic paradigms, including divide and conquer, greedy methods, dynamic programming -- advanced data structures not covered in CS 2, such as heaps, hashing, or height-balanced trees -- graph algorithms -- minimum spanning trees, shortest path, connected components -- proofs of algorithm correctness -- complexity analysis of both parallel and recursive algorithms -- parallel algorithms -- parallel sorting and searching, reduction, parallel prefix -- algorithms for numerical problem solving, error analysis, stability -- algorithms associated with process synchronization -- algorithms concerning deadlock: its avoidance, detection, and resolution It should be noted that, as time permits, additional algorithms from a range of problem domains might be presented to illustrate the use of various problem-solving approaches. Depending on his or her experience, an instructor may wish to discuss such areas as computational geometry or visualization algorithms. Also, it is worth emphasizing the inclusion of algorithms drawn from the areas of computer architecture and systems, e.g., deadlock and process synchronization. It is important for students to see connections between courses and the interrelationships between courses. By using algorithms drawn from the area of systems, this will demonstrate the important relationship between a study of algorithms (CO 1) and computer organization (CS 3). CO 2. Foundations of Computing Mathematical concepts are recurring themes in the Revised Model Curriculum, and courses discuss such topics as the complexity analysis of algorithms, Boolean logic, the use of recurrence relations to analyze recursive algorithms, and the formal description of abstract data types. This course builds upon those ideas, demonstrating the logical and mathematical foundations of computer science and providing a context for this theory by using the ideas in some practical applications. 1. Models of Computation -- finite and pushdown automata, nondeterminism, recursive functions, regular expressions 2. Grammars and parsing -- language syntax, context free grammars, BNF, parsing -- short overview of language processors, compilers, interpreters 3. Solvable and unsolvable problems -- Turing machines -- Church's thesis and universal Turing machines -- The halting problem, unsolvability 4. P and NP Complexity Classes -- the classes P and NP -- NP-complete problems and intractable problems -- approximate, nonoptimal solutions to NP problems Theoretical models and their practical applications should be thoroughly intertwined throughout this course. For example, after discussing various types of automata, one could discuss the concepts of a simple lexical parser. After discussing context-free languages and BNF, students might write a simple recursive-descent parser for expressions. With these applications, there may be time for the inclusion of only selected proofs related to Turing machines and Church's thesis. CO 3. Programming Languages and Systems The third core course explores computer languages and system environments from multiple perspectives, including connections with problem-solving paradigms, language design, implementation, and capabilities for parallelism. The course demonstrates the application of formal methods to programming languages through discussions of formal semantics and verification. As several language models have already been covered in CS 1 and CS 2, less time needs to be spent in this new course than in previous language courses, with correspondingly more time available for issues of design and implementation. Course topics may be divided into the following four major groups: 1. Language paradigms: procedural, functional, object-oriented,logic 2. Language design and implementation issues -- language representations, data structures, control structures -- binding, the run-time environment -- language support for modularity, information hiding, exception handling, encapsulation -- type issues: static and dynamic types, polymorphism, type inference 3. Language issues related to parallelism -- language mechanisms for parallel architectures -- processes, process management, interprocess communications -- message passing, shared memory 4. Proving properties of programs -- formal semantics (axiomatic, operational, and/or denotational) -- program proofs To summarize, the Revised Model Curriculum utilizes six computer science courses plus discrete mathematics to introduce students to the breadth of computer science and to cover the appropriate core areas of the discipline. This proposal also specifies two additional mathematics courses, chosen to support course work in those core areas and the advanced electives. 5.4 Relationship of the Introductory and Core Sequence to Curricula 1991 The courses recommended for the first three levels cover many of the areas suggested in Curricula 1991 [1], although some differences in emphasis may be noted. Overall, the core of Curricula 1991 includes 283 hours of lecture, with some additional, but unspecified time devoted to laboratories. This proposal recommends six computer science courses at the introductory, intermediate, or core level. Since formal course work normally will include lectures, discussions, and laboratories, estimates of how much time will be devoted to lecture during each course must be very rough. As a conservative estimate, one might suppose that a typical course meets three times a week for a 14 week semester, and each of these recommended courses would total 42 hours. Allowing a couple of hours for tests or reviews, each course would contain approximately 40 hours of lecture, and six courses would involve a total of 240 hours. Thus, in terms of size, the required courses in this proposal involve about 43 fewer hours of lecture than Curricula 1991, a difference of about 15%. Beyond this difference in required contact hours, there are also significant differences in content. Table 4 shows the approximate number of hours spent in each of the 11 topic areas specified in Curriculum 91 and compares this total against the recommended number of hours in that report. The assignment of lecture hours to topics is based on the course descriptions given in this paper. Specific numbers in the table should be treated as tentative and approximate, as any such tabulation depends on many subjective choices regarding course design. They do allow, however, a rough comparison. ------------------------------------------------------------------------------ Curricula| Approx. Hours Recommended in this Proposal 1991 | Introductory Core Courses | Courses (Alg)(Found)(Lang) Subject Area Total | Total CS1 CS2 CS3 CO1 CO2 CO3 ----------------------------------|------------------------------------------ Algorithms & Data Str. 47 | 76 13 20 19 24 Architecture 59 | 38 1 1 30 2 4 ----------------------------------|------------------------------------------ AI and Robotics 9 | 3 3 Database & Info Retrieval 9 | 2 1 1 ----------------------------------|------------------------------------------ Human-Computer Comm. 8 | 3 1 2 Intro. to a Prog. Language 12 | 15 10 5 Numerical & Symbolic Comp. 7 | 7 1 1 5 ----------------------------------|------------------------------------------ Operating Systems 31 | 25 1 1 9 5 9 Programming Languages 46 | 48 3 2 16 27 ----------------------------------|------------------------------------------ Software Methodology & Eng. 44 | 13 5 4 4 Social and Ethical Issues 11 | 10 4 4 2 Table 4. Comparison of the Hours Spent in Each Subject Area in Curriculum 1991 and the Revised Model Curriculum ------------------------------------------------------------------------------- While specific numbers in this table should be treated as highly approximate, these values suggest a significant difference in emphases between the two programs. Specifically, these liberal arts recommendations clearly emphasize the topics of algorithms and data structures with 76 hours spent on these topics compared to 47 in Curriculum 91. Further, even with fewer overall hours of lecture required in this proposal, the courses required here roughly meet the goals prescribed by Curricula 1991 in programming languages, operating systems, symbolic and numerical computation, and social issues. This reflects the liberal arts emphasis on concepts and the pervasive role of theory throughout this curriculum. On the other hand, this curriculum contains significantly less material in such applied areas as architecture, software engineering, robotics, and database systems although such topics could be covered in more depth in electives. 5.5 Electives and the Senior Project (Level 4) The fourth level of the curriculum is the computer science electives. The purpose of these electives is three-fold: 1. to introduce students to specific areas of research and development within computer science, 2. to show how ideas presented in the introductory, intermediate, and core sequences can be used to solve important real world problems in computer science, and 3. to involve seniors in a research or development project. Point number 2 above is particularly important and is the reason why the first three levels of the curriculum should be completed (or nearly completed) prior to beginning the electives. Courses like graphics, networks, and artificial intelligence are typically viewed as the "fun" courses, and most students want to enroll in these courses as soon as possible, frequently well before they have completed the core. This should be discouraged as the elective courses build upon the important concepts studied in the first six computer science courses. For example, an elective in the area of computer networks would likely draw upon hardware topics from CS 3, process synchronization algorithms introduced in CO 1, and graph algorithms (for routing) studied in MA 1. Similarly, a compiler course would utilize the concepts of regular expressions and finite state machines presented in CO 2 as well as the language design and implementation concepts discussed in both CS 3, CO 2, and CO 3. Thus, the student must resist the urge to hurry into the elective level without first building the base of ideas and knowledge on which these elective courses will rest. The specific electives included in the program will, of course, depend on a number of factors, including the interests of the faculty and the size of the student population. The following is an alphabetized list of electives that might appear in the catalogs of typical liberal arts computer science programs. EL 1 Advanced Algorithms EL 2 Artificial Intelligence EL 3 Compiler Design EL 4 Computer Architecture EL 5 Database Principles EL 6 Formal Semantics EL 7 Graphics EL 8 Natural Language Understanding EL 9 Networks EL 10 Numerical Methods EL 11 Operating Systems EL 12 Parallel Processing EL 13 Simulation EL 14 Social and Ethical Issues of Computing EL 15 Software Engineering EL 16 Advanced Topics in the Theory of Computation EL 17 Topics in Computer Science Since one of the hallmarks of a liberal arts curriculum is interdisciplinary study, it is also possible, and even beneficial, if there are courses offered in other departments that would be of interest to computer science students and that would meet part of the elective requirement. Examples of such courses might include: Physics: Hardware design, logic design Linguistics: Computational linguistics Business: Management information systems, systems analysis While students should take enough courses to gain depth in advanced areas of computer science, major requirements must fit within the bounds prescribed by a liberal arts education. Thus, these proposed recommendations specify that a computer science major must complete a minimum of three electives chosen from the above list or from other approved courses available at their institution. However, as schedules permit, majors are strongly encouraged to take an additional course or two at this level if it can be accommodated within the major program and the rules of the college. Regardless of which electives are offered, the curriculum should be arranged so that each student will work on a significant project during his or her senior year. This project should allow seniors to participate either in a one-on-one scholarly endeavor with a faculty member or in a small, possibly interdisciplinary, team involving both students and faculty. This experience could last either one semester or possibly a full year, depending on the number of graduates, the number of faculty, and the amount of resources available. While this work could be done independently with a faculty member, it is expected that for the majority of students this experience will be included as part of one of their elective courses. While the nature of this project will vary a great deal from school to school, at a minimum it should involve the following three important components: 1. a review of one or more scholarly papers from the primary literature of computer science, 2. the writing of a significant scientific paper or substantial technical document to give the student experience in writing for a scientific audience, and 3. an oral presentation to students and/or faculty. The additional details of the senior project will depend heavily on the interests and capabilities of the student and the time available to both students and faculty. Therefore, there must be a number of options on how this project could be fulfilled. Some possibilities include: - an actual research project involving a one-on-one research experience between the student and a faculty member lasting either 1 or 2 semesters. At many schools, this experience is called an Honors Project. This experience also may be integrated into an elective course at the senior level. - a group software-engineering project involving a team of students specifying, designing, implementing and documenting a substantial software project over a 1 or 2 semester time frame. - a special "senior project course" required of all graduating seniors. For example, this could be a course looking at important emerging areas of research within the discipline. - a review of the literature within a specific area and the writing of a scholarly paper summarizing ones findings as part of an elective course. All of these models could be reasonable implementations of a senior project experience. The key concern is whether or not they include the three required characteristics listed above: exposure to the primary research literature of computer science, the writing of a scholarly technical paper, and an oral presentation of findings and results to ones peers. This required senior project experience represents an important and unique change from the 1986 curriculum proposal. Experience with a major project can be extremely helpful for careers both in and out of computer science. Expanded research opportunities for undergraduates are vital, so that they, like graduate students, can experience the excitement (and frustrations) of scholarly inquiry and the scientific method. Further, students should be exposed to the literature of computer science, and they should be given practice with both oral and written technical communication. A senior project can provide these important learning experiences. Liberal arts colleges, with their smaller number of graduating seniors and their emphasis on oral and written communications, are in an excellent position to implement this important curricular initiative. In total, this revised Model Curriculum requires a total of 9 computer science courses (1 introductory, 2 intermediate, 3 core, 3 electives), and 3 mathematics courses, a total of 12 required courses. Assuming that students take 32 courses during their college studies, then the recommended 12 course major represents 38% of the total course load--certainly within the limits of most liberal arts colleges. If one or two additional laboratory science courses are added as part of the general distribution requirement, the total undergraduate computer science degree program will contain 13 or 14 courses out of 32. This curriculum therefore covers 41 to 44% of the overall credits within computer science, mathematics, and laboratory sciences, considerably less than the minimum of 58% proposed by CSAB. There is also a good deal of flexibility to add more computer science or mathematics courses should a student so desire. 6. POSSIBLE COURSE STRUCTURES AND SCHEDULES The requirements for a computer science major following this revised model curriculum is a total of 12 semester courses. The following discussion shows that the proposed curriculum recommendations can be completed by students within the normal four year program and can be implemented given the limited number of faculty available at many liberal arts colleges. The sample programs, shown in Table 5, demonstrate how students can complete the required courses within the normal four year college period. In fact, two possible schedules are given. The first chart shows a schedule for the student who begins work in computer science immediately upon entering college. However, at liberal arts colleges, many students do not begin as computer science majors but switch into it from other areas in their first or second year. The second chart indicates that scheduling is flexible enough to permit students to start the program in their second year and still complete it within the four year time span required of most colleges. The project is listed in parenthesis in each semester of the senior year, but it may be taken with any elective. Further, if an elective were taken in the third year, then one elective could be taken each semester of the fourth year, and the senior project could extend for a full year. ----------------------------------------------------------------------------- Schedule for a Student Starting | Schedule for a Student Starting Computer Science in the First | Computer Science in the Second Year | Year Fall Spring | Fall Spring | | First Year | CS 1 CS 2 | MA 1 | | Second Year | CS 3 Core 1 | CS 1 CS 2 Math 2 Math 3 | MA 1 Math 2 | Third Year | | Core 2 Core 3 | CS 3 Core 1 Elective 1 | Math 3 Core 2 | Fourth Year | | Elective 2 Elective 3 | Core 3 Elective 2 (project) (project) | Elective 1 Elective 3 (project) | Table 5. Typical Schedules for Students Completing a Computer Science Major ----------------------------------------------------------------------------- Staffing of the proposed four-level curriculum is possible under only modest assumptions. For example, assuming that the Mathematics Department teaches both Discrete Math and the two subsequent mathematics courses, then a modest but fully reasonable schedule might offer CS 1 and CS 2 every semester, CS 3 and all three core courses once each year, and four electives per year, two each semester. Given these assumptions, Table 6 shows the teaching load needed to staff that program. ----------------------------------------------------------------------------- Annual Number of Course Comments Sections 2 CS 1 (1 section each semester) 2 CS 2 (1 section each semester) 1 CS 3 (1 section each year) 3 Core courses (each core course offered annually) 4 Elective courses (four electives per year) 0-1 Project (in addition to teaching electives, some faculty members may receive teaching credit for guiding student research) TOTAL 12-13 Table 6. A Possible Staffing Schedule ----------------------------------------------------------------------------- Overall, this minimal but fully reasonable schedule requires the staffing of only 12 to 13 computer science sections each year. Details concerning how these courses are scheduled among faculty will depend upon such institutional policies as teaching loads, faculty size, and the number of sections of service courses for non-majors. Certainly additional sections would enhance the richness of the curriculum by offering greater scheduling flexibility, more elective courses, and greater research opportunities. However, the chart above shows that with a relatively modest number of sections, a small liberal arts computer science faculty can offer a rigorous and high quality undergraduate program in computer science. 7. CONCLUSIONS Computer science is a young discipline, and its curriculum is growing, changing and evolving in response to new developments and new ideas. This report has described a revision of the 1986 Curriculum proposal entitled "A Model Curriculum For A Liberal Arts Degree in Computer Science." This revised four-layer curriculum, comprised of 9 computer science and 3 mathematics courses, allows a liberal arts college to maintain the strengths of the liberal arts environment while, at the same time, providing sufficient depth and rigor within the discipline. In addition to an emphasis on the fundamental principles of computer science, the curriculum includes expanded mathematical study, exposure to the empirical aspects of computer science via formal laboratories, and--most importantly--gives all students a chance to experience the excitement of scientific research and inquiry. Taken together, these characteristics make this a strong and rigorous program of study that can be implemented with the resources and faculty available today at most liberal arts colleges. 8. REFERENCES 1. ACM/IEEE-CS Joint Curriculum Task Force, Computing Curricula 1991, IEEE Computer Society Press, 1991. 2. ACM Curriculum Committee on Computer Science, Curriculum 78: Recommendations for the undergraduate program in computer science. Communications of the ACM, 22(3), March 1979, pp. 151-197. 3. M. J. Clancy and M. C. Linn, ``The Case for Case Studies of Programming Problems,'' paper presented at the annual meeting of the American Educational Research Association, March, 1989, San Francisco, California. 4. Computing Sciences Accreditation Board, ``Criteria for Accrediting Programs in Computer Science in the United States'', 1993 Annual Report of the Computing Sciences Accreditation Board, Stamford, CT, pp. 26-41. 5. Robert Cupper, ``Undergraduate Research in Computer Science at Allegheny College,'' presentation at the 1993 Liberal Arts Computer Science Consortium Meeting, June, 1993, Washington and Lee University. 6. Robert Cupper, ``The Required Senior Thesis and a Topics and Research Methods junior seminar course,'' presentation at the 1991 Liberal Arts Computer Science Consortium Meeting, June, 1991, Grinnell College. 7. Peter J. Denning, Douglas E. Comer, David Gries, Michael C. Mulder, Allen B. Tucker, A. Joe Turner, and Paul R. Young, Computing as a Discipline, Communications of the ACM, 32(1), January 1989, pp. 9-23. 8. Norman Gibbs and Allen Tucker, ``Model Curriculum for a Liberal Arts Degree in Computer Science'' Communications of the ACM, 29(3), March 1986, pp. 202-210. 9. Elliot P. Koffman, David Stemple, and Caroline E. Wardle, Recommended Curriculum for CS1: 1984, A Report of the ACM Curriculum Task Force for CS1, Communications of the ACM, 27(10), October 1984, pp. 998-1001. 10. Elliot P. Koffman, David Stemple, and Caroline E. Wardle, Recommended Curriculum for CS2: 1984, A Report of the ACM Curriculum Task Force for CS2, Communications of the ACM, 28(8), August 1985, pp. 815-818. 11. Jeff Parker, Robert Cupper, Charles Kelemen, Dick Molnar, Greg Scragg, Laboratories in the Computer Science Curriculum, Journal of Computer Science Education, 1990, pp. 205-221. 12. Allen Tucker and David Garrick, ``A Breadth-First Introductory Curriculum in Computing,'' Computer Science Education 2(3), Fall 1991. ------------------------------------------------------------------------ SIDEBAR This report reflects the on-going discussions of an active working group, the Liberal Arts Computer Science Consortium. Initially funded by a grant from the Sloan Foundation, the group's first major product was the 1986 paper, A Model Curriculum for a Liberal Arts Degree in Computer Science, by Norman Gibbs and Allen Tucker (Communications of the ACM, March 1986, pp. 202-210). Subsequent meetings and discussions have led to a range of papers and presentations, covering such topics as service courses, approaches to laboratories, experiments involving a breadth-first emphasis in the first courses, and goals for the first two years of undergraduate computer science. The current Revised Model Curriculum focuses upon the computer science major itself. It does not address other issues, such as computer literacy, a computer science minor, or various interdisciplinary programs. Similarly, following the original Model Curriculum, it does not consider majors outside the liberal arts setting. Thus, it does not address the needs of many B.S. and engineering programs. The following members of the Liberal Arts Computer Science Consortium have been active in discussing the this Revised Model Curriculum, in contributing ideas, and in making many suggestions: Nancy Baxter, Dickinson College James Bradley, Calvin College Kim Bruce, Williams College Robert Cupper, Allegheny College Scot Drysdale, Dartmouth College Stuart Hirshfield, Hamilton College Michael Jipping, Hope College Charles Kelemen, Swarthmore College Christopher Nevison, Colgate University Robert Noonan, College of William and Mary Richard Salter, Oberlin College G. Michael Schneider, Macalaster College Greg Scragg, SUNY at Geneseo Allen Tucker, Bowdoin College Henry M. Walker, Grinnell College Tom Whaley, Washington and Lee University After circulating drafts of this proposal in the spring of 1994, the Consortium met at Swarthmore College in June 1994 for intensive discussions and an extensive reworking of the topics and structure of the proposed curriculum. Subsequent drafts were circulated widely in the summer of 1994, and helpful responses were received from several other colleagues in response.