Computing Curricula 2001
Computer Science Volume

Appendix A
CS Body of Knowledge

This appendix to the Computing Curricula 2001 report defines the knowledge domain that is likely to be taught in an undergraduate curriculum in computer science. The underlying rationale for this categorization scheme and additional details about its history, structure, and application are included in the full task force report. Because we expect the appendices to have wider circulation than the full report, the task force feels it is important to include in each appendix a summary of the fundamental concepts that are necessary to understand the recommendations. The most important concepts are outlined in the sections that follow.

Structure of the body of knowledge

The CS body of knowledge is organized hierarchically into three levels. The highest level of the hierarchy is the area, which represents a particular disciplinary subfield. Each area is identified by a two-letter abbreviation, such as OS for operating systems or PL for programming languages. The areas are broken down into smaller divisions called units, which represent individual thematic modules within an area. Each unit is identified by adding a numeric suffix to the area name; as an example, OS3 is a unit on concurrency. Each unit is further subdivided into a set of topics, which are the lowest level of the hierarchy.

Core and elective units

In updating the body of knowledge from the framework established in Computing Curricula 1991, the CC2001 Task Force has to take account of the fact that the computing discipline has expanded to such an extent that it is impossible for undergraduates to learn every topic that has at one time been considered fundamental to the discipline. The task force has therefore sought to define a minimal core consisting of that material that essentially everyone teaching computer science agrees is essential to anyone obtaining an undergraduate degree in this field. Material offered as part of an undergraduate program that falls outside the core is considered to be elective. By insisting on a broad consensus in the definition of the core, the task force hopes to keep the core as small as possible, giving institutions the freedom to tailor the elective components of the curriculum in ways that meet their individual needs.

In discussing the CC2001 recommendations during their development, we have found that it helps to emphasize the following points:

• The core is not a complete curriculum. Because the core is defined as minimal, it does not, by itself, constitute a complete undergraduate curriculum. Every undergraduate program must include additional elective units from the body of knowledge, although the CC2001 report does not define what those units will be.
• Core units are not necessarily limited to a set of introductory courses taken early in the undergraduate curriculum. Although many of the units defined as core are indeed introductory, there are also some core units that clearly must be covered only after students have developed significant background in the field. For example, the task force believes that all students must develop a significant application as some point during their undergraduate program. The material that is essential to successful management of projects at this scale is therefore part of the core, since it is required of all students. At the same time, the project course experience is very likely to come toward the end of a student's undergraduate program. Similarly, introductory courses may include elective units alongside the coverage of core material. The designation core simply means required and says nothing about the level of the course in which it appears.

  Assessing the time required to cover a unit

  To give readers a sense of the time required to cover a particular unit, the CC2001 report must define a metric that establishes a standard of measurement. Choosing such a metric has proven difficult, because no standard measure is recognized throughout the world. For consistency with the earlier curriculum reports, the task force has chosen to express time in hours, corresponding to the in-class time required to present the material in a traditional lecture-oriented format. To dispel ny potential confusion, however, it is important to underscore the following observations about the use of lecture hours as a measure:

  • The task force does not seek to endorse the lecture format. Even though we have used a metric with its roots in a classical, lecture-oriented form, the task force believes that there are other styles -- particular given recent improvements in educational technology -- that can be at least as effective. For some of these styles, the notion of hours may be difficult to apply. Even so, the time specifications should at least serve as a comparative measure, in the sense that a 5-hour unit will presumably take roughly five times as much time to cover as a 1-hour unit, independent of the teaching style.
  • The hours specified do not include time spent outside of class. The time assigned to a unit does not include the instructor's preparation time or the time students spend outside of class. As a general guideline, the amount of out-of-class work is approximately three times the in-class time. Thus, a unit that is listed as requiring 3 hours will typically entail a total of 12 hours (3 in class and 9 outside).
  • The hours listed for a unit represent a minumum level of coverage. The time measurements we have assigned for each unit should be interpreted as the minimum amount of time necessary to enable a student to perform the learning objectives for that unit. It is always appropriate to spend more time on a unit than the mandated minimum.

  Details of the CS body of knowledge

  A summary of the body of knowledge -- showing the areas, units, which units are core, and the minimum time required for each -- appears as Figure A-1. The details of each area follow as separate sections.

  The following links will take you to the individual descriptions of these areas:

  1.	Discrete Structures (DS)
  2.	Programming Fundamentals (PF)
  3.	Algorithms and Complexity (AL)
  4.	Architecture and Organization (AR)
  5.	Operating Systems (OS)
  6.	Net-Centric Computing (NC)
  7.	Programming Languages (PL)
  8.	Human-Computer Interaction (HC)
  9.	Graphics and Visual Computing (GV)
  10.	Intelligent Systems (IS)
  11.	Information Management (IM)
  12.	Social and Professional Issues (SP)
  13.	Software Engineering (SE)
  14.	Computational Science and Numerical Methods (CN)

  Figure A-1. Computer science body of knowledge with core topics underlined

  DS. Discrete Structures (43 core hours)    DS1. Functions, relations, and sets (6)    DS2. Basic logic (10)    DS3. Proof techniques (12)    DS4. Basics of counting (5)    DS5. Graphs and trees (4)    DS6. Discrete probability (6) PF. Programming Fundamentals (38 core hours)    PF1. Fundamental programming constructs (9)    PF2. Algorithms and problem-solving (6)    PF3. Fundamental data structures (14)    PF4. Recursion (5)    PF5. Event-driven programming (4) AL. Algorithms and Complexity (31 core hours)    AL1. Basic algorithmic analysis (4)    AL2. Algorithmic strategies (6)    AL3. Fundamental computing algorithms (12)    AL4. Distributed algorithms (3)    AL5. Basic computability (6)    AL6. The complexity classes P and NP    AL7. Automata theory    AL8. Advanced algorithmic analysis    AL9. Cryptographic algorithms    AL10. Geometric algorithms    AL11. Parallel algorithms AR. Architecture and Organization (36 core hours)    AR1. Digital logic and digital systems (6)    AR2. Machine level representation of data (3)    AR3. Assembly level machine organization (9)    AR4. Memory system organization and architecture (5)    AR5. Interfacing and communication (3)    AR6. Functional organization (7)    AR7. Multiprocessing and alternative architectures (3)    AR8. Performance enhancements    AR9. Architecture for networks and distributed systems OS. Operating Systems (18 core hours)    OS1. Overview of operating systems (2)    OS2. Operating system principles (2)    OS3. Concurrency (6)    OS4. Scheduling and dispatch (3)    OS5. Memory management (5)    OS6. Device management    OS7. Security and protection    OS8. File systems    OS9. Real-time and embedded systems    OS10. Fault tolerance    OS11. System performance evaluation    OS12. Scripting NC. Net-Centric Computing (15 core hours)    NC1. Introduction to net-centric computing (2)    NC2. Communication and networking (7)    NC3. Network security (3)    NC4. The web as an example of client-server computing (3)    NC5. Building web applications    NC6. Network management    NC7. Compression and decompression    NC8. Multimedia data technologies    NC9. Wireless and mobile computing PL. Programming Languages (21 core hours)    PL1. Overview of programming languages (2)    PL2. Virtual machines (1)    PL3. Introduction to language translation (2)    PL4. Declarations and types (3)    PL5. Abstraction mechanisms (3)    PL6. Object-oriented programming (10)    PL7. Functional programming    PL8. Language translation systems    PL9. Type systems    PL10. Programming language semantics    PL11. Programming language design

  HC. Human-Computer Interaction (8 core hours)    HC1. Foundations of human-computer interaction (6)    HC2. Building a simple graphical user interface (2)    HC3. Human-centered software evaluation    HC4. Human-centered software development    HC5. Graphical user-interface design    HC6. Graphical user-interface programming    HC7. HCI aspects of multimedia systems    HC8. HCI aspects of collaboration and communication GV. Graphics and Visual Computing (3 core hours)    GV1. Fundamental techniques in graphics (2)    GV2. Graphic systems (1)    GV3. Graphic communication    GV4. Geometric modeling    GV5. Basic rendering    GV6. Advanced rendering    GV7. Advanced techniques    GV8. Computer animation    GV9. Visualization    GV10. Virtual reality    GV11. Computer vision IS. Intelligent Systems (10 core hours)    IS1. Fundamental issues in intelligent systems (1)    IS2. Search and constraint satisfaction (5)    IS3. Knowledge representation and reasoning (4)    IS4. Advanced search    IS5. Advanced knowledge representation and reasoning    IS6. Agents    IS7. Natural language processing    IS8. Machine learning and neural networks    IS9. AI planning systems    IS10. Robotics IM. Information Management (10 core hours)    IM1. Information models and systems (3)    IM2. Database systems (3)    IM3. Data modeling (4)    IM4. Relational databases    IM5. Database query languages    IM6. Relational database design    IM7. Transaction processing    IM8. Distributed databases    IM9. Physical database design    IM10. Data mining    IM11. Information storage and retrieval    IM12. Hypertext and hypermedia    IM13. Multimedia information and systems    IM14. Digital libraries SP. Social and Professional Issues (16 core hours)    SP1. History of computing (1)    SP2. Social context of computing (3)    SP3. Methods and tools of analysis (2)    SP4. Professional and ethical responsibilities (3)    SP5. Risks and liabilities of computer-based systems (2)    SP6. Intellectual property (3)    SP7. Privacy and civil liberties (2)    SP8. Computer crime    SP9. Economic issues in computing    SP10. Philosophical frameworks SE. Software Engineering (31 core hours)    SE1. Software design (8)    SE2. Using APIs (5)    SE3. Software tools and environments (3)    SE4. Software processes (2)    SE5. Software requirements and specifications (4)    SE6. Software validation (3)    SE7. Software evolution (3)    SE8. Software project management (3)    SE9. Component-based computing    SE10. Formal methods    SE11. Software reliability    SE12. Specialized systems development CN. Computational Science and Numerical Methods (no core hours)    CN1. Numerical analysis    CN2. Operations research    CN3. Modeling and simulation    CN4. High-performance computing