Research Notebook

Introductory Computer Science Education: A Dean's Perspective

By Randal E. Bryant, Klaus Sutner and Mark J. Stehlik
The School of Computer Science is planning major revisions to its introductory course sequence in ways that will affect not just our own students, but also the many students from across campus who take computer science courses. A committee of computer science faculty, chaired by Bob Harper, has done a careful analysis of our current course structure and proposed important changes. 


Over the years, undergraduate education has taken an increasingly higher priority among our faculty, and we take great pride in the quality of our program. Given the success of our current program, a natural question to ask is "Why change it?" Both our students and their employers are very pleased with the outcomes of our program. In making any changes, we must take care not to unintentionally cause harm. 


Three main factors motivate our desire for change--one concerning how we communicate an intellectual vision for computer science, one concerning the changing ways that computers get used and one concerning how computer systems are constructed.

Whom we serve

The School of Computer Science provides computer science education for almost the entire campus. Every semester, we have around 900 students taking our introductory courses, including students from all six colleges offering undergraduate degrees.

Considering that the university has around 1,450 entering undergraduate students every year, and even accounting for the fact that some students take two introductory courses, we can see that our courses engage a large fraction of the
undergraduate students at some point in their time here. We can partition the students taking our courses into three general categories:

1. CS Majors: Our undergraduate program enrolls 130-140 students per year. They are admitted directly into our program as entering freshmen. Their backgrounds range from students who have never written a line of code in their lives to ones who have developed commercial software.

2. Allied Non-Majors: A number of other students take multiple courses in computer science. These include all of the electrical and computer engineering majors (around 150 per year), plus some students in math, science, other parts of engineering, and even some in such diverse majors as architecture, psychology and philosophy. These students can be distinguished from the other non-majors by the fact that they take at least one of our "core" courses, typically 15-211 (algorithms and data structures) or 15-213 (computer systems). Some Electrical and Computer Engineering (ECE) students take many more CS courses, covering a large fraction of the undergraduate program. Around 30 students each year fulfill the requirements to receive a minor in computer science. All told, there are around 200 students per year whom we would classify  as "allied non-majors."

3. Other Non-Majors: Over 600 students per year take one or two computer science courses without any plan to go beyond an introductory level. Many of them are required to take at least one CS course as part of their degree requirements. This includes around 50 students per year enrolled in the Information Systems program in the School of Humanities & Social Sciences.

The diversity of the students we encounter has significant repercussions for how we structure our introductory courses. For one thing, the sheer number of students taking introductory courses stresses our teaching resources. For another, over half of our students never go beyond an introductory level. What we teach them in their first course will define their entire concept of the field of computer science.

We must satisfy the educational needs of a wide variety of students, ranging from those wishing to pursue computer science for the rest of their lives to those hoping to get by with minimal exposure. And we must structure our course sequences to be compatible with a number  of different educational programs.

Providing an educational model for the world

In addition to educating our own students, Carnegie Mellon has the opportunity, and perhaps the duty, to inform the world with a vision for computer science education.

For example, Jeannette Wing's writings on computational thinking have inspired educators worldwide. We historically have played a major role in designing the advanced placement exams for computer science. Our Alice Project has demonstrated that young people can learn the concepts of programming in the context of computer-game construction and storytelling. Our success at increasing the number of young women involved in computer science has gained widespread recognition.

How we teach introductory computer science is especially important in this role as an educational model. When students learn computer science in high school, a primary objective is to gain advanced placement, skipping over one or more college-level courses. Right now, the advanced-placement exam is largely a test of elementary programming in Java. High school teachers are highly motivated to "teach to the test," and consequently students are given a very skills-oriented perspective on computer science.

This conveys a message to many high school students--the ones we want to recruit--that computer science has little intellectual content, and that careers are limited to sitting in cubicles, churning out code. Students also see this path as providing weak prospects, as those jobs can readily be outsourced to lower-wage countries. Thus, how we teach introductory computer science has a ripple effect on how society views computer science as an intellectual discipline.

Overall, universities in the United States saw steep drops in enrollments in computer science programs, after peaking during the "dot-com boom." At Carnegie Mellon, we saw this as a drop in the number of students applying to the computer science program from an all-time high of 3,237 in 2001 to a low of 1,732 in 2005. Our applicant pool has since returned to a healthy level, with 3,026 students--the second-highest number ever--applying to enter in 2010. (Because we have the luxury of selecting only the top applicants, we have maintained a steady rate of 130 to 140 entering students per year without compromising on quality.)

Nationally, the number of students deciding to major in computer science has risen only slightly in the past few years. Yet the U.S. Bureau of Labor Statistics forecasts that between 2008 and 2018, almost 75 percent of the nation's new science and engineering jobs will be in computing fields, while just 16 percent will be in other engineering disciplines. Although close to 140,000 job openings in computing fields are forecast during that time, they project that only 50,000 students will receive degrees in computer science and related areas.

Another unfortunate trend is that computer science courses are rapidly disappearing from our nation's high schools due to budget pressures, the need to devote all resources to achieving the metrics imposed by the No Child Left Behind Act, a lack of qualified teachers and a lack of interest on the part of students. As a consequence, although our enrollment numbers are strong, many of our incoming students have had little opportunity to program computers. Thus, we must continue to accommodate a wide range of prior experience among students taking our introductory computer science classes.

Major efforts are underway by the Association for Computing, the Computing Research Association, the National Science Foundation and even the Department of Defense to find ways to infuse an appreciation and excitement for computer science in middle and high school students in the United States, through experiences both within and outside of the classroom. As an institution that wants to be viewed as one of the thought-leaders for the field, we would like to play a role in these efforts. A first step is to make sure our introductory courses provide a more inviting picture of the meaning of "computer science."

Promoting computational thinking

We believe that, even for non-majors, our introductory courses can serve the dual roles of providing a useful set of computer science skills while also providing a rigorous grounding in computational thinking, enabling students to acquire new skills throughout their careers.

Computational thinking, a term coined by Jeannette Wing, refers to the set of concepts and strategies used by computer scientists to formulate and solve problems. The term captures the idea that computer scientists have developed unique ways of formulating and solving computational problems, yielding a rigorous discipline with a well-defined intellectual core.

The principles embodied in this core can inform other disciplines, including math, science and engineering, as well as aspects of humanities, arts and business. We would like to pursue Jeannette's vision by bringing elements of computational thinking into our introductory computer science courses, especially those targeting non-majors.

Increasing software reliability

There is a growing sense that we must inject greater discipline into the software development process. As computers are increasingly used to control critical resources, such as heart pacemakers, antilock braking systems and the national power grid, a simple bug can literally cause people to die. In addition, most security breaches in computer systems occur due to poorly written programs. With the increasing number and sophistication of malicious adversaries in the world, systems are exposed to a very hostile testing environment that is likely to uncover even the most obscure bugs. Inspired by the work of Edmund Clarke, we believe it is important to introduce students to the tools and techniques by which they can reason about and evaluate their programs right from the start.

We want students to be able to argue both formally and informally that their programs will run under all possible conditions. We want them to understand the logical methods by which they can reason about programs, and to be familiar with the growing collection of tools that can aid systematic program development.

Preparing for a world of parallel computation

Maintaining the rate of improvements to computer performance we have experienced since the 1950s will soon require that we write programs that can exploit parallel computation.

While the number of transistors that can be integrated onto a chip continues to double every 18-24 months, semiconductor manufacturers are no longer able to design circuits that will execute individual code sequences much faster. Instead, they have shifted to a strategy of increasing the number of independent processors, or cores, integrated on to a single chip. Making a program run faster now requires that it be written in such a way that multiple parts can be executed in parallel.

With the exception of several upper-level and graduate courses, our current presentations of how computers operate, how they are programmed and what constitutes an efficient algorithm are based on a purely sequential model. As championed by Guy Blelloch, we want our students to think about how to decompose a problem such that many parts of the problem can be solved in parallel.

Opportunities for parallelism also arise in lower-level forms, where entire vectors of data can be processed in parallel. We must therefore shift to models that expose the many opportunities parallel execution within computations.

Our plan for revising (and renumbering) our data structures and algorithms course is to teach students to think parallel. By this we mean that every aspect of how programs are expressed, how they are analyzed, and how they are optimized will be reworked to consider:
  1. How they would perform if there were unbounded computing resources, and
  2. How they would perform if limited to n processors, with sequential execution being the special case of n =1.
The course will present traditional key algorithmic techniques such as divide-and-conquer, dynamic programming and greedy methods, as well as ones specifically oriented to parallel computation, such as contraction and map/reduce.

Proposed changes

Our introductory courses should present the core concepts of computer science, conveying the principles of computational thinking. Even though we cannot delve into them deeply, we can provide enough coverage to demonstrate the intellectual and practical value of the principles of computer science.

We will still teach students how to write programs, since programming provides the tools to actually try out computer science concepts and make them more concrete, but we must not let the mastery of programming skills be the principal focus. We also recognize the desire of other departments to have students be able to write programs to solve problems in their domains.

Figure 1 highlights the proposed introductory courses and several of the follow-on core courses:

15-110: Principles of Computer Science. An introduction to computer science, based on the principles of computational thinking. Many taking this course will be non-majors, but we will also use it as the entry point for any entering student with limited programming experience, as indicated by the dashed line from 15-110 to 15-122.

15-122: Principles of Imperative Computation. Introduces students to methods for writing and reasoning about programs written in an imperative style, where each step of computation updates some portion of the program state. The course will go beyond our current Java-based introductory programming course (15-121) to include elementary algorithms and data structures and how to systematically reason about program behavior, for example by expressing invariant properties of loops.

15-150: Principles of Functional Computation. Introduces students to methods for writing and reasoning about programs written in a functional style, where a computation is realized as a nested sequence of function calls, each call defining a map from inputs to outputs, but not altering any state. The course covers methods to define and reason about data types, infinite data structures and higher-order control constructs. The material will be based on the current 15-212 course, which will be discontinued.

15-210: Fundamental Algorithms and Data Structures, along with supporting theoretical foundations and practical applications. Our existing data structures and algorithms course (15-211), but totally revamped to include ways to reason about and optimize their performance on both sequential and parallel machines.

15-213: Introduction to Computer Systems. Our existing course introducing students to how computer systems execute programs, store information and communicate, presented from a programmer's perspective. This course will remain largely unchanged.

15-214: Principles of Software System Construction. A new course that will cover the methodology for designing large-scale software systems, including object-oriented programming, concurrency and component-based software reuse. The box for this course is shaded in gray, since much about this class has not been resolved, including its name, course number, prerequisites and content.

The two major changes to the overall course structure are moving our coverage of functional computation to an introductory course that precedes the data structures and algorithms course, and creating a new course on software system construction. The first change is based on our belief that a functional perspective should be a key part of expressing and reasoning about parallel computation. The second is in recognition of the need to better prepare students for the complex software systems they will encounter in their careers.

Conclusions

Although there are many details to work out, we are moving ahead with a revised set of introductory computer science courses that we believe will better serve majors and non-majors alike, and will put Carnegie Mellon at the intellectual forefront of computer science education.

We will shift away from a focus on the mechanics of programming and instead cover the general principles of computer science, based on the theme of computational thinking. We will have students learn to reason about programs in more systematic ways, recognizing the increasing need for secure and reliable programs. We will prepare students for a time when parallel computing becomes the main method by which we can continue to push the limits of computer performance.
For More Information: 

Jason Togyer | 412-268-8721 | jt3y@cs.cmu.edu