Below are the first 10 and last 10 pages of uncorrected machine-read text (when available) of this chapter, followed by the top 30 algorithmically extracted key phrases from the chapter as a whole.
Intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text on the opening pages of each chapter. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.
Do not use for reproduction, copying, pasting, or reading; exclusively for search engines.
OCR for page 45
Report of a Workshop on the Scope and Nature of Computational Thinking 4 Relationship to Past and Ongoing Efforts 4.1 PREVIOUS WORK A number of past activities and reports have argued for introducing computational thinking to populations broader than undergraduates and graduate students matriculating in computer science or information technology. In addition, several reports have sought to identify what computer scientists believe is the intellectual core of their discipline. 4.1.1 LOGO In the 1960s, Seymour Papert introduced the notion of a computer-based microworld that could serve as an environment in which a child could learn “to manipulate, to extend, to apply to projects, thereby gaining a greater and more articulate mastery of the world, a sense of the power of applied knowledge and a self-confidently realistic image of himself as an intellectual agent.” He argued that computation could have “a profound impact by concretizing and elucidating many previously subtle concepts in psychology, linguistics, biology, and the foundations of logic and mathematics” by giving a child the ability “to articulate the working of his own mind and particularly the interaction between himself and reality in the course of learning and thinking.”1 1 Seymour Papert, 1975, “Teaching Children Thinking,” Journal of Structural Language 4:219-29.
OCR for page 46
Report of a Workshop on the Scope and Nature of Computational Thinking As an example, Papert offered mathematics. He argued that many children never see the point of the formal use of language, which is what much of mathematics teaches. They also rarely, if ever, have the experience of designing a formalism of their own adapted to a particular personally meaningful task. But anyone who programs a computer does these things routinely. Through the construction of specialized formal microworlds, the LOGO environment is intended to provide appropriate terminology and concepts that facilitate the formal use of language and the child-driven extension of that language in useful ways. By programming the computer to do interesting things, Papert argued, children can become highly sophisticated and articulate in the art of developing models and developing formal systems. A number of workshop participants, Uri Wilenksy among them, also pointed out that although many of the intellectual ideas introduced by the LOGO movement are quite similar to those underlying the advocacy of computational thinking, there are many significant differences in the larger environment in which these activities were and are embedded. Forty years ago, when LOGO was first introduced, computational infrastructure was expensive, and access to networking and personal computing was non-existent for all practical purposes. Today, computational devices are everywhere, and access to networking and personal computing are quite commonplace. Moreover, the idea that computational technology could have a deep impact on everyday life for most citizens—outlandish then—is now easily accepted, and thus the ubiquitous presence of computational devices in our lives is an important motivator for systems of formal education to provide individuals with appropriate intellectual tools for managing and using such devices effectively. 4.1.2 Fluency with Information Technology (FIT) The 1999 report Being Fluent with Information Technology, also known as the FITness report or the fluency report, was an effort by the Computer Science and Telecommunications Board of the National Research Council to articulate what everyone should know about information technology.2 In formulating the relevant knowledge base, this effort identified three equally important categories of knowledge: cognitive/intellectual capabilities, computational concepts, and IT skills. Capabilities focus on logical reasoning and problem solving such as debugging. Concepts rep- 2 NRC, 1999, Being Fluent with Information Technology. Washington, D.C.: National Academy Press. Available at http://www.nap.edu/catalog.php?record_id=6482. Accessed December 28, 2009.
OCR for page 47
Report of a Workshop on the Scope and Nature of Computational Thinking resent the fundamental ideas that underlie technology, such as programming and algorithms. Finally, skills are the actual knowledge required when using information technology, such as creating a Word document or sending an e-mail. The attempt to define “everyone” was more problematic—although the members of the responsible committee likely believed, as individuals, that all K-12 students should be exposed to the elements of IT fluency, and indeed should become fluent with information technology, none of the committee members had any particular standing to make such an assertion, and in the end the committee limited the scope of its recommendations to all graduates of 4-year colleges and universities. The executive summary of Being Fluent with Information Technology is reprinted as Appendix C. I think the goals of the fluency report were [answering the question] what should everybody know to be a more effective user of technology? And I think that computational thinking focuses more on [the] intellectual activities that apply to all of the sciences and engineering that we talked about, and [also] all those other areas that could benefit from computation. So it seems to me that they’re slightly different objectives. I don’t see them as in conflict…. They overlap a lot because they do speak to a similar set of phenomena. —Lawrence Snyder 4.1.3 Computing the Future In 1992, the National Research Council issued the report Computing the Future,3 which was (among other things) the first Academy effort to articulate the nature of computer science and engineering as an intellectual discipline. That report noted the following (pp. 19-24): Intellectually, the “science” in “computer science and engineering” connotes understanding of computing activities, through mathematical and engineering models and based on theory and abstraction. The term “engineering” in “computer science and engineering” refers to the prac- 3 NRC, 1992, Computing the Future: A Broader Agenda for Computer Science and Engineering. Washington, D.C.: National Academy Press. Available at http://www.nap.edu/catalog.php?record_id=1982. Accessed December 28, 2009.
OCR for page 48
Report of a Workshop on the Scope and Nature of Computational Thinking tical application, based on abstraction and design, of the scientific principles and methodologies to the development and maintenance of computer systems—be they composed of hardware, software, or both. [The notion of CS&E as a discipline based on theory, abstraction, and design is described in Peter Denning, Douglas E. Comer, David Gries, Michael C. Mulder, Allen Tucker, Joe Turner, and Paul R. Young, 1989, “Computing as a Discipline,” Communications of the ACM, 32(1):9-23, January.] Thus both science and engineering characterize the approach of CS&E professionals to their object of study. What is the object of study? For the physicist, the object of study may be an atom or a star. For the biologist, it may be a cell or a plant. But computer scientists and engineers focus on information, on the ways of representing and processing information, and on the machines and systems that perform these tasks. The key intellectual themes in CS&E are algorithmic thinking, the representation of information, and computer programs. An algorithm is an unambiguous sequence of steps for processing information, and computer scientists and engineers tend to believe in an algorithmic approach to solving problems. In the words of Donald Knuth, one of the leaders of CS&E: CS&E is a field that attracts a different kind of thinker. I believe that one who is a natural computer scientist thinks algorithmically. Such people are especially good at dealing with situations where different rules apply in different cases; they are individuals who can rapidly change levels of abstraction, simultaneously seeing things “in the large” and “in the small.” [Personal communication to the NRC Committee to Assess the Scope and Direction of Computer Science and Technology, Donald Knuth, March 10, 1992, letter.] The second key theme is the selection of appropriate representations of information; indeed, designing data structures is often the first step in designing an algorithm. Much as with physics, where picking the right frame of reference and right coordinate system is critical to a simple solution, picking one data structure or another can make a problem easy or hard, its solution slow or fast. The issues are twofold: (1) how should the abstraction be represented, and (2) how should the representation be properly structured to allow efficient access for common operations? A classic example is the problem of representing parts, suppliers, and customers. Each of these entities is represented by its attributes (e.g., a customer has a name, an address, a billing number, and so on). Each supplier has a price list, and each customer has a set of outstanding orders to each supplier. Thus there are five record types: parts, suppliers, customers, price, and orders. The problem is to organize the data so that it is easy to answer questions like: Which supplier has the lowest price on part P?, or, Who is the largest customer of supplier S? By clustering related data together, and by constructing
OCR for page 49
Report of a Workshop on the Scope and Nature of Computational Thinking auxiliary indices on the data, it becomes possible to answer such questions quickly without having to search the entire database. The two examples below also illustrate the importance of proper representation of information: A “white pages” telephone directory is arranged by name: knowing the name, it is possible to look up a telephone number. But a “criss-cross” directory that is arranged by number is necessary when one needs to identify the caller associated with a given number. Each directory contains the same information, but the different structuring of the information makes each directory useful in its own way. A circle can be represented by an equation or by a set of points. A circle to be drawn on a display screen may be more conveniently represented as a set of points, whereas an equation is a better representation if a problem calls for determining if a given point lies inside or outside the circle. A computer program expresses algorithms and structures information using a programming language. Such languages provide a way to represent an algorithm precisely enough that a “high-level” description (i.e., one that is easily understood by humans) can be mechanically translated (“compiled”) into a “low-level” version that the computer can carry out (“execute”); the execution of a program by a computer is what allows the algorithm to come alive, instructing the computer to perform the tasks the person has requested. Computer programs are thus the essential link between intellectual constructs such as algorithms and information representations and the computers that enable the information revolution. Computer programs enable the computer scientist and engineer to feel the excitement of seeing something spring to life from the “mind’s eye” and of creating information artifacts that have considerable practical utility for people in all walks of life. Fred Brooks has captured the excitement of programming: The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds castles in the air, creating by the exertion of the imagination…. Yet the program construct, unlike the poet’s words, is real in the sense that it moves and works, producing visible outputs separate from the construct itself…. The magic of myth and legend has come true in our time. One types the correct incantation on a keyboard, and a display screen comes to life, showing things that never were, nor could be. [Frederick Brooks, 1975, The Mythical Man-Month, Reading, Mass.: Addison-Wesley.] Programmers are in equal portions playwright and puppeteer, working as a novelist would if he could make his characters come to life simply by touching the keys of his typewriter. As Ivan Sutherland, the father of computer graphics, has said,
OCR for page 50
Report of a Workshop on the Scope and Nature of Computational Thinking Through computer displays I have landed an airplane on the deck of a moving carrier, observed a nuclear particle hit a potential well, flown in a rocket at nearly the speed of light, and watched a computer reveal its innermost workings. [Ivan Sutherland, 1970, “Computer Displays,” Scientific American 222(6):56-81.] Programming is an enormously challenging intellectual activity. Apart from deciding on appropriate algorithms and representations of information, perhaps the most fundamental issue in developing computer programs arises from the fact that the computer (unlike other similar devices such as non-programmable calculators) has the ability to take different courses of action based on the outcome of various decisions. Here are three examples of decisions that programmers convey to a computer: Find a particular name in a list and dial the telephone number associated with it. If this point lies within this circle then color it black; otherwise color it white. While the input data are greater than zero, display them on the screen. When a program does not involve such decisions, the exact sequence of steps (i.e., the “execution path”) is known in advance. But in a program that involves many such decisions, the sequence of steps cannot be known in advance. Thus the programmer must anticipate all possible execution paths. The problem is that the number of possible paths grows very rapidly with the number of decisions: a program with only 10 “yes” or “no” decisions can have over 1000 possible paths, and one with 20 such decisions can have over 1 million…. The themes of algorithms, programs, and information representation also provide material for intellectual study in and of themselves, often with important practical results. The study of algorithms within CS&E is as challenging as any area of mathematics; it has practical importance as well, since improperly chosen algorithms may solve problems in a highly inefficient manner, and problems can have intrinsic limits on how many steps are needed to solve them. The study of programs is a broad area, ranging from the highly formal study of mathematically proving programs correct to very practical considerations regarding tools with which to specify, write, debug, maintain, and modify very large software systems (otherwise called software engineering). Information representation is the central theme underlying the study of data structures (how information can best be represented for computer processing) and much of human-computer interaction (how information can best be represented to maximize its utility for human beings).
OCR for page 51
Report of a Workshop on the Scope and Nature of Computational Thinking 4.1.4 Reflections on the Field The 2004 NRC report Computer Science: Reflections on the Field, Reflections from the Field included an essay by Gerald Sussman entitled “The Legacy of Computer Science.”4 Quoting from that essay (pp. 181-183): Computer Science is not a science, and its ultimate significance has little to do with computers. The computer revolution is a revolution in the way we think and in the way we express what we think. The essence of this change is the emergence of what might best be called procedural epistemology—the study of the structure of knowledge from an imperative point of view, as opposed to the more declarative point of view taken by classical mathematical subjects. Traditional mathematics provides a framework for dealing precisely with notions of “what is.” Computation provides a framework for dealing precisely with notions of “how to.” [Harold Abelson, Gerald Jay Sussman, with Julie Sussman, 1985, Structure and Interpretation of Computer Programs (1st edition), Cambridge, Mass., MIT Press.] Computation provides us with new tools to express ourselves. This has already had an impact on the way we teach other engineering subjects. For example, one often hears a student or teacher complain that the student knows the “theory” of the material but cannot effectively solve problems. We should not be surprised: the student has no formal way to learn technique. We expect the student to learn to solve problems by an inefficient process: the student watches the teacher solve a few problems, hoping to abstract the general procedures from the teacher’s behavior with particular examples. The student is never given any instructions on how to abstract from examples, nor is the student given any language for expressing what has been learned. It is hard to learn what one cannot express. In particular, in an introductory subject on electrical circuits we show students the mathematical descriptions of the behaviors of idealized circuit elements such as resistors, capacitors, inductors, diodes, and transistors. We also show them the formulation of Kirchoff’s laws, which describe the behaviors of interconnections. From these facts it is possible, in principle, to deduce the behavior of an interconnected combination of components. However, it is not easy to teach the techniques of circuit analysis. The problem is that for most interesting circuits there are many equations and the equations are quite complicated. So it takes organiza- 4 NRC, 2004, “The Legacy of Computer Science,” pp. 181-183 in Computer Science: Reflections on the Field, Reflections from the Field. Washington, D.C.: The National Academies Press. Available at http://www.nap.edu/catalog.php?record_id=11106. Accessed December 28, 2009.
OCR for page 52
Report of a Workshop on the Scope and Nature of Computational Thinking tional skills and judgment to effectively formulate the useful equations and to deduce the interesting behaviors from those equations. Traditionally, we try to communicate these skills by carefully solving selected problems on a blackboard, explaining our reasoning and organization. We hope that the students can learn by emulation, from our examples. However, the process of induction of a general plan from specific examples does not work very well, so it takes many examples and much hard work on the part of the faculty and students to transfer the skills. However, if I can assume that my students are literate in a computer programming language, then I can use programs to communicate ideas about how to solve problems: I can write programs that describe the general technique of solving a class of problems and give that program to the students to read. Such a program is precise and unambiguous—it can be executed by a dumb computer! In a nicely designed computer language a well-written program can be read by students, who will then have a precise description of the general method to guide their understanding. With a readable program and a few well-chosen examples it is much easier to learn the skills. Such intellectual skills are very hard to transfer without the medium of computer programming. Indeed, “a computer language is not just a way of getting a computer to perform operations but rather it is a novel formal medium for expressing ideas about methodology. Thus programs must be written for people to read, and only incidentally for machines to execute.” [Harold Abelson, Gerald Jay Sussman, with Julie Sussman, 1985, Structure and Interpretation of Computer Programs (1st edition), Cambridge, Mass., MIT Press.] I have used computational descriptions to communicate methodological ideas in teaching subjects in electrical circuits and in signals and systems. Jack Wisdom and I have written a book and are teaching a class that uses computational techniques to communicate a deeper understanding of classical mechanics. Our class is targeted for advanced undergraduates and graduate students in physics and engineering. In our class computational algorithms are used to express the methods used in the analysis of dynamical phenomena. Expressing the methods in a computer language forces them to be unambiguous and computationally effective. Students are expected to read our programs and to extend them and to write new ones. The task of formulating a method as a computer-executable program and debugging that program is a powerful exercise in the learning process. Also, once formalized procedurally, a mathematical idea becomes a tool that can be used directly to compute results. 4.1.5 Engineering in K-12 Education The National Academy of Engineering (NAE) and its Committee on K-12 Engineering Education issued a report arguing that an engineering component has been largely missing in recent attempts to improve sci-
OCR for page 53
Report of a Workshop on the Scope and Nature of Computational Thinking ence, technology, engineering, and mathematics (STEM) education.5 The NAE committee found this fact particularly troubling in light of its view that “… K-12 engineering education may improve student learning and achievement in science and mathematics; increase awareness of engineering and the work of engineers; boost youth interest in pursuing engineering as a career; and increase the technological literacy of all students.” That committee also hypothesized that the “future of K-12 engineering education” will depend on whether engineering becomes a more interconnected component of STEM education or remains a separate subject. The report noted that unlike mathematics and science education in the K-12 years, engineering education does not have much in the way of teaching standards, testing and assessment, or teacher professional development. More broadly, the committee held that there is “no widely accepted vision of what K-12 engineering education should include or accomplish. This lack of consensus reflects the ad hoc development of educational materials in engineering and that no major effort has been made to define the content of K-12 engineering in a rigorous way…. These shortcomings may be the result, at least in part, of the absence of a clear description of which engineering knowledge, skills, and habits of mind are most important, how they relate to and build on one another, and how and when (i.e., at what age) they should be introduced to students.” To improve engineering education, the report noted the importance of emphasizing engineering design, incorporating important and developmentally appropriate mathematics, science, and technology knowledge skills (among which were certain “computational methods”), and promoting engineering habits of mind (i.e., the values, attitudes, and thinking skills associated with engineering). Such considerations are relevant to the discussion of this workshop report because of the strong connections between many such engineering habits of mind and computational thinking. The report also called for research on various dimensions of engineering education (including its connection to other STEM fields) and for the initiation of a national dialogue on preparing K-12 educators to address the special challenges of engineering education at the K-12 level. 4.1.6 Technically Speaking In 2002, the National Academy of Engineering and the NRC issued the report Technically Speaking: Why All Americans Need to Know More 5 National Academy of Engineering and National Research Council, 2009, Engineering in K-12 Education: Understanding the Status and Improving the Prospects. Washington, D.C.: The National Academies Press. Available at http://www.nap.edu/catalog.php?record_id=12635. Accessed December 28, 2009.
OCR for page 54
Report of a Workshop on the Scope and Nature of Computational Thinking About Technology6 and its companion website.7 This report advanced a view of technological literacy that encompasses three interdependent dimensions—knowledge, ways of thinking and acting, and capabilities with the goal of providing people “with tools to participate intelligently and thoughtfully in the world around them”: Knowledge for technological literacy consists of a recognition of the pervasiveness of technology in everyday life, an understanding of basic engineering concepts, an understanding of the limitations of the engineering process, a knowledge of ways technology has shaped human history and vice versa, a recognition that technology reflect the values and culture of society, a recognition of technology risk, both anticipated and unanticipated, and an awareness that technology development involves cost/benefit tradeoffs. Ways of thinking and acting for technological literacy include questioning oneself and others regarding benefits and risks associated with technology, actively seeking information about new technologies, and actively taking part in decisions about the development and use of technology. Some of the basic capabilities the report points to as characteristic in a technically literate person include certain hands-on technical skills like word processing or navigating online, an ability to identify and fix simple technical malfunctions, and an ability to think about benefits and risk in basic mathematical terms. These three dimensions have approximate mappings to the tripartite framework of FITness (foundational concepts, intellectual capabilities, and contemporary skills), as discussed in Box 2.2. 4.2 SOME DRIVERS OF CHANGE Workshop participants described a number of ongoing efforts to revise and reform computing-related education. Implicit in these efforts is a presumption that they will all have to address computational thinking in some form, but for the most part, their efforts had not converged on a common definition of the term. 6 National Academy of Engineering and National Research Council, 2002, Technically Speaking: Why All Americans Need to Know More About Technology. Washington, D.C.: National Academy Press. Available at http://www.nap.edu/catalog.php?record_id=10250. Accessed December 28, 2009. 7 For the companion website, see National Academy of Engineering, “Technically Speaking,” available at http://www.nae.edu/techlit, accessed December 28, 2009.
OCR for page 55
Report of a Workshop on the Scope and Nature of Computational Thinking 4.2.1 The National Science Foundation CPATH Program In 2008, the Computer and Information Science and Engineering (CISE) Directorate of the National Science Foundation launched a program entitled “CISE Pathways to Revitalized Undergraduate Computing Education” (CPATH).8 This program emphasizes the development of student competencies in computing concepts, methods, technologies, and tools (which collectively constitute what the program calls computational thinking) in approaches that promise to revitalize undergraduate education. Founded on the importance of preparing a globally competitive U.S. workforce that is able to apply computational thinking to a broad range of societal challenges and opportunities, the program seeks to contribute to the development of a globally competitive U.S. workforce with computational thinking competencies essential to U.S. leadership in the global innovation enterprise; to increase the number of students developing computational thinking competencies by infusing opportunities for learning computational thinking into undergraduate education in the core computing fields—computer and information science and engineering— and in other fields of study; and to demonstrate transformative computational-thinking-focused undergraduate education models that are replicable across a variety of institutions. Although aimed primarily at revitalizing undergraduate education, the program also encourages the exploration of new models that extend from institutions of higher education into the K-12 environment. Activities that engage K-12 teachers and students to facilitate the seamless transition of secondary students into undergraduate programs focused on computational thinking are particularly encouraged. 4.2.2 The Computing Research Association Education Committee Andrew Bernat described for workshop participants some of the present-day efforts (2009) of the Computing Research Association (CRA) Education Committee.9 Stressing the importance of revitalizing computing education and noting the centrality of computers and computing to 8 For more information, see NSF Directorate for Computer and Information Science and Engineering (CISE), “CISE Pathways to Revitalized Undergraduate Computing Education (CPATH) FAQ Site,” available at http://www.nsf.gov/cise/funding/cpath_faq.jsp, accessed December 28, 2009, and CISE Pathways to Revitalized Undergraduate Computing Education (CPATH) Program Summary,” available at http://www.nsf.gov/funding/pgm_summ.jsp?pims_id=500025&org=CNS&from=home, accessed December 28, 2009. 9 For more information, visit the Computing Research Association at http://www.cra.org/, accessed December 28, 2009.
OCR for page 56
Report of a Workshop on the Scope and Nature of Computational Thinking a number of fields—art, music, history, and archeology, as well as the traditional sciences and engineering—Bernat said that these efforts focus on “the computing education that a researcher in any discipline needs to know and think about and understand. It is not intended to be the undergraduate curriculum that someone going on to do computer science should be exposed to or should learn. It’s about researchers in any discipline. What are the core things about computing that everyone needs to understand?” Bernat further emphasized that in contrast to groups such as the ACM that are focusing on education in computer science, the CRA intends to focus its efforts on computing skill, knowledge, and impact outside the computer science discipline. 4.2.3 Advanced Placement Computer Science— NSF Broadening Participation Program and the College Board Jan Cuny described for workshop participants the NSF/College Board collaboration to redesign and revitalize the high school Advanced Placement (AP) Computer Science (CS) curriculum.10,11 According to Cuny, the current CS AP course is inaccessible to students and fails to introduce the fundamental concepts of computational thinking. Cuny expressed the hope that a new “gold-standard” AP course that addresses these concepts will revive the flagging interest of high school students in computer science, information technology, and mathematics and will provide a foundation for future study in computing. She pointed out that developing the curriculum for this new course is not the most challenging aspect. The hardest part is to gain entry into “resource-strapped schools.” Nevertheless, Cuny hopes that this new gold-standard CS AP course can be introduced into 10,000 schools (with a complement of 10,000 teachers trained to teach the course) by 2014. She was not unmindful of the challenges, pointing out that most of these teachers are not computer scientists themselves. “Most of them are from math or from physics or from chemistry and they know how to program … but they don’t know about computability. They don’t know about algorithm design. There’s a whole lot of stuff that they don’t know. So it’s not just in-service preparation, meaning bring them in for a week. It’s really significant training that we have to provide. And we have to figure out how to make that palatable for them.” 10 The College Board, “National Science Foundation Awards $1.8 Million to College Board to Redesign AP Science Courses.” Available at http://www.collegeboard.com/press/releases/51572.html. Accessed December 28, 2009. 11 NSF Directorate for Computer and Information Science and Engineering (CISE), “Broadening Participation in Computing (BPC).” Available at http://www.nsf.gov/funding/pgm_summ.jsp?pims_id=13510&org=CNS&from=home. Accessed December 28, 2009.
OCR for page 57
Report of a Workshop on the Scope and Nature of Computational Thinking Finally, Cuny raised the related point that it is important to distinguish between ideas and concepts that can be tested on a standardized exam and what it means to assess whether students can think computationally. In the absence of a consensus on the scope and nature of computational thinking, she noted that it would be very difficult to develop an appropriate assessment tool for the latter. 4.2.4 Carnegie Mellon University’s Center on Computational Thinking Carnegie Mellon University’s Center for Computational Thinking is the home to a number of projects that focus on using computational thinking to tackle broad social and interdisciplinary issues. According to Peter Lee, these projects—known as PROBlem-oriented Explorations, or PROBEs in the local vernacular—cover a wide range of ongoing research projects, all of which are designed to demonstrate the critical importance of computational thinking. These projects typically engage the sciences, the arts, and literature.12 During the workshop, Lee pointed to the Optimal Kidney Exchange PROBE, which uses novel algorithm design and database networking to identify optimal kidney matches between donors based on a complex set of criteria. Traditionally, kidney matching is done manually by medical experts based on blood type, organ size, patient condition, and so on. The manual methods used by most physicians also tend to look at a small number of donors and patients—paired donations (involving two donors coordinating their donations) are the most common. By using larger numbers of coordinated donors (8 or 10 or 12 donors at a time), the number of organs made available that can match the needs of individual recipients can be vastly increased. However, the complexity of coordinating larger numbers of donors is quite daunting, unless efficient computational algorithms can be used to perform the search. The result is that medical experts can match kidneys among a much larger number of patients and donors in a number of kidney exchange programs more rapidly. More effective kidney exchanges can improve the quality of life for those on dialysis currently awaiting kidneys, save millions in medical costs for dialysis treatments, and save thousands of lives. Discussed on the center’s website, the Performer PROBE is an interactive music system for live performance that is capable of composing 12 See the Center for Computational Thinking, Carnegie Mellon University, “PROBEs,” available at http://www.cs.cmu.edu/~CompThink/probes.html, accessed December 28, 2009.
OCR for page 58
Report of a Workshop on the Scope and Nature of Computational Thinking and accompanying live music in different genres, such as classical, rock, and Latin.13 Unlike systems that merely accompany human-performed music and require a strict adherence to beat and score, Performer will be able to interact with other human musicians, change tempo, and even change styles in a manner that is similar to how a human would behave in such a situation. Performer employs modeling, sequencing, synchronicity, algorithms, human-computer interaction theory, sensors, and data management theory to dissect nuances of music composition and music performance. The center’s website also discusses the PROBE on Understanding and Harnessing Ensemble Behavior,14 which uses the “programming” metaphor to understand how the behavior of components aggregate to produce behavior in complex systems, whether natural or man-made. Although the complex system is “just” the aggregation of its constituent components, the capabilities of the system far exceed the aggregate of the capabilities of those components. Using a specially developed programming language called Meld, the project demonstrates abstraction, programming, logic, ensemble engineering, self-organization, robotics, and programming in the context of understanding emergent behavior. Meld is designed to streamline the process of programming for ensemble systems, and it works by propagating the commands that input through every node in the system, thus saving the programmer the time needed to propagate the command herself. 13 See the Center for Computational Thinking, Carnegie Mellon University, “PROBEs,” available at http://www.cs.cmu.edu/~CompThink/probes.html, accessed December 28, 2009. 14 See the Center for Computational Thinking, Carnegie Mellon University, “PROBEs,” available at http://www.cs.cmu.edu/~CompThink/probes.html, accessed December 28, 2009.