Computer Science Curricula 2013 Strawman Draft (February 2012) The Joint Task Force on Computing Curricula Association for Computing Machinery IEEE-Computer Society CS2013 Steering Committee ACM Delegation IEEE-CS Delegation Mehran Sahami, Chair (Stanford University) Steve Roach, Chair (Univ. of Texas, El Paso) Andrea Danyluk (Williams College) Ernesto Cuadros-Vargas (Univ. Catolica San Pablo) Sally Fincher (University of Kent) Ronald Dodge (US Military Academy) Kathleen Fisher (Tufts University) Robert France (Colorado State University) Dan Grossman (University of Washington) Amruth Kumar (Ramapo Coll. of New Jersey) Beth Hawthorne (Union County College) Brian Robinson (ABB Corporation) Randy Katz (UC Berkeley) Remzi Seker (Univ. of Arkansas, Little Rock) Rich LeBlanc (Seattle University) Alfred Thompson (Microsoft) Dave Reed (Creighton University) - 2 - Table of Contents Chapter 1: Introduction ................................................................................................................... 5 Charter......................................................................................................................................... 6 High-level Themes ...................................................................................................................... 6 Knowledge Areas ........................................................................................................................ 7 Previous Input ............................................................................................................................. 8 Coming Attractions in CS2013 ................................................................................................... 9 Timeline .................................................................................................................................... 10 Exemplars of Curricula and Courses ........................................................................................ 10 Professional Practice ................................................................................................................. 11 Institutional Challenges ............................................................................................................ 11 Opportunities for Involvement .................................................................................................. 12 References ................................................................................................................................. 12 Acknowledgments..................................................................................................................... 13 Chapter 2: Principles ..................................................................................................................... 16 Chapter 3: Characteristics of Graduates ....................................................................................... 19 Chapter 4: Constructing a Complete Curriculum ......................................................................... 22 Knowledge Areas are Not Necessarily Courses (and Important Examples Thereof) ............... 23 Tier-1 Core, Tier-2 Core, Elective: What These Terms Mean, What is Required ................... 24 Further Considerations .............................................................................................................. 26 - 3 - Chapter 5: Introduction to the Body of Knowledge...................................................................... 28 Process for Updating the Body of Knowledge ......................................................................... 28 Overview of New Knowledge Areas ........................................................................................ 29 How to Read the Body of Knowledge ...................................................................................... 31 Appendix A: The Body of Knowledge ......................................................................................... 35 Algorithms and Complexity (AL) ............................................................................................. 35 Architecture and Organization (AR) ......................................................................................... 42 Computational Science (CN) .................................................................................................... 48 Discrete Structures (DS) ........................................................................................................... 55 Graphics and Visualization (GV).............................................................................................. 61 Human-Computer Interaction (HC) .......................................................................................... 68 Information Assurance and Security (IAS)............................................................................... 76 Information Management (IM) ................................................................................................. 87 Intelligent Systems (IS)............................................................................................................. 95 Networking and Communication (NC) ................................................................................... 105 Operating Systems (OS) ......................................................................................................... 109 Platform-Based Development (PBD) ..................................................................................... 116 Parallel and Distributed Computing (PD) ............................................................................... 119 Programming Languages (PL) ................................................................................................ 128 Software Development Fundamentals (SDF) ......................................................................... 138 Software Engineering (SE) ..................................................................................................... 143 Systems Fundamentals (SF) .................................................................................................... 157 Social and Professional Practice (SP) ..................................................................................... 163 - 4 - 1 Chapter 1: Introduction 2 Continuing a process that began over 40 years ago with the publication of Curriculum 68 [1], the 3 major professional societies in computing—ACM and IEEE-Computer Society—have sponsored 4 efforts to establish international curricular guidelines for undergraduate programs in computing 5 on roughly a 10-year cycle. As the field of computing has grown and diversified, so too have the 6 curricular recommendations, and there are now curricular volumes for Computer Engineering, 7 Information Systems, Information Technology, and Software Engineering in addition to 8 Computer Science [3]. These volumes are updated regularly with the aim of keeping computing 9 curricula modern and relevant. The last complete Computer Science curricular volume was 10 released in 2001 (CC2001) [2], and an interim review effort concluded in 2008 (CS2008) [4]. 11 This volume, Computer Science Curricula 2013 (CS2013), represents a comprehensive revision. 12 CS2013 redefines the knowledge units in CS, rethinking the essentials necessary for a Computer 13 Science curriculum. It also seeks to identify exemplars of actual courses and programs to 14 provide concrete guidance on curricular structure and development in a variety of institutional 15 contexts. 16 The development of curricular guidelines for Computer Science is particularly challenging given 17 the rapid evolution and expansion of the field: material dates fast. Moreover, the growing 18 diversity of topics in Computer Science and the increasing integration of computing with other 19 disciplines create additional challenges. Balancing topical growth with the need to keep 20 recommendations realistic and implementable in the context of undergraduate education is 21 particularly difficult. As a result, it is important to engage the broader computer science 22 education community in a dialog to better understand new opportunities, local needs, and to 23 identify successful models of computing curriculum – whether established or novel. One aim of 24 this Strawman report is to provide the basis for such engagement, by providing an early draft of 25 the CS2013 volume that can be scrutinized by members of the computing community with the 26 goal of augmenting and refining the final report. 27 28 Charter 29 The ACM and IEEE-Computer Society chartered the CS2013 effort with the following directive: 30 To review the Joint ACM and IEEE-CS Computer Science volume of 31 Computing Curricula 2001 and the accompanying interim review CS 2008, 32 and develop a revised and enhanced version for the year 2013 that will match 33 the latest developments in the discipline and have lasting impact. 34 The CS2013 task force will seek input from a diverse audience with the goal of 35 broadening participation in computer science. The report will seek to be 36 international in scope and offer curricular and pedagogical guidance 37 applicable to a wide range of institutions. The process of producing the final 38 report will include multiple opportunities for public consultation and scrutiny. 39 Consequently, the CS2013 task force welcomes review of, and comment on, this draft report. 40 High-level Themes 41 In developing CS2013, several high-level themes provided an overarching guide for this volume. 42 These themes, which embody and reflect the CS2013 Principles (described in detail in another 43 section of this volume) are: 44 • The “Big Tent” view of CS. As CS expands to include more cross-disciplinary work and 45 new programs of the form “Computational Biology,” “Computational Engineering,” and 46 “Computational X” are developed, it is important to embrace an outward-looking view 47 that sees CS as a discipline actively seeking to work with and integrate into other 48 disciplines. 49 • Managing the size of the curriculum. Although the field of Computer Science continues 50 to grow unabated, it is not feasible to proportionately expand the size of the curriculum. 51 As a result, CS2013 seeks to re-evaluate the essential topics in computing to make room 52 for new topics without requiring more total instructional hours than the CS2008 53 guidelines. At the same time, the circumscription of curriculum size promotes more 54 flexible models for curricula without losing the essence of a rigorous CS education. 55 • Actual course exemplars. CS2001 took on the significant challenge of providing 56 descriptions of six curriculum models and forty-seven possible course descriptions 57 variously incorporating the knowledge units as defined in that report. While this effort 58 was valiant, in retrospect such course guidance did not seem to have much impact on 59 actual course design. CS2013 plans to take a different approach: to identify and describe 60 existing successful courses and curricula to show how relevant knowledge units are 61 addressed and incorporated in actual programs. - 6 - 62 • Institutional needs. CS2013 aims to be applicable in a broad range of geographic and 63 cultural contexts, understanding that curricula exist within specific institutional needs, 64 goals, and resource constraints. As a result, CS2013 allows for explicit flexibility in 65 curricular structure through a tiered set of core topics, where a small set of Core-Tier 1 66 topics are considered essential for all CS programs, but individual programs choose their 67 coverage of Core-Tier 2 topics. This tiered structure is described in more detail in 68 Chapter 4 of this report. 69 Knowledge Areas 70 The CS2013 Body of Knowledge is organized into a set of 18 Knowledge Areas (KAs), 71 corresponding to topical areas of study in computing. The Knowledge Areas are: 72 • AL - Algorithms and Complexity 73 • AR - Architecture and Organization 74 • CN - Computational Science 75 • DS - Discrete Structures 76 • GV - Graphics and Visual Computing 77 • HC - Human-Computer Interaction 78 • IAS - Information Assurance and Security 79 • IM - Information Management 80 • IS - Intelligent Systems 81 • NC - Networking and Communications 82 • OS - Operating Systems 83 • PBD - Platform-based Development 84 • PD - Parallel and Distributed Computing 85 • PL - Programming Languages 86 • SDF - Software Development Fundamentals 87 • SE - Software Engineering 88 • SF - Systems Fundamentals 89 • SP - Social and Professional Issues 90 - 7 - 91 Many of these Knowledge Areas are derived from CC2001/CS2008 but have been revised—in 92 some cases quite significantly—in CS2013; others are new. There are three major causes of KA 93 change: the reorganization of existing KAs, the development of cross-cutting KAs, and the 94 creation of entirely new KAs. Reorganized KAs are a refactoring of existing topics to better 95 reflect coherent units of knowledge as the field of Computer Science has evolved. For example, 96 Software Development Fundamentals is a significant reorganization of the previous 97 Programming Fundamentals KA. Cross-cutting KAs are a refactoring of existing KAs that 98 extract and integrates cross-cutting foundational topics into their own KA rather than duplicating 99 them across many others. Examples include SF-System Fundamentals and IAS-Information 100 Assurance and Security. Finally, new KAs reflect emerging topics in CS that have become 101 sufficiently prevalent to be included in the volume. PBD-Platform-based Development is an 102 example of such a KA. Chapter 5 contains a more comprehensive overview of these changes. 103 Previous Input 104 To lay the groundwork for CS2013, we conducted a survey of the usage of the CC2001 and 105 CS2008 volumes. The survey was sent to approximately 1500 Computer Science (and related 106 discipline) Department Chairs and Directors of Undergraduate Studies in the United States and 107 an additional 2000 Department Chairs internationally. We received 201 responses, representing a 108 wide range of institutions (self-identified): 109 • research-oriented universities (55%) 110 • teaching-oriented universities (17.5%) 111 • undergraduate-only colleges (22.5%) 112 • community colleges (5%) 113 The institutions also varied considerably in size, with the following distribution: 114 • less than 1,000 students (6.5%) 115 • 1,000 to 5,000 students (30%) 116 • 5,000 to 10,000 students (19%) 117 • more than 10,000 students (44.5%) - 8 - 118 In examining the usage of the CC2001/CS2008 reports, survey respondents reported that the 119 Body of Knowledge (i.e., the outline of topics that should appear in undergraduate Computer 120 Science curricula) was the most used aspect. When questioned about new topical areas that 121 should be added to the Body of Knowledge, survey respondents indicated a strong need to add 122 the topics of Security as well as Parallel and Distributed Computing. Indeed, feedback during 123 the CS2008 review had also indicated the importance of these two areas, but the CS2008 steering 124 committee had felt that creating new KAs was beyond their purview and deferred the 125 development of those areas to the next full curricular report. CS2013 includes these two new 126 KAs (among others): Information Assurance and Security, and Parallel and Distributed 127 Computing. 128 Coming Attractions in CS2013 129 The final version of the CS2013 volume is, naturally enough, scheduled for release in 2013. 130 Hence, this Strawman draft is—by design—incomplete. Not only will the final report include 131 revisions of the Body of Knowledge presented here, based on community feedback, it will also 132 include several sections which do not yet exist. Here we provide a timeline for CS2013 efforts 133 and outline some of the “coming attractions” (i.e., additional sections) that are planned for 134 inclusion in future drafts. 135 - 9 - 136 Timeline 137 The 2013 curricular guidelines will comprise several sorts of materials: the Body of Knowledge, 138 Exemplars of Curricula and Courses, Professional Practice, and Institutional Challenges. These 139 are being developed in offset phases, starting with the Body of Knowledge. 140 A summary of the CS2013 timeline is as follows: Fall 2010: CS2013 chartered and effort begins February 2011: CS2013 Principles outlined and Body of Knowledge revision begins CS2013 Strawman report released February 2012: Includes: Body of Knowledge, Characteristics of Graduates July 15, 2012: Comment period for Strawman draft closes CS2013 Ironman report planned for release February 2013: Includes: Body of Knowledge, Characteristics of Graduates, Curricula and Course Exemplars, Professional Practice, Institutional Challenges June 2013: Comment period for Ironman draft closes Summer 2013: CS2013 Final report planned for release 141 142 Exemplars of Curricula and Courses 143 Perhaps the most significant section of the CS2013 final report that is not included in the 144 Strawman draft is the presentation of actual curricula and courses that embody the topics in the 145 CS2013 Body of Knowledge. The CS2013 Ironman draft will include examples used in 146 practice—from a variety of universities and colleges—to illustrate how topics in the Knowledge 147 Areas may be covered and combined in diverse ways. 148 Importantly, we believe that the identification of such exemplary courses and curricula provides 149 a tremendous opportunity for further community involvement in the development of the CS2013 150 volume. We invite members of the computing community to contribute courses and curricula - 10 - 151 from their own institutions (or other institutions that they may be familiar with). Those 152 interested in potentially mapping courses/curricula to the CS2013 Body of Knowledge are 153 encouraged to contact members of the CS2013 steering committee for more details. 154 Professional Practice 155 The education that undergraduates in Computer Science receive must adequately prepare them 156 for the workforce in a more holistic way than simply conveying technical facts. Indeed, “soft 157 skills” (such as teamwork and communication) and personal attributes (such as identification of 158 opportunity and risk) play a critical role in the workplace. Successfully applying technical 159 knowledge in practice often requires an ability to tolerate ambiguity and work well with others 160 from different backgrounds and disciplines. These overarching considerations are important for 161 promoting successful professional practice in a variety of career paths. We will include 162 suggestions for, and examples of, ways in which curricula encourage the development of such 163 skills, including professional competencies and entrepreneurship, as part of an undergraduate 164 Computer Science program in the CS2013 Ironman draft. 165 Institutional Challenges 166 CS departments and programs often face institutional challenges in implementing a curriculum: 167 they may have too few faculty to cover all the knowledge areas, insufficient number of students 168 for a full program, and/or inadequate institutional resource for professional development. This 169 section will identify such challenges and provide suggestions for their amelioration. 170 - 11 - 171 Opportunities for Involvement 172 We believe it is essential for endeavours of this kind to engage the broad computing community 173 to review and critique successive drafts. To this end, the development of this Strawman report 174 has already benefited from the input of more than 100 contributors beyond the steering 175 committee. We welcome further community engagement on this effort in multiple ways, 176 including (but not limited to): 177 • Comments on the Strawman draft, especially with respect to the Body of Knowledge. 178 • Contribution of exemplar courses/curricula that are mapped against the Body of 179 Knowledge. 180 • Descriptions of pedagogic approaches and instructional designs (both time-tested and 181 novel) that address professional practice within undergraduate curricula. 182 • Sharing of institutional challenges, and solutions to them. 183 Comments on all aspects of this report are welcome and encouraged via the CS2013 website: 184 http://cs2013.org 185 186 References 187 [1] ACM Curriculum Committee on Computer Science. 1968. Curriculum 68: 188 Recommendations for Academic Programs in Computer Science. Comm. ACM 11, 3 (Mar. 189 1968), 151-197. 190 [2] ACM/IEEE-CS Joint Task Force on Computing Curricula. 2001. ACM/IEEE Computing 191 Curricula 2001 Final Report. http://www.acm.org/sigcse/cc2001. 192 [3] ACM/IEEE-CS Joint Task Force for Computer Curricula 2005. Computing Curricula 193 2005: An Overview Report. http://www.acm.org/education/curric_vols/CC2005- 194 March06Final.pdf 195 [4] ACM/IEEE-CS Joint Interim Review Task Force. 2008. Computer Science Curriculum 196 2008: An Interim Revision of CS 2001, Report from the Interim Review Task Force. 197 http://www.acm.org/education/curricula/ComputerScience2008.pdf 198 - 12 - 199 Acknowledgments 200 The CS2013 Strawman report has benefited from the input of many individuals, including: Alex 201 Aiken (Stanford University), Ross Anderson (Cambridge University), Florence Appel (Saint 202 Xavier University), Helen Armstrong (Curtin university), Colin Armstrong (Curtin university), 203 Krste Asanovic (UC Berkeley), Radu F. Babiceanu (University of Arkansas at Little Rock), 204 Mike Barker (Massachusetts Institute of Technology), Michael Barker (Nara Institute of Science 205 and Technology), Paul Beame (University of Washington), Robert Beck (VIllanova University), 206 Matt Bishop (University of California, Davis), Alan Blackwell (Cambridge University), Don 207 Blaheta (Longwood University), Olivier Bonaventure (Universite Catholique de Louvain), Roger 208 Boyle (University of Leeds), Clay Breshears (Intel), Bo Brinkman (Miami University), David 209 Broman (Linkoping University), Kim Bruce (Pomona College), Jonathan Buss (University of 210 Waterloo), Netiva Caftori (Northeastern Illinois University, Chicago), Paul Cairns (University of 211 York), Alison Clear (Christchurch Polytechnic Institute of Technology), Curt Clifton (Rose- 212 Hulman and The Omni Group), Yvonne Cody (University of Victoria), Tony Cowling 213 (University of Shefffield), Joyce Currie-Little (Towson University), Ron Cytron (Washington 214 University in St. Louis), Melissa Dark (Purdue University), Janet Davis (Grinnell College), 215 Marie DesJardins (University of Maryland, Baltimore County), Zachary Dodds (Harvey Mudd 216 College), Paul Dourish (University of California, Irvine), Lynette Drevin (North-West 217 Universit), Scot Drysdale (Dartmouth College), Kathi Fisler (Worcester Polytechnic Institute), 218 Susan Fox (Macalester College), Edward Fox (Virginia Tech), Eric Freudenthal (University of 219 Texas El Paso), Stephen Freund (Williams College), Lynn Futcher (Nelson Mandela 220 Metropolitan University), Greg Gagne (Wesminister College), Dan Garcia (UC Berkeley), Judy 221 Gersting (Indiana University-Purdue University Indianapolis), Yolanda Gil (University of 222 Southern California), Michael Gleicher (University Wisconsin, Madison), Frances Grodzinsky 223 (Sacred Heart University), Anshul Gupta (IBM), Mark Guzdial (Georgia Tech), Brian Hay 224 (University of Alaska, Fairbanks), Brian Henderson-Sellers (University of Technology, Sydney), 225 Matthew Hertz (Canisius College), Tom Hilburn (Embry-Riddle Aeronautical University), Tony 226 Hosking (Purdue University), Johan Jeuring (Utrecht University), Yiming Ji (University of South 227 Carolina Beaufort), Maggie Johnson (Google), Matt Jones (Swansea University), Frans 228 Kaashoek (MIT), Lisa Kaczmarczyk (ACM Education Council), Jennifer Kay (Rowan - 13 - 229 University), Scott Klemmer (Stanford University), Jim Kurose (University of Massachusetts, 230 Amherst), Doug Lea (SUNY Oswego), Terry Linkletter (Central Washington University), David 231 Lubke (NVIDIA), Bill Manaris (College of Charleston), Samuel Mann (Otago Polytechnic ), C. 232 Diane Martin (George Washington University ), Andrew McGettrick (University of Strathclyde), 233 Morgan Mcguire (Williams College), Keith Miller (University of Illinois at Springfield), 234 Narayan Murthy (Pace University), Kara Nance (University of Alaska, Fairbanks), Todd Neller 235 (Gettysburg College), Reece Newman (Sinclair Community College), Christine Nickell 236 (Information Assurance Center for Computer Network Operations, CyberSecurity, and 237 Information Assurance), James Noble (Victoria University of Wellington), Peter Norvig 238 (Google), Joseph O'Rourke (Smith College), Jens Palsberg (UCLA), Robert Panoff (Shodor.org), 239 Sushil Prasad (Georgia State University), Michael Quinn (Seattle University), Matt Ratto 240 (University of Toronto), Penny Rheingans (U. Maryland Baltimore County), Carols Rieder 241 (Lucerne University of Applied Sciences), Eric Roberts (Stanford University), Arny Rosenberg 242 (Northeastern and Colorado State University), Ingrid Russell (University of Hartford), Dino 243 Schweitzer (United States Air Force Academy), Michael Scott (University of Rochester), Robert 244 Sedgewick (Princeton University), Helen Sharp (Open Univeristy), Robert Sloan (University of 245 Illinois, Chicago), Ann Sobel (Miami University), Carol Spradling (Northwest Missouri State 246 University), Michelle Strout (Colorado State University), Alan Sussman (University of 247 Maryland, College Park), Blair Taylor (Towson University), Simon Thompson (University of 248 Kent), Johan Vanniekerk (Nelson Mandela Metropolitan University), Christoph von Praun 249 (Georg-Simon-Ohm Hochschule Nürnberg), Rossouw Von Solms (Nelson Mandela 250 Metropolitan University), John Wawrzynek (UC Berkeley), Charles Weems (Univ. of 251 Massachusettes, Amherst), David Wetherall (University of Washington), Michael Wrinn (Intel) 252 Additionally, review of various portions of the Strawman report took part in several venues, 253 including: the 42nd ACM Technical Symposium of the Special Interest Group on Computer 254 Science Education (SIGCSE-11), the 24th IEEE-CS Conference on Software Engineering 255 Education and Training (CSEET-11), the 2011 IEEE Frontiers in Education Conference (FIE- 256 11), the 2011 Federated Computing Research Conference (FCRC-11), the 2nd Symposium on 257 Educational Advances in Artificial Intelligence (EAAI-11), the Conference of ACM Special 258 Interest Group on Data Communication 2011 (SIGCOMM-11), the 2011 IEEE International 259 Joint Conference on Computer, Information, and Systems Sciences and Engineering (CISSE-11), - 14 - 260 the 2011 Systems, Programming, Languages and Applications: Software for Humanity 261 Conference (SPLASH-11), the 15th Colloquium for Information Systems Security Education, the 262 2011 National Centers of Academic Excellence in IA Education (CAE/IAE) Principles meeting, 263 and the 7th IFIP TC 11.8 World Conference on Information Security Education (WISE). 264 Several more conference special sessions to review and comment on drafts of CS2013 are 265 planned for the coming year, including 43rd ACM Technical Symposium of the Special Interest 266 Group on Computer Science Education (SIGCSE-12), the Special Session of the Special Interest 267 Group on Computers and Society at SIGCSE-12, Computer Research Association Snowbird 268 Conference 2012, and the 2012 IEEE Frontiers in Education Conference (FIE-12), among others. 269 A number of organizations also provided valuable feedback to the CS2013 Strawman effort, 270 including: the ACM Education Board and Council, the IEEE-CS Educational Activities Board, 271 the ACM SIGPLAN Education Board, the ACM Special Interest Group Computers and Society, 272 and the NSF/IEEE-TCPP Curriculum Initiative on Parallel and Distributed Computing 273 Committee - 15 - 1 Chapter 2: Principles 2 Early in its work, the 2013 Steering Committee agreed upon a set of principles to guide the 3 development of this volume. The principles adopted for CS2013 overlap significantly with the 4 principles adopted for previous curricular efforts, most notably CC2001 and CS2008. As with 5 previous ACM/IEEE curricula volumes, there are a variety of constituencies for CS2013, 6 including individual faculty members and instructors at a wide range of colleges, universities, 7 and technical schools on any of six continents; CS programs and the departments, colleges, and 8 institutions where they are housed; accreditation and certification boards; authors; and 9 researchers. Other constituencies include pre-college preparatory schools and advanced 10 placement curricula as well as graduate programs in computer science. 11 The principles were developed in consideration of these constituencies, as well as issues related 12 to student outcomes, development of curricula, and the review process. The order of presentation 13 is not intended to imply relative importance. 14 1. Computer Science curricula should be designed to provide students with the flexibility to 15 work across many disciplines. Computing is a broad field that connects to and draws from 16 many disciplines, including mathematics, electrical and systems engineering, psychology, 17 statistics, fine arts, linguistics, and physical and life sciences. Computer Science students 18 should develop the flexibility to work across disciplines. 19 2. Computer Science curricula should be designed to prepare graduates for a variety of 20 professions, attracting the full range of talent to the field. Computer Science impacts nearly 21 every modern endeavour. CS2013 takes a broad view of the field that includes topics such as 22 “computational-x” (e.g., computational finance or computational chemistry) and “x- 23 informatics” (e.g., eco-informatics or bio-informatics). Well-rounded CS graduates will have 24 a balance of theory and application, as described in Chapter 3: Characteristics of Graduates. 25 3. CS2013 should provide guidance for the expected level of mastery of topics by graduates. It 26 should suggest outcomes indicating the intended level of mastery and provide exemplars of 27 fielded curricula covering topics in the Body of Knowledge. 28 4. CS 2013 must provide realistic, adoptable recommendations that provide guidance and 29 flexibility, allowing curricular designs that are innovative and track recent developments in 30 the field. The guidelines are intended to provide clear, implementable goals, while also 31 providing the flexibility that programs need in order to respond to a rapidly changing field. 32 CS2013 is intended as guidance, not as a minimal standard against which to evaluate a 33 program. 34 5. The CS2013 guidelines must be relevant to a variety of institutions. Given the wide range of 35 institutions and programs (including 2-year, 3-year, and 4-year programs; liberal arts, 36 technological, and research institutions; and institutions of every size), it is neither possible 37 nor desirable for these guidelines to dictate curricula for computing. Individual programs will 38 need to evaluate their constraints and environments to construct curricula. 39 6. The size of the essential knowledge must be managed. While the range of relevant topics has 40 expanded, the size of undergraduate curricula has not. Thus, CS2013 must carefully choose 41 among topics and recommend the essential elements. 42 7. Computer Science curricula should be designed to prepare graduates to succeed in a rapidly 43 changing field. Computer Science is rapidly changing and will continue to change for the 44 foreseeable future. Curricula must prepare students for lifelong learning and must include 45 professional practice (e.g. communication skills, teamwork, ethics) as components of the 46 undergraduate experience. Computer science students must learn to integrate theory and 47 practice, to recognize the importance of abstraction, and to appreciate the value of good 48 engineering design. 49 8. CS2013 should identify the fundamental skills and knowledge that all computer science 50 graduates should possess while providing the greatest flexibility in selecting topics. To this 51 end, we have introduced three levels of knowledge description: Tier-1 Core, Tier-2 Core, and 52 Elective. For a full discussion of Tier-1 Core, Tier-2 Core, and Elective, see Chapter 4: 53 Completing the Curriculum. 54 9. CS2013 should provide the greatest flexibility in organizing topics into courses and 55 curricula. Knowledge areas are not intended to describe specific courses. There are many - 17 - 56 novel, interesting, and effective ways to combine topics from the Body of Knowledge into 57 courses. 58 10. The development and review of CS2013 must be broadly based. The CS2013 Task Force 59 must include participation from many different constituencies including industry, 60 government, and the full range of higher education institutions involved in computer science 61 education. It must take into account relevant feedback from these constituencies. - 18 - 1 Chapter 3: Characteristics of Graduates 2 Graduates of Computer Science programs should have fundamental competency in the areas 3 described by the Body of Knowledge (see Chapter 5), particularly the core topics contained 4 there. However, there are also competences that graduates of CS programs should have that are 5 not explicitly listed in the Body of Knowledge. Professionals in the field typically embody a 6 characteristic style of thinking and problem solving, a style that emerges from the experiences 7 obtained through study of the field and professional practice. Below, we describe the 8 characteristics that we believe should be met at least at an elementary level by graduates of 9 computer science programs. These characteristics will enable their success in the field and 10 further professional development. Some of these characteristics and skills also apply to other 11 fields. They are included here because the development of these skills and characteristics must 12 be explicitly addressed and encouraged by Computer Science programs. 13 This list is based on a similar list in CC2001 and CS2008. The substantial changes that led to 14 this new version were influenced by responses to a survey conducted by the CS2013 Steering 15 Committee. 16 17 At a broad level, the expected characteristics of computer science graduates include the 18 following: 19 Technical understanding of Computer Science 20 Graduates should have a mastery of computer science as described by the core of the Body of Knowledge. 21 Familiarity with common themes and principles 22 Graduates need understanding of a number of recurring themes, such as abstraction, complexity, and 23 evolutionary change, and a set of general principles, such as sharing a common resource, security, and 24 concurrency. Graduates should recognize that these themes and principles have broad application to the 25 field of computer science and should not consider them as relevant only to the domains in which they 26 were introduced. 27 28 Appreciation of the interplay between theory and practice 29 A fundamental aspect of computer science is understanding the interplay between theory and practice and 30 the essential links between them. Graduates of a computer science program need to understand how 31 theory and practice influence each other. 32 System-level perspective 33 Graduates of a computer science program need to think at multiple levels of detail and abstraction. This 34 understanding should transcend the implementation details of the various components to encompass an 35 appreciation for the structure of computer systems and the processes involved in their construction and 36 analysis. They need to recognize the context in which a computer system may function, including its 37 interactions with people and the physical world. 38 Problem solving skills 39 Graduates need to understand how to apply the knowledge they have gained to solve real problems, not 40 just write code and move bits. They should also realize that there are multiple solutions to a given 41 problem and that selecting among them is not a purely technical activity, as these solutions will have a 42 real impact on people’s lives. Graduates also should be able to communicate their solution to others, 43 including why and how a solution solves the problem and what assumptions were made. 44 Project experience 45 To ensure that graduates can successfully apply the knowledge they have gained, all graduates of 46 computer science programs should have been involved in at least one substantial project. In most cases, 47 this experience will be a software development project, but other experiences are also appropriate in 48 particular circumstances. Such projects should challenge students by being integrative, requiring 49 evaluation of potential solutions, and requiring work on a larger scale than typical course projects. 50 Students should have opportunities to develop their interpersonal communication skills as part of their 51 project experience. 52 Commitment to life-long learning 53 Graduates of a computer science program should realize that the computing field advances at a rapid 54 pace. Specific languages and technology platforms change over time. Therefore, graduates need to realize 55 that they must continue to learn and adapt their skills throughout their careers. To develop this ability, 56 students should be exposed to multiple programming languages, tools, and technologies as well as the 57 fundamental underlying principles throughout their education. 58 - 20 - 59 Commitment to professional responsibility 60 Graduates should recognize the social, legal, ethical and cultural issues involved in the deployment and 61 use of computer technology. They should respond to these issues from an informed perspective, guided 62 by personal and professional principles. They must further recognize that social, legal, and ethical 63 standards vary internationally. 64 Communication and organizational skills 65 Graduates should have the ability to make succinct presentations to a range of audiences about technical 66 problems and their solutions. This may involve face-to-face, written, or electronic communication. They 67 should be prepared to work effectively as members of teams. Graduates should be able to manage their 68 own learning and development, including managing time, priorities, and progress. 69 Awareness of the broad applicability of computing 70 Platforms range from embedded micro-sensors to high-performance clusters and distributed clouds. 71 Computer applications impact nearly every aspect of modern life. Graduates should understand the full 72 range of opportunities available in computing. 73 Appreciation of domain-specific knowledge 74 Graduates should understand that computing interacts with many different domains. Solutions to many 75 problems require both computing skills and domain knowledge. Therefore, graduates need to be able to 76 communicate with, and learn from, experts from different domains throughout their careers. - 21 - 1 Chapter 4: Constructing a Complete 2 Curriculum 3 This chapter provides high-level guidelines on how to use the Body of Knowledge to create an 4 institution’s undergraduate curriculum in computer science. It does not propose a particular set 5 of courses or curriculum structure -- that is the role of the (forthcoming) course/curriculum 6 exemplars. Rather, this chapter emphasizes the flexibility that the Body of Knowledge allows in 7 adapting curricula to institutional needs and the continual evolution of the field. In computer- 8 science terms, one can view the Body of Knowledge as a specification of content to cover and a 9 curriculum as an implementation. A large variety of curricula can meet the specification. 10 The following points are elaborated: 11 • Knowledge Areas are not intended to be in one-to-one correspondence with particular 12 courses in a curriculum: We expect curricula will have courses incorporating topics from 13 multiple Knowledge Areas. 14 • Topics are identified as either “core” or “elective” with the core further subdivided into 15 “tier-1” and “tier-2.” 16 o A curriculum should include all topics in the tier-1 core and ensure that all 17 students cover this material. 18 o A curriculum should include all or almost all topics in the tier-2 core and ensure 19 that all students cover the vast majority of this material. 20 o A curriculum should include significant elective material: Covering only “core” 21 topics is insufficient for a complete curriculum. 22 • Because it is a hierarchical outline, the Body of Knowledge under-emphasizes some key 23 issues that must be considered when constructing a curriculum. 24 25 Knowledge Areas are Not Necessarily Courses (and Important 26 Examples Thereof) 27 It is naturally tempting to associate each Knowledge Area with a course. We explicitly 28 discourage this practice in general, even though many curricula will have some courses 29 containing material from only one Knowledge Area or, conversely, all the material from one 30 Knowledge Area in one course. We view the hierarchical structure of the Body of Knowledge as 31 a useful way to group related information, not as a stricture for organizing material into courses. 32 Beyond this general flexibility, in several places we expect many curricula to integrate material 33 from multiple Knowledge Areas, in particular: 34 • Introductory courses: There are diverse successful approaches to introductory courses in 35 computer science. Many focus on the topics in Software Development Fundamentals 36 together with a subset of the topics in Programming Languages or Software Engineering, 37 while leaving most of the topics in these other Knowledge Areas to advanced courses. 38 But which topics from other Knowledge Areas are covered in introductory courses can 39 vary. Some courses use object-oriented programming, others functional programming, 40 others platform-based development (thereby covering topics in the Platform-Based 41 Development Knowledge Area), etc. Conversely, there is no requirement that all 42 Software Development Fundamentals be covered in a first or second course, though in 43 practice most topics will usually be covered in these early courses. 44 • Systems courses: The topics in the Systems Fundamentals Knowledge Area can be 45 covered in courses designed to cover general systems principles or in courses devoted to 46 particular systems areas such as computer architecture, operating systems, networking, or 47 distributed systems. For example, an Operating Systems course might spend 48 considerable time on topics of more general use, such as low-level programming, 49 concurrency and synchronization, performance measurement, or computer security. Such 50 courses may draw on material in several Knowledge Areas. Certain fundamental systems 51 topics like latency or parallelism will likely arise in many places in a curriculum. While 52 it is important that such topics do arise, preferably in multiple settings, the Body of 53 Knowledge does not specify the particular settings in which to teach such topics. - 23 - 54 • Parallel computing: Among the many changes to the Body of Knowledge compared to 55 previous reports is a new Knowledge Area in Parallel and Distributed Computing. An 56 alternative structure for the Body of Knowledge would place relevant topics in other 57 Knowledge Areas: parallel algorithms with algorithms, programming constructs in 58 software-development focused areas, multi-core design with computer architecture, and 59 so forth. We chose instead to provide guidance on the essential parallelism topics in one 60 place. Some, but not all, curricula will likely have courses dedicated to parallelism, at 61 least in the near term. 62 Tier-1 Core, Tier-2 Core, Elective: What These Terms Mean, What is 63 Required 64 As described at the beginning of this chapter, computer science curricula should cover all of the 65 core tier-1 topics, all or almost all of the core tier-2 topics, and significant depth in many of the 66 elective topics (i.e., the core is not sufficient for an undergraduate degree in computer science). 67 Here we provide additional perspective on what “tier-1 core,” “tier-2 core”, and “elective” mean, 68 including motivation for these distinctions. 69 Motivation for subdividing the core: Earlier versions of the ACM/IEEE Computer Science 70 Curricula had only “core” and “elective” with every topic in the former being required. We 71 departed from this strict interpretation of “everything in the core must be taught to every student” 72 for these reasons: 73 • It did not sufficiently reflect reality: Many strong computer science curricula were 74 missing at least one hour of core material. It is misleading to suggest that such curricula 75 are outside the definition of an undergraduate degree in computer science. 76 • As the field has grown, there is ever-increasing pressure to grow the core and allow 77 students to specialize in areas of interest. Doing so simply becomes impossible within 78 the short time-frame of an undergraduate degree. Providing some flexibility on coverage 79 of core topics enables curricula and students to specialize if they choose to do so. 80 Conversely, we could have allowed for any core topic to be skipped provided that the vast 81 majority was part of every student’s education. By retaining a smaller tier-1 core of required - 24 - 82 material, we provide additional guidance and structure for curriculum designers. In the tier-1 83 core are the topics that are fundamental to the structure of any computer-science program. 84 On the meaning of tier-1: A tier-1 topic should be a required part of every computer-science 85 curriculum for every student. This is not to say that tier-2 or even elective topics should not be, 86 but the tier-1 topics are those with widespread consensus for inclusion. Moreover, at least 87 preliminary treatment of most of these topics typically comes in the first two years of a 88 curriculum, precisely because so much of the field relies on these topics. However, introductory 89 courses need not cover all tier-1 material and will usually draw on tier-2 and elective material as 90 well. 91 On the meaning of tier-2: Tier-2 topics are generally essential in an undergraduate computer- 92 science degree. Requiring the vast majority of them is a minimum expectation, and we 93 encourage institutions to cover all of them for every student. That said, computer science 94 programs can allow students to focus in certain areas in which some tier-2 topics are not 95 required. We also acknowledge that resource constraints, such as a small number of faculty or 96 institutional limits on degree requirements, may make it prohibitively difficult to cover every 97 topic in the core while still providing advanced elective material. A computer-science 98 curriculum should aim to cover 90-100% of the tier-2 topics for every student, with 80% 99 considered as a minimum. 100 There is no expectation that tier-1 topics necessarily precede tier-2 topics in a curriculum. In 101 particular, we expect introductory courses will draw on both tier-1 and tier-2 (and possibly 102 elective) material and that some core material will be delayed until later courses. 103 On the meaning of elective: A program covering only core material would provide 104 insufficient breadth and depth in computer science, but most programs will not cover all the 105 elective material in the Body of Knowledge and certainly few, if any, students will cover all of it 106 within an undergraduate program. Conversely, the Body of Knowledge is by no means 107 exhaustive, and advanced courses may often go beyond the topics and learning outcomes 108 contained in it. Nonetheless, the Body of Knowledge provides a useful guide on material 109 appropriate for a computer-science undergraduate degree, and all students of computer science 110 should deepen their understanding in multiple areas via the elective topics. - 25 - 111 A curriculum may well require material designated elective in the Body of Knowledge. Many 112 curricula, especially those with a particular focus, will require some elective topics, by virtue of 113 them being covered in required courses. 114 The size of the core: The size of the core (tier-1 plus tier-2) is a few hours larger than in 115 previous versions of the computer-science curriculum, but this is counterbalanced by our more 116 flexible treatment of the core. As a result, we are not increasing the number of required courses 117 a curriculum should need. Indeed, a curriculum covering 90% of the tier-2 hours would have the 118 same number of core hours as a curriculum covering the core in the CS2008 volume, and a 119 curriculum covering 80% of the tier-2 hours would have fewer core hours than even a curriculum 120 covering the core in the CC2001 volume (the core grew from 2001 to 2008). 121 A note on balance: Computer science is an elegant interplay of theory, software, hardware, 122 and applications. The core in general and the tier-1 core in particular, when viewed in isolation, 123 may seem to focus on programming, discrete structures, and algorithms. This focus results from 124 the fact that these topics typically come early in a curriculum so that advanced courses can use 125 them as pre-requisites. Essential experience with systems and applications can be achieved in 126 more disparate ways using elective material in the Body of Knowledge. Because all curricula 127 will include appropriate elective material, an overall curriculum can and should achieve an 128 appropriate balance. 129 Further Considerations 130 As useful as the Body of Knowledge is, it is important to complement it with a thoughtful 131 understanding of cross-cutting themes in a curriculum, the “big ideas” of computer science. In 132 designing a curriculum, it is also valuable to identify curriculum-wide objectives, for which the 133 Principles and the Characteristics of Graduates chapters of this volume should prove useful. 134 In the last few years, two on-going trends have had deep effects on many curricula. First, the 135 continuing growth of computer science has led to many programs organizing their curricula to 136 allow for intradisciplinary specialization (using terms such as threads, tracks, vectors, etc.). 137 Second, the importance of computing to almost every other field has increasingly led to the 138 creation of interdisciplinary programs (joint majors, double majors, etc.) and incorporating 139 interdisciplinary material into computer-science programs. We applaud both trends and believe - 26 - 140 a flexible Body of Knowledge, including a flexible core, support them. Conversely, such 141 specialization is not required: Many programs will continue to offer a broad yet thorough 142 coverage of computer science as a distinct and coherent discipline. - 27 - 1 Chapter 5: Introduction to the Body of 2 Knowledge 3 Process for Updating the Body of Knowledge 4 The CS2013 Steering Committee constituted a subcommittee for each KA, chaired by a member 5 of the Steering Committee, and initially including at least two other members of the Steering 6 Committee. Individual subcommittee Chairs then invited expert members (outside the CS2013 7 Steering Committee) to join the work of defining and reviewing each KA; drafts of KAs were 8 also presented in various conference panel and special session presentations. The KA 9 subcommittee Chairs (as members of the CS2013 Steering Committee) worked to resolve 10 conflicts, eliminate redundancies and appropriately categorize and cross-reference topics 11 between the various KAs. This year-long process ultimately converged to the draft version of the 12 Body of Knowledge presented here. 13 As noted in the introduction to this report, we are soliciting continued community feedback 14 which will be considered and incorporated into future drafts of the CS2013 report. 15 The CS2013 Body of Knowledge is presented as a set of Knowledge Areas (KAs), organized on 16 topical themes rather than by course boundaries. Each KA is further organized into a set of 17 Knowledge Units (KUs), which are summarized in a table at the head of each KA section. We 18 expect that the topics within the KAs will be organized into courses in different ways at different 19 institutions. 20 Here, we provide background for understanding how to read the Body of Knowledge, and we 21 give an overview of the number of core hours in each KA. We also highlight the KAs that have 22 significant cross-topic components and those that are new to this volume. Chapter 4 presents 23 essential background on how the Body of Knowledge translates into actual curricula. 24 25 Overview of New Knowledge Areas 26 While computer science encompasses technologies that change rapidly over time, it is defined by 27 essential concepts, perspectives, and methodologies that are constant. As a result, much of the 28 core Body of Knowledge remains unchanged from earlier curricular volumes. However, new 29 developments in computing technology and pedagogy mean that some aspects of the core evolve 30 over time, and some of the previous structures and organization may no longer be appropriate for 31 describing the discipline. As a result, CS2013 has modified the organization of the curriculum in 32 various ways, adding some new KAs and restructuring others. We highlight these changes in the 33 remainder of this section. 34 IAS-Information Assurance and Security 35 IAS is a new KA in recognition of the world’s reliance on information technology and its critical 36 role in computer science education. IAS as a domain is the set of controls and processes, both 37 technical and policy, intended to protect and defend information and information systems. IAS 38 draws together topics that are pervasive throughout other KAs. Topics germane to only IAS are 39 presented in depth in this KA, whereas other topics are noted and cross referenced to the KAs 40 that contain them. As such, this KA is prefaced with a detailed table of cross-references to other 41 KAs. 42 NC-Networking and Communication 43 CC2001 introduced a KA entitled “Net-Centric Computing” which encompassed a combination 44 of topics including traditional networking, web development, and network security. Given the 45 growth and divergence in these topics since the last report, we renamed and refactored this KA 46 to focus specifically on topics in networking and communication. Discussions of web 47 applications and mobile device development are now covered in the new PBD-Platform-Based 48 Development KA. Security is covered in the new IAS-Information Assurance and Security KA. 49 - 29 - 50 PBD-Platform-Based Development 51 PBD is a new KA that recognizes the increasing use of platform-specific programming 52 environments, both at the introductory level and in upper-level electives. Platforms such as the 53 Web or mobile devices enable students to learn within and about environments constrained by 54 hardware, APIs, and special services (often in cross-disciplinary contexts). These environments 55 are sufficiently different from “general purpose” programming to warrant this new (wholly 56 elective) KA. 57 PD-Parallel and Distributed Computing 58 Previous curricular volumes had parallelism topics distributed across disparate KAs as electives. 59 Given the vastly increased importance of parallel and distributed computing, it seemed crucial to 60 identify essential concepts in this area and to promote those topics to the core. To highlight and 61 coordinate this material, CS2013 dedicates a KA to this area. This new KA includes material on 62 programming models, programming pragmatics, algorithms, performance, computer architecture, 63 and distributed systems. 64 SDF-Software Development Fundamentals 65 This new KA generalizes introductory programming to focus on the entire software development 66 process, identifying concepts and skills that should be mastered in the first year of a computer 67 science program. As a result of its broad purpose, the SDF KA includes fundamental concepts 68 and skills that could appear in other software-oriented KAs (e.g., programming constructs from 69 Programming Languages, simple algorithm analysis from Algorithms and Complexity, simple 70 development methodologies from Software Engineering). Likewise, each of those KAs will 71 contain more advanced material that builds upon the fundamental concepts and skills in SDF. 72 Compared to previous volumes, key approaches to programming -- including object-oriented 73 programming, functional programming, and event-driven programming -- are kept in one place, 74 namely the PL KA, even though many curricula will cover some of these topics in introductory 75 courses. 76 - 30 - 77 SF-Systems Fundamentals 78 In previous curricular volumes, the interacting layers of a typical computing system, from 79 hardware building blocks, to architectural organization, to operating system services, to 80 application execution environments (particularly for parallel execution in a modern view of 81 applications), were presented in independent knowledge units. The new Systems Fundamentals 82 KA presents a unified systems perspective and common conceptual foundation for other KAs 83 (notably Architecture and Organization, Network and Communications, Operating Systems, and 84 Parallel and Distributed Algorithms). An organizational principle is “programming for 85 performance”: what a programmer needs to understand about the underlying system to achieve 86 high performance, particularly in terms of exploiting parallelism. 87 88 How to Read the Body of Knowledge 89 Curricular Hours 90 Continuing in the tradition of CC2001/CS2008, we define the unit of coverage in the Body of 91 Knowledge in terms of lecture hours, as being the sole unit that is understandable in (and 92 transferable to) cross-cultural contexts. An “hour” corresponds to the time required to present the 93 material in a traditional lecture-oriented format; the hour count does not include any additional 94 work that is associated with a lecture (e.g., in self-study, lab classes, assessments, etc.). Indeed, 95 we expect students to spend a significant amount of additional time outside of class developing 96 facility with the material presented in class. As with previous reports, we maintain the principle 97 that the use of a lecture-hour as the unit of measurement does not require or endorse the use of 98 traditional lectures for the presentation of material. 99 The specification of topic hours represents the minimum amount of time we expect such 100 coverage to take. Any institution may opt to cover the same material in a longer period of time as 101 warranted by the individual needs of that institution. 102 - 31 - 103 Courses 104 Throughout the Body of Knowledge, when we refer to a “course” we mean an institutionally- 105 recognised unit of study. Depending on local circumstance, full-time students will take several 106 “courses” at any one time, typically eight or more per academic year. While “course” is a 107 common term at some institutions, others will use other names, for example “module” or 108 “paper”. 109 Guidance on Learning Outcomes 110 Each KU within a KA lists both a set of topics and the learning outcomes students are expected 111 to achieve with respect to the topics specified. Each learning outcome has a level of mastery 112 associated with it. There are three levels of mastery, defined as: 113 • Knowledge: The student understands what a concept is or what it means. This level of 114 mastery provides a basic awareness of a concept as opposed to expecting real facility 115 with its application. 116 • Application: The student is able to apply a concept in a concrete way. Applying a 117 concept may include, for example, the ability to implement a programming concept, use a 118 particular proof technique, or perform a particular analysis. 119 • Evaluation: The student is able to consider a concept from multiple view points and/or 120 justify the selection of a particular approach to solve a problem. This level of mastery 121 implies more than the application of a concept; it involves the ability to select an 122 appropriate approach from understood alternatives. 123 As a concrete, although admittedly simplistic, example of these levels of mastery, we consider 124 the notion of iteration in software development, for example for-loops, while-loops, iterators. At 125 the level of “Knowledge,” a student would be expected to know what the concept of iteration is 126 in software development and why it is a useful technique. In order to show mastery at the 127 “Application” level, a student should be able to write a program using a form of iteration. 128 Understanding iteration at the “Evaluation” level would require a student to understand multiple 129 methods for iteration and be able to appropriately select among them for different applications. 130 - 32 - 131 Core Hours in Knowledge Areas 132 An overview of the number of core hours (both Tier1 and Tier2) by KA in the CS2013 Body of 133 Knowledge is provided below (for a discussion of Tier1 and Tier2, see Chapter 4). For 134 comparison, the number of core hours from both the previous CS2008 and CC2001 reports are 135 provided as well. CS2013 CS2008 CC2001 Knowledge Area Tier1 Tier2 Core Core AL-Algorithms and Complexity 19 9 31 31 AR-Architecture and Organization 0 16 36 36 CN-Computational Science 1 0 0 0 DS-Discrete Structures 37 4 43 43 GV-Graphics and Visual Computing 2 1 3 3 HC-Human-Computer Interaction 4 4 8 8 IAS-Security and Information Assurance 2 6 -- -- IM-Information Management 1 9 11 10 IS-Intelligent Systems 0 10 10 10 NC-Networking and Communication 3 7 15 15 OS-Operating Systems 4 11 18 18 PBD-Platform-based Development 0 0 -- -- PD-Parallel and Distributed Computing 5 10 -- -- PL-Programming Languages 8 20 21 21 SDF-Software Development Fundamentals 42 0 47 38 SE-Software Engineering 6 21 31 31 SF-Systems Fundamentals 18 9 -- -- SP-Social and Professional Issues 11 5 16 16 Total Core Hours 163 142 290 280 All Tier1 + All Tier2 Total 305 All Tier1 + 90% of Tier2 Total 290.8 All Tier1 + 80% of Tier2 Total 276.6 136 137 As seen above, in CS2013 the total Tier1 hours together with the entirety of Tier2 hours slightly 138 exceeds the total core hours from previous reports. However, it is important to note that the 139 tiered structure of the core in CS2013 explicitly provides the flexibility for institutions to select - 33 - 140 topics from Tier2 (to include at least 80%). As a result, it is possible to implement the CS2013 141 guidelines with slightly fewer hours than previous curricular guidelines. - 34 - 1 Appendix A: The Body of Knowledge 2 Algorithms and Complexity (AL) 3 Algorithms are fundamental to computer science and software engineering. The real-world 4 performance of any software system depends on: (1) the algorithms chosen and (2) the suitability 5 and efficiency of the various layers of implementation. Good algorithm design is therefore 6 crucial for the performance of all software systems. Moreover, the study of algorithms provides 7 insight into the intrinsic nature of the problem as well as possible solution techniques 8 independent of programming language, programming paradigm, computer hardware, or any 9 other implementation aspect. 10 An important part of computing is the ability to select algorithms appropriate to particular 11 purposes and to apply them, recognizing the possibility that no suitable algorithm may exist. This 12 facility relies on understanding the range of algorithms that address an important set of well- 13 defined problems, recognizing their strengths and weaknesses, and their suitability in particular 14 contexts. Efficiency is a pervasive theme throughout this area. 15 This knowledge area defines the central concepts and skills required to design, implement, and 16 analyze algorithms for solving problems. Algorithms are essential in all advanced areas of 17 computer science: artificial intelligence, databases, distributed computing, graphics, networking, 18 operating systems, programming languages, security, and so on. Algorithms that have specific 19 utility in each of these are listed in the relevant knowledge areas. Cryptography, for example, 20 appears in the new knowledge area on Information Assurance and Security, while parallel and 21 distributed algorithms appear in PD-Parallel and Distributed Computing. 22 As with all knowledge areas, the order of topics and their groupings do not necessarily correlate 23 to a specific order of presentation. Different programs will teach the topics in different courses 24 and should do so in the order they believe is most appropriate for their students. 25 26 AL. Algorithms and Complexity (19 Core-Tier1 hours, 9 Core-Tier2 hours) Core-Tier1 Core-Tier2 Includes hours hours Electives AL/Basic Analysis 2 2 N AL/Algorithmic Strategies 5 1 N AL/Fundamental Data Structures and 9 3 N Algorithms AL/Basic Automata, Computability and 3 3 N Complexity AL/Advanced Computational Complexity Y AL/Advanced Automata Theory and Y Computability AL/Advanced Data Structures, Algorithms, and Y Analysis 27 28 AL/Basic Analysis 29 [2 Core-Tier1 hours, 2 Core-Tier2 hours] 30 Topics: 31 [Core-Tier1] 32 • Differences among best, average, and worst case behaviors of an algorithm 33 • Asymptotic analysis of upper and average complexity bounds 34 • Big O notation: formal definition 35 • Complexity classes, such as constant, logarithmic, linear, quadratic, and exponential 36 • Empirical measurements of performance 37 • Time and space trade-offs in algorithms 38 39 [Core-Tier2] 40 • Big O notation: use 41 • Little o, big omega and big theta notation 42 • Recurrence relations and analysis of recursive algorithms 43 • Some version of a Master Theorem 44 45 Learning Outcomes: 46 1. Explain what is meant by “best”, “average”, and “worst” case behavior of an algorithm. [Knowledge] 47 2. In the context of specific algorithms, identify the characteristics of data and/or other conditions or 48 assumptions that lead to different behaviors. [Evaluation] 49 3. Determine informally the time and space complexity of simple algorithms. [Application] 50 4. Understand the formal definition of big O. [Knowledge] 51 5. List and contrast standard complexity classes. [Knowledge] - 36 - 52 6. Perform empirical studies to validate hypotheses about runtime stemming from mathematical analysis. 53 Run algorithms on input of various sizes and compare performance. [Evaluation] 54 7. Give examples that illustrate time-space trade-offs of algorithms. [Knowledge] 55 8. Use big O notation formally to give asymptotic upper bounds on time and space complexity of algorithms. 56 [Application] 57 9. Use big O notation formally to give average case bounds on time complexity of algorithms. [Application] 58 10. Explain the use of big omega, big theta, and little o notation to describe the amount of work done by an 59 algorithm. [Knowledge] 60 11. Use recurrence relations to determine the time complexity of recursively defined algorithms. [Application] 61 12. Solve elementary recurrence relations, e.g., using some form of a Master Theorem. [Application] 62 63 AL/Algorithmic Strategies 64 [5 Core-Tier1 hours, 1 Core-Tier2 hours] 65 An instructor might choose to cover these algorithmic strategies in the context of the algorithms 66 presented in “Fundamental Data Structures and Algorithms” below. While the total number of 67 hours for the two knowledge units (18) could be divided differently between them, our sense is 68 that the 1:2 ratio is reasonable. 69 Topics: 70 [Core-Tier1] 71 • Brute-force algorithms 72 • Greedy algorithms 73 • Divide-and-conquer (cross-reference SDF/Algorithms and Design/Problem-solving strategies) 74 • Recursive backtracking 75 • Dynamic Programming 76 77 [Core-Tier2] 78 • Branch-and-bound 79 • Heuristics 80 • Reduction: transform-and-conquer 81 82 Learning Outcomes: 83 1. For each of the above strategies, identify a practical example to which it would apply. [Knowledge] 84 2. Have facility mapping pseudocode to implementation, implementing examples of algorithmic strategies 85 from scratch, and applying them to specific problems. [Application] 86 3. Use a greedy approach to solve an appropriate problem and determine if the greedy rule chosen leads to an 87 optimal solution. [Application, Evaluation] 88 4. Use a divide-and-conquer algorithm to solve an appropriate problem. [Application] 89 5. Use recursive backtracking to solve a problem such as navigating a maze. [Application] 90 6. Use dynamic programming to solve an appropriate problem. [Application] 91 7. Describe various heuristic problem-solving methods. [Knowledge] 92 8. Use a heuristic approach to solve an appropriate problem. [Application] 93 9. Describe the trade-offs between brute force and other strategies. [Evaluation] 94 95 - 37 - 96 AL/Fundamental Data Structures and Algorithms 97 [9 Core-Tier1 hours, 3 Core-Tier2 hours] 98 This knowledge unit builds directly on the foundation provided by Software Development 99 Fundamentals (SDF), particularly the material in SDF/Fundamental Data Structures and 100 SDF/Algorithms and Design. 101 Topics: 102 [Core-Tier1] 103 Implementation and use of: 104 • Simple numerical algorithms, such as computing the average of a list of numbers, finding the min, max, 105 and mode in a list, approximating the square root of a number, or finding the greatest common divisor 106 • Sequential and binary search algorithms 107 • Worst case quadratic sorting algorithms (selection, insertion) 108 • Worst or average case O(N log N) sorting algorithms (quicksort, heapsort, mergesort) 109 • Hash tables, including strategies for avoiding and resolving collisions 110 • Binary search trees 111 • Common operations on binary search trees such as select min, max, insert, delete, iterate over tree 112 • Graphs and graph algorithms 113 • Representations of graphs (e.g., adjacency list, adjacency matrix) 114 • Depth- and breadth-first traversals 115 116 [Core-Tier2] 117 • Graphs and graph algorithms 118 • Shortest-path algorithms (Dijkstra’s and Floyd’s algorithms) 119 • Minimum spanning tree (Prim’s and Kruskal’s algorithms) 120 • Pattern matching and string/text algorithms (e.g., substring matching, regular expression matching, longest 121 common subsequence algorithms) 122 123 Learning Outcomes: 124 1. Implement basic numerical algorithms. [Application] 125 2. Implement simple search algorithms and explain the differences in their time complexities. [Application, 126 Evaluation] 127 3. Be able to implement common quadratic and O(N log N) sorting algorithms. [Application] 128 4. Understand the implementation of hash tables, including collision avoidance and resolution. [Knowledge] 129 5. Discuss the runtime and memory efficiency of principal algorithms for sorting, searching, and hashing. 130 [Knowledge] 131 6. Discuss factors other than computational efficiency that influence the choice of algorithms, such as 132 programming time, maintainability, and the use of application-specific patterns in the input data. 133 [Knowledge] 134 7. Solve problems using fundamental graph algorithms, including depth-first and breadth-first search. 135 [Application] 136 8. Demonstrate the ability to evaluate algorithms, to select from a range of possible options, to provide 137 justification for that selection, and to implement the algorithm in a particular context. [Application, 138 Evaluation] 139 9. Solve problems using graph algorithms, including single-source and all-pairs shortest paths, and at least 140 one minimum spanning tree algorithm. [Application] 141 10. Be able to implement a string-matching algorithm. [Application] 142 - 38 - 143 AL/Basic Automata Computability and Complexity 144 [3 Core-Tier1 hours, 3 Core-Tier2 hours] 145 Topics: 146 [Core-Tier1] 147 • Finite-state machines 148 • Regular expressions 149 • The halting problem 150 151 [Core-Tier2] 152 • Context-free grammars (cross-reference PL/Syntax Analysis) 153 • P vs NP (tractable and intractable problems) 154 • Definition of P, NP, and NP-complete 155 • Exemplary NP-complete problems (e.g., SAT, Knapsack) 156 157 Learning Outcomes: 158 1. Discuss the concept of finite state machines. [Knowledge] 159 2. Design a deterministic finite state machine to accept a specified language. [Application] 160 3. Generate a regular expression to represent a specified language. [Application] 161 4. Explain why the halting problem has no algorithmic solution. [Knowledge] 162 5. Design a context-free grammar to represent a specified language. [Application] 163 6. Define the classes P and NP. [Knowledge] 164 7. Explain the significance of NP-completeness. [Knowledge] 165 166 AL/Advanced Computational Complexity 167 [Elective] 168 Topics: 169 • Review definitions of the classes P and NP; introduce EXP 170 • NP-completeness (Cook’s theorem) 171 • Classic NP-complete problems 172 • Reduction Techniques 173 174 Learning Outcomes: 175 1. Define the classes P and NP. (Also appears in AL/Basic Automata, Computability, and Complexity) 176 [Knowledge] 177 2. Define the class EXP. [Knowledge] 178 3. Explain the significance of NP-completeness. (Also appears in AL/Basic Automata, Computability, and 179 Complexity) [Knowledge] 180 4. Provide examples of classic NP-complete problems. [Knowledge] 181 5. Prove that a problem is NP-complete by reducing a classic known NP-complete problem to it. 182 [Application] 183 184 - 39 - 185 AL/Advanced Automata Theory and Computability 186 [Elective] 187 Topics: 188 • Sets and languages 189 • Regular languages 190 • Review of deterministic finite automata (DFAs) 191 • Nondeterministic finite automata (NFAs) 192 • Equivalence of DFAs and NFAs 193 • Review of regular expressions; their equivalence to finite automata 194 • Closure properties 195 • Proving languages non-regular, via the pumping lemma or alternative means 196 • Context-free languages 197 • Push-down automata (PDAs) 198 • Relationship of PDAs and context-free grammars 199 • Properties of context-free languages 200 • Turing machines, or an equivalent formal model of universal computation 201 • Nondeterministic Turing machines 202 • Chomsky hierarchy 203 • The Church-Turing thesis 204 • Computability 205 • Rice’s Theorem 206 • Examples of uncomputable functions 207 • Implications of uncomputability 208 209 Learning Outcomes: 210 1. Determine a language’s place in the Chomsky hierarchy (regular, context-free, recursively enumerable). 211 [Evaluation] 212 2. Prove that a language is in a specified class and that it is not in the next lower class. [Evaluation] 213 3. Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular 214 expressions, and between PDAs and CFGs. [Application] 215 4. Explain the Church-Turing thesis and its significance. [Knowledge] 216 5. Explain Rice’s Theorem and its significance. [Knowledge] 217 6. Provide examples of uncomputable functions. [Knowledge] 218 7. Prove that a problem is uncomputable by reducing a classic known uncomputable problem to it. 219 [Application] 220 221 AL/Advanced Data Structures Algorithms and Analysis 222 [Elective] 223 Many programs will want their students to have exposure to more advanced algorithms or 224 methods of analysis. Below is a selection of possible advanced topics that are current and timely 225 but by no means exhaustive. 226 Topics: 227 • Balanced trees (e.g., AVL trees, red-black trees, splay trees, treaps) 228 • Graphs (e.g., topological sort, Tarjan’s algorithm, matching) 229 • Advanced data structures (e.g., B-trees, tries, Fibonacci heaps) - 40 - 230 • Network flows (e.g., max flow [Ford-Fulkerson algorithm], max flow – min cut, maximum bipartite 231 matching) 232 • Linear Programming (e.g., duality, simplex method, interior point algorithms) 233 • Number-theoretic algorithms (e.g., modular arithmetic, primality testing, integer factorization) 234 • Geometric algorithms (e.g., points, line segments, polygons [properties, intersections], finding convex hull, 235 spatial decomposition, collision detection, geometric search/proximity) 236 • Randomized algorithms 237 • Approximation algorithms 238 • Amortized analysis 239 • Probabilistic analysis 240 • Online algorithms and competitive analysis 241 242 Learning Outcomes: 243 1. Understand the mapping of real-world problems to algorithmic solutions (e.g., as graph problems, linear 244 programs, etc.) [Application, Evaluation] 245 2. Use advanced algorithmic techniques (e.g., randomization, approximation) to solve real problems. 246 [Application] 247 3. Apply advanced analysis techniques (e.g., amortized, probabilistic, etc.) to algorithms. - 41 - 1 Architecture and Organization (AR) 2 Computing professionals should not regard the computer as just a black box that executes 3 programs by magic. AR builds on SF to develop a deeper understanding of the hardware 4 environment upon which all of computing is based, and the interface it provides to higher 5 software layers. Students should acquire an understanding and appreciation of a computer 6 system’s functional components, their characteristics, performance, and interactions, and, in 7 particular, the challenge of harnessing parallelism to sustain performance improvements now and 8 into the future. Students need to understand computer architecture to develop programs that can 9 achieve high performance through a programmer’s awareness of parallelism and latency. In 10 selecting a system to use, students should to able to understand the tradeoff among various 11 components, such as CPU clock speed, cycles per instruction, memory size, and average memory 12 access time. 13 The learning outcomes specified for these topics correspond primarily to the core and are 14 intended to support programs that elect to require only the minimum 16 hours of computer 15 architecture of their students. For programs that want to teach more than the minimum, the same 16 topics (AR1-AR8) can be treated at a more advanced level by implementing a two-course 17 sequence. For programs that want to cover the elective topics, those topics can be introduced 18 within a two-course sequence and/or be treated in a more comprehensive way in a third course. 19 20 AR. Architecture and Organization (0 Core-Tier 1 hours, 16 Core-Tier 2 hours) Core-Tier 1 Core-Tier 2 Includes hours Hours Elective AR/Digital logic and digital systems 3 N AR/Machine level representation of data 3 N AR/Assembly level machine organization 6 N AR/Memory system organization and 3 N architecture AR/Interfacing and communication 1 N AR/Functional organization Y AR/Multiprocessing and alternative Y architectures AR/Performance enhancements Y 21 22 AR/Digital logic and digital systems 23 [3 Core-Tier 2 hours] 24 Topics: 25 • Overview and history of computer architecture 26 • Combinational vs. sequential logic/Field programmable gate arrays as a fundamental combinational + 27 sequential logic building block 28 • Multiple representations/layers of interpretation (hardware is just another layer) 29 • Computer-aided design tools that process hardware and architectural representations 30 • Register transfer notation/Hardware Description Language (Verilog/VHDL) 31 • Physical constraints (gate delays, fan-in, fan-out, energy/power) 32 33 Learning outcomes: 34 1. Describe the progression of computer technology components from vacuum tubes to VLSI, from 35 mainframe computer architectures to the organization of warehouse-scale computers [Knowledge]. 36 2. Comprehend the trend of modern computer architectures towards multi-core and that parallelism is inherent 37 in all hardware systems [Knowledge]. 38 3. Explain the implications of the “power wall” in terms of further processor performance improvements and 39 the drive towards harnessing parallelism [Knowledge]. 40 4. Articulate that there are many equivalent representations of computer functionality, including logical 41 expressions and gates, and be able to use mathematical expressions to describe the functions of simple 42 combinational and sequential circuits [Knowledge]. 43 5. Design the basic building blocks of a computer: arithmetic-logic unit (gate-level), registers (gate-level), 44 central processing unit (register transfer-level), memory (register transfer-level) [Application]. 45 6. Use CAD tools for capture, synthesis, and simulation to evaluate simple building blocks (e.g., arithmetic- 46 logic unit, registers, movement between registers) of a simple computer design [Application]. - 43 - 47 7. Evaluate the functional and timing diagram behavior of a simple processor implemented at the logic circuit 48 level [Evaluation]. 49 50 AR/Machine-level representation of data 51 [3 Core-Tier 2 hours] 52 Topics: 53 • Bits, bytes, and words 54 • Numeric data representation and number bases 55 • Fixed- and floating-point systems 56 • Signed and twos-complement representations 57 • Representation of non-numeric data (character codes, graphical data) 58 • Representation of records and arrays 59 60 Learning outcomes: 61 1. Explain why everything is data, including instructions, in computers [Knowledge]. 62 2. Explain the reasons for using alternative formats to represent numerical data [Knowledge]. 63 3. Describe how negative integers are stored in sign-magnitude and twos-complement representations 64 [Knowledge]. 65 4. Explain how fixed-length number representations affect accuracy and precision [Knowledge]. 66 5. Describe the internal representation of non-numeric data, such as characters, strings, records, and arrays 67 [Knowledge]. 68 6. Convert numerical data from one format to another [Application]. 69 7. Write simple programs at the assembly/machine level for string processing and manipulation [Application]. 70 71 AR/Assembly level machine organization 72 [6 Core-Tier 2 hours] 73 Topics: 74 • Basic organization of the von Neumann machine 75 • Control unit; instruction fetch, decode, and execution 76 • Instruction sets and types (data manipulation, control, I/O) 77 • Assembly/machine language programming 78 • Instruction formats 79 • Addressing modes 80 • Subroutine call and return mechanisms 81 • I/O and interrupts 82 • Heap vs. Static vs. Stack vs. Code segments 83 • Shared memory multiprocessors/multicore organization 84 • Introduction to SIMD vs. MIMD and the Flynn Taxonomy 85 86 Learning outcomes: 87 1. Explain the organization of the classical von Neumann machine and its major functional units 88 [Knowledge]. 89 2. Describe how an instruction is executed in a classical von Neumann machine, with extensions for threads, 90 multiprocessor synchronization, and SIMD execution [Knowledge]. - 44 - 91 3. Describe instruction level parallelism and hazards, and how they are managed in typical processor pipelines 92 [Knowledge]. 93 4. Summarize how instructions are represented at both the machine level and in the context of a symbolic 94 assembler [Knowledge]. 95 5. Demonstrate how to map between high-level language patterns into assembly/machine language notations 96 [Knowledge]. 97 6. Explain different instruction formats, such as addresses per instruction and variable length vs. fixed length 98 formats [Knowledge]. 99 7. Explain how subroutine calls are handled at the assembly level [Knowledge]. 100 8. Explain the basic concepts of interrupts and I/O operations [Knowledge]. 101 9. Explain how subroutine calls are handled at the assembly level [Knowledge]. 102 10. Write simple assembly language program segments [Application]. 103 11. Show how fundamental high-level programming constructs are implemented at the machine-language level 104 [Application]. 105 106 AR/Memory system organization and architecture 107 [3 Core-Tier 2 hours] 108 [Cross-reference OS/Memory Management--Virtual Machines] 109 Topics: 110 • Storage systems and their technology 111 • Memory hierarchy: importance of temporal and spatial locality 112 • Main memory organization and operations 113 • Latency, cycle time, bandwidth, and interleaving 114 • Cache memories (address mapping, block size, replacement and store policy) 115 • Multiprocessor cache consistency/Using the memory system for inter-core synchronization/atomic memory 116 operations 117 • Virtual memory (page table, TLB) 118 • Fault handling and reliability 119 • Coding, data compression, and data integrity 120 121 Learning outcomes: 122 1. Identify the main types of memory technology [Knowledge]. 123 2. Explain the effect of memory latency on running time [Knowledge]. 124 3. Describe how the use of memory hierarchy (cache, virtual memory) is used to reduce the effective memory 125 latency [Knowledge]. 126 4. Describe the principles of memory management [Knowledge]. 127 5. Explain the workings of a system with virtual memory management [Knowledge]. 128 6. Compute Average Memory Access Time under a variety of memory system configurations and workload 129 assumptions [Application]. 130 131 - 45 - 132 AR/Interfacing and communication 133 [1 Core-Tier 2 hour] 134 [Cross-reference OS Knowledge Area for a discussion of the operating system view of 135 input/output processing and management. The focus here is on the hardware mechanisms for 136 supporting device interfacing and processor-to-processor communications.] 137 Topics: 138 • I/O fundamentals: handshaking, buffering, programmed I/O, interrupt-driven I/O 139 • Interrupt structures: vectored and prioritized, interrupt acknowledgment 140 • External storage, physical organization, and drives 141 • Buses: bus protocols, arbitration, direct-memory access (DMA) 142 • Introduction to networks: networks as another layer of access hierarchy 143 • Multimedia support 144 • RAID architectures 145 146 Learning outcomes: 147 1. Explain how interrupts are used to implement I/O control and data transfers [Knowledge]. 148 2. Identify various types of buses in a computer system [Knowledge]. 149 3. Describe data access from a magnetic disk drive [Knowledge]. 150 4. Compare common network organizations, such as ethernet/bus, ring, switched vs. routed [Knowledge]. 151 5. Identify interfaces needed for multimedia support, from storage, through network, to memory and display 152 [Knowledge]. 153 6. Describe the advantages and limitations of RAID architectures [Knowledge]. 154 155 AR/Functional organization 156 [Elective] 157 [Note: elective for computer scientist; would be core for computer engineering curriculum] 158 Topics: 159 • Implementation of simple datapaths, including instruction pipelining, hazard detection and resolution 160 • Control unit: hardwired realization vs. microprogrammed realization 161 • Instruction pipelining 162 • Introduction to instruction-level parallelism (ILP) 163 164 Learning outcomes: 165 1. Compare alternative implementation of datapaths [Knowledge]. 166 2. Discuss the concept of control points and the generation of control signals using hardwired or 167 microprogrammed implementations [Knowledge]. 168 3. Explain basic instruction level parallelism using pipelining and the major hazards that may occur 169 [Knowledge]. 170 4. Design and implement a complete processor, including datapath and control [Application]. 171 5. Determine, for a given processor and memory system implementation, the average cycles per instruction 172 [Evaluation]. 173 - 46 - 174 AR/Multiprocessing and alternative architectures 175 [Elective] 176 [Cross-reference PD/Parallel Architecture: The view here is on the hardware implementation of 177 SIMD and MIMD architectures; in PD/Parallel Architecture, it is on the way that algorithms can 178 be matched to the underlying hardware capabilities for these kinds of parallel processing 179 architectures.] 180 Topics: 181 • Power Law: Energy as a limiting factor in processor design 182 • Example SIMD and MIMD instruction sets and architectures 183 • Interconnection networks (hypercube, shuffle-exchange, mesh, crossbar) 184 • Shared multiprocessor memory systems and memory consistency 185 • Multiprocessor cache coherence 186 187 Learning outcomes: 188 1. Discuss the concept of parallel processing beyond the classical von Neumann model [Knowledge]. 189 2. Describe alternative architectures such as SIMD and MIMD [Knowledge]. 190 3. Explain the concept of interconnection networks and characterize different approaches [Knowledge]. 191 4. Discuss the special concerns that multiprocessing systems present with respect to memory management and 192 describe how these are addressed [Knowledge]. 193 5. Describe the differences between memory backplane, processor memory interconnect, and remote memory 194 via networks [Knowledge]. 195 196 AR/Performance enhancements 197 [Elective] 198 Topics: 199 • Superscalar architecture 200 • Branch prediction, Speculative execution, Out-of-order execution 201 • Prefetching 202 • Vector processors and GPUs 203 • Hardware support for Multithreading 204 • Scalability 205 • Alternative architectures, such as VLIW/EPIC, and Accelerators and other kinds of Special-Purpose 206 Processors 207 208 Learning outcomes: 209 1. Describe superscalar architectures and their advantages [Knowledge]. 210 2. Explain the concept of branch prediction and its utility [Knowledge]. 211 3. Characterize the costs and benefits of prefetching [Knowledge]. 212 4. Explain speculative execution and identify the conditions that justify it [Knowledge]. 213 5. Discuss the performance advantages that multithreading offered in an architecture along with the factors 214 that make it difficult to derive maximum benefits from this approach [Knowledge]. 215 6. Describe the relevance of scalability to performance [Knowledge]. - 47 - 1 Computational Science (CN) 2 Computational Science is a field of applied computer science, that is, the application of computer 3 science to solve problems across a range of disciplines. According to the book “Introduction to 4 Computational Science”, Shiflet & Shiflet offer the following definition: “the field of 5 computational science combines computer simulation, scientific visualization, mathematical 6 modeling, computer programming and data structures, networking, database design, symbolic 7 computation, and high performance computing with various disciplines.”Computer science, 8 which largely focuses on the theory, design, and implementation of algorithms for manipulating 9 data and information, can trace its roots to the earliest devices used to assist people in 10 computation over four thousand years ago. Various systems were created and used to calculate 11 astronomical positions. Ada Lovelace’s programming achievement was intended to calculate 12 Bernoulli numbers. In the late nineteenth century, mechanical calculators became available, and 13 were immediately put to use by scientists. The needs of scientists and engineers for computation 14 have long driven research and innovation in computing. As computers increase in their problem- 15 solving power, computational science has grown in both breadth and importance. It is a 16 discipline in its own right (President’s Information Technology Advisory Committee, 2005, page 17 13) and is considered to be “one of the five college majors on the rise” (Fischer and Gleen, “5 18 College Majors on the Rise”, The Chronicle of Higher Education, 2009.) An amazing assortment 19 of sub-fields have arisen under the umbrella of Computational Science, including computational 20 biology, computational chemistry, computational mechanics, computational archeology, 21 computational finance, computational sociology and computational forensics. 22 Some fundamental concepts of computational science are germane to every computer scientist, 23 and computational science topics are extremely valuable components of an undergraduate 24 program in computer science. This area offers exposure to many valuable ideas and techniques, 25 including precision of numerical representation, error analysis, numerical techniques, parallel 26 architectures and algorithms, modeling and simulation, information visualization, software 27 engineering, and optimization. At the same time, students who take courses in this area have an 28 opportunity to apply these techniques in a wide range of application areas, such as: molecular 29 and fluid dynamics, celestial mechanics, economics, biology, geology, medicine, and social 30 network analysis. 31 In the computational science community, the terms run, modify, and create are often used to 32 describe levels of understanding. This chapter follows the conventions of other chapters in this 33 volume and uses the terms knowledge, application, and evaluation. 34 35 CN. Computational Science (1 Core-Tier1 hours, 0 Core-Tier2 hours) Core-Tier1 hours Core-Tier2 hours Includes Electives CN/Fundamentals N 1 CN/Modeling and Simulation Y CN/Processing Y CN/Interactive Visualization Y CN/Data, Information, and Y Knowledge 36 37 - 49 - 38 CN/Fundamentals 39 [1 Core-Tier1 hours] 40 This describes part of the abstraction that computer scientists do. The real world doesn’t fit in the 41 machine, so we have to abstract, simulate, and model the world in order to make the machine do 42 something useful. This is a principal approach to computing. This can be thought of as where the 43 field came from: modeling things such as trajectories of artillery shells, which was the impetus 44 for building the Eniac at the Moore School of the University of Pennsylvania in the mid-1940’s. 45 Modeling and simulation are essential topics for computational science. Any introduction to 46 computational science would either include or presume an introduction to computing. Topics 47 relevant to computational science include fundamental concepts in program construction 48 (SDF/Fundamental Programming Concepts), algorithm design (SDF/Algorithms and Design), 49 program testing (SDF/Development Methods), data representations (AR/Machine 50 Representation of Data), and basic computer architecture (AR/Memory System Organization and 51 Architecture). In addition, a general set of modeling and simulation techniques, data 52 visualization methods, and software testing and evaluation mechanisms are also important CN 53 fundamentals. 54 Topics: 55 • Introduction to modeling and simulation 56 • Simulation techniques and tools, such as physical simulations, human-in-the-loop guided simulations, and 57 virtual reality. 58 • Foundational approaches to validating models 59 60 Learning Outcomes: 61 1. Explain the concept of modeling and the use of abstraction that allows the use of a machine to solve a 62 problem. [knowledge] 63 2. Explain the concept of simulation. [knowledge] 64 3. Describe the relationship between modeling and simulation, i.e., thinking of simulation as dynamic 65 modeling. [knowledge] 66 4. Articulate the use of a formal mathematical model of a situation in the validation of a simulation. 67 [knowledge] 68 5. Differentiate among the different types of simulations. [knowledge] 69 6. Describe several approaches to validating models. [knowledge] 70 71 CN/Modeling and Simulation 72 [Elective] 73 Topics: 74 • Purpose of modeling and simulation including optimization; supporting decision making, forecasting, 75 safety considerations; for training and education. 76 • Tradeoffs including performance, accuracy, validity, and complexity. 77 • The simulation process; identification of key characteristics or behaviors, simplifying assumptions; 78 validation of outcomes. 79 • Model building: use of mathematical formula or equation, graphs, constraints; methodologies and 80 techniques; use of time stepping for dynamic systems. - 50 - 81 • Formal models and modeling techniques: mathematical descriptions involving simplifying assumptions 82 and avoiding detail. The descriptions use fundamental mathematical concepts such as set and function. 83 Random numbers. Examples of techniques including: 84 • Monte Carlo methods 85 • Stochastic processes 86 • Queuing theory 87 • Petri nets and colored Petri nets 88 • Graph structures such as directed graphs, trees, networks 89 • Games, game theory, the modeling of things using game theory 90 • Linear programming and its extensions 91 • Dynamic programming 92 • Differential equations: ODE, PDE 93 • Non-linear techniques 94 • State spaces and transitions 95 • Assessing and evaluating models and simulations in a variety of contexts; verification and validation of 96 models and simulations. 97 • Important application areas including health care and diagnostics, economics and finance, city and urban 98 planning, science, and engineering. 99 • Software in support of simulation and modeling; packages, languages. 100 101 Learning Outcomes: 102 1. Explain and give examples of the benefits of simulation and modeling in a range of important application 103 areas. 104 2. Demonstrate the ability to apply the techniques of modeling and simulation to a range of problem areas. 105 3. Explain the constructs and concepts of a particular modeling approach. 106 4. Explain the difference between validation and verification of a model; demonstrate the difference with 1 107 specific examples . 108 5. Verify and validate the results of a simulation. 109 6. Evaluate a simulation, highlighting the benefits and the drawbacks. 110 7. Choose an appropriate modeling approach for a given problem or situation. 111 8. Compare results from different simulations of the same situation and explain any differences. 112 9. Infer the behavior of a system from the results of a simulation of the system. 113 10. Extend or adapt an existing model to a new situation. 114 115 1 Verification means that the computations of the model are correct. If we claim to compute total time, for example, the computation actually does that. Validation asks whether the model matches the real situation. - 51 - 116 CN/Processing 117 [Elective] 118 The processing topic area includes numerous topics from other knowledge areas. Specifically, 119 coverage of processing should include a discussion of hardware architectures, including parallel 120 systems, memory hierarchies, and interconnections among processors. These are covered in 121 AR/Interfacing and Communication, AR/Multiprocessing and Alternative Architectures, 122 AR/Performance Enhancements. 123 Topics: 124 • Fundamental programming concepts: 125 • The concept of an algorithm consisting of a finite number of well-defined steps, each of which completes in 126 a finite amount of time, as does the entire process. 127 • Examples of well-known algorithms such as sorting and searching. 128 • The concept of analysis as understanding what the problem is really asking, how a problem can be 129 approached using an algorithm, and how information is represented so that a machine can process it. 130 • The development or identification of a workflow. 131 • The process of converting an algorithm to machine-executable code. 132 • Software processes including lifecycle models, requirements, design, implementation, verification and 133 maintenance. 134 • Machine representation of data computer arithmetic, and numerical methods, specifically sequential and 135 parallel architectures and computations. 136 • Fundamental properties of parallel and distributed computation: 137 • Bandwidth. 138 • Latency. 139 • Scalability. 140 • Granularity. 141 • Parallelism including task, data, and event parallelism. 142 • Parallel architectures including processor architectures, memory and caching. 143 • Parallel programming paradigms including threading, message passing, event driven techniques, parallel 144 software architectures, and MapReduce. 145 • Grid computing. 146 • The impact of architecture on computational time. 147 • Total time to science curve for parallelism: continuum of things. 148 • Computing costs, e.g., the cost of re-computing a value vs. the cost of storing and lookup. 149 150 Learning Outcomes: 151 1. Explain the characteristics and defining properties of algorithms and how they relate to machine 152 processing. 153 2. Analyze simple problem statements to identify relevant information and select appropriate processing to 154 solve the problem. 155 3. Identify or sketch a workflow for an existing computational process such as the creation of a graph based 156 on experimental data. 157 4. Describe the process of converting an algorithm to machine-executable code. 158 5. Summarize the phases of software development and compare several common lifecycle models. 159 6. Explain how data is represented in a machine. Compare representations of integers to floating point 160 numbers. Describe underflow, overflow, round off, and truncation errors in data representations. 161 7. Apply standard numerical algorithms to solve ODEs and PDEs. Use computing systems to solve systems of 162 equations. 163 8. Describe the basic properties of bandwidth, latency, scalability and granularity. 164 9. Describe the levels of parallelism including task, data, and event parallelism. - 52 - 165 10. Compare and contrast parallel programming paradigms recognizing the strengths and weaknesses of each. 166 11. Identify the issues impacting correctness and efficiency of a computation. 167 12. Design, code, test and debug programs for a parallel computation. 168 169 CN/Interactive Visualization 170 [Elective] 171 This sub-area is related to modeling and simulation. Most topics are discussed in detail in other 172 knowledge areas in this document. There are many ways to present data and information, 173 including immersion, realism, variable perspectives; haptics and heads-up displays, sonification, 174 and gesture mapping. 175 Interactive visualization in general requires understanding of human perception (GV/Basics); 176 graphics pipelines, geometric representations and data structures (GV/Fundamental Concepts); 177 2D and 3D rendering, surface and volume rendering (GV/Rendering, GV/Modeling, and 178 GV/Advanced Rendering); and the use of APIs for developing user interfaces using standard 179 input components such as menus, sliders, and buttons; and standard output components for data 180 display, including charts, graphs, tables, and histograms (HCI/GUI Construction, HCI/GUI 181 Programming). 182 Topics: 183 • Principles of data visualization. 184 • Graphing and visualization algorithms. 185 • Image processing techniques. 186 • Scalability concerns. 187 188 Learning Outcomes: 189 1. Compare common computer interface mechanisms with respect to ease-of-use, learnability, and cost. 190 2. Use standard APIs and tools to create visual displays of data, including graphs, charts, tables, and 191 histograms. 192 3. Describe several approaches to using a computer as a means for interacting with and processing data. 193 4. Extract useful information from a dataset. 194 5. Analyze and select visualization techniques for specific problems. 195 6. Describe issues related to scaling data analysis from small to large data sets. 196 197 - 53 - 198 CN/Data, Information, and Knowledge 199 [Elective] 200 Many topics are discussed in detail in other knowledge areas in this document, specifically 201 Information Management (IM/Information Management Concepts, IM/Database Systems, and 202 IM/Data Modeling), Algorithms and Complexity (AL/Basic Analysis, AL/Fundamental Data 203 Structures and Algorithms), and Software Development Fundamentals (SDF/Fundamental 204 Programming Concepts, SDF/Development Methods). 205 Topics: 206 • Content management models, frameworks, systems, design methods (as in IM. Information Management). 207 • Digital representations of content including numbers, text, images (e.g., raster and vector), video (e.g., 208 QuickTime, MPEG2, MPEG4), audio (e.g., written score, MIDI, sampled digitized sound track) and 209 animations; complex/composite/aggregate objects; FRBR. 210 • Digital content creation/capture and preservation, including digitization, sampling, compression, 211 conversion, transformation/translation, migration/emulation, crawling, harvesting. 212 • Content structure / management, including digital libraries and static/dynamic/stream aspects for: 213 • Data: data structures, databases. 214 • Information: document collections, multimedia pools, hyperbases (hypertext, hypermedia), catalogs, 215 repositories. 216 • Knowledge: ontologies, triple stores, semantic networks, rules. 217 • Processing and pattern recognition, including indexing, searching (including: queries and query languages; 218 central / federated / P2P), retrieving, clustering, classifying/categorizing, analyzing/mining/extracting, 219 rendering, reporting, handling transactions. 220 • User / society support for presentation and interaction, including browse, search, filter, route, visualize, 221 share, collaborate, rate, annotate, personalize, recommend. 222 • Modeling, design, logical and physical implementation, using relevant systems/software. 223 224 Learning Outcomes: 225 1. Identify all of the data, information, and knowledge elements and related organizations, for a computational 226 science application. 227 2. Describe how to represent data and information for processing. 228 3. Describe typical user requirements regarding that data, information, and knowledge. 229 4. Select a suitable system or software implementation to manage data, information, and knowledge. 230 5. List and describe the reports, transactions, and other processing needed for a computational science 231 application. 232 6. Compare and contrast database management, information retrieval, and digital library systems with regard 233 to handling typical computational science applications. 234 7. Design a digital library for some computational science users / societies, with appropriate content and 235 services. - 54 - 1 Discrete Structures (DS) 2 Discrete structures are foundational material for computer science. By foundational we mean that 3 relatively few computer scientists will be working primarily on discrete structures, but that many 4 other areas of computer science require the ability to work with concepts from discrete 5 structures. Discrete structures include important material from such areas as set theory, logic, 6 graph theory, and probability theory. 7 The material in discrete structures is pervasive in the areas of data structures and algorithms but 8 appears elsewhere in computer science as well. For example, an ability to create and understand 9 a proof—either a formal symbolic proof or a less formal but still mathematically rigorous 10 argument—is important in virtually every area of computer science, including (to name just a 11 few) formal specification, verification, databases, and cryptography. Graph theory concepts are 12 used in networks, operating systems, and compilers. Set theory concepts are used in software 13 engineering and in databases. Probability theory is used in intelligent systems, networking, and a 14 number of computing applications. 15 Given that discrete structures serves as a foundation for many other areas in computing, it is 16 worth noting that the boundary between discrete structures and other areas, particularly 17 Algorithms and Complexity, Software Development Fundamentals, Programming Languages, 18 and Intelligent Systems, may not always be crisp. Indeed, different institutions may choose to 19 organize the courses in which they cover this material in very different ways. Some institutions 20 may cover these topics in one or two focused courses with titles like "discrete structures" or 21 "discrete mathematics", whereas others may integrate these topics in courses on programming, 22 algorithms, and/or artificial intelligence. Combinations of these approaches are also prevalent 23 (e.g., covering many of these topics in a single focused introductory course and covering the 24 remaining topics in more advanced topical courses). 25 26 DS. Discrete Structures (37 Core-Tier1 hours, 4 Core-Tier2 hours) Core-Tier1 hours Core-Tier2 hours Includes Electives DS/Sets, Relations, and Functions 4 N DS/Basic Logic 9 N DS/Proof Techniques 10 1 N DS/Basics of Counting 5 N DS/Graphs and Trees 3 1 N DS/Discrete Probability 6 2 N 27 28 DS/Sets, Relations, and Functions 29 [4 Core-Tier1 hours] 30 Topics: 31 [Core-Tier1] 32 • Sets 33 • Venn diagrams 34 • Union, intersection, complement 35 • Cartesian product 36 • Power sets 37 • Cardinality of finite sets 38 • Relations 39 • Reflexivity, symmetry, transitivity 40 • Equivalence relations, partial orders 41 • Functions 42 • Surjections, injections, bijections 43 • Inverses 44 • Composition 45 46 Learning Outcomes: 47 1. Explain with examples the basic terminology of functions, relations, and sets. [Knowledge] 48 2. Perform the operations associated with sets, functions, and relations. [Application] 49 3. Relate practical examples to the appropriate set, function, or relation model, and interpret the associated 50 operations and terminology in context. [Evaluation] 51 52 - 56 - 53 DS/Basic Logic 54 [9 Core-Tier1 hours] 55 Topics: 56 [Core-Tier1] 57 • Propositional logic (cross-reference: Propositional logic is also reviewed in IS/Knowledge Based 58 Reasoning) 59 • Logical connectives 60 • Truth tables 61 • Normal forms (conjunctive and disjunctive) 62 • Validity 63 • Propositional inference rules (concepts of modus ponens and modus tollens) 64 • Predicate logic 65 • Universal and existential quantification 66 • Limitations of propositional and predicate logic (e.g., expressiveness issues) 67 68 Learning Outcomes: 69 1. Convert logical statements from informal language to propositional and predicate logic expressions. 70 [Application] 71 2. Apply formal methods of symbolic propositional and predicate logic, such as calculating validity of 72 formulae and computing normal forms. [Application] 73 3. Use the rules of inference to construct proofs in propositional and predicate logic. [Application] 74 4. Describe how symbolic logic can be used to model real-life situations or applications, including those 75 arising in computing contexts such as software analysis (e.g., program correctness), database queries, and 76 algorithms. [Application] 77 5. Apply formal logic proofs and/or informal, but rigorous, logical reasoning to real problems, such as 78 predicting the behavior of software or solving problems such as puzzles. [Application] 79 6. Describe the strengths and limitations of propositional and predicate logic. [Knowledge] 80 81 DS/Proof Techniques 82 [10 Core-Tier1 hours, 1 Core-Tier2 hour] 83 Topics: 84 [Core-Tier1] 85 • Notions of implication, equivalence, converse, inverse, contrapositive, negation, and contradiction 86 • The structure of mathematical proofs 87 • Direct proofs 88 • Disproving by counterexample 89 • Proof by contradiction 90 • Induction over natural numbers 91 • Structural induction 92 • Weak and strong induction (i.e., First and Second Principle of Induction) 93 • Recursive mathematical definitions 94 95 [Core-Tier2] 96 • Well orderings 97 - 57 - 98 Learning Outcomes: 99 1. Identify the proof technique used in a given proof. [Knowledge] 100 2. Outline the basic structure of each proof technique described in this unit. [Application] 101 3. Apply each of the proof techniques correctly in the construction of a sound argument. [Application] 102 4. Determine which type of proof is best for a given problem. [Evaluation] 103 5. Explain the parallels between ideas of mathematical and/or structural induction to recursion and recursively 104 defined structures. [Evaluation] 105 6. Explain the relationship between weak and strong induction and give examples of the appropriate use of 106 each. [Evaluation] 107 108 DS/Basics of Counting 109 [5 Core-Tier1 hours] 110 Topics: 111 [Core-Tier1] 112 • Counting arguments 113 • Set cardinality and counting 114 • Sum and product rule 115 • Inclusion-exclusion principle 116 • Arithmetic and geometric progressions 117 • The pigeonhole principle 118 • Permutations and combinations 119 • Basic definitions 120 • Pascal’s identity 121 • The binomial theorem 122 • Solving recurrence relations (cross-reference: AL/Basic Analysis) 123 • An example of a simple recurrence relation, such as Fibonacci numbers 124 • Other examples, showing a variety of solutions 125 • Basic modular arithmetic 126 127 Learning Outcomes: 128 1. Apply counting arguments, including sum and product rules, inclusion-exclusion principle and 129 arithmetic/geometric progressions. [Application] 130 2. Apply the pigeonhole principle in the context of a formal proof. [Application] 131 3. Compute permutations and combinations of a set, and interpret the meaning in the context of the particular 132 application. [Application] 133 4. Map real-world applications to appropriate counting formalisms, such as determining the number of ways 134 to arrange people around a table, subject to constraints on the seating arrangement, or the number of ways 135 to determine certain hands in cards (e.g., a full house). [Application] 136 5. Solve a variety of basic recurrence relations. [Application] 137 6. Analyze a problem to determine underlying recurrence relations. [Application] 138 7. Perform computations involving modular arithmetic. [Application] 139 140 - 58 - 141 DS/Graphs and Trees 142 [3 Core-Tier1 hours, 1 Core-Tier2 hour] 143 (cross-reference: AL/Fundamental Data Structures and Algorithms) 144 Topics: 145 [Core-Tier1] 146 • Trees 147 • Undirected graphs 148 • Directed graphs 149 • Weighted graphs 150 • Traversal strategies 151 152 [Core-Tier2] 153 • Spanning trees/forests 154 • Graph isomorphism 155 156 Learning Outcomes: 157 1. Illustrate by example the basic terminology of graph theory, and some of the properties and special cases of 158 each type of graph/tree. [Knowledge] 159 2. Demonstrate different traversal methods for trees and graphs, including pre, post, and in-order traversal of 160 trees. [Application] 161 3. Model a variety of real-world problems in computer science using appropriate forms of graphs and trees, 162 such as representing a network topology or the organization of a hierarchical file system. [Application] 163 4. Show how concepts from graphs and trees appear in data structures, algorithms, proof techniques 164 (structural induction), and counting. [Application] 165 166 DS/Discrete Probability 167 [6 Core-Tier1 hours, 2 Core-Tier2 hour] 168 (Cross-reference IS/Basic Knowledge Representation and Reasoning, which includes a review of 169 basic probability) 170 Topics: 171 [Core-Tier1] 172 • Finite probability space, events 173 • Axioms of probability and probability measures 174 • Conditional probability, Bayes’ theorem 175 • Independence 176 • Integer random variables (Bernoulli, binomial) 177 • Expectation, including Linearity of Expectation 178 179 [Core-Tier2] 180 • Variance 181 • Conditional Independence 182 - 59 - 183 Learning Outcomes: 184 1. Calculate probabilities of events and expectations of random variables for elementary problems such as 185 games of chance. [Application] 186 2. Differentiate between dependent and independent events. [Application] 187 3. Explain how events that are independent can be conditionally dependent (and vice-versa). Identify real- 188 world examples of such cases. [Application] 189 4. Identify a case of the binomial distribution and compute a probability using that distribution. [Application] 190 5. Make a probabilistic inference in a real-world problem using Bayes’ theorem to determine the probability 191 of a hypothesis given evidence. [Application] 192 6. Apply the tools of probability to solve problems such as the average case analysis of algorithms or 193 analyzing hashing. [Application] - 60 - 1 Graphics and Visualization (GV) 2 Computer graphics is the term commonly used to describe the computer generation and 3 manipulation of images. It is the science of enabling visual communication through computation. 4 Its uses include cartoons, film special effects, video games, medical imaging, engineering, as 5 well as scientific, information, and knowledge visualization. Traditionally, graphics at the 6 undergraduate level has focused on rendering, linear algebra, and phenomenological approaches. 7 More recently, the focus has begun to include physics, numerical integration, scalability, and 8 special-purpose hardware, In order for students to become adept at the use and generation of 9 computer graphics, many implementation-specific issues must be addressed, such as file formats, 10 hardware interfaces, and application program interfaces. These issues change rapidly, and the 11 description that follows attempts to avoid being overly prescriptive about them. The area 12 encompassed by Graphics and Visual Computing (GV) is divided into several interrelated fields: 13 • Fundamentals: Computer graphics depends on an understanding of how humans use 14 vision to perceive information and how information can be rendered on a display device. 15 Every computer scientist should have some understanding of where and how graphics can 16 be appropriately applied and the fundamental processes involved in display rendering. 17 • Modeling: Information to be displayed must be encoded in computer memory in some 18 form, often in the form of a mathematical specification of shape and form. 19 • Rendering: Rendering is the process of displaying the information contained in a model. 20 • Animation: Animation is the rendering in a manner that makes images appear to move 21 and the synthesis or acquisition of the time variations of models. 22 • Visualization. The field of visualization seeks to determine and present underlying 23 correlated structures and relationships in data sets from a wide variety of application 24 areas. The prime objective of the presentation should be to communicate the information 25 in a dataset so as to enhance understanding 26 • Computational Geometry: Computational Geometry is the study of algorithms that are 27 stated in terms of geometry. 28 29 Graphics and Visualization is related to machine vision and image processing (in the Intelligent 30 Systems KA) and algorithms such as computational geometry, which can be found in the 31 Algorithms and Complexity KA. Topics in virtual reality can be found in the Human Computer 32 Interaction KA. 33 This description assumes students are familiar with fundamental concepts of data representation, 34 abstraction, and program implementation. 35 36 GV. Graphics and Visualization (2 Core-Tier1 hours, 1 Core-Tier2 hours) Core-Tier1 hours Core-Tier2 hours Includes Electives GV/Fundamental Concepts 2 1 N GV/Basic Rendering Y GV/Geometric Modeling Y GV/Advanced Rendering Y GV/Computer Animation Y GV/Visualization Y 37 38 - 62 - 39 GV/Fundamental Concepts 40 [2 Core-Tier1 and 1 Core-Tier2 hours] 41 For nearly every computer scientist and software developer, an understanding of how humans 42 interact with machines is essential. While these topics may be covered in a standard 43 undergraduate graphics course, they may also be covered in introductory computer science and 44 programming courses. Part of our motivation for including immediate and retained modes is that 45 these modes are roughly analogous to polling vs. event driven programming. This is a 46 fundamental question in computer science: Is there a button object, or is there just the display of 47 a button on the screen? Note that most of the outcomes in this section are at the knowledge level, 48 and many of these topics may be revisited in greater depth. 49 Topics: 50 [Core-Tier1] 51 • Basics of Human visual perception (HCI Foundations). 52 • Image representations, vector vs. raster, color models, meshes. 53 • Forward and backward rendering (i.e., ray-casting and rasterization). 54 • Applications of computer graphics: including game engines, cad, visualization, virtual reality. 55 56 [Core-Tier2] 57 • Polygonal representation. 58 • Basic radiometry, similar triangles, and projection model. 59 • Use of standard graphics APIs (see HCI GUI construction). 60 • Compressed image representation and the relationship to information theory. 61 • Immediate and retained mode. 62 • Double buffering. 63 64 Learning Outcomes: 65 Students should be able to: 66 1. Describe the basic process of human visual perception including the perception of continuous motion from 67 a sequence of discrete frames (sometimes called “flicker fusion”), tricolor stimulus, depth cues, contrast 68 sensitivity, and the limits of human visual acuity. [knowledge level] 69 2. Describe color models and their use in graphics display devices. [knowledge level] 70 3. Differentiate between vector and raster rendering. [knowledge level] 71 4. Introduce the algorithmic distinction between projecting light from surfaces forward to the screen (e.g., 72 triangle rasterization and splatting) vs. tracing the path of light backwards (e.g., ray or beam tracing). 73 [knowledge level] 74 5. Identify common uses of computer graphics. [knowledge level] 75 6. Model simple graphics images. [application level] 76 7. Derive linear perspective from similar triangles by converting points (x, y, z) to points (x/z, y/z, 1). 77 [application level] 78 8. Create 2D or 3D images using a standard graphics API. [application level] 79 9. Describe the basic graphics pipeline and how forward and backward rendering factor in this. [knowledge 80 level] 81 10. Describe the differences between lossy and lossless image compression techniques, for example as 82 reflected in common graphics image file formats such as JPG, PNG, and GIF. [knowledge level] 83 11. Apply a data compression algorithm such as run-length, Haar-wavelet, JPEG encoding, Huffman coding or 84 Ziv-Lempel. [application level] 85 12. Apply double-buffering in the generation of a graphics application. [application level] - 63 - 86 87 GV/Basic Rendering 88 [Elective] 89 This section describes basic rendering and fundamental graphics techniques that nearly every 90 undergraduate course in graphics will cover and that is essential for further study in graphics. 91 Sampling and anti-aliasing is related to the effect of digitization and appears in other areas of 92 computing, for example, in audio sampling. 93 94 Topics: 95 • Rendering in nature, i.e., the emission and scattering of light and its relation to numerical integration. 96 • Affine and coordinate system transformations. 97 • Ray tracing. 98 • Visibility and occlusion, including solutions to this problem such as depth buffering, Paiter’s algorithm, 99 and ray tracing. 100 • The forward and backward rendering equation. 101 • Simple triangle rasterization. 102 • Rendering with a shader-based API. 103 • Texture mapping, including minification and magnification (e.g., trilinear MIP-mapping). 104 • Application of spatial data structures to rendering. 105 • Sampling and anti-aliasing. 106 • Scene graphs and the graphics pipeline. 107 108 Learning Outcomes: 109 Students should be able to: 110 1. Discuss the light transport problem and its relation to numerical integration i.e., light is emitted, scatters 111 around the scene, and is measured by the eye; the form is an integral equation without analytic solution, but 112 we can approach it as numerical integration. 113 2. Obtain 2-dimensional and 3-dimensional points by applying affine transformations. 114 3. Apply 3-dimensional coordinate system and the changes required to extend 2D transformation operations to 115 handle transformations in 3D. 116 4. Contrast forward and backward rendering. 117 5. Explain the concept and applications of texture mapping, sampling, and anti-aliasing. 118 6. Explain the ray tracing – rasterization duality for the visibility problem. 119 7. Implement simple procedures that perform transformation and clipping operations on simple 2-dimensional 120 images. 121 8. Implement a simple real-time renderer using a rasterization API (e.g., OpenGL) using vertex buffers and 122 shaders. 123 9. Compare and contrast the different rendering techniques. 124 10. Compute space requirements based on resolution and color coding. 125 11. Compute time requirements based on refresh rates, rasterization techniques. 126 127 - 64 - 128 GV/Geometric Modeling 129 [Elective] 130 Topics: 131 • Basic geometric operations such as intersection calculation and proximity tests 132 • Volumes, voxels, and point-based representations. 133 • Parametric polynomial curves and surfaces. 134 • Implicit representation of curves and surfaces. 135 • Approximation techniques such as polynomial curves, Bezier curves, spline curves and surfaces, and non- 136 uniform rational basis (NURB) spines, and level set method. 137 • Surface representation techniques including tessellation, mesh representation, mesh fairing, and mesh 138 generation techniques such as Delaunay triangulation, marching cubes, . 139 • Spatial subdivision techniques. 140 • Procedural models such as fractals, generative modeling, and L-systems. 141 • Graftals, cross referenced with programming languages (grammars to generated pictures). 142 • Elastically deformable and freeform deformable models. 143 • Subdivision surfaces. 144 • Multiresolution modeling. 145 • Reconstruction. 146 • Constructive Solid Geometry (CSG) representation. 147 148 Learning Outcomes: 149 1. Represent curves and surfaces using both implicit and parametric forms. 150 2. Create simple polyhedral models by surface tessellation. 151 3. Implement such algorithms as 152 4. Generate a mesh representation from an implicit surface. 153 5. Generate a fractal model or terrain using a procedural method. 154 6. Generate a mesh from data points acquired with a laser scanner. 155 7. Construct CSG models from simple primitives, such as cubes and quadric surfaces. 156 8. Contrast modeling approaches with respect to space and time complexity and quality of image. 157 158 GV/Advanced Rendering 159 [Elective] 160 Topics: 161 • Solutions and approximations to the rendering equation, for example: 162 • Distribution ray tracing and path tracing 163 • Photon mapping 164 • Bidirectional path tracing 165 • Reyes (micropolygon) rendering 166 • Metropolis light transport 167 • Considering the dimensions of time (motion blur), lens position (focus), and continuous frequency (color). 168 • Shadow mapping. 169 • Occlusion culling. 170 • Bidirectional Scattering Distribution function (BSDF) theory and microfacets. 171 • Subsurface scattering. 172 • Area light sources. 173 • Hierarchical depth buffering. - 65 - 174 • The Light Field, image-based rendering. 175 • Non-photorealistic rendering. 176 • GPU architecture. 177 • Human visual systems including adaptation to light, sensitivity to noise, and flicker fusion. 178 179 Learning Outcomes: 180 1. Demonstrate how an algorithm estimates a solution to the rendering equation. 181 2. Prove the properties of a rendering algorithm, e.g., complete, consistent, and/or unbiased. 182 3. Analyze the bandwidth and computation demands of a simple algorithm. 183 4. Implement a non-trivial shading algorithm (e.g., toon shading, cascaded shadow maps) under a rasterization 184 API. 185 5. Discuss how a particular artistic technique might be implemented in a renderer. 186 6. Explain how to recognize the graphics techniques used to create a particular image. 187 7. Implement any of the specified graphics techniques using a primitive graphics system at the individual 188 pixel level. 189 8. Implement a ray tracer for scenes using a simple (e.g., Phong’s) BRDF plus reflection and refraction. 190 191 GV/Computer Animation 192 [Elective] 193 Topics: 194 • Forward and inverse kinematics. 195 • Collision detection and response 196 • Procedural animation using noise, rules (boids/crowds), and particle systems. 197 • Skinning algorithms. 198 • Physics based motions including rigid body dynamics, physical particle systems, mass-spring networks for 199 cloth and flesh and hair. 200 • Key-frame animation. 201 • Splines. 202 • Data structures for rotations, such as quaternions. 203 • Camera animation. 204 • Motion capture. 205 206 Learning Outcomes: 207 1. Compute the location and orientation of model parts using an forward kinematic approach. 208 2. Compute the orientation of articulated parts of a model from a location and orientation using an inverse 209 kinematic approach. 210 3. Describe the tradeoffs in different representations of rotations. 211 4. Implement the spline interpolation method for producing in-between positions and orientations. 212 5. Implement algorithms for physical modeling of particle dynamics using simple Newtonian mechanics, for 213 example Witkin & Kass, snakes and worms, symplectic Euler, Stormer/Verlet, or midpoint Euler methods. 214 6. Describe the tradeoffs in different approaches to ODE integration for particle modeling. 215 7. Discuss the basic ideas behind some methods for fluid dynamics for modeling ballistic trajectories, for 216 example for splashes, dust, fire, or smoke. 217 8. Use common animation software to construct simple organic forms using metaball and skeleton. 218 219 - 66 - 220 GV/Visualization 221 [Elective] 222 Visualization has strong ties to Human Computer Interaction as well as Computational Science. 223 Readers should refer to the HCI and CN KAs for additional topics related to user population and 224 interface evaluations. 225 Topics: 226 • Visualization of 2D/3D scalar fields: color mapping, isosurfaces. 227 • Direct volume data rendering: ray-casting, transfer functions, segmentation. 228 • Visualization of: 229 • Vector fields and flow data 230 • Time-varying data 231 • High-dimensional data: dimension reduction, parallel coordinates, 232 • Non-spatial data: multi-variate, tree/graph structured, text 233 • Perceptual and cognitive foundations that drive visual abstractions. 234 • Visualization design. 235 • Evaluation of visualization methods. 236 • Applications of visualization. 237 238 Learning Outcomes: 239 1. Describe the basic algorithms for scalar and vector visualization. 240 2. Describe the tradeoffs of algorithms in terms of accuracy and performance. 241 3. Propose a suitable visualization design for a particular combination of data characteristics and application 242 tasks. 243 4. Discuss the effectiveness of a given visualization for a particular task. 244 5. Design a process to evaluate the utility of a visualization algorithm or system. 245 6. Recognize a variety of applications of visualization including representations of scientific, medical, and 246 mathematical data; flow visualization; and spatial analysis. 247 - 67 - 1 Human-Computer Interaction (HC) 2 Human–computer interaction (HCI) is concerned with designing the interaction between people 3 and computers and the construction of interfaces to afford this interaction. 4 Interaction between users and computational artifacts occurs at an interface which includes both 5 software and hardware. Interface design impacts the software life-cycle in that it should occur 6 early; the design and implementation of core functionality can influence the user interface – for 7 better or worse. 8 Because it deals with people as well as computers, as a knowledge area HCI draws on a variety 9 of disciplinary traditions including psychology, computer science, product design, anthropology 10 and engineering. 11 HC: Human Computer Interaction (4 Core-Tier1 hours, 4 Core-Tier2 hours) Core-Tier1 Core-Tier2 Includes hours hours Electives HC/Foundations 4 N HC/Designing Interaction 4 N HC/Programming Interactive Systems Elective HC/User-cantered design & testing Elective HC/Design for non-Mouse interfaces Elective HC/Collaboration & communication Elective HC/Statistical Methods for HCI Elective HC/Human factors & security Elective HC/Design-oriented HCI Elective HC/Mixed, Augmented and Virtual Elective Reality 12 13 14 HC/Foundations 15 [4 Core-Tier1 hours] 16 Motivation: For end-users, the interface is the system. So design in this domain must be 17 interaction-focused and human-centered. Students need a different repertoire of techniques to 18 address interaction design than is provided elsewhere in the curriculum. 19 Topics: 20 • Contexts for HCI (anything with a user interface: webpage, business applications, mobile applications, 21 games, etc.) 22 • Processes for user-centered development: early focus on users, empirical testing, iterative design. 23 • Different measures for evaluation: utility, efficiency, learnability, user satisfaction. 24 • Physical capabilities that inform interaction design: color perception, ergonomics 25 • Cognitive models that inform interaction design: attention, perception and recognition, movement, and 26 memory. Gulfs of expectation and execution. 27 • Social models that inform interaction design: culture, communication, networks and organizations. 28 • Principles of good design and good designers; engineering tradeoffs 29 • Accessibility: interfaces for differently-abled populations (e.g. blind, motion-impaired) 30 • Interfaces for differently-aged population groups (e.g. children, 80+) 31 32 Learning Outcomes: 33 Students should be able to: 34 1. Discuss why human-centered software development is important (knowledge) 35 2. Summarize the basic precepts of psychological and social interaction (knowledge) 36 3. Develop and use a conceptual vocabulary for analyzing human interaction with software: affordance, 37 conceptual model, feedback, and so forth (comprehension) 38 4. Define a user-centered design process that explicitly recognizes that the user is not like the developer or her 39 acquaintances (comprehension) 40 5. Create and conduct a simple usability test for an existing software application (application) 41 42 HC/Designing Interaction 43 [4 Core-Tier2 hours] 44 Motivation: CS students need a minimal set of well-established methods and tools to bring to 45 interface construction. 46 Topics: 47 • Principles of different styles of interface: e.g. command line, graphical tangible. 48 • Basic two-dimensional design fundamentals as applied to the visual interface, including use of grid, 49 typography, color and contrast, scale, ordering and hierarchy.) 50 • Task analysis 51 • Paper prototyping 52 • Basic statistics and techniques for controlled experimentation (especially in regard to web data) 53 • KLM evaluation 54 • Help & documentation 55 • Handling human/system failure 56 • User interface standards 57 - 69 - 58 Learning Outcomes: 59 1. Students should be able to apply the principles of HCI foundations to: 60 2. Create a simple application, together with help & documentation, that supports a user interface 61 (application) 62 3. Conduct a quantitative evaluation and discuss/report the results (application) 63 4. Discuss at least one national or international user interface design standard (comprehension) 64 65 HC/Programming Interactive Systems 66 [Elective] 67 Motivation: To take a user-experience-centered view of software development and then cover 68 approaches and technologies to make that happen. 69 Topics: 70 Software Architecture Patterns: Model-View controller; command objects, online, offline, (cross 71 reference SE/Software Design) 72 • Interaction Design Patterns: visual hierarchy, navigational distance 73 • Event management and user interaction 74 • Geometry management (cross reference GV/Geometric Modeling) 75 • Choosing interaction styles and interaction techniques 76 • Presenting information: navigation, representation, manipulation 77 • Interface animation techniques (scene graphs, etc) 78 • Widget classes and libraries 79 • Modern GUI libraries (iOS, Android, JavaFX) GUI builders and UI programming environments (cross 80 reference to PBD/Mobile Platforms) 81 • Declarative Interface Specification: Stylesheets and DOMs 82 • Data-driven applications (database-backed web pages) 83 • Cross-platform design 84 • Design for resource-constrained devices (e.g. small, mobile devices) 85 86 Learning Outcomes: 87 Students should be able to apply the principles of HCI foundations to: 88 1. Understand there are common approaches to design problems, and be able to explain the importance of 89 MVC to GUI programming (knowledge) 90 2. Create an application with a modern l user interface (application) 91 3. Identify commonalities and differences in UIs across different platforms (application) 92 4. Explain and use GUI programming concepts: event handling, constraint-based layout management, etc 93 (evaluation) 94 - 70 - 95 HC/User-centered design and testing [elective] 96 Motivation: An exploration of techniques to ensure that end-users are fully considered at all 97 stages of the design process, from inception to implementation. 98 Topics: 99 • Approaches and characteristics of design process 100 • Functionality and usability requirements (cross reference to SE Software Design) 101 • Techniques for gathering requirements: interviews, surveys, ethnographic & contextual enquiry (cross 102 reference to SE Requirements Engineering) 103 • Techniques and tools for analysis & presentation of requirements: reports, personas 104 • Prototyping techniques and tools: sketching, storyboards, low-fidelity prototyping, wireframes 105 • Evaluation without users, using both qualitative and quantitative techniques: walkthroughs, GOMS, expert- 106 based analysis, heuristics, guidelines, and standards 107 • Evaluation with users: observation, think-aloud, interview, survey, experiment. 108 • Challenges to effective evaluation: sampling, generalization. 109 • Reporting the results of evaluations 110 • Internationalization, designing for users from other cultures, cross-cultural evaluation 111 112 Learning Outcomes: 113 Students should be able to apply the principles of HCI foundations to: 114 1. Understand how user-centered design complements other software process models (knowledge) 115 2. Choose appropriate methods to support the development of a specific UI (application) 116 3. Use a variety of techniques to evaluate a given UI (application) 117 4. Use lo-fi prototyping techniques to gather, and report, user responses (application) 118 5. Describe the constraints and benefits of different evaluative methods (comprehension) 119 120 HC/Design for non-mouse interfaces 121 [Elective] 122 Motivation: As technologies evolve, new interaction styles are made possible. This knowledge 123 unit should be considered extensible, to track emergent technology. 124 Topics: 125 • Choosing interaction styles and interaction techniques 126 • Representing information to users: navigation, representation, manipulation 127 • Approaches to design, implementation and evaluation of non-mouse interaction 128 • Touch and multi-touch interfaces 129 • New Windows (iPhone, Android) 130 • Speech recognition and natural language processing – (cross reference IS/Perception and Computer Vision) 131 • Wearable and tangible interfaces 132 • Persuasive interaction and emotion 133 • Ubiquitous and context-aware (Ubicomp) 134 • Bayesian inference (e.g. predictive text, guided pointing) 135 • Ambient/peripheral display and interaction 136 - 71 - 137 Learning Outcomes: 138 Students should be able to apply the principles of HCI foundations to: 139 1. Describe when non-mouse interfaces are appropriate (knowledge) 140 2. Discuss the advantages (and disadvantages) of non-mouse interfaces (application) 141 3. Understand the interaction possibilities beyond mouse-and-pointer interfaces (comprehension) 142 143 HC/Collaboration and communication 144 [Elective] 145 Motivation: Computer interfaces not only support users in achieving their individual goals but 146 also in their interaction with others, whether that is task-focused (work or gaming) or task- 147 unfocussed (social networking). 148 Topics: 149 • Asynchronous group communication: e-mail, forums, Facebook 150 • Synchronous group communication: chat rooms, conferencing, online games 151 • Online communities 152 • Software characters and intelligent agents, virtual worlds and avatars (cross reference IS/Agents) 153 • Social psychology 154 • Social networking 155 • Social computing 156 157 Learning Outcomes: 158 Students should be able to apply the principles of HCI foundations to: 159 1. Describe the difference between synchronous and asynchronous communication (knowledge) 160 2. Compare the HCI issues in individual interaction with group interaction (comprehension) 161 3. Discuss several issues of social concern raised by collaborative software (comprehension) 162 4. Discuss the HCI issues in software that embodies human intention (comprehension) 163 164 HC/Statistical methods for HCI 165 [Elective] 166 Motivation: Much HCI work depends on the proper use, understanding and application of 167 statistics. This knowledge is often held by students who join the field from psychology, but less 168 common in students with a CS background. 169 Topics: 170 • t-tests 171 • ANOVA 172 • randomization (non-parametric) testing, within v. between-subjects design 173 • calculating effect size 174 • exploratory data analysis 175 • presenting statistical data - 72 - 176 • using statistical data 177 • using qualitative and quantitative results together 178 179 Learning Outcomes: 180 Students should be able to apply the principles of HCI foundations to: 181 1. Explain basic statistical concepts and their areas of application (knowledge) 182 2. Extract and articulate the statistical arguments used in papers which report HCI results (comprehension) 183 3. Devise appropriate statistical tests for a given HCI problem (application) 184 185 HC/Human factors and security 186 [Elective] 187 Motivation: Effective interface design requires basic knowledge of security psychology. Many 188 attacks do not have a technological basis, but exploit human propensities and vulnerabilities. 189 “Only amateurs attack machines; professionals target people” (Bruce Schneier) 190 Topics: 191 • Applied psychology and security policies 192 • Security economics 193 • Regulatory environments – responsibility, liability and self-determination 194 • Organizational vulnerabilities and threats 195 • Usability design and security 196 • Pretext, impersonation and fraud. Phishing and spear phishing (cross reference IAS/Fundamentals) 197 • Trust, privacy and deception 198 • Biometric authentication (camera, voice) 199 • Identity management 200 201 Learning Outcomes: 202 Students should be able to apply the principles of HCI foundations to: 203 1. Explain the concepts of phishing and spear phishing, and how to recognize them (knowledge) 204 2. Explain the concept of identity management and its importance (knowledge) 205 3. Describe the issues of trust in interface design with an example of a high and low trust system (knowledge) 206 4. Design a user interface for a security mechanism (application) 207 5. Analyze a security policy and/or procedures to show where they consider, or fail to consider, human factors 208 (comprehension) 209 - 73 - 210 HC/Design-oriented HCI 211 [Elective] 212 Motivation: Some curricula will want to emphasize an understanding of the norms and values of 213 HCI work itself as emerging from, and deployed within specific historical, disciplinary and 214 cultural contexts. 215 Topics: 216 • Intellectual styles and perspectives to technology and its interfaces 217 • Consideration of HCI as a design discipline: 218 • Sketching 219 • Participatory design 220 • Critically reflective HCI 221 • Critical technical practice 222 • Technologies for political activism 223 • Philosophy of user experience 224 • Ethnography and ethno-methodology 225 • Indicative domains of application 226 • Sustainability 227 • Arts-informed computing 228 229 Learning Objectives 230 Students should be able to apply the principles of HCI foundations to: 231 1. Detail the processes of design appropriate to specific design orientations (knowledge) 232 2. Apply a variety of design methods to a given problem (application) 233 3. Understand HCI as a design-oriented discipline. (comprehension) 234 235 HC/Mixed, Augmented and Virtual Reality 236 [Elective] 237 Motivation: A detailed consideration of the interface components required for the creation and 238 development of immersive environments, especially games. 239 Topics: 240 • Output 241 • Sound 242 • Stereoscopic display 243 • Force feedback simulation, haptic devices 244 • User input 245 • Viewer and object tracking 246 • Pose and gesture recognition 247 • Accelerometers 248 • Fiducial markers 249 • User interface issues 250 • Physical modeling and rendering 251 • Physical simulation: collision detection & response, animation - 74 - 252 • Visibility computation 253 • Time-critical rendering, multiple levels of details (LOD) 254 • System architectures 255 • Game engines 256 • Mobile augmented reality 257 • Flight simulators 258 • CAVEs 259 • Medical imaging 260 • Networking 261 • p2p, client-server, dead reckoning, encryption, synchronization 262 • Distributed collaboration 263 264 Learning Objectives: 265 1. Describe the optical model realized by a computer graphics system to synthesize stereoscopic view 266 (knowledge) 267 2. Describe the principles of different viewer tracking technologies. (knowledge) 268 3. Describe the differences between geometry- and image-based virtual reality.(knowledge) 269 4. Describe the issues of user action synchronization and data consistency in a networked 270 environment.(knowledge) 271 5. Determine the basic requirements on interface, hardware, and software configurations of a VR system for a 272 specified application. (application) 273 6. To be aware of the range of possibilities for games engines, including their potential and their limitations. 274 (comprehension) - 75 - 1 Information Assurance and Security (IAS) 2 In CS2013, the Information Assurance and Security KA is added to the Body of Knowledge in 3 recognition of the world’s reliance on information technology and its critical role in computer 4 science education. Information assurance and security as a domain is the set of controls and 5 processes both technical and policy intended to protect and defend information and information 6 systems by ensuring their availability, integrity, authentication, and confidentiality and providing 7 for non-repudiation. The concept of assurance also carries an attestation that current and past 8 processes and data are valid. Both assurance and security concepts are needed to ensure a 9 complete perspective. Information assurance and security education, then, includes all efforts to 10 prepare a workforce with the needed knowledge, skills, and abilities to protect our information 11 systems and attest to the assurance of the past and current state of processes and data. The 12 Information Assurance and Security KA is unique among the set of KA’s presented here given 13 the manner in which the topics are pervasive throughout other Knowledge Areas. The topics 14 germane to only IAS are presented in depth in the IAS section; other topics are noted and cross 15 referenced in the IAS KA, with the details presented in the KA in which they are tightly 16 integrated. 17 The aim of this KA is two-fold. First, the KA defines the core (tier1and tier2) and the elective 18 components that depict topics that are part of an undergraduate computer science curriculum. 19 Secondly (and almost more importantly), we document the pervasive presence of IAS within a 20 computer science undergraduate curriculum. 21 The IAS KA is shown in two groups; (1) concepts that are, at the first order, germane to 22 Information Assurance and Security and (2) IAS topics that are integrated into other KA’s. For 23 completeness, the total distribution of hours is summarized in the table below. 24 Core-Tier1 hours Core-Tier2 hours Elective Topics IAS 2 6 Y IAS distributed in other 23 46 Y KA’s 25 26 IAS. Information Assurance and Security (2 Core-Tier1 hours, 6 Core-Tier2 hours) Core-Tier1 hours Core-Tier2 hours Includes Electives IAS/Fundamental 1 2 N Concepts IAS/Network Security 1 4 N IAS/Cryptography Y IAS/Risk Management Y IAS/Security Policy and Y Governance IAS / Digital Forensics Y IAS / Security Y Architecture and Systems Administration IAS/Secure Software Y Design and Engineering 27 28 IAS. Information Assurance and Security (distributed) (23 Core-Tier1 hours, 46 29 Core-Tier2 hours) Knowledge Area and Core-Tier1 hours Core-Tier2 hours Includes Electives Topic OS/ Overview of OS 1* OS/OS Principles 1* OS/Concurrency 3 OS/Scheduling and 3 Dispatch OS/Memory 1* Management OS/Security and 2 Protection OS/Virtual Machines Y OS/Device Management Y OS/File Systems Y OS/Real Time and Y Embedded Systems - 77 - OS/Fault Tolerance Y OS/System Y Performance Evaluation NC/Introduction 1.5 NC/Networked 1.5 Applications NC/Reliable Data 2 Delivery NC/Routing and 1.5 Forwarding NC/Local Area Networks 1.5 NC/Resource Allocation 1 NC/Mobility 1 PBD/Web Platforms Y PBD/Mobile Platforms Y PBD/Industrial Y Platforms IM/Information 2 Management Concepts IM/Transaction Y Processing IM/Distributed Y Databases PL/Functional 2 Programming PL/Type Systems 1 4 PL/Language 1 3 Translation And Execution PD/Parallelism 1* Y Fundamentals PD/Communication and 1 3 Coordination SDF/Development 9 Methods - 78 - SE/Software Processes 1 SE/Software Project 3 Management SE/Tools and 1 Environments SE/Software 2 Y Construction SE/Software Verification 3 Y Validation SP/Professional Ethics 2 1 SP/Intellectual Property 2 SP/Security Policies, Y Laws and Computer Crimes HCI/Human factors and Y security IS/Reasoning Under Y Uncertainty 30 * Indicates not all hours in the KU are classified as cross referenced to IAS 31 32 IAS/Fundamental Concepts 33 [1 Core-Tier1 hours, 2 Core-Tier2 hours] 34 Topics: 35 [Core-Tier1] 36 • Nature of the Threats 37 • Need for Information Assurance. 38 • Basic Terminology that should be recognized by those studying the field. (Confidentiality, Integrity, 39 Availability) 40 • Information Assurance Concepts that are key to building an understanding of the IA area. 41 42 [Core-Tier2] 43 • Industry and Government Guidelines and Standards concerning Information Assurance. 44 • National and Cultural Differences including topics such as HIPAA, Safe Harbor, and data protection laws. 45 • Legal, Ethical, and Social Issues (cross reference with SP KA) 46 • Threats and Vulnerabilities. 47 • Types of Attacks 48 • Types of Attackers. 49 • Defense Mechanisms. 50 • Incident Response. 51 - 79 - 52 Learning outcomes: 53 1. Describe the types of threats to data and information systems [Knowledge] 54 2. Describe why processes and data need protection [Knowledge] 55 3. Describe the context in which Confidentiality, Integrity, and Availability are important to given processes 56 or data? [Application] 57 4. Determine if the security controls provide sufficient security for the required level of Confidentiality, 58 Integrity, and/or Availability [Evaluation] 59 5. What are significant national level laws affecting the obligation for the protection of data? [Knowledge] 60 6. Describe how laws affecting privacy and data/IP protection differ based on country? [Evaluation] 61 7. Describe the major vulnerabilities present in systems today. [Knowledge] 62 8. Define the fundamental motivations for intentional malicious exploitation of vulnerabilities. [Knowledge] 63 9. Define the defense mechanisms that can be used to detect or mitigate malicious activity in IT systems. 64 [Knowledge] 65 10. Define an incident. [Knowledge] 66 11. Enumerate the roles required in incident response and the common steps after an incident has been 67 declared. [Knowledge] 68 12. Describe the actions taken in response to the discovery of a given incident. [Application] 69 70 IAS/Network Security 71 [1 Core-Tier1 hours, 4 Core-Tier2 hours] 72 Discussion of network security relies on previous understanding on fundamental concepts of 73 networking, including protocols, such as TCP/IP, and network architecture/organization (xref 74 NC/Network Communication). 75 Topics: 76 [Core-Tier1] 77 • Application of Cryptography 78 • TLS 79 • Secret-key algorithms 80 • Public-key algorithms 81 • Hybrid 82 83 [Core-Tier2] 84 • Network attack types: Denial of service, flooding, sniffing and traffic redirection, message integrity attacks, 85 • Identity hijacking, exploit attacks (buffer overruns, Trojans, backdoors), inside attacks, infrastructure (DNS 86 hijacking, route blackholing, misbehaving routers that drop traffic), etc.) 87 • Authentication protocols 88 • Digital signatures 89 • Message Digest 90 • Defense Mechanisms /Countermeasures. (Intrusion Detection, Firewalls, Detection of malware, IPSec, 91 Virtual Private Networks, Network Address Translation.) 92 • Network Auditing. 93 94 Learning outcomes: 95 1. Identify protocols used to enhance Internet communication, and choose the appropriate protocol for a 96 particular [Knowledge] 97 2. Discuss the difference between secret key and public key encryption. [Knowledge] - 80 - 98 3. Discuss the fundamental ideas of public-key cryptography. [Knowledge] 99 4. Discuss the role of a certificate authority in public-key cryptography. [Knowledge] 100 5. Discuss non-repudiation [Knowledge] 101 6. Describe a digital signature[Knowledge] 102 7. Describe how public key encryption is used to encrypt email traffic. [Knowledge] 103 8. Generate and distribute a PGP key pair and use the PGP package to send an encrypted e-mail message. 104 [Application] 105 9. Describe how public key encryption is used to secure HTTP traffic. [Knowledge] 106 10. Describe the security risks present in networking. [Knowledge] 107 11. Discuss the differences in Network Intrusion Detection and Network Intrusion Prevention. [Knowledge] 108 12. Describe how the basic security implications of a hub and a switch. [Knowledge] 109 13. Describe how a system can intercept traffic in a local subnet. [Knowledge] 110 14. Describe different implementations for intrusion detection. [Knowledge] 111 15. Identify a buffer overflow vulnerability in code [Evaluation] 112 16. Correct a buffer overflow error in code [Application] 113 17. Describe the methods that can be used to alert that a system has a backdoor installed. [Knowledge] 114 18. Describe the methods that can be used to identify a system is running processes not desired be the system 115 owner. [Knowledge] 116 19. Analyze a port listing for unwanted TCP/UDP listeners. [Application] 117 20. Describe the difference between non-routable and routable IP addresses. [Knowledge] 118 21. List the class A, B, and C non-routable IP ranges. [Knowledge] 119 22. Describe the difference between stateful and non-stateful firewalls. [Knowledge] 120 23. Implement firewalls to prevent specific IP’s or ports from traversing the firewall. [Application] 121 24. Describe the different actions a firewall can take with a packet. [Knowledge] 122 25. Summarize common authentication protocols. [Knowledge] 123 26. Describe and discuss recent successful security attacks. [Knowledge] 124 27. Summarize the strengths and weaknesses associated with different approaches to security. [Knowledge] 125 28. Describe what a message digest is and how it is commonly used. [Knowledge] 126 127 IAS/ Cryptography 128 [Elective] 129 Topics: 130 • The Basic Cryptography Terminology covers notions pertaining to the different (communication) partners, 131 secure/unsecure channel, attackers and their capabilities, encryption, decryption, keys and their 132 characteristics, signatures, etc. 133 • Cipher types:, Caesar cipher, affine cipher, etc. together with typical attack methods such as frequency 134 analysis, etc. 135 • Mathematical Preliminaries; include topics in linear algebra, number theory, probability theory, and 136 statistics. (Discrete Structures) 137 • Cryptographic Primitives include encryption (stream ciphers, block ciphers public key encryption), digital 138 signatures, message authentication codes, and hash functions. 139 • Cryptanalysis covers the state-of-the-art methods including differential cryptanalysis, linear cryptanalysis, 140 factoring, solving discrete logarithm problem, lattice based methods, etc. 141 • Cryptographic Algorithm Design covers principles that govern the design of the various cryptographic 142 primitives, especially block ciphers and hash functions. (Algorithms and Complexity - Hash functions) 143 • The treatment of Common Protocols includes (but should not be limited to) current protocols such as RSA, 144 DES, DSA, AES, ElGamal, MD5, SHA-1, Diffie-Hellman Key exchange, identification and authentication 145 protocols, secret sharing, multi-party computation, etc. 146 • Public Key Infrastructure deals with challenges, opportunities, local infrastructures, and national 147 infrastructure. 148 - 81 - 149 Learning outcomes: 150 1. What is the purpose of Cryptography? [Knowledge] 151 2. What is plain text? [Knowledge] 152 3. What is cipher text? [Knowledge] 153 4. What are the two basic methods (ciphers) for transforming plain text in cipher text? [Knowledge] 154 5. Describe attacks against a specified cypher. [Knowledge] 155 6. Define the following terms: Cipher, Cryptanalysis, Cryptographic Algorithm, Cryptology. [Knowledge] 156 7. What is the Work Function of a given cryptographic algorithm? [Knowledge] 157 8. What is a One Time Pad (Vernam Cipher)? [Knowledge] 158 9. What is a Symmetric Key operation? [Knowledge] 159 10. What is an Asymmetric Key operation? [Knowledge] 160 11. For a given problem and environment weigh the tradeoffs between a Symmetric and Asymmetric key 161 operation. [Evaluation] 162 12. What are common Symmetric Key algorithms? [Knowledge] 163 13. Explain in general how a public key algorithm works. [Knowledge] 164 14. How does “key recovery” work? [Knowledge] 165 15. List 5 public key algorithms. [Knowledge] 166 16. Describe the process in the Diffie-Hellman key exchange. [Knowledge] 167 17. What is a message digest and list 4 common algorithms? [Knowledge] 168 18. What is a digital signature and how is one created? [Knowledge] 169 19. What the three components of a PKI? [Knowledge] 170 20. List the ways a PKI infrastructure can be attacked. [Knowledge] 171 172 IAS/Risk Management 173 [Elective] 174 Topics: 175 • Risk Analysis involves identifying the assets, probable threats, vulnerabilities and control measures to 176 discern risk levels and likelihoods. It can be applied to a program, organization, sector, etc. Knowledge in 177 this area includes knowing different risk analysis models and methods, their strengths and benefits and the 178 apropriateness of the different methods and models given the situation. This includes periodic 179 reassessment. 180 • Cost/Benefit Analysis is used to weigh private and/or public costs versus benefits and can be applied to 181 security policies, investments, programs, tools, deployments, etc. 182 • Continuity Planning will help organizations deliver critical services and ensure survival. 183 • Disaster Recovery will help an organization continue normal operations in a minimum amount of time with 184 a minimum amount of disruption and cost. 185 • Security Auditing: a systematic assessment of an organization’s system measuring the conformity vis-àvis a 186 set of pre-established criteria. 187 • Asset Management minimizes the life cost of assets and includes critical factors such as risk or business 188 continuity. 189 • Risk communication Enforcement of risk management policies is critical for an organization. 190 191 Learning outcomes: 192 1. How is risk determined? [Knowledge] 193 2. What does it mean to manage risk? [Knowledge] 194 3. What is the primary purpose of risk management? [Knowledge] 195 4. Who can accept Risk? [Knowledge] 196 5. What is the objective of Security Controls in security management? [Knowledge] 197 6. With respect to a risk program, what is an Asset? [Knowledge] 198 7. With respect to a risk program, what is a Threat? [Knowledge] - 82 - 199 8. With respect to a risk program, what is a Vulnerability? [Knowledge] 200 9. With respect to a risk program, what is a Safeguard? [Knowledge] 201 10. With respect to a risk program, what is the Exposure Factor (EF)? [Knowledge] 202 11. What is the difference between Quantitative Risk Analysis and Qualitative Risk Analysis? [Knowledge] 203 12. How does an organization determine what safeguards or controls to implement? [Knowledge] 204 13. Given the value of an asset and the cost of the security controls to mitigate loss/damage/destruction, is the 205 security plan appropriate? [Evaluation] 206 14. What is Risk Analysis (RA)? [Knowledge] 207 15. Describe how data is classified in either (government or commercial)? [Knowledge] 208 16. When are the factors used when determining the classification of a piece of information? [Knowledge] 209 17. What are three ways to deal with Risk? [Knowledge] 210 211 212 IAS/Security Policy and Governance 213 [Elective] 214 Topics: 215 • Strategies and Plans for creating security policies. 216 • Policies, Guidelines, Standards and Best Practices for individuals or organizations, including national 217 security policies. 218 • Procedures for creating policies, guidelines, standards, specifications, regulations and laws. 219 • Privacy Policies to help protect personal and other sensitive information. 220 • Compliance and Enforcement of policies, standards, regulations, and laws. 221 • Formal Policy Models such as Bell-LaPadula, Biba and Clark-Wilson, which provide precise specifications 222 of security objectives. 223 • Relation of national security policies, regulations, organizational security policies, formal policy models, 224 and policy languages. 225 • Policy as related to Risk Aversion. 226 227 Learning outcomes: 228 1. What is a security policy and why does an organization need a security policy? [Knowledge] 229 2. Come up with an example of your own, which would be caused by missing security policies.[Application] 230 3. What are the basic things that need to be explained to every employee about a security policy? At what 231 point in their employment? Why? [Application] 232 4. Say you have an e-mail server that processes sensitive emails from important people. What kind of things 233 should be put into the security policy for the email server? [Evaluation] 234 5. Read your institution’s security plan and critique the plan. [Evaluation] 235 6. Update your institution’s security plan. [Evaluation] 236 237 IAS/ Digital Forensics 238 [Elective] 239 Topics: 240 • Basic Principles and methodologies for digital forensics. 241 • Rules of Evidence – general concepts and differences between jurisdictions and Chain of Custody. 242 • Search and Seizure of evidence, e.g., computers, including search warrant issues. 243 • Digital Evidence methods and standards. 244 • Techniques and standards for Preservation of Data. - 83 - 245 • Data analysis and validation. 246 • Legal and Reporting Issues including working as an expert witness. 247 • OS/File System Forensics 248 • Application Forensics 249 • Network Forensics 250 • Mobile Device Forensics 251 • Computer/network/system attacks. 252 253 Learning outcomes: 254 1. What is a Digital Investigation? [Knowledge] 255 2. What systems in an IT infrastructure might have forensically recoverable data? [Knowledge] 256 3. Who in an organization is authorized to permit the conduct of a forensics investigation? [Knowledge] 257 4. What is the Rule of Evidence? [Knowledge] 258 5. What is a Chain of Custody? [Knowledge] 259 6. Conduct a data collection on a hard drive. [Application] 260 7. Validate the integrity of a digital forensics data set. [Application] 261 8. Determine if a digital investigation is sound. [Evaluation] 262 9. Describe the file system structure for a given device (NTFA, MFS, iNode, HFS…) [Knowledge] 263 10. Determine if a certain string of data exists on a hard drive. [Application] 264 11. Describe the capture of live data for a forensics investigation. [Knowledge] 265 12. Capture and interpret network traffic. [Application] 266 13. Discuss identity management and its role in access control systems. [Knowledge] 267 14. Determine what user was logged onto a given system at a given time. [Application] 268 15. Determine the submissability (from a legal perspective) of data. [Evaluation] 269 16. Evaluate a system for the presence of malware. [Evaluation] 270 271 - 84 - 272 IAS/Security Architecture and Systems Administration 273 [Elective] 274 Topics: 275 • How to secure Hardware, including how to make hardware tokens and chip cards tamper-proof and tamper- 276 resistance. 277 • Configuring systems to operate securely as an IT system. 278 • Access Control 279 • Basic Principles of an access control system prevent unauthorized access. 280 • Physical Access Control determines who is allowed to enter or exit, where the user is allowed to enter or 281 exit, and when the user is allowed to enter or exit. 282 • Technical/System Access Control is the process of preventing unauthorized users or services to utilize 283 information systems. 284 • Usability includes the difficulty for humans to deal with security (e.g., remembering PINs), social 285 engineering, phishing, and other similar attacks. 286 • Analyzing and identifying System Threats and Vulnerabilities 287 • Investigating Operating Systems Security for various systems. 288 • Multi-level/Multi-lateral Security 289 • Design and Testing for architectures and systems of different scale 290 • Penetration testing in the system setting 291 • Products available in the marketplace 292 • Supervisory Control and Data Acquisition (SCADA) 293 • SCADA system uses. Communications protocols supporting data acquisition 294 • Communications protocols supporting distributed control. 295 • Data Integrity 296 • Data Confidentiality 297 298 Learning outcomes: 299 1. Explain the need for software security and how software security is different from security features like 300 access control or cryptography. [Knowledge] 301 2. Understand common threats to web applications and common vulnerabilities written by developers. 302 [Knowledge] 303 3. Define least privilege. [Knowledge] 304 4. Define “Defense in Depth”. [Knowledge] 305 5. Define service isolation in the context of enterprise systems. [Knowledge] 306 6. Architect an enterprise system using the concept of service isolation. [Application] 307 7. Describe the methods to provide for access control and what enterprise services must exist. [Knowledge] 308 8. Discuss how user systems integrate into an enterprise environment. [Knowledge] 309 9. Discuss the risks client systems pose to an enterprise environment. [Knowledge] 310 10. Describe various methods to manage client systems. [Knowledge] 311 11. Create a risk model of a web application, ranking and detailing the risks to the system’s assets. 312 [Application] 313 12. Construct, document, and analyze security requirements with abuse cases and constraints. [Application] 314 13. Apply secure design principles, such as least privilege, to the design of a web application. [Application] 315 14. Validate both the input and output of a web application. [Application] 316 15. Use cryptography appropriately, including SSL and certificate management. [Application] 317 16. Create a test plan and conduct thorough testing of web applications with appropriate software assistance. 318 [Application] 319 320 - 85 - 321 IAS/Secure Software Design and Engineering 322 [Elective] 323 Fundamentals of secure coding practices covered in other knowledge areas, including 324 SDF/SE/PL. 325 Topics: 326 • Building security into the Software Development Lifecycle 327 • Secure Design Principles and Patterns (Saltzer and Schroeder, etc) 328 • Secure Software Specification and Requirements deals with specifying what the program should and should 329 not do, which can be done either using a requirements document or using a more formal mathematical 330 specification. 331 • Secure Coding involves applying the correct balance of theory and practice to minimize vulnerabilities in 332 code. 333 • Data validation 334 • Memory handling 335 • Crypto implementation 336 • Secure Testing is the process of testing that security requirements are met (including Static and Dynamic 337 analysis). 338 • Program Verification and Simulation is the process of ensuring that a certain version of a certain 339 implementation meets the required security goals, either by a mathematical proof or by simulation. 340 341 Learning outcomes: 342 1. Describe the Design Principles for Protection Mechanisms (Saltzer and Schroeder ) [Knowledge] 343 2. Describe the Principles for Software Security (Viega and McGraw) [Knowledge] 344 3. Define Principles for a Secure Design (Morrie Gasser) [Knowledge] 345 4. Compare the principles for software and systems in the context of a software development effort. 346 [Application] 347 5. Discuss the benefits and drawbacks of open-source vs proprietary software and security [Knowledge] 348 6. Integrate trustworthy development practices into an existing software development lifecycle [Application] 349 7. Integrate authenticating libraries, DLL, run-time [Application] 350 8. Identify a buffer overflow in a code sample [Knowledge] 351 9. Describe the difference between static and dynamic analysis. [Knowledge] 352 10. Conduct static analysis to determine the security posture of a given application. [Application] 353 11. Monitor the execution of a software (dynamic analysis) and discuss the observed process flows. 354 [Application] 355 12. How is quality assurance conducted for software development? [Knowledge] 356 13. Participate in a code review focused on finding security bugs using static analysis tools. [Application] 357 14. Where does patch management fit in a software development project? [Knowledge] - 86 - 1 Information Management (IM) 2 Information Management (IM) is primarily concerned with the capture, digitization, 3 representation, organization, transformation, and presentation of information; algorithms for 4 efficient and effective access and updating of stored information, data modeling and abstraction, 5 and physical file storage techniques. The student needs to be able to develop conceptual and 6 physical data models, determine what IM methods and techniques are appropriate for a given 7 problem, and be able to select and implement an appropriate IM solution that addresses relevant 8 design concerns including scalability, accessibility and usability. 9 IM. Information Management (1 Core-Tier1 hour; 9 Core-Tier2 hours) Core-Tier1 hours Core-Tier2 hours Includes Electives IM/Information Management Concepts 1 2 N IM/Database Systems 3 N IM/Data Modeling 4 N IM/Indexing Y IM/Relational Databases Y IM/Query Languages Y IM/Transaction Processing Y IM/Distributed Databases Y IM/Physical Database Design Y IM/Data Mining Y IM/Information Storage And Retrieval Y 10 11 IM/Information Management Concepts 12 [1 Core-Tier1 hour; 2 Core-Tier2 hours] 13 Topics: 14 [Core-Tier1] 15 • Basic information storage and retrieval (IS&R) concepts 16 • Information capture and representation 17 • Supporting human needs: Searching, retrieving, linking, browsing, navigating 18 19 20 [Core-Tier2] 21 • Information management applications 22 • Declarative and navigational queries, use of links 23 • Analysis and indexing 24 • Quality issues: Reliability, scalability, efficiency, and effectiveness 25 26 Learning Outcomes: 27 1. Describe how humans gain access to information and data to support their needs [Knowledge] 28 2. Compare and contrast information with data and knowledge [Analysis] 29 3. Demonstrate uses of explicitly stored metadata/schema associated with data [Application] 30 4. Identify issues of data persistence to an organization [Knowledge] 31 5. Critique/defend a small- to medium-size information application with regard to its satisfying real user 32 information needs [Evaluation] 33 6. Explain uses of declarative queries [Knowledge] 34 7. Give a declarative version for a navigational query [Knowledge] 35 8. Describe several technical solutions to the problems related to information privacy, integrity, security, and 36 preservation [Knowledge] 37 9. Explain measures of efficiency (throughput, response time) and effectiveness (recall, precision) 38 [Knowledge] 39 10. Describe approaches that scale up to globally networked systems [Knowledge] 40 11. Identify vulnerabilities and failure scenarios in common forms of information systems [Knowledge] 41 42 IM/Database Systems 43 [3 Core-Tier2 hours] 44 Topics: 45 [Core-Tier2] 46 • Approaches to and evolution of database systems 47 • Components of database systems 48 • DBMS functions 49 • Database architecture and data independence 50 • Use of a declarative query language 51 • Systems supporting structured and/or stream content 52 53 Learning Outcomes: 54 1. Explain the characteristics that distinguish the database approach from the traditional approach of 55 programming with data files [Knowledge] 56 2. Cite the basic goals, functions, models, components, applications, and social impact of database systems 57 [Knowledge] 58 3. Describe the components of a database system and give examples of their use [Knowledge] 59 4. Identify major DBMS functions and describe their role in a database system [Knowledge] 60 5. Explain the concept of data independence and its importance in a database system [Knowledge] 61 6. Use a declarative query language to elicit information from a database [Application] 62 7. Describe how various types of content cover the notions of structure and/or of stream (sequence), e.g., 63 documents, multimedia, tables [Knowledge] 64 65 - 88 - 66 IM/Data Modeling 67 [4 Core-Tier2 hours] 68 Topics: 69 [Core-Tier2] 70 • Data modeling 71 • Conceptual models (e.g., entity-relationship and UML diagrams) 72 • Relational data model 73 • Object-oriented model 74 • Semi-structured data model (expressed using DTD or XML Schema, for example) 75 76 Learning Outcomes: 77 1. Categorize data models based on the types of concepts that they provide to describe the database 78 structure—that is, conceptual data model, physical data model, and representational data model 79 [Comprehension] 80 2. Describe the modeling concepts and notation of widely used modeling notation (e.g., ERD notation, and 81 UML), including their use in data modeling [Knowledge] 82 3. Define the fundamental terminology used in the relational data model [Knowledge] 83 4. Describe the basic principles of the relational data model [Knowledge] 84 5. Apply the modeling concepts and notation of the relational data model [Application] 85 6. Describe the main concepts of the OO model such as object identity, type constructors, encapsulation, 86 inheritance, polymorphism, and versioning [Knowledge] 87 7. Describe the differences between relational and semi-structured data models [Knowledge] 88 8. Give a semi-structured equivalent (e.g., in DTD or XML Schema) for a given relational schema 89 [Application] 90 91 IM/Indexing 92 [Elective] 93 Topics: 94 • The impact of indexes on query performance 95 • The basic structure of an index; [Robert: Not sure if this warrants a topic by itself] 96 • Keeping a buffer of data in memory; [Robert: Why is this listed as a topic?] 97 • Creating indexes with SQL 98 • Indexing text 99 • Indexing the web (how search engines work) 100 101 Learning Outcomes: 102 1. Generate an index file for a collection of resources. 103 2. Explain the role of an inverted index in locating a document in a collection 104 3. Explain how stemming and stop words affect indexing 105 4. Identify appropriate indices for given relational schema and query set 106 5. Estimate time to retrieve information, when indices are used compared to when they are not used. 107 108 - 89 - 109 IM/Relational Databases 110 [Elective] 111 Topics: 112 Elective 113 • Mapping conceptual schema to a relational schema 114 • Entity and referential integrity 115 • Relational algebra and relational calculus 116 • Relational Database design 117 • Functional dependency 118 • Decomposition of a schema; lossless-join and dependency-preservation properties of a decomposition 119 • Candidate keys, superkeys, and closure of a set of attributes 120 • Normal forms (1NF, 2NF, 3NF, BCNF) 121 • Multi-valued dependency (4NF) 122 • Join dependency (PJNF, 5NF) 123 • Representation theory 124 125 Learning Outcomes: 126 1. Prepare a relational schema from a conceptual model developed using the entity- relationship model 127 2. Explain and demonstrate the concepts of entity integrity constraint and referential integrity constraint 128 (including definition of the concept of a foreign key). 129 3. Demonstrate use of the relational algebra operations from mathematical set theory (union, intersection, 130 difference, and Cartesian product) and the relational algebra operations developed specifically for relational 131 databases (select (restrict), project, join, and division). 132 4. Demonstrate queries in the relational algebra. 133 5. Demonstrate queries in the tuple relational calculus. 134 6. Determine the functional dependency between two or more attributes that are a subset of a relation. 135 7. Connect constraints expressed as primary key and foreign key, with functional dependencies 136 8. Compute the closure of a set of attributes under given functional dependencies 137 9. Determine whether or not a set of attributes form a superkey and/or candidate key for a relation with given 138 functional dependencies 139 10. Evaluate a proposed decomposition, to say whether or not it has lossless-join and dependency-preservation 140 11. Describe what is meant by 1NF, 2NF, 3NF, and BCNF. 141 12. Identify whether a relation is in 1NF, 2NF, 3NF, or BCNF. 142 13. Normalize a 1NF relation into a set of 3NF (or BCNF) relations and denormalize a relational schema. 143 14. Explain the impact of normalization on the efficiency of database operations, especially query optimization. 144 15. Describe what is a multivalued dependency and what type of constraints it specifies. 145 16. Explain why 4NF is useful in schema design. 146 147 - 90 - 148 IM/Query Languages 149 [Elective] 150 Topics: 151 • Overview of database languages 152 • SQL (data definition, query formulation, update sublanguage, constraints, integrity) 153 • QBE and 4th-generation environments 154 • Embedding non-procedural queries in a procedural language 155 • Introduction to Object Query Language 156 • Stored procedures 157 158 Learning Outcomes: 159 1. Create a relational database schema in SQL that incorporates key, entity integrity, and referential integrity 160 constraints. 161 2. Demonstrate data definition in SQL and retrieving information from a database using the SQL SELECT 162 statement. 163 3. Evaluate a set of query processing strategies and select the optimal strategy. 164 4. Create a non-procedural query by filling in templates of relations to construct an example of the desired 165 query result. 166 5. Embed object-oriented queries into a stand-alone language such as C++ or Java (e.g., SELECT 167 Col.Method() FROM Object). 168 6. Write a stored procedure that deals with parameters and has some control flow, to provide a given 169 functionality 170 171 IM/Transaction Processing 172 [Elective] 173 Topics: 174 • Transactions 175 • Failure and recovery 176 • Concurrency control 177 178 Learning Outcomes: 179 1. Create a transaction by embedding SQL into an application program. 180 2. Explain the concept of implicit commits. 181 3. Describe the issues specific to efficient transaction execution. 182 4. Explain when and why rollback is needed and how logging assures proper rollback. 183 5. Explain the effect of different isolation levels on the concurrency control mechanisms. 184 6. Choose the proper isolation level for implementing a specified transaction protocol. 185 186 - 91 - 187 IM/Distributed Databases 188 [Elective] 189 Topics: 190 • Distributed data storage 191 • Distributed query processing 192 • Distributed transaction model 193 • Concurrency control 194 • Homogeneous and heterogeneous solutions 195 • Client-server distributed databases (cross-reference SF/Computational Paradigms) 196 197 Learning Outcomes: 198 1. Explain the techniques used for data fragmentation, replication, and allocation during the distributed 199 database design process. 200 2. Evaluate simple strategies for executing a distributed query to select the strategy that minimizes the amount 201 of data transfer. 202 3. Explain how the two-phase commit protocol is used to deal with committing a transaction that accesses 203 databases stored on multiple nodes. 204 4. Describe distributed concurrency control based on the distinguished copy techniques and the voting 205 method. 206 5. Describe the three levels of software in the client-server model. 207 208 IM/Physical Database Design 209 [Elective] 210 Topics: 211 • Storage and file structure 212 • Indexed files 213 • Hashed files 214 • Signature files 215 • B-trees 216 • Files with dense index 217 • Files with variable length records 218 • Database efficiency and tuning 219 220 Learning Outcomes: 221 1. Explain the concepts of records, record types, and files, as well as the different techniques for placing file 222 records on disk. 223 2. Give examples of the application of primary, secondary, and clustering indexes. 224 3. Distinguish between a non-dense index and a dense index. 225 4. Implement dynamic multilevel indexes using B-trees. 226 5. Explain the theory and application of internal and external hashing techniques. 227 6. Use hashing to facilitate dynamic file expansion. 228 7. Describe the relationships among hashing, compression, and efficient database searches. 229 8. Evaluate costs and benefits of various hashing schemes. 230 9. Explain how physical database design affects database transaction efficiency. 231 - 92 - 232 IM/Data Mining 233 [Elective] 234 Topics: 235 • The usefulness of data mining 236 • Data mining algorithms 237 • Associative and sequential patterns 238 • Data clustering 239 • Market basket analysis 240 • Data cleaning 241 • Data visualization 242 243 Learning Outcomes: 244 1. Compare and contrast different conceptions of data mining as evidenced in both research and application. 245 2. Explain the role of finding associations in commercial market basket data. 246 3. Characterize the kinds of patterns that can be discovered by association rule mining. 247 4. Describe how to extend a relational system to find patterns using association rules. 248 5. Evaluate methodological issues underlying the effective application of data mining. 249 6. Identify and characterize sources of noise, redundancy, and outliers in presented data. 250 7. Identify mechanisms (on-line aggregation, anytime behavior, interactive visualization) to close the loop in 251 the data mining process. 252 8. Describe why the various close-the-loop processes improve the effectiveness of data mining. 253 254 IM/Information Storage and Retrieval 255 [Elective] 256 Topics: 257 • Characters, strings, coding, text 258 • Documents, electronic publishing, markup, and markup languages 259 • Tries, inverted files, PAT trees, signature files, indexing 260 • Morphological analysis, stemming, phrases, stop lists 261 • Term frequency distributions, uncertainty, fuzziness, weighting 262 • Vector space, probabilistic, logical, and advanced models 263 • Information needs, relevance, evaluation, effectiveness 264 • Thesauri, ontologies, classification and categorization, metadata 265 • Bibliographic information, bibliometrics, citations 266 • Routing and (community) filtering 267 • Search and search strategy, multimedia search, information seeking behavior, user modeling, feedback 268 • Information summarization and visualization 269 • Integration of citation, keyword, classification scheme, and other terms 270 • Protocols and systems (including Z39.50, OPACs, WWW engines, research systems) 271 • Digital libraries 272 • Digitization, storage, interchange, digital objects, composites, and packages 273 • Metadata, cataloging, author submission 274 • Naming, repositories, archives 275 • Spaces (conceptual, geographical, 2/3D, VR) 276 • Architectures (agents, buses, wrappers/mediators), interoperability 277 • Services (searching, linking, browsing, and so forth) - 93 - 278 • Intellectual property rights management, privacy, and protection (watermarking) 279 • Archiving and preservation, integrity 280 281 Learning Outcomes: 282 1. Explain basic information storage and retrieval concepts. 283 2. Describe what issues are specific to efficient information retrieval. 284 3. Give applications of alternative search strategies and explain why the particular search strategy is 285 appropriate for the application. 286 4. Perform Internet-based research. 287 5. Design and implement a small to medium size information storage and retrieval system, or digital library. 288 6. Describe some of the technical solutions to the problems related to archiving and preserving information in 289 a digital library. - 94 - 1 Intelligent Systems (IS) 2 Artificial intelligence (AI) is the study of solutions for problems that are difficult or impractical to solve with 3 traditional methods. It is used pervasively in support of everyday applications such as email, word-processing and 4 search, as well as in the design and analysis of autonomous agents that perceive their environment and interact 5 rationally with the environment. 6 The solutions rely on a broad set of general and specialized knowledge representation schemes, problem 7 solving mechanisms and learning techniques. They deal with sensing (e.g., speech recognition, natural language 8 understanding, computer vision), problem-solving (e.g., search, planning), and acting (e.g., robotics) and the 9 architectures needed to support them (e.g,. agents, multi-agents). The study of Artificial Intelligence prepares the 10 student to determine when an AI approach is appropriate for a given problem, identify the appropriate representation 11 and reasoning mechanism, and implement and evaluate it. 12 13 IS. Intelligent Systems (10 Core-Tier2 hours) Core-Tier1 Core-Tier2 Includes hours hours Electives IS/Fundamental Issues 1 Y IS/Basic Search Strategies 4 N IS/Basic Knowledge Representation and 3 N Reasoning IS/Basic Machine Learning 2 N IS/Advanced Search Y IS/Advanced Representation and Reasoning Y IS/Reasoning Under Uncertainty Y IS/Agents Y IS/Natural Language Processing Y IS/Advanced Machine Learning Y IS/Robotics Y IS/Perception and Computer Vision Y 14 15 16 17 IS/Fundamental Issues 18 [1 Core-Tier2 hours] 19 Topics: 20 • Overview of AI problems, Examples of successful recent AI applications 21 • What is intelligent behavior? 22 • The Turing test 23 • Rational versus non-rational reasoning 24 • Nature of human reasoning 25 • Nature of environments 26 • Fully versus partially observable 27 • Single versus multi-agent 28 • Deterministic versus stochastic 29 • Episodic versus sequential 30 • Static versus dynamic 31 • Discrete versus continuous 32 • Nature of Agents 33 • Autonomous versus Semi-Autonomous 34 • Reflexive, Goal-based, and Utility-based 35 • The importance of perception and environmental interactions 36 • Philosophical and ethical issues [elective] 37 38 Learning Outcomes: 39 1. Describe Turing test and the “Chinese Room” thought experiment. [Knowledge] 40 2. Differentiate between the concepts of optimal reasoning/behavior and human-like reasoning/behavior. 41 [Knowledge] 42 3. Describe a given problem domain using the characteristics of the environments in which intelligent systems 43 must function. [Evaluation] 44 45 IS/Basic Search Strategies 46 [4 Core-Tier2 hours] 47 (Cross-reference AL/Basic Analysis, AL/Algorithmic Strategies, AL/Fundamental Data 48 Structures and Algorithms) 49 Topics: 50 • Problem spaces (states, goals and operators), problem solving by search 51 • Factored representation (factoring state into variables) 52 • Uninformed search (breadth-first, depth-first, depth-first with iterative deepening) 53 • Heuristics and informed search (hill-climbing, generic best-first, A*) 54 • Space and time efficiency of search 55 • Two-player games (Introduction to minimax search) 56 • Constraint satisfaction (backtracking and local search methods) 57 58 - 96 - 59 Learning Outcomes: 60 1. Formulate an efficient problem space for a problem expressed in natural language (e.g., English) in terms 61 of initial and goal states, and operators. [Application] 62 2. Describe the role of heuristics and describe the trade-offs among completeness, optimality, time 63 complexity, and space complexity. [Knowledge] 64 3. Describe the problem of combinatorial explosion of search space and its consequences. [Knowledge] 65 4. Select and implement an appropriate uninformed search algorithm for a problem, and characterize its time 66 and space complexities. [Evaluation, Application] 67 5. Select and implement an appropriate informed search algorithm for a problem by designing the necessary 68 heuristic evaluation function. [Evaluation, Application] 69 6. Evaluate whether a heuristic for a given problem is admissible/can guarantee optimal solution. [Evaluation] 70 7. Formulate a problem specified in natural language (e.g., English) as a constraint-satisfaction problem and 71 implement it using a chronological backtracking algorithm or stochastic local search. [Application] 72 8. Compare and contrast basic search issues with game playing issues [Knowledge] 73 74 IS/Basic Knowledge Representation and Reasoning 75 [3 Core-Tier2 hours] 76 Topics: 77 • Review of propositional and predicate logic (cross-reference DS/Basic Logic) 78 • Resolution and theorem proving, unification and lifting (propositional logic only) 79 • Forward chaining, backward chaining 80 • Review of probabilistic reasoning, Bayes theorem (cross-reference with DS/Discrete Probability) 81 82 Learning Outcomes: 83 1. Translate a natural language (e.g., English) sentence into predicate logic statement. [Application] 84 2. Convert a quantified logic statement into clause form. [Application] 85 3. Apply resolution to a set of logic statements to answer a query. [Application] 86 4. Apply Bayes theorem to determine conditional probabilities in a problem. [Application] 87 88 IS/Basic Machine Learning 89 [2 Core-Tier2 hours] 90 Topics: 91 • Definition and examples of machine learning for classification 92 • Inductive learning 93 • Simple statistical-based learning such as Naive Bayesian Classifier, Decision trees 94 • Define overfitting problem 95 • Measuring classifier accuracy 96 97 Learning Outcomes: 98 1. Identify examples of classification tasks, including the available input features and output to be predicted. 99 [Knowledge] 100 2. Explain the difference between inductive and deductive learning. [Knowledge] 101 3. Apply the simple statistical learning algorithm such as Naive Bayesian Classifier to a classification task and 102 measure the classifier's accuracy. [Application] 103 - 97 - 104 IS/Advanced Search 105 [Elective] 106 Topics: 107 • Constructing search trees, dynamic search space, combinatorial explosion of search space 108 • Stochastic search 109 • Simulated annealing 110 • Genetic algorithms 111 • A* search, Beam search 112 • Minimax Search, Alpha-beta pruning 113 • Expectimax search (MDP-solving) and chance nodes 114 115 Learning Outcomes: 116 1. Design and implement a genetic algorithm solution to a problem. [Application] 117 2. Design and implement a simulated annealing schedule to avoid local minima in a problem. [Application] 118 3. Design and implement A*/beam search to solve a problem. [Application] 119 4. Apply minimax search with alpha-beta pruning to prune search space in a two-player game. [Application] 120 5. Compare and contrast genetic algorithms with classic search techniques. [Evaluation] 121 6. Compare and contrast various heuristic searches vis-a-vis applicability to a given problem. [Evaluation] 122 123 IS/Advanced Representation and Reasoning 124 [Elective] 125 Topics: 126 • Knowledge representation issues 127 • Description logics 128 • Ontology engineering 129 • Non-monotonic reasoning 130 • Non-classical logics 131 • Default reasoning 132 • Belief revision 133 • Preference logics 134 • Integration of knowledge sources 135 • Aggregation of conflicting belief 136 • Reasoning about action and change 137 • Situation calculus 138 • Event calculus 139 • Ramification problems 140 • Temporal and spatial reasoning 141 • Rule-based Expert Systems 142 • Model-based and Case-based reasoning 143 • Planning: 144 • Partial and totally ordered planning 145 • Plan graphs 146 • Hierarchical planning 147 • Planning and execution including conditional planning and continuous planning 148 • Mobile agent/Multi-agent planning 149 - 98 - 150 Learning Outcomes: 151 1. Compare and contrast the most common models used for structured knowledge representation, highlighting 152 their strengths and weaknesses. [Evaluation] 153 2. Identify the components of non-monotonic reasoning and its usefulness as a representational mechanisms 154 for belief systems. [Knowledge] 155 3. Compare and contrast the basic techniques for representing uncertainty. [Knowledge, Evaluation] 156 4. Compare and contrast the basic techniques for qualitative representation. [Knowledge, Evaluation] 157 5. Apply situation and event calculus to problems of action and change. [Application] 158 6. Explain the distinction between temporal and spatial reasoning, and how they interrelate. [Knowledge, 159 Evaluation] 160 7. Explain the difference between rule-based, case-based and model-based reasoning techniques. [Knowledge, 161 Evaluation] 162 8. Define the concept of a planning system and how they differ from classical search techniques. [Knowledge, 163 Evaluation] 164 9. Describe the differences between planning as search, operator-based planning, and propositional planning, 165 providing examples of domains where each is most applicable. [Knowledge, Evaluation] 166 10. Explain the distinction between monotonic and non-monotonic inference. [Knowledge] 167 168 IS/Reasoning Under Uncertainty 169 [Elective] 170 Topics: 171 • Review of basic probability (cross-reference DS/Discrete Probability) 172 • Unconditional/prior probabilities 173 • Conditional/posterior probabilities 174 • Random variables and probability distributions 175 • Axioms of probability 176 • Probabilistic inference 177 • Bayes’ Rule 178 • Conditional Independence 179 • Knowledge representations 180 • Bayesian Networks 181 • Exact inference and its complexity 182 • Randomized sampling (Monte Carlo) methods (e.g. Gibbs sampling) 183 • Markov Networks 184 • Relational probability models 185 • Hidden Markov Models 186 • Decision Theory 187 • Preferences and utility functions 188 • Maximizing expected utility 189 190 Learning Outcomes: 191 1. Apply Bayes’ rule to determine the probability of a hypothesis given evidence. [Application] 192 2. Explain how conditional independence assertions allow for greater efficiency of probabilistic systems. 193 [Evaluation] 194 3. Identify examples of knowledge representations for reasoning under uncertainty. [Knowledge] 195 4. State the complexity of exact inference. Identify methods for approximate inference. [Knowledge] 196 5. Design and implement at least one knowledge representation for reasoning under uncertainty. [Application] 197 6. Describe the complexities of temporal probabilistic reasoning. [Knowledge] 198 7. Explain the complexities of temporal probabilistic reasoning. [Evaluation] - 99 - 199 8. Design and implement an HMM as one example of a temporal probabilistic system. [Application] 200 9. Describe the relationship between preferences and utility functions. [Knowledge] 201 10. Explain how utility functions and probabilistic reasoning can be combined to make rational decisions. 202 [Evaluation] 203 204 IS/Agents 205 [Elective] 206 (Cross-reference HC/Collaboration and Communication) 207 Topics: 208 • Definitions of agents 209 • Agent architectures 210 • Simple reactive agents 211 • Reactive planners 212 • Layered architectures 213 • Cognitive architectures 214 • Integrated architecture 215 • Example architectures and applications 216 • Agent theory 217 • Rationality, Game Theory 218 • Commitments 219 • Intentions 220 • Decision-theoretic agents 221 • Markov decision processes (MDP) 222 • Software agents, personal assistants, and information access 223 • Collaborative agents 224 • Information-gathering agents 225 • Believable agents (synthetic characters, modeling emotions in agents) 226 • Learning agents 227 • Multi-agent systems 228 • Collaborating agents 229 • Agent teams 230 • Competitive agents 231 • Game theory 232 • Voting 233 • Auctions 234 • Swarm systems and biologically inspired models 235 236 Learning Outcomes: 237 1. List the defining characteristics of an intelligent agent. [Knowledge] 238 2. Characterize and contrast the standard agent architectures. [Evaluation] 239 3. Describe the applications of agent theory to domains such as software agents, personal assistants, and 240 believable agents. [Knowledge] 241 4. Describe the primary paradigms used by learning agents. [Knowledge] 242 5. Demonstrate using appropriate examples how multi-agent systems support agent interaction. [Application] 243 244 - 100 - 245 IS/Natural Language Processing 246 [Elective] 247 (Cross-reference HC/Design for non-mouse Interfaces) 248 Topics: 249 • Deterministic and stochastic grammars 250 • Parsing algorithms 251 • CFGs and chart parsers (e.g. CYK) 252 • Probabilistic CFGs and weighted CYK 253 • Representing meaning / Semantics 254 • Logic-based knowledge representations 255 • Semantic roles 256 • Temporal representations 257 • Verbs and event types 258 • Beliefs, desires, and intentions 259 • Ambiguity 260 • Long-distance dependencies 261 • Corpus-based methods 262 • N-grams and HMMs 263 • Smoothing and backoff 264 • Perplexity 265 • Zipf’s law 266 • Examples of use: POS tagging and morphology 267 • Information retrieval (Cross-reference IM/Information Storage and Retrieval) 268 • Vector space model 269 • TF & IDF 270 • Precision and recall 271 • Information extraction 272 • Language translation 273 • Transfer-based models 274 • Statistical, phrase-based models 275 • Text classification, categorization 276 • Bag of words model 277 278 Learning Outcomes: 279 1. Define and contrast deterministic and stochastic grammars, providing examples to show the adequacy of 280 each. [Evaluation] 281 2. Simulate, apply, or implement classic and stochastic algorithms for parsing natural language. [Application] 282 3. Identify the challenges of representing meaning. [Knowledge] 283 4. List the advantages of using standard corpora. Identify examples of current corpora for a variety of NLP 284 tasks. [Knowledge] 285 5. Identify techniques for information retrieval, language translation, and text classification. [Knowledge] 286 287 - 101 - 288 IS/Advanced Machine Learning 289 [Elective] 290 Topics: 291 • Definition and examples of broad variety of machine learning tasks 292 • General statistical-based learning, parameter estimation (maximum likelihood) 293 • Inductive logic programming (ILP) 294 • Supervised learning 295 • Learning decision trees 296 • Learning neural networks 297 • Support vector machines (SVMs) 298 • Ensembles 299 • Nearest-neighbor algorithms 300 • Unsupervised Learning and clustering 301 • EM 302 • K-means 303 • Self-organizing maps 304 • Semi-supervised learning 305 • Learning graphical models (Cross-reference IS/Reasoning under Uncertainty) 306 • Performance evaluation (such as cross-validation, area under ROC curve) 307 • Learning theory 308 • The problem of overfitting, the curse of dimensionality 309 • Reinforcement learning 310 • Exploration vs. exploitation trade-off 311 • Markov decision processes 312 • Value and policy iteration 313 • Application of Machine Learning algorithms to Data Mining (Cross-reference IM/Data Mining) 314 315 Learning Outcomes: 316 1. Explain the differences among the three main styles of learning: supervised, reinforcement, and 317 unsupervised. [Knowledge] 318 2. Implement simple algorithms for supervised learning, reinforcement learning, and unsupervised learning. 319 [Application] 320 3. Determine which of the three learning styles is appropriate to a particular problem domain. [Application] 321 4. Compare and contrast each of the following techniques, providing examples of when each strategy is 322 superior: decision trees, neural networks, and belief networks. [Evaluation] 323 5. Evaluate the performance of a simple learning system on a real-world dataset. [Evaluation] 324 6. Characterize the state of the art in learning theory, including its achievements and its shortcomings. 325 [Knowledge] 326 7. Explain the problem of overfitting, along with techniques for detecting and managing the problem. 327 [Application] 328 329 - 102 - 330 IS/Robotics 331 [Elective] 332 Topics: 333 • Overview: problems and progress 334 • State-of-the-art robot systems, including their sensors and an overview of their sensor processing 335 • Robot control architectures, e.g., deliberative vs. reactive control and Braitenberg vehicles 336 • World modeling and world models 337 • Inherent uncertainty in sensing and in control 338 • Configuration space and environmental maps 339 • Interpreting uncertain sensor data 340 • Localizing and mapping 341 • Navigation and control 342 • Motion planning 343 • Multiple-robot coordination 344 345 Learning Outcomes: 346 1. List capabilities and limitations of today's state-of-the-art robot systems, including their sensors and the 347 crucial sensor processing that informs those systems. [Knowledge] 348 2. Integrate sensors, actuators, and software into a robot designed to undertake some task. [Application] 349 3. Program a robot to accomplish simple tasks using deliberative, reactive, and/or hybrid control architectures. 350 [Application] 351 4. Implement fundamental motion planning algorithms within a robot configuration space. [Application] 352 5. Characterize the uncertainties associated with common robot sensors and actuators; articulate strategies 353 for mitigating these uncertainties. [Knowledge] 354 6. List the differences among robots' representations of their external environment, including their strengths 355 and shortcomings. [Knowledge] 356 7. Compare and contrast at least three strategies for robot navigation within known and/or unknown 357 environments, including their strengths and shortcomings. [Evaluation] 358 8. Describe at least one approach for coordinating the actions and sensing of several robots to accomplish a 359 single task. [Knowledge] 360 361 IS/Perception and Computer Vision 362 [Elective] 363 Topics: 364 • Computer vision 365 • Image acquisition, representation, and properties 366 • Image pre-processing via linear and nonlinear filtering 367 • Foreground/background segmentation 368 • Shape representation and object recognition 369 • Image inference based on prior models, i.e., image understanding 370 • Motion analysis 371 • Other modes of sensing 372 • Audio and speech recognition 373 • Sensory transformations 374 • Modularity in recognition 375 • Raw signals, acquisition issues, and sources of noise - 103 - 376 • Task-independent features, e.g., image edges or phonetic frames 377 • Percepts as collections of features, e.g., edge-based contours or word-level hypotheses 378 • Task-dependent features and percepts: the importance and use of prior models 379 • Approaches to pattern recognition [overlapping with machine learning] 380 • Classification algorithms and measures of classification quality 381 • Statistical techniques 382 383 Learning Outcomes: 384 1. Summarize the importance of image and object recognition in AI and indicate several significant 385 applications of this technology. [Knowledge] 386 2. List at least three image-segmentation approaches, such as thresholding, edge-based and region-based 387 algorithms, along with their defining characteristics, strengths, and weaknesses. [Knowledge] 388 3. Implement 2d object recognition based on contour- and/or region-based shape representations. 389 [Application] 390 4. Distinguish the goals of sound-recognition, speech-recognition, and speaker-recognition and identify how 391 the raw audio signal will be handled differently in each of these cases. [Knowledge] 392 5. Provide at least two examples of a transformation of a data source from one sensory domain to another, 393 e.g., tactile data interpreted as single-band 2d images. [Knowledge] 394 6. Implement a feature-extraction algorithm on real data, e.g., an edge or corner detector for images or vectors 395 of Fourier coefficients describing a short slice of audio signal. [Application] 396 7. Implement an algorithm combining features into higher-level percepts, e.g., a contour or polygon from 397 visual primitives or phoneme hypotheses from an audio signal. [Application] 398 8. Implement a classification algorithm that segments input percepts into output categories and quantitatively 399 evaluates the resulting classification. [Application] 400 9. Evaluate the performance of the underlying feature-extraction, relative to at least one alternative possible 401 approach (whether implemented or not) in its contribution to the classification task (8), above. [Evaluation] 402 10. Describe at least three classification approaches, their prerequisites for applicability, their strengths, and 403 their shortcomings. [Knowledge] 404 - 104 - 1 Networking and Communication (NC) 2 The Internet and computer networks are now ubiquitous and a growing number of computing 3 activities strongly depend on the correct operation of the underlying network. Networks, both 4 fixed and mobile, are a key part of today's and tomorrow's computing environment. Many 5 computing applications that are used today would not be possible without networks. This 6 dependency on the underlying network is likely to increase in the future. 7 The high-level learning objective of this module can be summarized as follows: 8 • Thinking in a networked world. The world is more and more interconnected and the use 9 of networks will continue to increase. Students must understand how the network 10 behaves and the key principles behind the organization and the operation of the computer 11 networks. 12 • Continued study. The networking domain is rapidly evolving and a first networking 13 course should be a starting point to other more advanced courses on network design, 14 network management, sensor networks, etc. 15 • Principles and practice interact. Networking is real and many of the design choices that 16 involve networks also depend on practical constraints. Students should be exposed to 17 these practical constraints by experimenting with networking, using tools, and writing 18 networked software. 19 There are different ways of organizing a networking course. Some educators prefer a top-down 20 approach, i.e. the course starts from the applications and then explains reliable delivery, routing 21 and forwarding, etc. Other educators prefer a bottom-up approach where the students start with 22 the lower layers and build their understanding of the network, transport and application layers 23 later. 24 25 26 NC. Networking and Communication (3 Core-Tier1 hours, 7 Core-Tier2 hours) Core-Tier1 hours Core-Tier2 hours Includes Electives NC/Introduction 1.5 N NC/Networked Applications 1.5 N NC/Reliable Data Delivery 2 N NC/Routing And Forwarding 1.5 N NC/Local Area Networks 1.5 N NC/Resource Allocation 1 N NC/Mobility 1 N 27 28 29 NC/Introduction 30 [1.5 Core-Tier1 hours] 31 Topics: 32 [Core-Tier1] 33 • Organization of the Internet (Internet Service Providers, Content Providers, etc.) 34 • Switching techniques (Circuit, packet, etc.) 35 • Physical pieces of a network (hosts, routers, switches, ISPs, wireless, LAN, access point, firewalls, etc.) 36 • Layering principles (encapsulation, multiplexing) 37 • Roles of the different layers (application, transport, network, datalink, physical) 38 39 Learning Outcomes: 40 1. Articulate the organization of the Internet [Knowledge] 41 2. List and define the appropriate network terminology [Knowledge] 42 3. Describe the layered structure of a typical networked architecture [Knowledge] 43 4. Identify the different levels of complexity in a network (edges, core, etc.) [Knowledge] 44 45 NC/Networked Applications 46 [1.5 Core-Tier1 hours] 47 Topics: 48 [Core-Tier1] 49 • Naming and address schemes (DNS, IP addresses, Uniform Resource Identifiers, etc.) 50 • Distributed applications (client/server, peer-to-peer, cloud, etc.) 51 • HTTP as an application layer protocol 52 • Multiplexing with TCP and UDP 53 • Socket APIs - 106 - 54 55 Learning Outcomes: 56 1. List the differences and the relations between names and addresses in a network [Knowledge] 57 2. Define the principles behind DNS and HTTP [Knowledge] 58 3. Be able to implement a simple client-server socket-based application [Knowledge] 59 60 NC/Reliable Data Delivery 61 [2 Core-Tier2 hours] 62 This Knowledge Unit is related to SF-Systems Fundamentals. Cross-reference SF/State-State 63 Transition and SF/Reliability through Redundancy. 64 Topics: 65 [Core-Tier2] 66 • Error control (retransmission techniques, timers) 67 • Flow control (acknowledgements, sliding window) 68 • Performance issues (pipelining) 69 • TCP 70 71 Learning Outcomes: 72 1. Describe the operation of reliable delivery protocols [Knowledge] 73 2. List the factors that affect the performance of reliable delivery protocols [Knowledge] 74 3. Design and implement a simple reliable protocol [Application] 75 76 NC/Routing And Forwarding 77 [1.5 Core-Tier2 hours] 78 Topics: 79 [Core-Tier2] 80 • Routing versus forwarding 81 • Static routing 82 • Internet Protocol (IP) 83 • Scalability issues (hierarchical addressing) 84 85 Learning Outcomes: 86 1. Describe the organization of the network layer [Knowledge] 87 2. Describe how packets are forwarded in an IP networks [Knowledge] 88 3. List the scalability benefits of hierarchical addressing [Knowledge] 89 90 - 107 - 91 NC/Local Area Networks 92 [1.5 Core-Tier2 hours] 93 Topics: 94 [Core-Tier2] 95 • Multiple Access 96 • Local Area Networks 97 • Ethernet 98 • Switching 99 100 Learning Outcomes: 101 1. List the major steps in solving the multiple access problem [Application] 102 2. Describe how frames are forwarded in an Ethernet network [Knowledge] 103 3. Identify the differences between IP and Ethernet [Knowledge] 104 4. Describe the interrelations between IP and Ethernet [Application] 105 106 NC/Resource Allocation 107 [1 Core-Tier2 hours] 108 Topics: 109 [Core-Tier2] 110 • Need for resource allocation 111 • Fixed allocation (TDM, FDM, WDM) versus dynamic allocation 112 • End-to-end versus network assisted approaches 113 • Fairness 114 • Principles of congestion control 115 116 Learning Outcomes: 117 1. Describe how resources can be allocated in a network [Knowledge] 118 2. Describe the congestion problem in a large network [Knowledge] 119 3. Compare and contrast the fixed and dynamic allocation techniques [Evaluation] 120 121 NC/Mobility 122 [1 Core-Tier2 hours] 123 Topics: 124 [Core-Tier2] 125 • Principles of cellular networks 126 • 802.11 networks 127 • Issues in supporting mobile nodes (home agents) 128 129 Learning Outcomes: 130 1. Describe the organization of a wireless network [Knowledge] 131 2. Describe how wireless networks support mobile users [Knowledge] - 108 - 1 Operating Systems (OS) 2 An operating system defines an abstraction of hardware and manages resource sharing among 3 the computer’s users. The topics in this area explain the most basic knowledge of operating 4 systems in the sense of interfacing an operating system to networks, teaching the difference 5 between the kernel and user modes, and developing key approaches to operating system design 6 and implementation. This knowledge area is structured to be complementary to Systems 7 Fundamentals, Networks, Information Assurance, and the Parallel and Distributed Computing 8 knowledge areas. The Systems Fundamentals and Information Assurance knowledge areas are 9 the new ones to include contemporary issues. For example, the Systems Fundamentals includes 10 topics such as performance, virtualization and isolation, and resource allocation and scheduling; 11 Parallel and Distributed Systems knowledge area includes parallelism fundamentals; and 12 Information Assurance includes forensics and security issues in depth. Many courses in 13 Operating Systems will draw material from across these Knowledge Areas. 14 OS. Operating Systems (4 Core-Tier1 hours; 11 Core Tier2 hours) Core-Tier1 hours Core-Tier2 hours Includes Electives OS/Overview of Operating Systems 2 N OS/Operating System Principles 2 N OS/Concurrency 3 N OS/Scheduling and Dispatch 3 N OS/Memory Management 3 N OS/Security and Protection 2 N OS/Virtual Machines Y OS/Device Management Y OS/File Systems Y OS/Real Time and Embedded Systems Y OS/Fault Tolerance Y OS/System Performance Evaluation Y 15 16 OS/Overview of Operating Systems 17 [2 Core-Tier1 hours] 18 Topics: 19 • Role and purpose of the operating system 20 • Functionality of a typical operating system 21 • Mechanisms to support client-server models, hand-held devices 22 • Design issues (efficiency, robustness, flexibility, portability, security, compatibility) 23 • Influences of security, networking, multimedia, windows 24 25 Learning Objectives: 26 1. Explain the objectives and functions of modern operating systems [Knowledge]. 27 2. Analyze the tradeoffs inherent in operating system design [Application]. 28 3. Describe the functions of a contemporary operating system with respect to convenience, efficiency, and the 29 ability to evolve [Knowledge]. 30 4. Discuss networked, client-server, distributed operating systems and how they differ from single user 31 operating systems [Knowledge]. 32 5. Identify potential threats to operating systems and the security features design to guard against them 33 [Knowledge]. 34 35 OS/Operating System Principles 36 [2 core-T1 hours] 37 Topics: 38 • Structuring methods (monolithic, layered, modular, micro-kernel models) 39 • Abstractions, processes, and resources 40 • Concepts of application program interfaces (APIs) 41 • Application needs and the evolution of hardware/software techniques 42 • Device organization 43 • Interrupts: methods and implementations 44 • Concept of user/system state and protection, transition to kernel mode 45 46 Learning Objectives: 47 1. Explain the concept of a logical layer [Knowledge]. 48 2. Explain the benefits of building abstract layers in hierarchical fashion [Knowledge]. 49 3. Defend the need for APIs and middleware [Evaluation]. 50 4. Describe how computing resources are used by application software and managed by system software 51 [Knowledge]. 52 5. Contrast kernel and user mode in an operating system [Application]. 53 6. Discuss the advantages and disadvantages of using interrupt processing [Knowledge]. 54 7. Explain the use of a device list and driver I/O queue [Knowledge]. 55 56 - 110 - 57 OS/Concurrency 58 [3 Core-Tier2 hours] 59 Topics: 60 • States and state diagrams (cross reference SF/State-State Transition-State Machines) 61 • Structures (ready list, process control blocks, and so forth) 62 • Dispatching and context switching 63 • The role of interrupts 64 • Managing atomic access to OS objects 65 • Implementing synchronization primitives 66 • Multiprocessor issues (spin-locks, reentrancy) (cross reference SF/Parallelism) 67 68 Learning Objectives: 69 1. Describe the need for concurrency within the framework of an operating system [Knowledge]. 70 2. Demonstrate the potential run-time problems arising from the concurrent operation of many separate tasks 71 [Application]. 72 3. Summarize the range of mechanisms that can be employed at the operating system level to realize 73 concurrent systems and describe the benefits of each [Knowledge]. 74 4. Explain the different states that a task may pass through and the data structures needed to support the 75 management of many tasks [Knowledge]. 76 5. Summarize techniques for achieving synchronization in an operating system (e.g., describe how to 77 implement a semaphore using OS primitives) [Knowledge]. 78 6. Describe reasons for using interrupts, dispatching, and context switching to support concurrency in an 79 operating system [Knowledge]. 80 7. Create state and transition diagrams for simple problem domains [Application]. 81 82 OS/Scheduling and Dispatch 83 [3 Core-Tier2 hours] 84 Topics: 85 • Preemptive and nonpreemptive scheduling (cross reference SF/Resource Allocation and Scheduling, 86 PD/Parallel Performance) 87 • Schedulers and policies (cross reference SF/Resource Allocation and Scheduling, PD/Parallel Performance) 88 • Processes and threads (cross reference SF/computational paradigms) 89 • Deadlines and real-time issues 90 91 Learning Objectives: 92 1. Compare and contrast the common algorithms used for both preemptive and non-preemptive scheduling of 93 tasks in operating systems, such as priority, performance comparison, and fair-share schemes [Application]. 94 2. Describe relationships between scheduling algorithms and application domains [Knowledge]. 95 3. Discuss the types of processor scheduling such as short-term, medium-term, long-term, and I/O 96 [Knowledge]. 97 4. Describe the difference between processes and threads [Application]. 98 5. Compare and contrast static and dynamic approaches to real-time scheduling [Application]. 99 6. Discuss the need for preemption and deadline scheduling [Knowledge]. 100 7. Identify ways that the logic embodied in scheduling algorithms are applicable to other domains, such as 101 disk I/O, network scheduling, project scheduling, and problems beyond computing [Application]. 102 - 111 - 103 OS/Memory Management 104 [3 Core-Tier2 hours] 105 Topics: 106 • Review of physical memory and memory management hardware 107 • Working sets and thrashing 108 • Caching 109 110 Learning Objectives: 111 1. Explain memory hierarchy and cost-performance trade-offs [Knowledge]. 112 2. Summarize the principles of virtual memory as applied to caching and paging [Knowledge]. 113 3. Evaluate the trade-offs in terms of memory size (main memory, cache memory, auxiliary memory) and 114 processor speed [Evaluation]. 115 4. Defend the different ways of allocating memory to tasks, citing the relative merits of each [Evaluation]. 116 5. Describe the reason for and use of cache memory (performance and proximity, different dimension of how 117 caches complicate isolation and VM abstraction) [Knowledge]. 118 6. Discuss the concept of thrashing, both in terms of the reasons it occurs and the techniques used to recognize 119 and manage the problem [Knowledge]. 120 121 OS/Security and Protection 122 [2 Core-Tier2 hours] 123 Topics: 124 • Overview of system security 125 • Policy/mechanism separation 126 • Security methods and devices 127 • Protection, access control, and authentication 128 • Backups 129 130 Learning Objectives: 131 1. Defend the need for protection and security in an OS (cross reference IAS/Security Architecture and 132 Systems Administration/Investigating Operating Systems Security for various systems) [Evaluation]. 133 2. Summarize the features and limitations of an operating system used to provide protection and security 134 (cross reference IAS/Security Architecture and Systems Administration) [Knowledge]. 135 3. Explain the mechanisms available in an OS to control access to resources (cross reference IAS/Security 136 Architecture and Systems Administration/Access Control/Configuring systems to operate securely as an IT 137 system) [Knowledge]. 138 4. Carry out simple system administration tasks according to a security policy, for example creating accounts, 139 setting permissions, applying patches, and arranging for regular backups (cross reference IAS/Security 140 Architecture and Systems Administration ) [Application]. 141 142 - 112 - 143 OS/Virtual Machines 144 [Elective] 145 Topics: 146 • Types of virtualization (Hardware/Software, OS, Server, Service, Network, etc.) 147 • Paging and virtual memory 148 • Virtual file systems 149 • Virtual file 150 • Hypervisors 151 • Portable virtualization; emulation vs. isolation 152 • Cost of virtualization 153 154 Learning Objectives: 155 1. Explain the concept of virtual memory and how it is realized in hardware and software [Knowledge]. 156 2. Differentiate emulation and isolation [Knowledge]. 157 3. Evaluate virtualization trade-offs [Evaluation]. 158 4. Discuss hypervisors and the need for them in conjunction with different types of hypervisors [Application]. 159 160 OS/Device Management 161 [Elective] 162 Topics: 163 • Characteristics of serial and parallel devices 164 • Abstracting device differences 165 • Buffering strategies 166 • Direct memory access 167 • Recovery from failures 168 169 Learning Objectives: 170 1. Explain the key difference between serial and parallel devices and identify the conditions in which each is 171 appropriate [Knowledge]. 172 2. Identify the relationship between the physical hardware and the virtual devices maintained by the operating 173 system [Application]. 174 3. Explain buffering and describe strategies for implementing it [Knowledge]. 175 4. Differentiate the mechanisms used in interfacing a range of devices (including hand-held devices, 176 networks, multimedia) to a computer and explain the implications of these for the design of an operating 177 system [Application]. 178 5. Describe the advantages and disadvantages of direct memory access and discuss the circumstances in 179 which its use is warranted [Application]. 180 6. Identify the requirements for failure recovery [Knowledge]. 181 7. Implement a simple device driver for a range of possible devices [Application]. 182 183 - 113 - 184 OS/File Systems 185 [Elective] 186 Topics: 187 • Files: data, metadata, operations, organization, buffering, sequential, nonsequential 188 • Directories: contents and structure 189 • File systems: partitioning, mount/unmount, virtual file systems 190 • Standard implementation techniques 191 • Memory-mapped files 192 • Special-purpose file systems 193 • Naming, searching, access, backups 194 • Journaling and log-structured file systems 195 196 Learning Objectives: 197 1. Summarize the full range of considerations in the design of file systems [Knowledge]. 198 2. Compare and contrast different approaches to file organization, recognizing the strengths and weaknesses 199 of each [Application]. 200 3. Summarize how hardware developments have led to changes in the priorities for the design and the 201 management of file systems [Knowledge]. 202 4. Summarize the use of journaling and how log-structured file systems enhance fault tolerance [Knowledge]. 203 204 OS/Real Time and Embedded Systems 205 [Elective] 206 Topics: 207 • Process and task scheduling 208 • Memory/disk management requirements in a real-time environment 209 • Failures, risks, and recovery 210 • Special concerns in real-time systems 211 212 Learning Objectives: 213 1. Describe what makes a system a real-time system [Knowledge]. 214 2. Explain the presence of and describe the characteristics of latency in real-time systems [Knowledge]. 215 3. Summarize special concerns that real-time systems present and how these concerns are addressed 216 [Knowledge]. 217 218 OS/Fault Tolerance 219 [Elective] 220 Topics: 221 • Fundamental concepts: reliable and available systems (cross reference SF/Reliability through Redundancy) 222 • Spatial and temporal redundancy (cross reference SF/Reliability through Redundancy) 223 • Methods used to implement fault tolerance 224 • Examples of OS mechanisms for detection, recovery, restart to implement fault tolerance, use of these 225 techniques for the OS’s own services - 114 - 226 227 Learning Objectives: 228 1. Explain the relevance of the terms fault tolerance, reliability, and availability [Knowledge]. 229 2. Outline the range of methods for implementing fault tolerance in an operating system [Knowledge]. 230 3. Explain how an operating system can continue functioning after a fault occurs [Knowledge]. 231 232 OS/System Performance Evaluation 233 [Elective] 234 Topics: 235 • Why system performance needs to be evaluated (cross reference SF/Performance/Figures of performance 236 merit) 237 • What is to be evaluated (cross reference SF/Performance/Figures of performance merit) 238 • Policies for caching, paging, scheduling, memory management, security, and so forth 239 • Evaluation models: deterministic, analytic, simulation, or implementation-specific 240 • How to collect evaluation data (profiling and tracing mechanisms) 241 242 Learning Objectives: 243 1. Describe the performance measurements used to determine how a system performs [Knowledge]. 244 2. Explain the main evaluation models used to evaluate a system [Knowledge]. - 115 - 1 Platform-Based Development (PBD) 2 Platform-based development is concerned with the design and development of software 3 applications that reside on specific software platforms. In contrast to general purpose 4 programming, platform-based development takes into account platform-specific constraints. For 5 instance web programming, multimedia development, mobile computing, app development, and 6 robotics are examples of relevant platforms which provide specific services/APIs/hardware 7 which constrain development. Such platforms are characterized by the use of specialized APIs, 8 distinct delivery/update mechanisms, and being abstracted away from the machine level. 9 Platform-based development may be applied over a wide breadth of ecosystems. 10 While we recognize that some platforms (e.g., web development) are prominent, we are also 11 cognizant of the fact that no particular platform should be specified as a requirement in the 12 CS2013 curricular guidelines. Consequently, this Knowledge Area highlights many of the 13 platforms which have become popular, without including any such platform in the core 14 curriculum. We note that the general skill of developing with respect to an API or a constrained 15 environment is covered in other Knowledge Areas, such as SDF-Software Development 16 Fundamentals. Platform-based development further emphasizes such general skills within the 17 context of particular platforms. 18 19 PBD. Platform-Based Development (Elective) Core-Tier1 hours Core-Tier2 hours Includes Electives PBD/Introduction Y PBD/Web Platforms Y PBD/Mobile Platforms Y PBD/Industrial Platforms Y PBD/Game Platforms Y 20 21 22 PBD/Introduction 23 [Elective] 24 This unit describes the fundamental differences that Platform-Based Development has over 25 traditional software development. 26 Topics: 27 • Overview of platforms (Web, Mobile, Game, Industrial etc) 28 • Programming via platform-specific APIs 29 • Overview of Platform Languages (Objective C, HTML5, etc) 30 • Programming under platform constraints 31 32 Learning Outcomes: 33 1. Describe how platform-based development differs from general purpose programming [Knowledge] 34 2. List characteristics of platform languages [Knowledge] 35 3. Write and execute a simple platform-based program [Application] 36 4. List the advantages and disadvantages of programming with platform constraints [Knowledge] 37 38 PBD/Web Platforms 39 [Elective] 40 Topics: 41 • Web programming languages (HTML5, Java Script, PHP, CSS, etc.) 42 • Web platform constraints 43 • Software as a Service (SaaS) 44 45 Learning Outcomes: 46 1. Design and Implement a simple web application [Application] 47 2. Describe the constraints that the web puts on developers [ Knowledge] 48 3. Compare and contrast web programming with general purpose programming [Evaluation] 49 4. Describe the differences between Software-as-a-Service and traditional software products [Knowledge] 50 51 PBD/Mobile Platforms 52 [Elective] 53 Topics: 54 • Mobile Programming Languages (Objective C, Java Script, Java, etc.) 55 • Challenges with mobility and wireless communication 56 • Location-aware applications 57 • Performance / power tradeoffs 58 • Mobile platform constraints 59 • Emerging Technologies 60 61 - 117 - 62 Learning Outcomes: 63 1. Design and implement a mobile application for a given mobile platform. [Application] 64 2. Discuss the constraints that mobile platforms put on developers [Knowledge] 65 3. Discuss the performance vs. power tradeoff [Knowledge] 66 4. Compare and Contrast mobile programming with general purpose programming [Evaluation] 67 68 PBD/Industrial Platforms 69 [Elective] 70 This knowledge unit is related to IS/Robotics. 71 Topics: 72 • Types of Industrial Platforms (Mathematic, Robotics, Industrial Controls, etc.) 73 • Robotic Software and its Architecture 74 • Domain Specific Languages 75 • Industrial Platform Constraints 76 77 Learning Outcomes: 78 1. Design and implement an industrial application on a given platform (Lego Mindstorms, Matlab, etc.) 79 [Application] 80 2. Compare and contrast domain specific languages with general purpose programming languages. [Evaluate] 81 3. Discuss the constraints that a given industrial platforms impose on developers [Knowledge] 82 83 PBD/Game Platforms 84 [Elective] 85 Topics: 86 • Types of Game Platforms (XBox, Wii, PlayStation, etc) 87 • Game Platform Languages (C++, Java, Lua, Python, etc) 88 • Game Platform Constraints 89 90 Learning Outcomes: 91 1. Design and Implement a simple application on a game platform. [Application] 92 2. Describe the constraints that game platforms impose on developers. [Knowledge] 93 3. Compare and contrast game programming with general purpose programming [Evaluation] - 118 - 1 Parallel and Distributed Computing (PD) 2 The past decade has brought explosive growth in multiprocessor computing, including multi-core 3 processors and distributed data centers. As a result, parallel and distributed computing has 4 moved from a largely elective topic to become more of a core component of undergraduate 5 computing curricula. Both parallel and distributed computing entail the logically simultaneous 6 execution of multiple processes, whose operations have the potential to interleave in complex 7 ways. Parallel and distributed computing builds on foundations in many areas, including an 8 understanding of fundamental systems concepts such as concurrency and parallel execution, 9 consistency in state/memory manipulation, and latency. Communication and coordination 10 among processes is rooted in the message-passing and shared-memory models of computing, the 11 system goals of concurrency and speedup, and such algorithmic concepts as atomicity, 12 consensus, and conditional waiting. Achieving speedup in practice requires an understanding of 13 parallel algorithms, strategies for problem decomposition, system architecture, and performance 14 analysis and tuning. Distributed systems highlight the problems of security and fault tolerance, 15 emphasize the maintenance of replicated state, and introduce additional issues that bridge to 16 computer networking. 17 Because parallelism interacts with so many areas of computing, including at least algorithms, 18 languages, systems, networking, and hardware, many curricula will put different parts of the 19 knowledge area in different courses, rather than in a dedicated course. While we acknowledge 20 that computer science is moving in this direction and may reach that point, in 2013 this process is 21 still in flux and we feel it provides more useful guidance to curriculum designers to aggregate the 22 fundamental parallelism topics in one place. Note, however, that the fundamentals of 23 concurrency and mutual exclusion appear in Systems Fundamentals. Many curricula may 24 choose to introduce parallelism and concurrency in the same course. Further, we note that the 25 topics and learning outcomes listed below include only brief mentions of purely elective 26 coverage. At the present time, there is too much diversity in topics that share little in common 27 (including for example, parallel scientific computing, process calculi, and non-blocking data 28 structures) to recommend particular topics be covered in elective courses. [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ [Link] http://www.cs.gsu.edu/~tcpp/curriculum/ 29 Because the terminology of parallel and distributed computing varies among communities, we 30 provide here brief descriptions of the intended senses of a few terms. This list is not exhaustive 31 or definitive, but is provided for the sake of clarity: 32 • Activity: A computation that may proceed concurrently with others; for example a 33 program, process, thread, or active parallel hardware component. 34 • Atomicity: Rules and properties governing whether an action is observationally 35 indivisible; for example setting all of the bits in a word, transmitting a single packet, or 36 completing a transaction. 37 • Consensus: Agreement among two or more activities about a given predicate; for 38 example the value of a counter, the owner of a lock, or the termination of a thread. 39 • Consistency: Rules and properties governing agreement about the values of variables 40 written, or messages produced, by some activities and used by others (thus possibly 41 exhibiting a data race); for example, sequential consistency, stating that the values of all 42 variables in a shared memory parallel program are equivalent to that of a single program 43 performing some interleaving of the memory accesses of these activities. 44 • Multicast: A message sent to possibly many recipients, generally without any constraints 45 about whether some recipients receive the message before others. An event is a multicast 46 message sent to a designated set of listeners or subscribers. 47 As multi-processor computing continues to grow in the coming years, so too will the role of 48 parallel and distributed computing in undergraduate computing curricula. In addition to the 49 guidelines presented here, we also direct the interested reader to the document entitled 50 "NSF/TCPP Curriculum Initiative on Parallel and Distributed Computing - Core Topics for 51 Undergraduates", available from the website: http://www.cs.gsu.edu/~tcpp/curriculum/. 52 General cross-referencing note: Systems Fundamentals also contains an introduction to 53 parallelism (SF/Computational Paradigms, SF/System Support for Parallelism, SF/Performance). 54 The introduction to parallelism in SF complements the one here and there is no ordering 55 constraint between them. In SF, the idea is to provide a unified view of the system support for 56 simultaneous execution at multiple levels of abstraction (parallelism is inherent in gates, 57 processors, operating systems, servers, etc.), whereas here the focus is on a preliminary - 120 - 58 understanding of parallelism as a computing primitive and the complications that arise in parallel 59 and concurrent programming. Given these different perspectives, the hours assigned to each are 60 not redundant: the layered systems view and the high-level computing concepts are accounted 61 for separately in terms of the core hours. 62 PD. Parallel and Distributed Computing (5 Core-Tier1 hours, 9 Core-Tier2 hours) Core-Tier1 hours Core-Tier2 hours Includes Electives PD/Parallelism Fundamentals 2 N PD/Parallel Decomposition 1 3 N PD/Communication and Coordination 1 3 Y PD/Parallel Algorithms, Analysis, and 3 Y Programming PD/Parallel Architecture 1 1 Y PD/Parallel Performance Y PD/Distributed Systems Y PD/Formal Models and Semantics Y 63 64 - 121 - 65 PD/Parallelism Fundamentals 66 [2 Core-Tier1 hours] 67 Build upon students’ familiarity with the notion of basic parallel execution--a concept addressed 68 in Systems Fundamentals--to delve into the complicating issues that stem from this notion, such 69 as race conditions and liveness. 70 (Cross-reference SF/Computational Paradigms and SF/System Support for Parallelism) 71 Topics: 72 [Core-Tier1] 73 • Multiple simultaneous computations 74 • Goals of parallelism (e.g., throughput) versus concurrency (e.g., controlling access to shared resources) 75 • Programming constructs for creating parallelism, communicating, and coordinating 76 • Programming errors not found in sequential programming 77 o Data races (simultaneous read/write or write/write of shared state) 78 o Higher-level races (interleavings violating program intention) 79 o Lack of liveness/progress (deadlock, starvation) 80 81 Learning outcomes: 82 1. Distinguish using computational resources for a faster answer from managing efficient access to a shared 83 resource [Knowledge] 84 2. Distinguish multiple sufficient programming constructs for synchronization that may be inter- 85 implementable but have complementary advantages [Knowledge] 86 3. Distinguish data races from higher level races [Knowledge] 87 88 PD/Parallel Decomposition 89 [1 Core-Tier1 hour, 3 Core-Tier2 hours] 90 (Cross-reference SF/System Support for Parallelism) 91 Topics: 92 [Core-Tier1] 93 • Need for communication and coordination/synchronization 94 • Independence and partitioning 95 96 [Core-Tier2] 97 • Basic knowledge of parallel decomposition concepts (cross-reference SF/System Support for Parallelism) 98 • Task-based decomposition 99 • Implementation strategies such as threads 100 • Data-parallel decomposition 101 • Implementation strategies such as SIMD and MapReduce 102 • Actors and reactive processes (e.g., request handlers) 103 - 122 - 104 Learning outcomes: 105 1. Explain why synchronization is necessary in a specific parallel program [Application] 106 2. Write a correct and scalable parallel algorithm [Application] 107 3. Parallelize an algorithm by applying task-based decomposition [Application] 108 4. Parallelize an algorithm by applying data-parallel decomposition [Application] 109 110 PD/Communication and Coordination 111 [1 Core-Tier1 hour, 3 Core-Tier2 hours] 112 Topics: 113 [Core-Tier1] 114 • Shared Memory 115 • Sequential consistency, and its role in programming language guarantees for data-race-free programs 116 117 [Core-Tier2] 118 • Consistency in shared memory models 119 • Message passing 120 o Point-to-point versus multicast (or event-based) messages 121 o Blocking versus non-blocking styles for sending and receiving messages 122 o Message buffering (cross-reference PF/Fundamental Data Structures/Queues) 123 • Atomicity 124 o Specifying and testing atomicity and safety requirements 125 o Granularity of atomic accesses and updates, and the use of constructs such as critical sections or 126 transactions to describe them 127 o Mutual Exclusion using locks, semaphores, monitors, or related constructs 128 o Potential for liveness failures and deadlock (causes, conditions, prevention) 129 • Composition 130 • Composing larger granularity atomic actions using synchronization 131 • Transactions, including optimistic and conservative approaches 132 133 [Elective] 134 • Consensus 135 • (Cyclic) barriers, counters, or related constructs 136 • Conditional actions 137 • Conditional waiting (e.g., using condition variables) 138 139 Learning outcomes: 140 1. Use mutual exclusion to avoid a given race condition [Application] 141 2. Give an example of an ordering of accesses among concurrent activities that is not sequentially consistent 142 [Knowledge] 143 3. Give an example of a scenario in which blocking message sends can deadlock [Application] 144 4. Explain when and why multicast or event-based messaging can be preferable to alternatives [Knowledge] 145 5. Write a program that correctly terminates when all of a set of concurrent tasks have completed 146 [Application] 147 6. Use a properly synchronized queue to buffer data passed among activities [Application] - 123 - 148 7. Explain why checks for preconditions, and actions based on these checks, must share the same unit of 149 atomicity to be effective [Knowledge] 150 8. Write a test program that can reveal a concurrent programming error; for example, missing an update when 151 two activities both try to increment a variable [Application] 152 9. Describe at least one design technique for avoiding liveness failures in programs using multiple locks or 153 semaphores [Knowledge] 154 10. Describe the relative merits of optimistic versus conservative concurrency control under different rates of 155 contention among updates [Knowledge] 156 11. Give an example of a scenario in which an attempted optimistic update may never complete [Knowledge] 157 12. Use semaphores or condition variables to block threads until a necessary precondition holds [Application] 158 159 PD/Parallel Algorithms, Analysis, and Programming 160 [3 Core-Tier2 hours] 161 Topics: 162 [Core-Tier2] 163 • Critical paths, work and span, and the relation to Amdahl’s law (cross-reference SF/Performance) 164 • Speed-up and scalability 165 • Naturally (embarassingly) parallel algorithms 166 • Parallel algorithmic patterns (divide-and-conquer, map and reduce, others) 167 • Specific algorithms (e.g., parallel MergeSort) 168 169 [Elective] 170 • Parallel graph algorithms (e.g., parallel shortest path, parallel spanning tree) (cross-reference 171 AL/Algorithmic Strategies/Divide-and-conquer) 172 • Producer-consumer and pipelined algorithms 173 174 Learning outcomes: 175 1. Define “critical path”, “work”, and “span” [Knowledge] 176 2. Compute the work and span, and determine the critical path with respect to a parallel execution diagram 177 [application] 178 3. Define “speed-up” and explain the notion of an algorithm’s scalability in this regard [Knowledge] 179 4. Identify independent tasks in a program that may be parallelized [Application] 180 5. Characterize features of a workload that allow or prevent it from being naturally parallelized [Knowledge] 181 6. Implement a parallel divide-and-conquer and/or graph algorithm and empirically measure its performance 182 relative to its sequential analog [application] 183 7. Decompose a problem (e.g., counting the number of occurrences of some word in a document) via map and 184 reduce operations [Application] 185 8. Provide an example of a problem that fits the producer-consumer paradigm [Knowledge] 186 9. Give examples of problems where pipelining would be an effective means of parallelization [Knowledge] 187 10. Identify issues that arise in producer-consumer algorithms and mechanisms that may be used for addressing 188 them [Knowledge] 189 190 - 124 - 191 PD/Parallel Architecture 192 [1 Core-Tier1 hour, 1 Core-Tier2 hour] 193 The topics listed here are related to knowledge units in the Architecture and Organization area 194 (AR/Assembly Level Machine Organization and AR/Multiprocessing and Alternative 195 Architectures). Here, we focus on parallel architecture from the standpoint of applications, 196 whereas the Architecture and Organization area presents the topic from the hardware 197 perspective. 198 [Core-Tier1] 199 • Multicore processors 200 • Shared vs. distributed memory 201 202 [Core-Tier2] 203 • Symmetric multiprocessing (SMP) 204 • SIMD, vector processing 205 206 [Elective] 207 • GPU, co-processing 208 • Flynn’s taxonomy 209 • Instruction level support for parallel programming 210 • Atomic instructions such as Compare and Set 211 • Memory issues 212 • Multiprocessor caches and cache coherence 213 • Non-uniform memory access (NUMA) 214 • Topologies [Elective] 215 • Interconnects 216 • Clusters 217 • Resource sharing (e.g., buses and interconnects) 218 219 Learning outcomes: 220 1. Describe the SMP architecture and note its key features [Knowledge] 221 2. Characterize the kinds of tasks that are a natural match for SIMD machines [Knowledge] 222 3. Explain the features of each classification in Flynn’s taxonomy [Knowledge] 223 4. Explain the differences between shared and distributed memory [Knowledge] 224 5. Describe the challenges in maintaining cache coherence [Knowledge] 225 6. Describe the key features of different distributed system topologies [Knowledge] 226 227 - 125 - 228 PD/Parallel Performance 229 [Elective] 230 Topics: 231 • Load balancing 232 • Performance measurement 233 • Scheduling and contention (cross-reference OS/Scheduling and Dispatch) 234 • Data management 235 o Non-uniform communication costs due to proximity (cross-reference SF/Proximity) 236 o Cache effects (e.g., false sharing) 237 o Maintaining spatial locality 238 • Impact of composing multiple concurrent components 239 • Power usage and management 240 241 Learning outcomes: 242 1. Calculate the implications of Amdahl’s law for a particular parallel algorithm [Application] 243 2. Describe how data distribution/layout can affect an algorithm’s communication costs [Knowledge] 244 3. Detect and correct a load imbalance [Application] 245 4. Detect and correct an instance of false sharing [Application] 246 5. Explain the impact of scheduling on parallel performance [Knowledge] 247 6. Explain performance impacts of data locality [Knowledge] 248 7. Explain the impact and trade-off related to power usage on parallel performance [Knowledge] 249 250 PD/Distributed Systems 251 [Elective] 252 Topics: 253 • Faults (cross-reference OS/Fault Tolerance) 254 o Network-based (including partitions) and node-based failures 255 o Impact on system wide guarantees (e.g., availability) 256 • Distributed message sending 257 o Data conversion and transmission 258 o Sockets 259 o Message sequencing 260 o Buffering, retrying, and dropping messages 261 • Distributed system design tradeoffs 262 o Latency versus throughput 263 o Consistency, availability, partition tolerance 264 • Distributed service design 265 o Stateful versus stateless protocols and services 266 o Session (connection-based) designs 267 o Reactive (IO-triggered) and multithreaded designs 268 • Core distributed algorithms 269 o Election, discovery 270 • Scaling 271 o Clusters, grids, meshes, and clouds 272 - 126 - 273 Learning outcomes: 274 1. Distinguish network faults from other kinds of failures [Knowledge] 275 2. Explain why synchronization constructs such as simple locks are not useful in the presence of distributed 276 faults [Knowledge] 277 3. Give examples of problems for which consensus algorithms such as leader election are required 278 [Application] 279 4. Write a program that performs any required marshalling and conversion into message units, such as 280 packets, to communicate interesting data between two hosts [Application] 281 5. Measure the observed throughput and response latency across hosts in a given network [Application] 282 6. Explain why no distributed system can be simultaneously consistent, available, and partition tolerant 283 [Knowledge] 284 7. Implement a simple server -- for example, a spell checking service [Application] 285 8. Explain the tradeoffs among overhead, scalability, and fault tolerance when choosing a stateful v. stateless 286 design for a given service [Knowledge] 287 9. Describe the scalability challenges associated with a service growing to accommodate many clients, as well 288 as those associated with a service only transiently having many clients [Knowledge] 289 290 PD/Formal Models and Semantics 291 [Elective] 292 Topics: 293 • Formal models of processes and message passing, including algebras such as Communicating Sequential 294 Processes (CSP) and pi-calculus 295 • Formal models of parallel computation, including the Parallel Random Access Machine (PRAM) and 296 alternatives such as Bulk Synchronous Parallel (BSP) 297 • Models of (relaxed) shared memory consistency and their relation to programming language specifications 298 • Algorithmic correctness criteria including linearizability 299 • Models of algorithmic progress, including non-blocking guarantees and fairness 300 • Techniques for specifying and checking correctness properties such as atomicity and freedom from data 301 races 302 303 Learning outcomes: 304 1. Model a concurrent process using a formal model, such as pi-calculus [Application] 305 2. Explain the characteristics of a particular formal parallel model [Knowledge] 306 3. Formally model a shared memory system to show if it is consistent [Application 307 4. Use a model to show progress guarantees in a parallel algorithm [Application] 308 5. Use formal techniques to show that a parallel algorithm is correct with respect to a safety or liveness 309 property [Application] 310 6. Decide if a specific execution is linearizable or not [Application] - 127 - 1 Programming Languages (PL) 2 Programming languages are the medium through which programmers precisely describe 3 concepts, formulate algorithms, and reason about solutions. In the course of a career, a computer 4 scientist will work with many different languages, separately or together. Software developers 5 must understand the programming models underlying different languages, and make informed 6 design choices in languages supporting multiple complementary approaches. Computer 7 scientists will often need to learn new languages and programming constructs, and must 8 understand the principles underlying how programming language features are defined, 9 composed, and implemented. The effective use of programming languages, and appreciation of 10 their limitations, also requires a basic knowledge of programming language translation and static 11 program analysis, as well as run-time components such as memory management. 12 13 PL. Programming Languages (8 Core-Tier1 hours, 20 Core-Tier2 hours) Core-Tier1 hours Core-Tier2 hours Includes Electives PL/Object-Oriented Programming 4 6 N PL/Functional Programming 3 4 N PL/Event-Driven and Reactive 2 N Programming PL/Basic Type Systems 1 4 N PL/Program Representation 1 N PL/Language Translation and 3 N Execution PL/Syntax Analysis Y PL/Compiler Semantic Analysis Y PL/Code Generation Y PL/Runtime Systems Y PL/Static Analysis Y PL/Advanced Programming Y Constructs PL/Concurrency and Parallelism Y PL/Type Systems Y PL/Formal Semantics Y PL/Language Pragmatics Y PL/Logic Programming Y 14 15 Note: 16 • Some topics from one or more of the first three Knowledge Units (Object-Oriented 17 Programming, Functional Programming, Event-Driven and Reactive Programming) are 18 likely to be integrated with topics in the Software Development Fundamentals 19 Knowledge Area in a curriculum’s introductory courses. Curricula will differ on which 20 topics are integrated in this fashion and which are delayed until later courses on software 21 development and programming languages. 22 • The Knowledge Units with core hours have a unified collection of learning outcomes, 23 which appears below these Knowledge Units. 24 - 129 - 25 PL/Object-Oriented Programming 26 [4 Core-Tier1 hours, 6 Core-Tier2 hours] 27 Topics: 28 [Core-Tier1] 29 • Object-oriented design 30 o Decomposition into objects carrying state and having behavior 31 o Class-hierarchy design for modeling 32 • Definition of classes: fields, methods, and constructors 33 • Subclasses, inheritance, and overriding 34 • Dynamic dispatch: definition of method-call 35 36 [Core-Tier2] 37 • Subtyping (cross-reference PL/Type Systems) 38 o Subtype polymorphism; implicit upcasts in typed languages 39 o Notion of behavioral replacement 40 o Relationship between subtyping and inheritance 41 • Object-oriented idioms for encapsulation 42 o Private fields 43 o Interfaces revealing only method signatures 44 o Abstract base classes 45 • Using collection classes, iterators, and other common library components 46 47 PL/Functional Programming 48 [3 Core-Tier1 hours, 4 Core-Tier2 hours] 49 Topics: 50 [Core-Tier1] 51 • Benefits of effect-free programming 52 o Data can be freely aliased or copied without introducing unintended effects from mutation 53 o Function calls have no side effects, facilitating compositional reasoning 54 o Variables are immutable, preventing unexpected changes to program data by other code 55 • Processing structured data (e.g., trees) via functions with cases for each data variant 56 o Associated language constructs such as discriminated unions and pattern-matching over them 57 o Compositional functions over structured data 58 • First-class functions (taking, returning, and storing functions) 59 60 [Core-Tier2] 61 • Function closures (functions using variables in the enclosing lexical environment) 62 o Basic meaning and definition -- creating closures at run-time by capturing the environment 63 o Canonical idioms: call-backs, arguments to iterators, reusable code via function arguments 64 o Using a closure to encapsulate data in its environment 65 • Defining higher-order operations on aggregates, especially map, reduce/fold, and filter 66 67 - 130 - 68 PL/Event-Driven and Reactive Programming 69 [2 Core-Tier2 hours] 70 This material can stand alone or be integrated with other knowledge units on concurrency, 71 asynchrony, and threading to allow contrasting events with threads. 72 Topics: 73 • Events and event handlers 74 • Canonical uses such as GUIs, mobile devices, robots, servers 75 • Using a reactive framework 76 o Defining event handlers/listeners 77 o Main event loop not under event-handler-writer’s control 78 • Externally-generated events and program-generated events 79 • Separation of model, view, and controller 80 81 PL/Basic Type Systems 82 [1 Core-Tier1 hour, 4 Core-Tier2 hours] 83 The core-tier2 hours would be profitably spent both on the core-tier2 topics and on a less shallow 84 treatment of the core-tier1 topics. 85 Topics: 86 [Core-Tier1] 87 88 • A type as a set of values together with a set of operations 89 o Primitive types (e.g., numbers, Booleans) 90 o Reference types 91 o Compound types built from other types (e.g., records, unions, arrays, lists, functions) 92 • Association of types to variables, arguments, results, and fields 93 • Type safety and errors caused by using values inconsistently with their intended types 94 • Goals and limitations of static typing 95 o Eliminating some classes of errors without running the program 96 o Inherent conservative approximation of static analysis due to undecidability 97 98 [Core-Tier2] 99 100 • Generic types (parametric polymorphism) 101 o Definition 102 o Use for generic libraries such as collections 103 o Comparison with ad hoc polymorphism (overloading) and subtype polymorphism 104 • Complementary benefits of static and dynamic typing 105 o Errors early vs. errors late/avoided 106 o Enforce invariants during code maintenance vs. postpone typing decisions while prototyping 107 o Avoid misuse of code vs. allow more code reuse 108 o Detect incomplete programs vs. allow incomplete programs to run 109 110 - 131 - 111 PL/Program Representation 112 [1 Core-Tier2 hour] 113 Topics: 114 • Programs that take (other) programs as input such as interpreters, compilers, type-checkers, documentation 115 generators, etc. 116 • Abstract syntax trees; contrast with concrete syntax 117 • Data structures to represent code for execution, translation, or transmission 118 119 PL/Language Translation and Execution 120 [3 Core-Tier2 hours] 121 Topics: 122 • Interpretation vs. compilation to native code vs. compilation to portable intermediate representation 123 • Language translation pipeline: parsing, optional type-checking, translation, linking, execution 124 o Execution as native code or within a virtual machine 125 o Alternatives like dynamic loading and dynamic code generation 126 • Run-time representation of core language constructs such as objects (method tables) and first-class 127 functions (closures) 128 • Run-time layout of memory: call-stack, heap, static data 129 o Implementing loops, recursion, and tail calls 130 • Automated vs. manual memory management; garbage collection as an automatic technique using the notion 131 of reachability 132 133 Learning outcomes for all PL Knowledge Units with Core Topics: 134 1. Compare and contrast (1) the procedural/functional approach—defining a function for each operation with 135 the function body providing a case for each data variant—and (2) the object-oriented approach—defining a 136 class for each data variant with the class definition providing a method for each operation. Understand 137 both as defining a matrix of operations and variants. [Evaluation] 138 2. Use subclassing to design simple class hierarchies that allow code to be reused for distinct subclasses. 139 [Application] 140 3. Use multiple encapsulation mechanisms, such as function closures, object-oriented interfaces, and support 141 for abstract datatypes, in multiple programming languages. [Application] 142 4. Define and use iterators and other operations on aggregates using idioms most natural in multiple 143 programming languages, including taking functions as arguments. [Application] 144 5. Write basic algorithms that avoid assigning to mutable state or considering object identity. [Application] 145 6. Write event handlers for use in reactive systems, such as GUIs. [Application] 146 7. Explain the relationship between object-oriented inheritance (code-sharing and overriding) and subtyping 147 (the idea of a subtype being usable in a context that expects the supertype). [Knowledge] 148 8. Explain benefits and limitations of static typing. [Knowledge] 149 9. For multiple programming languages, identify program properties checked statically and program 150 properties checked dynamically. Use this knowledge when writing and debugging programs. [Application] - 132 - 151 10. Distinguish a language definition (what constructs mean) from a particular language implementation 152 (compiler vs. interpreter, run-time representation of data objects, etc.). [Knowledge] 153 11. Explain how programming language implementations typically organize memory into global data, text, 154 heap, and stack sections and how features such as recursion and memory management map to this memory 155 model. [Knowledge] 156 12. Reason about memory leaks, dangling-pointer dereferences, and the benefits and limitations of garbage 157 collection. [Application] 158 13. Process some representation of code for some purpose, such as an interpreter, an expression optimizer, a 159 documentation generator, etc. [Application] 160 161 PL/Syntax Analysis 162 [Elective] 163 Topics: 164 • Scanning (lexical analysis) using regular expressions 165 • Parsing strategies including top-down (e.g., recursive descent, Earley parsing, or LL) and bottom-up (e.g., 166 backtracking or LR) techniques; role of context-free grammars 167 • Generating scanners and parsers from declarative specifications 168 169 Learning outcomes: 170 1. Use formal grammars to specify the syntax of languages. [Application] 171 2. Use declarative tools to generate parsers and scanners. [Application] 172 3. Identify key issues in syntax definitions: ambiguity, associativity, precedence. [Knowledge] 173 174 PL/Compiler Semantic Analysis 175 [Elective] 176 Topics: 177 • High-level program representations such as abstract syntax trees 178 • Scope and binding resolution 179 • Type checking 180 • Declarative specifications such as attribute grammars 181 182 Learning outcomes: 183 1. Implement context-sensitive, source-level static analyses such as type-checkers or resolving identifiers to 184 identify their binding occurrences. [Application] 185 186 - 133 - 187 PL/Code Generation 188 [Elective] 189 Topics: 190 • Instruction selection 191 • Procedure calls and method dispatching 192 • Register allocation 193 • Separate compilation; linking 194 • Instruction scheduling 195 • Peephole optimization 196 197 Learning outcomes: 198 1. Identify all essential steps for automatically converting source code into assembly or other low-level 199 languages. [Knowledge] 200 2. Generate the low-level code for calling functions/methods in modern languages. [Application] 201 3. Discuss opportunities for optimization introduced by naive translation and approaches for achieving 202 optimization. [Knowledge] 203 204 PL/Runtime Systems 205 [Elective] 206 Topics: 207 • Target-platform characteristics such as registers, instructions, bytecodes 208 • Dynamic memory management approaches and techniques: malloc/free, garbage collection (mark-sweep, 209 copying, reference counting), regions (also known as arenas or zones) 210 • Data layout for objects and activation records 211 • Just-in-time compilation and dynamic recompilation 212 • Other features such as class loading, threads, security, etc. 213 214 Learning outcomes: 215 1. Compare the benefits of different memory-management schemes, using concepts such as fragmentation, 216 locality, and memory overhead. [Knowledge] 217 2. Discuss benefits and limitations of automatic memory management. [Knowledge] 218 3. Identify the services provided by modern language run-time systems. [Knowledge] 219 4. Discuss advantages, disadvantages, and difficulties of dynamic recompilation. [Knowledge] 220 221 - 134 - 222 PL/Static Analysis 223 [Elective] 224 Topics: 225 • Relevant program representations, such as basic blocks, control-flow graphs, def-use chains, static single 226 assignment, etc. 227 • Flow-insensitive analyses, such as type-checking and scalable pointer and alias analyses 228 • Flow-sensitive analyses, such as forward and backward dataflow analyses 229 • Path-sensitive analyses, such as software model checking 230 • Tools and frameworks for defining analyses 231 • Role of static analysis in program optimization 232 • Role of static analysis in (partial) verification and bug-finding 233 234 Learning outcomes: 235 1. Define useful static analyses in terms of a conceptual framework such as dataflow analysis. [Application] 236 2. Communicate why an analysis is correct (sound and terminating). [Application] 237 3. Distinguish “may” and “must” analyses. [Knowledge] 238 4. Explain why potential aliasing limits sound program analysis and how alias analysis can help. [Knowledge] 239 5. Use the results of a static analysis for program optimization and/or partial program correctness. 240 [Application] 241 242 PL/Advanced Programming Constructs 243 [Elective] 244 Topics: 245 • Lazy evaluation and infinite streams 246 • Control Abstractions: Exception Handling, Continuations, Monads 247 • Object-oriented abstractions: Multiple inheritance, Mixins, Traits, Multimethods 248 • Metaprogramming: Macros, Generative programming, Model-based development 249 • Module systems 250 • String manipulation via pattern-matching 251 • Dynamic code evaluation (“eval”) 252 • Language support for checking assertions, invariants, and pre/post-conditions 253 254 Learning outcomes: 255 1. Use various advanced programming constructs and idioms correctly. [Application] 256 2. Discuss how various advanced programming constructs aim to improve program structure, software 257 quality, and programmer productivity. [Knowledge] 258 3. Discuss how various advanced programming constructs interact with the definition and implementation of 259 other language features. [Knowledge] 260 261 - 135 - 262 PL/Concurrency and Parallelism 263 [Elective] 264 Support for concurrency is a fundamental programming-languages issue with rich material in 265 programming language design, language implementation, and language theory. Due to coverage 266 in other Knowledge Areas, this elective Knowledge Unit aims only to complement the material 267 included elsewhere in the body of knowledge. Courses on programming languages are an 268 excellent place to include a general treatment of concurrency including this other material. 269 (Cross-reference: PD-Parallel and Distributed Computing) 270 Topics: 271 • Constructs for thread-shared variables and shared-memory synchronization 272 • Actor models 273 • Futures 274 • Language support for data parallelism 275 • Models for passing messages between sequential processes 276 • Effect of memory-consistency models on language semantics and correct code generation 277 278 Learning outcomes: 279 1. Write correct concurrent programs using multiple programming models. [Application] 280 2. Explain why programming languages do not guarantee sequential consistency in the presence of data races 281 and what programmers must do as a result. [Knowledge] 282 283 PL/Type Systems 284 [Elective] 285 Topics: 286 • Compositional type constructors, such as product types (for aggregates), sum types (for unions), function 287 types, quantified types, and recursive types 288 • Type checking 289 • Type safety as preservation plus progress 290 • Type inference 291 • Static overloading 292 293 Learning outcomes: 294 1. Define a type system precisely and compositionally. [Application] 295 2. For various foundational type constructors, identify the values they describe and the invariants they 296 enforce. [Knowledge] 297 3. Precisely specify the invariants preserved by a sound type system. [Knowledge] 298 299 - 136 - 300 PL/Formal Semantics 301 [Elective] 302 Topics: 303 • Syntax vs. semantics 304 • Lambda Calculus 305 • Approaches to semantics: Operational, Denotational, Axiomatic 306 • Proofs by induction over language semantics 307 • Formal definitions and proofs for type systems 308 • Parametricity 309 310 Learning outcomes: 311 1. Give a formal semantics for a small language. [Application] 312 2. Use induction to prove properties of all (or a well-defined subset of) programs in a language. [Application] 313 3. Use language-based techniques to build a formal model of a software system. [Application] 314 315 PL/Language Pragmatics 316 [Elective] 317 Topics: 318 • Principles of language design such as orthogonality 319 • Evaluation order, precedence, and associativity 320 • Eager vs. delayed evaluation 321 • Defining control and iteration constructs 322 • External calls and system libraries 323 324 Learning outcomes: 325 1. Discuss the role of concepts such as orthogonality and well-chosen defaults in language design. 326 [Knowledge] 327 2. Use crisp and objective criteria for evaluating language-design decisions. [Application] 328 329 PL/Logic Programming 330 [Elective] 331 Topics: 332 • Clausal representation of data structures and algorithms 333 • Unification 334 • Backtracking and search 335 336 Learning outcomes: 337 1. Use a logic language to implement conventional algorithms. [Application] 338 2. Use a logic language to implement algorithms employing implicit search using clauses and relations. 339 [Application] - 137 - 1 Software Development Fundamentals (SDF) 2 Fluency in the process of software development is a prerequisite to the study of most of 3 computer science. In order to effectively use computers to solve problems, students must be 4 competent at reading and writing programs in multiple programming languages. Beyond 5 programming skills, however, they must be able to design and analyze algorithms, select 6 appropriate paradigms, and utilize modern development and testing tools. This knowledge area 7 brings together those fundamental concepts and skills related to the software development 8 process. As such, it provides a foundation for other software-oriented knowledge areas, most 9 notably Programming Languages, Algorithms and Complexity, and Software Engineering. 10 It is important to note that this knowledge area is distinct from the old Programming 11 Fundamentals knowledge area from CC2001. Whereas that knowledge area focused exclusively 12 on the programming skills required in an introductory computer science course, this new 13 knowledge area is intended to fill a much broader purpose. It focuses on the entire software 14 development process, identifying those concepts and skills that should be mastered in the first 15 year of a computer science program. This includes the design and simple analysis of algorithms, 16 fundamental programming concepts and data structures, and basic software development 17 methods and tools. As a result of its broader purpose, the Software Development Fundamentals 18 knowledge area includes fundamental concepts and skills that could naturally be listed in other 19 software-oriented knowledge areas (e.g., programming constructs from Programming 20 Languages, simple algorithm analysis from Algorithms & Complexity, simple development 21 methodologies from Software Engineering). Likewise, each of these knowledge areas will 22 contain more advanced material that builds upon the fundamental concepts and skills listed here. 23 While broader in scope than the old Programming Fundamentals, this knowledge area still allows 24 for considerable flexibility in the design of first-year curricula. For example, the Fundamental 25 Programming Concepts unit identifies only those concepts that are common to all programming 26 paradigms. It is expected that an instructor would select one or more programming paradigms 27 (e.g., object-oriented programming, functional programming, scripting) to illustrate these 28 programming concepts, and would pull paradigm-specific content from the Programming 29 Languages knowledge area to fill out a course. Likewise, an instructor could choose to 30 emphasize formal analysis (e.g., Big-Oh, computability) or design methodologies (e.g., team 31 projects, software life cycle) early, thus integrating hours from the Programming Languages, 32 Algorithms and Complexity, and/or Software Engineering knowledge areas. Thus, the 42-hours 33 of material in this knowledge area should be augmented with core material from one or more of 34 these knowledge areas to form a complete and coherent first-year experience. 35 When considering the hours allocated to each knowledge unit, it should be noted that these hours 36 reflect the minimal amount of classroom coverage needed to introduce the material. Many 37 software development topics will reappear and be reinforced by later topics (e.g., applying 38 iteration constructs when processing lists). In addition, the mastery of concepts and skills from 39 this knowledge area requires a significant amount of software development experience outside of 40 class. 41 42 SDF. Software Development Fundamentals (42 Core-Tier1 hours) Includes Core-Tier1 hours Core-Tier2 hours Electives SDF/Algorithms and Design 11 N SDF/Fundamental Programming Concepts 10 N SDF/Fundamental Data Structures 12 N SDF/Development Methods 9 N 43 44 - 139 - 45 SDF/Algorithms and Design 46 [11 Core-Tier1 hours] 47 This unit builds the foundation for core concepts in the Algorithms & Complexity knowledge 48 area, most notably in the Basic Analysis and Algorithmic Strategies units. 49 Topics: 50 • The concept and properties of algorithms 51 o Informal comparison of algorithm efficiency (e.g., operation counts) 52 • The role of algorithms in the problem-solving process 53 • Problem-solving strategies 54 o Iterative and recursive mathematical functions 55 o Iterative and recursive traversal of data structure 56 o Divide-and-conquer strategies 57 • Implementation of algorithms 58 • Fundamental design concepts and principles 59 o Abstraction 60 o Program decomposition 61 o Encapsulation and information hiding 62 o Separation of behavior and implementation 63 64 Learning Outcomes: 65 1. Discuss the importance of algorithms in the problem-solving process. [Knowledge] 66 2. Discuss how a problem may be solved by multiple algorithms, each with different properties. [Knowledge] 67 3. Create algorithms for solving simple problems. [Application] 68 4. Use pseudocode or a programming language to implement, test, and debug algorithms for solving simple 69 problems. [Application] 70 5. Implement, test, and debug simple recursive functions and procedures. [Application] 71 6. Determine when a recursive solution is appropriate for a problem. [Evaluation] 72 7. Implement a divide-and-conquer algorithm for solving a problem. [Application] 73 8. Apply the techniques of decomposition to break a program into smaller pieces. [Application] 74 9. Identify the data components and behaviors of multiple abstract data types. [Application] 75 10. Implement a coherent abstract data type, with loose coupling between components and behaviors. 76 [Application] 77 11. Identify the relative strengths and weaknesses among multiple designs or implementations for a problem. 78 [Evaluation] 79 80 SDF/Fundamental Programming Concepts 81 [10 Core-Tier1 hours] 82 This unit builds the foundation for core concepts in the Programming Languages knowledge 83 area, most notably in the paradigm-specific units: Object-Oriented Programming, Functional 84 Programming, and Event-Driven & Reactive Programming. 85 Topics: 86 • Basic syntax and semantics of a higher-level language 87 • Variables and primitive data types (e.g., numbers, characters, Booleans) 88 • Expressions and assignments 89 • Simple I/O 90 • Conditional and iterative control structures - 140 - 91 • Functions and parameter passing 92 • The concept of recursion 93 94 Learning Outcomes: 95 1. Analyze and explain the behavior of simple programs involving the fundamental programming constructs 96 covered by this unit. [Evaluation] 97 2. Identify and describe uses of primitive data types. [Knowledge] 98 3. Write programs that use each of the primitive data types. [Application] 99 4. Modify and expand short programs that use standard conditional and iterative control structures and 100 functions. [Application] 101 5. Design, implement, test, and debug a program that uses each of the following fundamental programming 102 constructs: basic computation, simple I/O, standard conditional and iterative structures, the definition of 103 functions, and parameter passing. [Application] 104 6. Choose appropriate conditional and iteration constructs for a given programming task. [Evaluation] 105 7. Describe the concept of recursion and give examples of its use. [Knowledge] 106 8. Identify the base case and the general case of a recursively-defined problem. [Evaluation] 107 108 SDF/Fundamental Data Structures 109 [12 Core-Tier1 hours] 110 This unit builds the foundation for core concepts in the Algorithms & Complexity knowledge 111 area, most notably in the Fundamental Data Structures & Algorithms and Basic Computability & 112 Complexity units. 113 Topics: 114 • Arrays 115 • Records/structs (heterogeneous aggregates) 116 • Strings and string processing 117 • Stacks, queues, priority queues, sets & maps 118 • References and aliasing 119 • Simple linked structures 120 • Strategies for choosing the appropriate data structure 121 122 Learning Outcomes: 123 1. Discuss the appropriate use of built-in data structures. [Knowledge] 124 2. Describe common applications for each data structure in the topic list. [Knowledge] 125 3. Compare alternative implementations of data structures with respect to performance. [Evaluation] 126 4. Write programs that use each of the following data structures: arrays, strings, linked lists, stacks, queues, 127 sets, and maps. [Application] 128 5. Compare and contrast the costs and benefits of dynamic and static data structure implementations. 129 [Evaluation] 130 6. Choose the appropriate data structure for modeling a given problem. [Evaluation] 131 132 - 141 - 133 SDF/Development Methods 134 [9 Core-Tier1 hours] 135 This unit builds the foundation for core concepts in the Software Engineering knowledge area, 136 most notably in the Software Design and Software Processes units. 137 Topics: 138 • Program correctness 139 • The concept of a specification 140 • Defensive programming (e.g. secure coding, exception handling) 141 • Code reviews 142 • Testing fundamentals and test-case generation 143 • Test-driven development 144 • The role and the use of contracts, including pre- and post-conditions 145 • Unit testing 146 • Modern programming environments 147 • Programming using library components and their APIs 148 • Debugging strategies 149 • Documentation and program style 150 151 Learning Outcomes: 152 1. Explain why the creation of correct program components is important in the production of quality software. 153 [Knowledge] 154 2. Identify common coding errors that lead to insecure programs (e.g., buffer overflows, memory leaks, 155 malicious code) and apply strategies for avoiding such errors. [Application] 156 3. Conduct a personal code review (focused on common coding errors) on a program component using a 157 provided checklist. [Application] 158 4. Contribute to a small-team code review focused on component correctness. [Application] 159 5. Describe how a contract can be used to specify the behavior of a program component. [Knowledge] 160 6. Create a unit test plan for a medium-size code segment. [Application] 161 7. Apply a variety of strategies to the testing and debugging of simple programs. [Application] 162 8. Construct, execute and debug programs using a modern IDE (e.g., Visual Studio or Eclipse) and associated 163 tools such as unit testing tools and visual debuggers. [Application] 164 9. Construct and debug programs using the standard libraries available with a chosen programming language. 165 [Application] 166 10. Apply consistent documentation and program style standards that contribute to the readability and 167 maintainability of software. [Application] 168 - 142 - 1 Software Engineering (SE) 2 In every computing application domain, professionalism, quality, schedule, and cost are critical 3 to producing software systems. Because of this, the elements of software engineering are 4 applicable to developing software in all areas of computing. A wide variety of software 5 engineering practices have been developed and utilized since the need for a discipline of 6 software engineering was first recognized. Many trade-offs between these different practices 7 have also been identified. Practicing software engineers have to select and apply appropriate 8 techniques and practices to a given development effort to maximize value. To learn how to do 9 this, they study the elements of software engineering. 10 Software engineering is the discipline concerned with the application of theory, knowledge, and 11 practice to effectively and efficiently build reliable software systems that satisfy the requirements 12 of customers and users. This discipline is applicable to small, medium, and large-scale systems. 13 It encompasses all phases of the lifecycle of a software system, including requirements 14 elicitation, analysis and specification; design; construction; verification and validation; 15 deployment; and operation and maintenance. Whether small or large, following a traditional 16 disciplined development process, an agile approach, or some other method, software engineering 17 is concerned with the best way to build good software systems. 18 Software engineering uses engineering methods, processes, techniques, and measurements. It 19 benefits from the use of tools for managing software development; analyzing and modeling 20 software artifacts; assessing and controlling quality; and for ensuring a disciplined, controlled 21 approach to software evolution and reuse. The software engineering toolbox has evolved over the 22 years. For instance, the use of contracts, with requires and ensure clauses and class invariants, is 23 one good practice that has become more common. Software development, which can involve an 24 individual developer or a team or teams of developers, requires choosing the most appropriate 25 tools, methods, and approaches for a given development environment. 26 27 Students and instructors need to understand the impacts of specialization on software engineering 28 approaches. For example, specialized systems include: 29 • Real time systems 30 • Client-server systems 31 • Distributed systems 32 • Parallel systems 33 • Web-based systems 34 • High integrity systems 35 • Games 36 • Mobile computing 37 • Domain specific software (e.g., scientific computing or business applications) 38 Issues raised by each of these specialized systems demand specific treatments in each phase of 39 software engineering. Students must become aware of the differences between general software 40 engineering techniques and principles and the techniques and principles needed to address issues 41 specific to specialized systems. 42 An important effect of specialization is that different choices of material may need to be made 43 when teaching applications of software engineering, such as between different process models, 44 different approaches to modeling systems, or different choices of techniques for carrying out any 45 of the key activities. This is reflected in the assignment of core and elective material, with the 46 core topics and learning outcomes focusing on the principles underlying the various choices, and 47 the details of the various alternatives from which the choices have to be made being assigned to 48 the elective material. 49 Another division of the practices of software engineering is between those concerned with the 50 fundamental need to develop systems that implement correctly the functionality that is required 51 for them, and those concerned with other qualities for systems and the trade-offs needed to 52 balance these qualities. This division too is reflected in the assignment of core and elective 53 material, so that topics and learning outcomes concerned with the basic methods for developing - 144 - 54 such system are assigned to the core, and those that are concerned with other qualities and trade- 55 offs between them are assigned to the elective material. 56 In general, students learn best at the application level much of the material defined in the SE KA 57 by participating in a project. Such projects should require students to work on a team to develop 58 a software system through as much of its lifecycle as is possible. Much of software engineering 59 is devoted to effective communication among team members and stakeholders. Utilizing project 60 teams, projects can be sufficiently challenging to require the use of effective software 61 engineering techniques and that students develop and practice their communication skills. While 62 organizing and running effective projects within the academic framework can be challenging, the 63 best way to learn to apply software engineering theory and knowledge is in the practical 64 environment of a project. The minimum hours specified for some knowledge units in this 65 document may appear insufficient to accomplish associated application-level learning outcomes. 66 It should be understood that these outcomes are to be achieved through project experience that 67 may even occur later in the curriculum than when the topics within the knowledge unit are 68 introduced. 69 Note: The SDF/Development Methods knowledge unit includes 9 Core-Tier1 hours that 70 constitute an introduction to certain aspects of software engineering. The knowledge units, 71 topics and core hour specifications in this document must be understood as assuming previous 72 exposure to the material described in SDF/Development Methods. 73 - 145 - 74 SE. Software Engineering (6 Core-Tier1 hours; 21 Core-Tier2 hours) Core-Tier1 hours Core-Tier2 hours Includes Electives SE/Software Processes 1 2 Y SE/Software Project Management 3 Y SE/Tools and Environments 2 N SE/Requirements Engineering 1 3 Y SE/Software Design 4 4 Y SE/Software Construction 2 Y SE/Software Verification Validation 3 Y SE/Software Evolution 1 Y SE/Formal Methods Y SE/Software Reliability 1 Y 75 76 - 146 - 77 SE/Software Processes 78 [1 Core-Tier1 hours; 2 Core-Tier2 hours] 79 Topics: 80 [Core-Tier1] 81 • Systems level considerations, i.e., the interaction of software with its intended environment 82 • Phases of software life-cycles 83 • Programming in the large vs. individual programming 84 85 [Core-Tier2] 86 • Software process models (e.g., waterfall, incremental, agile) 87 88 [Elective] 89 • Software quality concepts 90 • Process improvement 91 • Software process capability maturity models 92 • Software process measurements 93 94 Learning Outcomes: 95 [Core-Tier1] 96 1. Describe how software can interact with and participate in various systems including information 97 management, embedded, process control, and communications systems. [Knowledge] 98 2. Differentiate among the phases of software development. [Knowledge] 99 3. Explain the concept of a software life cycle and provide an example, illustrating its phases including the 100 deliverables that are produced. [Knowledge] 101 4. Describe how programming in the large differs from individual efforts with respect to understanding a large 102 code base, code reading, understanding builds, and understanding context of changes. [Knowledge] 103 104 [Core-Tier2] 105 1. Describe the difference between principles of the waterfall model and models using iterations. 106 [Knowledge] 107 2. Compare several common process models with respect to their value for development of particular classes 108 of software systems taking into account issues such as requirement stability, size, and non-functional 109 characteristics. [Application] 110 111 [Elective] 112 1. Define software quality and describe the role of quality assurance activities in the software process. 113 [Knowledge] 114 2. Describe the intent and fundamental similarities among process improvement approaches. [Knowledge] 115 3. Compare several process improvement models such as CMM, CMMI, CQI, Plan-Do-Check-Act, or 116 ISO9000. [Knowledge] 117 4. Use a process improvement model such as PSP to assess a development effort and recommend approaches 118 to improvement. [Application] 119 5. Explain the role of process maturity models in process improvement. [Knowledge] 120 6. Describe several process metrics for assessing and controlling a project. [Knowledge] 121 7. Use project metrics to describe the current state of a project. [Application] 122 - 147 - 123 SE/Software Project Management 124 [3 Core-Tier2 hours] 125 Topics: 126 [Core-Tier2] 127 • Risk 128 o The role of risk in the life cycle 129 o Risk categories including security, safety, market, financial, technology, people, quality, structure 130 and process 131 o Risk identification 132 o Risk tolerance (e.g., risk-adverse, risk-neutral, risk-seeking) 133 o Risk planning 134 o Risk removal, reduction and control 135 • Team participation 136 o Team processes including responsibilities for tasks, meeting structure, and work schedule 137 o Roles and responsibilities in a software team 138 o Team conflict resolution 139 o Risks associated with virtual teams (communication, perception, structure) 140 • Effort Estimation (at the personal level) 141 142 [Elective] 143 • Team management 144 o Team organization and decision-making 145 o Role identification and assignment 146 o Individual and team performance assessment 147 • Project management 148 o Scheduling and tracking 149 o Project management tools 150 o Cost/benefit analysis 151 • Software measurement and estimation techniques 152 • Software quality assurance and the role of measurements 153 • Principles of risk management 154 • Risk analysis and evaluation 155 • System-wide approach to risk including hazards associated with tools 156 157 Learning Outcomes: 158 [Core-Tier2] 159 1. List several examples of software risks. [Knowledge] 160 2. Describe the impact of risk in a software development life cycle. [Knowledge] 161 3. Describe different categories of risk in software systems. [Knowledge] 162 4. Describe the impact of risk tolerance on the software development process. [Application] 163 5. Identify risks and describe approaches to managing risk (avoidance, acceptance, transference, mitigation), 164 and characterize the strengths and shortcomings of each. [Knowledge] 165 6. Explain how risk affects decisions in the software development process. [Application] 166 7. Identify behaviors that contribute to the effective functioning of a team. [Knowledge] 167 8. Create and follow an agenda for a team meeting. [Application] 168 9. Identify and justify necessary roles in a software development team. [Application] 169 10. Understand the sources, hazards, and potential benefits of team conflict. [Application] 170 11. Apply a conflict resolution strategy in a team setting. [Application] 171 12. Use an ad hoc method to estimate software development effort (e.g., time) and compare to actual effort 172 required. [Application] - 148 - 173 174 [Elective] 175 1. Identify security risks for a software system. [Application] 176 2. Demonstrate through involvement in a team project the central elements of team building and team 177 management. [Application] 178 3. Identify several possible team organizational structures and team decision-making processes. [Knowledge] 179 4. Create a team by identifying appropriate roles and assigning roles to team members. [Application] 180 5. Assess and provide feedback to teams and individuals on their performance in a team setting. [Application] 181 6. Prepare a project plan for a software project that includes estimates of size and effort, a schedule, resource 182 allocation, configuration control, change management, and project risk identification and management. 183 [Application] 184 7. Track the progress of a project using appropriate project metrics. [Application] 185 8. Compare simple software size and cost estimation techniques. [Application] 186 9. Use a project management tool to assist in the assignment and tracking of tasks in a software development 187 project. [Application] 188 10. Demonstrate a systematic approach to the task of identifying hazards and risks in a particular situation. 189 [Application] 190 11. Apply the basic principles of risk management in a variety of simple scenarios including a security 191 situation. [Application] 192 12. Conduct a cost/benefit analysis for a risk mitigation approach. [Application] 193 13. Identify and analyze some of the risks for an entire system that arise from aspects other than the software. 194 195 SE/Tools and Environments 196 [2 Core-Tier2 hours] 197 Topics: 198 [Core-Tier2] 199 • Software configuration management and version control; release management 200 • Requirements analysis and design modeling tools 201 • Testing tools including static and dynamic analysis tools 202 • Programming environments that automate parts of program construction processes (e.g., automated builds) 203 • Tool integration concepts and mechanisms 204 205 Learning Outcomes: 206 [Core-Tier2] 207 1. Describe the difference between centralized and distributed software configuration management. 208 [Knowledge] 209 2. Identify configuration items and use a source code control tool in a small team-based project. [Application] 210 3. Describe the issues that are important in selecting a set of tools for the development of a particular software 211 system, including tools for requirements tracking, design modeling, implementation, build automation, and 212 testing. [Knowledge] 213 4. Demonstrate the capability to use software tools in support of the development of a software product of 214 medium size. [Application] 215 216 - 149 - 217 SE/Requirements Engineering 218 [1 Core-Tier1 hour; 3 Core-Tier2 hours] 219 Topics: 220 [Core-Tier1] 221 • Fundamentals of software requirements elicitation and modeling 222 223 [Core-Tier2] 224 • Properties of requirements including consistency, validity, completeness, and feasibility 225 • Software requirements elicitation 226 • Describing functional requirements using, for example, use cases or users stories 227 • Non-functional requirements and their relationship to software quality 228 • Describing system data using, for example, class diagrams or entity-relationship diagrams 229 • Evaluation and use of requirements specifications 230 231 [Elective] 232 • Requirements analysis modeling techniques 233 • Acceptability of certainty / uncertainty considerations regarding software / system behavior 234 • Prototyping 235 • Basic concepts of formal requirements specification 236 • Requirements specification 237 • Requirements validation 238 • Requirements tracing 239 240 Learning Outcomes: 241 [Core-Tier1] 242 1. Describe the fundamental challenges of and common techniques used for requirements elicitation. 243 [Knowledge] 244 2. Interpret a given requirements model for a simple software system. [Knowledge] 245 246 [Core-Tier2] 247 1. Conduct a review of a set of software requirements to determine the quality of the requirements with 248 respect to the characteristics of good requirements. [Application] 249 2. List the key components of a use case or similar description of some behavior that is required for a system 250 and discuss their role in the requirements engineering process. [Knowledge] 251 3. List the key components of a class diagram or similar description of the data that a system is required to 252 handle. [Knowledge] 253 4. Identify both functional and non-functional requirements in a given requirements specification for a 254 software system. [Application] 255 256 [Elective] 257 1. Apply key elements and common methods for elicitation and analysis to produce a set of software 258 requirements for a medium-sized software system. [Application] 259 2. Use a common, non-formal method to model and specify (in the form of a requirements specification 260 document) the requirements for a medium-size software system [Application] 261 3. Translate into natural language a software requirements specification (e.g., a software component contract) 262 written in a formal specification language. [Application] 263 4. Create a prototype of a software system to mitigate risk in requirements. [Application] - 150 - 264 5. Differentiate between forward and backward tracing and explain their roles in the requirements validation 265 process. [Knowledge] 266 267 SE/Software Design 268 [4 Core-Tier1 hours; 4 Core-Tier2 hours] 269 Topics: 270 [Core-Tier1] 271 • Overview of design paradigms 272 • System design principles: divide and conquer (architectural design and detailed design), separation of 273 concerns, information hiding, coupling and cohesion, re-use of standard structures. 274 • Appropriate models of software designs, including structure and behavior. 275 • Software architecture concepts 276 277 [Core-Tier2] 278 • Design Paradigms such as structured design (top-down functional decomposition), object-oriented analysis 279 and design, event driven design, component-level design, data-structured centered, aspect oriented, 280 function oriented, service oriented. 281 • Relationships between requirements and designs: transformation of models, design of contracts. 282 • Architectural design: standard architectures (e.g. client-server, n-layer, transform centered, pipes-and- 283 filters, etc). 284 • Refactoring designs and the use of design patterns. 285 • The use of components in design: component selection, design, adaptation and assembly of components, 286 components and patterns, components and objects, (for example, build a GUI using a standard widget set). 287 288 [Elective] 289 • Internal design qualities, and models for them: efficiency and performance, redundancy and fault 290 tolerance, traceability of requirements. 291 • External design qualities, and models for them: functionality, reliability, performance and efficiency, 292 usability, maintainability, portability. 293 • Measurement and analysis of design quality. 294 • Tradeoffs between different aspects of quality. 295 • Application frameworks. 296 • Middleware: the object-oriented paradigm within middleware, object request brokers and marshalling, 297 transaction processing monitors, workflow systems. 298 299 Learning Outcomes: 300 [Core-Tier1] 301 1. Articulate design principles including separation of concerns, information hiding, coupling and cohesion, 302 and encapsulation. [Knowledge] 303 2. Use a design paradigm to design a simple software system, and explain how system design principles have 304 been applied in this design. [Application] 305 3. Construct models of the design of a simple software system that are appropriate for the paradigm used to 306 design it. [Application] 307 4. For the design of a simple software system within the context of a single design paradigm, describe the 308 software architecture of that system. [Knowledge] 309 5. Within the context of a single design paradigm, describe one or more design patterns that could be 310 applicable to the design of a simple software system. [Knowledge] - 151 - 311 6. Given a high-level design, identify the software architecture by differentiating among common software 312 architectures such as 3-tier, pipe-and-filter, and client-server. [Knowledge] 313 314 [Core-Tier2] 315 1. For a simple system suitable for a given scenario, discuss and select an appropriate design paradigm. 316 [Application] 317 2. Create appropriate models for the structure and behavior of software products from their requirements 318 specifications. [Application] 319 3. Explain the relationships between the requirements for a software product and the designed structure and 320 behavior, in terms of the appropriate models and transformations of them. [Evaluation] 321 4. Apply simple examples of patterns in a software design. [Application] 322 5. Investigate the impact of software architectures selection on the design of a simple system. 323 6. Select suitable components for use in the design of a software product. [Application] 324 7. Explain how suitable components might need to be adapted for use in the design of a software product. 325 [Knowledge]. 326 8. Design a contract for a typical small software component for use in a given system. [Application] 327 328 [Elective] 329 1. Discuss and select appropriate software architecture for a simple system suitable for a given scenario. 330 [Application] 331 2. Apply models for internal and external qualities in designing software components to achieve an acceptable 332 tradeoff between conflicting quality aspects. [Application] 333 3. Analyze a software design from the perspective of a significant internal quality attribute. [Evaluation] 334 4. Analyze a software design from the perspective of a significant external quality attribute. [Evaluation] 335 5. Explain the role of objects in middleware systems and the relationship with components. [Knowledge] 336 6. Apply component-oriented approaches to the design of a range of software, such as using components for 337 concurrency and transactions, for reliable communication services, for database interaction including 338 services for remote query and database management, or for secure communication and access. 339 [Application] 340 - 152 - 341 342 SE/Software Construction 343 [2 Core-Tier2 hours] 344 Topics: 345 [Core-Tier2] 346 • Coding practices: techniques, idioms/patterns, mechanisms for building quality programs 347 o Defensive coding practices 348 o Secure coding practices 349 o Using exception handling mechanisms to make programs more robust, fault-tolerant 350 • Coding standards 351 • Integration strategies 352 353 [Elective] 354 • Robust And Security Enhanced Programming 355 o Defensive programming 356 o Principles of secure design and coding: 357 o Principle of least privilege 358 o Principle of fail-safe defaults 359 o Principle of psychological acceptability 360 • Potential security problems in programs 361 o Buffer and other types of overflows 362 o Race conditions 363 o Improper initialization, including choice of privileges 364 o Checking input 365 o Assuming success and correctness 366 o Validating assumptions 367 • Documenting security considerations in using a program 368 369 Learning Outcomes: 370 [Core-Tier2] 371 1. Describe techniques, coding idioms and mechanisms for implementing designs to achieve desired 372 properties such as reliability, efficiency, and robustness. [Knowledge] 373 2. Build robust code using exception handling mechanisms. [Application] 374 3. Describe secure coding and defensive coding practices. [Knowledge] 375 4. Select and use a defined coding standard in a small software project. [Application] 376 5. Compare and contrast integration strategies including top-down, bottom-up, and sandwich integration. 377 [Knowledge] 378 379 [Elective] 380 1. Rewrite a simple program to remove common vulnerabilities, such as buffer overflows, integer overflows 381 and race conditions 382 2. State and apply the principles of least privilege and fail-safe defaults. 383 3. Write a simple library that performs some non-trivial task and will not terminate the calling program 384 regardless of how it is called 385 386 - 153 - 387 SE/Software Verification Validation 388 [3 Core-Tier2 hours] 389 Topics: 390 [Core-Tier2] 391 • Verification and validation concepts 392 • Inspections, reviews, audits 393 • Testing types, including human computer interface, usability, reliability, security, conformance to 394 specification 395 • Testing fundamentals 396 • Unit, integration, validation, and system testing 397 • Test plan creation and test case generation 398 • Black-box and white-box testing techniques 399 • Defect tracking 400 • Testing parallel and distributed systems 401 402 [Elective] 403 • Static approaches and dynamic approaches to verification 404 • Regression testing 405 • Test-driven development 406 • Validation planning; documentation for validation 407 • Object-oriented testing; systems testing 408 • Verification and validation of non-code artifacts (documentation, help files, training materials) 409 • Fault logging, fault tracking and technical support for such activities 410 • Fault estimation and testing termination including defect seeding 411 412 Learning Outcomes: 413 [Core-Tier2] 414 1. Distinguish between program validation and verification. [Knowledge] 415 2. Describe the role that tools can play in the validation of software. [Knowledge] 416 3. Undertake, as part of a team activity, an inspection of a medium-size code segment. [Application] 417 4. Describe and distinguish among the different types and levels of testing (unit, integration, systems, and 418 acceptance). [Knowledge] 419 5. Describe techniques for identifying significant test cases for unit, integration, and system testing. 420 [Knowledge] 421 6. Use a defect tracking tool to manage software defects in a small software project. [Application] 422 7. Describe the issues and approaches to testing distributed and parallel systems. [Knowledge] 423 424 [Elective] 425 1. Create, evaluate, and implement a test plan for a medium-size code segment. [Application] 426 2. Compare static and dynamic approaches to verification. [Knowledge] 427 3. Discuss the issues involving the testing of object-oriented software. [Application] 428 4. Describe techniques for the verification and validation of non-code artifacts. [Knowledge] 429 5. Describe approaches for fault estimation. [Knowledge] 430 6. Estimate the number of faults in a small software application based on fault density and fault seeding. 431 [Application] 432 7. Conduct an inspection or review of software source code for a small or medium sized software project. 433 [Application] - 154 - 434 435 SE/Software Evolution 436 [1 Core-Tier2 hour] 437 Topics: 438 [Core-Tier2] 439 • Software development in the context of large, pre-existing code bases 440 • Software evolution 441 • Characteristics of maintainable software 442 • Reengineering systems 443 • Software reuse 444 445 Learning Outcomes: 446 [Core-Tier2] 447 1. Identify the principal issues associated with software evolution and explain their impact on the software life 448 cycle. [Knowledge] 449 2. Discuss the challenges of evolving systems in a changing environment. [Knowledge] 450 3. Outline the process of regression testing and its role in release management. [Application] 451 4. Discuss the advantages and disadvantages of software reuse. [Knowledge] 452 453 [Elective] 454 1. Estimate the impact of a change request to an existing product of medium size. [Application] 455 2. Identify weaknesses in a given simple design, and removed them through refactoring. [Application] 456 457 SE/Formal Methods 458 [Elective] 459 The topics listed below have a strong dependency on core material from the Discrete Structures 460 area, particularly knowledge units DS/Functions Relations And Sets, DS/Basic Logic and 461 DS/Proof Techniques. 462 Topics: 463 • Role of formal specification and analysis techniques in the software development cycle 464 • Program assertion languages and analysis approaches (including languages for writing and analyzing pre- 465 and post-conditions, such as OCL, JML) 466 • Formal approaches to software modeling and analysis 467 • Model checkers 468 • Model finders 469 • Tools in support of formal methods 470 471 Learning Outcomes: 472 1. Describe the role formal specification and analysis techniques can play in the development of complex 473 software and compare their use as validation and verification techniques with testing. [Knowledge] - 155 - 474 2. Apply formal specification and analysis techniques to software designs and programs with low complexity. 475 [Application] 476 3. Explain the potential benefits and drawbacks of using formal specification languages. [Knowledge] 477 4. Create and evaluate program assertions for a variety of behaviors ranging from simple through complex. 478 [Application] 479 5. Using a common formal specification language, formulate the specification of a simple software system 480 and derive examples of test cases from the specification. [Application] 481 482 SE/Software Reliability 483 [1 Core-Tier2] 484 Topics: 485 [Core-Tier2] 486 • Software reliability engineering concepts 487 • Software reliability, system reliability and failure behavior (cross-reference SF9/Reliability Through 488 Redundancy) 489 • Fault lifecycle concepts and techniques 490 491 [Elective] 492 • Software reliability models 493 • Software fault tolerance techniques and models 494 • Software reliability engineering practices 495 • Measurement-based analysis of software reliability 496 497 Learning Outcomes: 498 [Core-Tier2] 499 1. Explain the problems that exist in achieving very high levels of reliability. [Knowledge] 500 2. Describe how software reliability contributes to system reliability [Knowledge] 501 3. List approaches to minimizing faults that can be applied at each stage of the software lifecycle. 502 [Knowledge] 503 504 [Elective] 505 1. Compare the characteristics of three different reliability modeling approaches. [Knowledge] 506 2. Demonstrate the ability to apply multiple methods to develop reliability estimates for a software system. 507 [Application] 508 3. Identify methods that will lead to the realization of a software architecture that achieves a specified 509 reliability level of reliability. [Application] 510 4. Identify ways to apply redundancy to achieve fault tolerance for a medium-sized application. [Application] - 156 - 1 Systems Fundamentals (SF) 2 The underlying hardware and software infrastructure upon which applications are constructed is 3 collectively described by the term "computer systems." Computer systems broadly span the sub- 4 disciplines of operating systems, parallel and distributed systems, communications networks, and 5 computer architecture. Traditionally, these areas are taught in a non-integrated way through 6 independent courses. However these sub-disciplines increasingly share important common 7 fundamental concepts within their respective cores. These include computational paradigms, 8 parallelism, cross-layer communications, state and state transition, resource allocation and 9 scheduling, and so on. This knowledge area presents an integrative cross-layer view of these 10 fundamental concepts in a unified albeit simplified fashion, providing a common foundation for 11 the different specialized mechanisms and policies appropriate to the particular knowledge areas 12 that it underlies. An organizing principle is “programming for performance”: what does a 13 programmer need to know about the underlying system in order to achieve high performance in 14 an application being developed. 15 16 SF. Systems Fundamentals [18 core Tier 1, 9 core Tier 2 hours, 27 total] Core-Tier 1 Core-Tier 2 Includes hours hours Electives SF/Computational Paradigms 3 SF/Cross-Layer Communications 3 SF/State-State Transition-State 6 Machines SF/System Support for Parallelism 3 SF/Performance 3 SF/Resource Allocation and Scheduling 2 SF/Proximity 3 SF/Virtualization and Isolation 2 SF/Reliability through Redundancy 2 17 18 19 SF/Computational Paradigms 20 [3 Core-Tier 1 hours] 21 [Cross-reference PD/parallelism fundamentals: The view presented here is the multiple 22 representations of a system across layers, from hardware building blocks to application 23 components, and the parallelism available in each representation; PD/parallelism fundamentals 24 focuses on the application structuring concepts for parallelism.] 25 Topics: 26 • A computing system as a layered collection of representations 27 • Basic building blocks and components of a computer (gates, flip-flops, registers, interconnections; 28 Datapath + Control + Memory) 29 • Hardware as a computational paradigm: Fundamental logic building blocks (logic gates, flip-flops, 30 counters, registers, PL); Logic expressions, minimization, sum of product forms 31 • Application-level sequential processing: single thread [xref PF/] 32 • Simple application-level parallel processing: request level (web services/client-server/distributed), single 33 thread per server, multiple threads with multiple servers 34 • Basic concept of pipelining, overlapped processing stages 35 • Basic concept of scaling: going faster vs. handling larger problems 36 37 Learning Outcomes: 38 1. List commonly encountered patterns of how computations are organized [Knowledge]. 39 2. Describe the basic building blocks of computers and their role in the historical development of computer 40 architecture [Knowledge]. 41 3. Articulate the differences between single thread vs. multiple thread, single server vs. multiple server 42 models, motivated by real world examples (e.g., cooking recipes, lines for multiple teller machines, couple 43 shopping for food, wash-dry-fold, etc.) [Knowledge]. 44 4. Articulate the concept of strong vs. weak scaling, i.e., how performance is affected by scale of problem vs. 45 scale of resources to solve the problem. This can be motivated by the simple, real-world examples 46 [Knowledge]. 47 5. Design and simulate a simple logic circuit using the fundamental building blocks of logic design 48 [Application]. 49 6. Write a simple sequential problem and a simple parallel version of the same program [Application]. 50 7. Evaluate performance of simple sequential and parallel versions of a program with different problem sizes, 51 and be able to describe the speed-ups achieved [Evaluation]. 52 53 SF/Cross-Layer Communications 54 [3 Core-Tier 1 hours] 55 Topics: 56 • Programming abstractions, interfaces, use of libraries 57 • Distinction between application and OS services, remote procedure call 58 • Interactions between applications and virtual machines 59 • Reliability 60 61 - 158 - 62 Learning Outcomes: 63 1. Describe how computing systems are constructed of layers upon layers, based on separation of concerns, 64 with well-defined interfaces, hiding details of low layers from the higher layers [knowledge]. 65 2. Recognize that hardware, VM, OS, application are just additional layers of interpretation/processing 66 [knowledge]. 67 3. Describe the mechanisms of how errors are detected, signaled back, and handled through the layers 68 [knowledge] 69 4. Construct a simple program using methods of layering, error detection and recovery, and reflection of error 70 status across layers [application]. 71 5. Find bugs in a layered program by using tools for program tracing, single stepping, and debugging 72 [evaluation]. 73 74 SF/State-State Transition-State Machines 75 [6 Core-Tier 1 hours] 76 [Cross-reference AL/Basic Computability and Complexity, OS/state and state diagrams, 77 NC/protocols] 78 Topics: 79 • Digital vs. analog/discrete vs. continuous systems 80 • Simple logic gates, logical expressions, Boolean logic simplification 81 • Clocks, state, sequencing 82 • Combinational Logic, Sequential Logic, Registers, Memories 83 • Computers and Network Protocols as examples of State Machines 84 85 Learning Outcomes: 86 1. Describe computations as a system with a known set of configurations, and a byproduct of the computation 87 is to transition from one unique configuration (state) to another (state) [Knowledge]. 88 2. Recognize the distinction between systems whose output is only a function of their input (Combinational) 89 and those with memory or history (Sequential) [Knowledge]. 90 3. Describe a computer as a state machine that interprets machine instructions [Knowledge]. 91 4. Explain how a program or network protocol can also be expressed as a state machine, and that alternative 92 representations for the same computation can exist [Knowledge]. 93 5. Develop state machine descriptions for simple problem statement solutions (e.g., traffic light sequencing, 94 pattern recognizers) [Application]. 95 6. Derive time-series behavior of a state machine from its state machine representation [Evaluation]. 96 97 SF/System Support for Parallelism 98 [3 Core-Tier1 hours] 99 [Cross-reference: PD/Parallelism Fundamentals] 100 Topics: 101 • Execution and runtime models that distinguish Sequential vs. Parallel processing 102 • System organizations that support Request and Task parallelism and other parallel processing paradigms, 103 such as Client-Server/Web Services, Thread parallelism(Fork-Join), and Pipelining 104 • Multicore architectures and hardware support for parallelism 105 - 159 - 106 Learning Outcomes: 107 1. For a given program, distinguish between its sequential and parallel execution, and the performance 108 implications thereof [knowledge]. 109 2. Demonstrate on an execution time line that parallel events and operations can take place simultaneously 110 (i.e., at the same time). Explain how work can be performed in less elapsed time if this can be exploited 111 [knowledge]. 112 3. Explain other uses of parallelism, such as for reliability/redundancy of execution [knowledge]. 113 4. Define the differences between the concepts of Instruction Parallelism, Data Parallelism, Thread 114 Parallelism/Multitasking, Task/Request Parallelism. 115 5. Write a simple parallel program in more than one paradigm so as to be able to compare and contrast ease of 116 expression and performance in solving a given problem [application]. 117 6. Use performance tools to measure speed-up achieved by parallel programs in terms of both problem size 118 and number of resources [evaluation]. 119 120 SF/Performance 121 [3 Core-Tier 1 hours] 122 [Cross-reference PD/Parallel Performance] 123 Topics: 124 • Figures of performance merit (e.g., speed of execution, energy consumption, bandwidth vs. latency, 125 resource cost) 126 • Benchmarks (e.g., SPEC) and measurement methods 127 • CPI equation (Execution time = # of instructions * cycles/instruction * time/cycle) as tool for 128 understanding tradeoffs in the design of instruction sets, processor pipelines, and memory system 129 organizations. 130 • Amdahl’s Law: the part of the computation that cannot be sped up limits the effect of the parts that can 131 132 Learning Outcomes: 133 1. Explain how the components of system architecture contribute to improving its performance [Knowledge]. 134 2. Describe Amdahl’s law and its implications for parallel system speed-up when limited by sequential 135 portions, e.g., in processing pipelines [Knowledge]. 136 3. Benchmark a parallel program with different data sets in order to iteratively improve its performance 137 [Application]. 138 4. Use software tools to profile and measure program performance [Evaluation]. 139 140 SF/Resource Allocation and Scheduling 141 [2 Core-Tier 2 hours] 142 Topics: 143 • Kinds of resources: processor share, memory, disk, net bandwidth 144 • Kinds of scheduling: first-come, priority 145 • Advantages of fair scheduling, preemptive scheduling 146 147 Learning Outcomes: 148 1. Define how finite computer resources (e.g., processor share, memory, storage and network bandwidth) are 149 managed by their careful allocation to existing entities [Knowledge]. - 160 - 150 2. Describe the scheduling algorithms by which resources are allocated to competing entities, and the figures 151 of merit by which these algorithms are evaluated, such as fairness [Knowledge]. 152 3. Implement simple scheduling algorithms [Application]. 153 4. Measure figures of merit of different scheduler implementations [Evaluation]. 154 155 SF/Proximity 156 [3 Core-Tier 2 hours] 157 [Cross-reference: AR/Memory Management, OS/VM/Virtual Memory] 158 Topics: 159 • Speed of light and computers (one foot per nanosecond vs. one GHz clocks) 160 • Latencies in computer systems: memory vs. disk latencies vs. across the network memory 161 • Caches, spatial and temporal locality, in processors and systems 162 • Elementary introduction into the processor memory hierarchy: registers and multi-level caches, and the 163 formula for average memory access time 164 165 Learning Outcomes: 166 1. Explain the importance of locality in determining performance [Knowledge]. 167 2. Describe why things that are close in space take less time to access [Knowledge]. 168 3. Calculate average memory access time and describe the tradeoffs in memory hierarchy performance in 169 terms of capacity, miss/hit rate, and access time [Evaluation]. 170 171 SF/Virtualization and Isolation 172 [2 Core-Tier 2 hours] 173 Topics: 174 • Rationale for protection and predictable performance 175 • Levels of indirection, illustrated by virtual memory for managing physical memory resources 176 • Methods for implementing virtual memory and virtual machines 177 178 Learning Outcomes: 179 1. Explain why it is important to isolate and protect the execution of individual programs and environments 180 that share common underlying resources, including the processor, memory, storage, and network access 181 [Knowledge]. 182 2. Describe how the concept of indirection can create the illusion of a dedicated machine and its resources 183 even when physically shared among multiple programs and environments [Knowledge]. 184 3. Measure the performance of two application instances running on separate virtual machines, and determine 185 the effect of performance isolation [Evaluation]. 186 187 - 161 - 188 SF/Reliability through Redundancy 189 [2 Core-Tier 2 hours] 190 Topics: 191 • Distinction between bugs and faults, and how they arise in hardware vs. software 192 • How errors increase the longer the distance between the communicating entities; the end-to-end principle 193 as it applies to systems and networks 194 • Redundancy through check and retry 195 • Redundancy through redundant encoding (error correcting codes, CRC/Cyclic Redundancy Codes, 196 FEC/Forward Error Correction) 197 • Duplication/mirroring/replicas 198 199 Learning Outcomes: 200 1. Explain the distinction between program errors, system errors, and hardware faults (e.g., bad memory) and 201 exceptions (e.g., attempt to divide by zero) [Knowledge]. 202 2. Articulate the distinction between detecting, handling, and recovering from faults, and the methods for their 203 implementation [Knowledge]. 204 3. Describe the role of error correcting codes in providing error checking and correction techniques in 205 memories, storage, and networks [Knowledge]. 206 4. Apply simple algorithms for exploiting redundant information for the purposes of data correction 207 [Application]. 208 5. Compare different error detection and correction methods for their data overhead, implementation 209 complexity, and relative execution time for encoding, detecting, and correcting errors [Evaluation]. 210 - 162 - 1 Social and Professional Practice (SP) 2 While technical issues are central to the computing curriculum, they do not constitute a complete 3 educational program in the field. Students must also be exposed to the larger societal context of 4 computing to develop an understanding of the relevant social, ethical and professional issues. 5 This need to incorporate the study of these non-technical issues into the ACM curriculum was 6 formally recognized in 1991, as can be seen from the following excerpt [Tucker91]: 7 Undergraduates also need to understand the basic cultural, social, legal, and ethical 8 issues inherent in the discipline of computing. They should understand where the 9 discipline has been, where it is, and where it is heading. They should also understand 10 their individual roles in this process, as well as appreciate the philosophical questions, 11 technical problems, and aesthetic values that play an important part in the development 12 of the discipline. 13 Students also need to develop the ability to ask serious questions about the social 14 impact of computing and to evaluate proposed answers to those questions. Future 15 practitioners must be able to anticipate the impact of introducing a given product into a 16 given environment. Will that product enhance or degrade the quality of life? What will 17 the impact be upon individuals, groups, and institutions? 18 Finally, students need to be aware of the basic legal rights of software and hardware 19 vendors and users, and they also need to appreciate the ethical values that are the basis 20 for those rights. Future practitioners must understand the responsibility that they will 21 bear, and the possible consequences of failure. They must understand their own 22 limitations as well as the limitations of their tools. All practitioners must make a long- 23 term commitment to remaining current in their chosen specialties and in the discipline 24 of computing as a whole. 25 As technological advances continue to significantly impact the way we live and work, the critical 26 importance of these social and professional issues continues to increase; new computer-based 27 products and venues pose ever more challenging problems each year. It is our students who 28 must enter the workforce and academia with intentional regard for the identification and 29 resolution of these problems. [Link] http://www.acm.org/about/code-of-ethics 30 Computer science educators may opt to deliver this core and elective material in stand-alone 31 courses, integrated into traditional technical and theoretical courses, or as special units in 32 capstone and professional practice courses. The material in this knowledge area is best covered 33 through a combination of one required course along with short modules in other courses. On the 34 one hand, some units listed as core-tier 1—in particular, Social Context, Analytical Tools, 35 Professional Ethics, and Intellectual Property—do not readily lend themselves to being covered 36 in other traditional courses. Without a standalone course, it is difficult to cover these topics 37 appropriately. On the other hand, if ethical considerations are covered only in the standalone 38 course and not “in context,” it will reinforce the false notion that technical processes are void of 39 ethical issues. Thus it is important that several traditional courses include modules that analyze 40 ethical considerations in the context of the technical subject matter of the course. Courses in 41 areas such as software engineering, databases, computer networks, and introduction to 42 computing provide obvious context for analysis of ethical issues. However, an ethics-related 43 module could be developed for almost any course in the curriculum. It would be explicitly 44 against the spirit of the recommendations to have only a standalone course. Running through all 45 of the issues in this area is the need to speak to the computer practitioner’s responsibility to 46 proactively address these issues by both moral and technical actions. The ethical issues discussed 47 in any class should be directly related to and arise naturally from the subject matter of that class. 48 Examples include a discussion in the database course of data aggregation or data mining, or a 49 discussion in the software engineering course of the potential conflicts between obligations to the 50 customer and obligations to the user and others affected by their work. Programming 51 assignments built around applications such as controlling the movement of a laser during eye 52 surgery can help to address the professional, ethical and social impacts of computing. Computing 53 faculty who are unfamiliar with the content and/or pedagogy of applied ethics are urged to take 54 advantage of the considerable resources from ACM, IEEE-CS and other organizations. 55 It should be noted that the application of ethical analysis underlies every subsection of this 56 knowledge area on Social and Professional Issues in computing. The ACM Code of Ethics and 57 Professional Conduct - www.acm.org/about/code-of-ethics - provide guidelines that serve as the 58 basis for the conduct of our professional work. The General Moral Imperatives provide an 59 understanding of our commitment to personal responsibility, professional conduct, and our 60 leadership roles. - 164 - 61 SP. Social and Professional Practice [11 Core-Tier1 hours, 5 Core-Tier2 hours] Core-Tier1 hours Core-Tier2 hours Includes Electives SP/Social Context 1 2 N SP/Analytical Tools 2 N SP/Professional Ethics 2 2 N SP/Intellectual Property 2 Y SP/Privacy and Civil Liberties 2 Y SP/Professional Communication 1 Y SP/Sustainability 1 1 Y SP/History Y SP/Economies of Computing Y SP/Security Policies, Laws and Y Computer Crimes 62 63 SP/Social Context 64 [1 Core-Tier1 hour, 2 Core-Tier2 hours] 65 Topics: 66 [Core-Tier1] 67 • Social implications of computing in a networked world 68 • Impact of social media on individualism, collectivism and culture. 69 70 [Core-Tier2] 71 • Growth and control of the Internet 72 • The digital divide (including gender, class, ethnicity, underdeveloped countries) 73 • Accessibility issues, including legal requirements 74 • Context-aware computing 75 76 Learning Outcomes: 77 [Core-Tier1] 78 1. Describe positive and negative ways in which computer technology (networks, mobile computing, cloud 79 computing) alters modes of social interaction at the personal level. [Knowledge] 80 2. Identify developers’ assumptions and values embedded in hardware and software design, especially as they 81 pertain to usability for diverse populations including under-represented populations and the disabled. 82 [Knowledge] 83 3. Interpret the social context of a given design and its implementation. [Knowledge] 84 4. Evaluate the efficacy of a given design and implementation using empirical data. [Evaluation] 85 5. Investigate the implications of social media on individualism versus collectivism and culture. [Application] 86 - 165 - 87 [Core-Tier2] 88 1. Discuss how Internet access serves as a liberating force for people living under oppressive forms of 89 government; explain how limits on Internet access are used as tools of political and social repression. 90 [Knowledge] 91 2. Analyze the pros and cons of reliance on computing in the implementation of democracy (e.g. delivery of 92 social services, electronic voting). [Evaluation] 93 3. Describe the impact of the under-representation of diverse populations in the computing profession (e.g., 94 industry culture, product diversity). [Knowledge] 95 4. Investigate the implications of context awareness in ubiquitous computing systems. [Application] 96 97 SP/Analytical Tools 98 [2 Core-Tier1 hours] 99 Topics: 100 [Core-Tier1] 101 • Ethical argumentation 102 • Ethical theories and decision-making 103 • Moral assumptions and values 104 105 Learning Outcomes: 106 [Core-Tier1] 107 1. Evaluate stakeholder positions in a given situation. [Evaluation] 108 2. Analyze basic logical fallacies in an argument. [Evaluation] 109 3. Analyze an argument to identify premises and conclusion. [Evaluation] 110 4. Illustrate the use of example and analogy in ethical argument. [Application] 111 5. Evaluate ethical tradeoffs in technical decisions. [Evaluation] 112 113 SP/Professional Ethics 114 [2 Core-Tier1 hours, 2 Core-Tier2 hours] 115 Topics: 116 [Core-Tier1] 117 • Community values and the laws by which we live 118 • The nature of professionalism including care, attention and discipline, fiduciary responsibility, and 119 mentoring 120 • Keeping up-to-date as a professional in terms of knowledge, tools, skills, legal and professional framework 121 as well as the ability to self-assess and computer fluency 122 • Codes of ethics, conduct, and practice such as the ACM/IEEE, SE, AITP, IFIP and international societies 123 • Accountability, responsibility and liability 124 125 - 166 - 126 [Core-Tier2] 127 • The role of the professional in public policy 128 • Maintaining awareness of consequences 129 • Ethical dissent and whistle-blowing 130 • Dealing with harassment and discrimination 131 • Forms of professional credentialing 132 • Acceptable use policies for computing in the workplace 133 • Ergonomics and healthy computing environments 134 • Time to market versus quality professional standards 135 136 Learning Outcomes: 137 [Core-Tier1] 138 1. Identify ethical issues that arise in software development and determine how to address them technically 139 and ethically. [Knowledge] 140 2. Recognize the ethical responsibility of ensuring software correctness, reliability and safety. [Knowledge] 141 3. Describe the mechanisms that typically exist for a professional to keep up-to-date. [Knowledge] 142 4. Describe the strengths and weaknesses of relevant professional codes as expressions of professionalism 143 and guides to decision-making. [Knowledge] 144 5. Analyze a global computing issue, observing the role of professionals and government officials in 145 managing the problem. [Evaluation] 146 6. Evaluate the professional codes of ethics from the ACM, the IEEE Computer Society, and other 147 organizations. [Evaluation] 148 149 [Core-Tier2] 150 1. Describe ways in which professionals may contribute to public policy. [Knowledge] 151 2. Describe the consequences of inappropriate professional behavior. [Knowledge] 152 3. Identify progressive stages in a whistle-blowing incident. [Knowledge] 153 4. Investigate forms of harassment and discrimination and avenues of assistance [Application] 154 5. Examine various forms of professional credentialing [Application] 155 6. Identify the social implications of ergonomic devices and the workplace environment to people’s health. 156 [Knowledge] 157 7. Develop a computer use policy with enforcement measures. [Evaluation] 158 8. Describe issues associated with industries push to focus on time to market versus enforcing quality 159 professional standards [Knowledge] 160 161 162 SP/ Intellectual Property 163 [2 Core-Tier1 hours] 164 Topics: 165 [Core-Tier1] 166 • Philosophical foundations of intellectual property 167 • Intellectual property rights 168 • Intangible digital intellectual property (IDIP) 169 • Legal foundations for intellectual property protection 170 • Digital rights management 171 • Copyrights, patents, trademarks 172 • Plagiarism - 167 - 173 174 [Elective] 175 • Foundations of the open source movement 176 • Software piracy 177 178 Learning Outcomes: 179 [Core-Tier1] 180 1. Discuss the philosophical bases of intellectual property. [Knowledge] 181 2. Discuss the rationale for the legal protection of intellectual property. [Knowledge] 182 3. Describe legislation aimed at digital copyright infringements. [Knowledge] 183 4. Critique legislation aimed at digital copyright infringements [Evaluation] 184 5. Identify contemporary examples of intangible digital intellectual property [Knowledge] 185 6. Justify uses of copyrighted materials. [Evaluation] 186 7. Evaluate the ethical issues inherent in various plagiarism detection mechanisms. [Evaluation] 187 8. Interpret the intent and implementation of software licensing. [Knowledge] 188 9. Discuss the issues involved in securing software patents. [Knowledge] 189 10. Characterize and contrast the concepts of copyright, patenting and trademarks. [Evaluation] 190 191 [Elective] 192 1. Identify the goals of the open source movement. [Knowledge] 193 2. Identify the global nature of software piracy. [Knowledge] 194 195 SP/ Privacy and Civil Liberties 196 [2 Core-Tier1 hours] 197 Topics: 198 [Core-Tier1] 199 • Philosophical foundations of privacy rights 200 • Legal foundations of privacy protection 201 • Privacy implications of widespread data collection for transactional databases, data warehouses, 202 surveillance systems, and cloud computing 203 • Ramifications of differential privacy 204 • Technology-based solutions for privacy protection 205 206 [Elective] 207 • Privacy legislation in areas of practice 208 • Civil liberties 209 • Freedom of expression and its limitations 210 211 Learning Outcomes: 212 [Core-Tier1] 213 1. Discuss the philosophical basis for the legal protection of personal privacy. [Knowledge] 214 2. Evaluate solutions to privacy threats in transactional databases and data warehouses. [Evaluation] 215 3. Recognize the fundamental role of data collection in the implementation of pervasive surveillance systems 216 (e.g., RFID, face recognition, toll collection, mobile computing). [Knowledge] 217 4. Recognize the ramifications of differential privacy. [Knowledge] 218 5. Investigate the impact of technological solutions to privacy problems. [Application] - 168 - 219 220 [Elective] 221 1. Critique the intent, potential value and implementation of various forms of privacy legislation. [Evaluation] 222 2. Identify the global nature of software piracy. [Knowledge] 223 3. Identify strategies to enable appropriate freedom of expression. [Knowledge] 224 225 SP/ Professional Communication 226 [1 Core-Tier1 hour] 227 228 Topics: 229 [Core-Tier1] 230 • Reading, understanding and summarizing technical material, including source code and documentation 231 • Writing effective technical documentation and materials 232 • Dynamics of oral, written, and electronic team and group communication 233 • Communicating professionally with stakeholders 234 • Utilizing collaboration tools 235 236 [Elective] 237 • Dealing with cross-cultural environments 238 • Tradeoffs of competing risks in software projects, such as technology, structure/process, quality, people, 239 market and financial 240 241 Learning Outcomes: 242 [Core-Tier1] 243 1. Write clear, concise, and accurate technical documents following well-defined standards for format and for 244 including appropriate tables, figures, and references. [Application] 245 2. Evaluate written technical documentation to detect problems of various kinds. [Evaluation] 246 3. Develop and deliver a good quality formal presentation. [Evaluation] 247 4. Plan interactions (e.g. virtual, face-to-face, shared documents) with others in which they are able to get 248 their point across, and are also able to listen carefully and appreciate the points of others, even when they 249 disagree, and are able to convey to others that they have heard. [Application] 250 5. Describe the strengths and weaknesses of various forms of communication (e.g. virtual, face-to-face, shared 251 documents) [Knowledge] 252 6. Examine appropriate measures used to communicate with stakeholders involved in a project. [Application] 253 7. Compare and contrast various collaboration tools. [Evaluation] 254 255 [Elective] 256 1. Discuss ways to influence performance and results in cross-cultural teams. [Knowledge] 257 2. Examine the tradeoffs and common sources of risk in software projects regarding technology, 258 structure/process, quality, people, market and financial. [Application] 259 260 - 169 - 261 SP/ Sustainability 262 [1 Core-Tier1 hour, 1 Core-Tier2 hour] 263 Sustainability was first introduced in the CS2008 curricular guidelines. Topics in this emerging 264 area can be naturally integrated into other knowledge areas and units. 265 Topics: 266 [Core-Tier1] 267 • Being a sustainable practitioner, e.g., consideration of impacts of issues, such as power consumption and 268 resource consumption 269 • Explore global social and environmental impacts of computer use and disposal (e-waste) 270 271 [Core-Tier2] 272 • Environmental impacts of design choices in specific areas such as algorithms, operating systems, networks, 273 databases, programming languages, or human-computer interaction 274 (cross-reference: HCI/Embedded and Intelligent Systems/Energy-aware interfaces) 275 276 [Elective] 277 • Guidelines for sustainable design standards 278 • Systemic effects of complex computer-mediated phenomena (e.g. telecommuting or web shopping) 279 • Pervasive computing. Information processing that has been integrated into everyday objects and activities, 280 such as smart energy systems, social networking and feedback systems to promote sustainable behavior, 281 transportation, environmental monitoring, citizen science and activism. 282 • Conduct research on applications of computing to environmental issues, such as energy, pollution, resource 283 usage, recycling and reuse, food management, farming and others. 284 285 Learning Outcomes: 286 [Core-Tier1] 287 1. Identify ways to be a sustainable practitioner [Knowledge] 288 2. Illustrate global social and environmental impacts of computer use and disposal (e-waste) [Application] 289 290 [Core-Tier2] 291 1. Describe the environmental impacts of design choices within the field of computing that relate to algorithm 292 design, operating system design, networking design, database design, etc. [Knowledge] 293 2. Investigate the social and environmental impacts of new system designs through projects. [Application] 294 295 [Elective] 296 1. Identify guidelines for sustainable IT design or deployment [Knowledge] 297 2. List the sustainable effects of telecommuting or web shopping [Knowledge] 298 3. Investigate pervasive computing in areas such as smart energy systems, social networking, transportation, 299 agriculture, supply-chain systems, environmental monitoring and citizen activism. [Application] 300 4. Develop applications of computing and assess through research areas pertaining to environmental issues 301 (e.g. energy, pollution, resource usage, recycling and reuse, food management, farming) [Evaluation] 302 303 - 170 - 304 SP/ History 305 [Elective] 306 Topics: 307 • Prehistory—the world before 1946 308 • History of computer hardware, software, networking 309 • Pioneers of computing 310 • History of Internet 311 312 Learning Outcomes: 313 1. Identify significant continuing trends in the history of the computing field. [Knowledge] 314 2. Identify the contributions of several pioneers in the computing field. [Knowledge] 315 3. Discuss the historical context for several programming language paradigms. [Knowledge] 316 4. Compare daily life before and after the advent of personal computers and the Internet. [Evaluation] 317 318 SP/ Economies of Computing 319 [Elective] 320 Topics: 321 • Monopolies and their economic implications 322 • Effect of skilled labor supply and demand on the quality of computing products 323 • Pricing strategies in the computing domain 324 • The phenomenon of outsourcing and off-shoring; impacts on employment and on economics 325 • Differences in access to computing resources and the possible effects thereof 326 • Costing out jobs with considerations on manufacturing, hardware, software, and engineering implications 327 • Cost estimates versus actual costs in relation to total costs 328 • Entrepreneurship: prospects and pitfalls 329 • Use of engineering economics in dealing with finances 330 331 Learning Outcomes: 332 1. Summarize the rationale for antimonopoly efforts. [Knowledge] 333 2. Identify several ways in which the information technology industry is affected by shortages in the labor 334 supply. [Knowledge] 335 3. Identify the evolution of pricing strategies for computing goods and services. [Knowledge] 336 4. Discuss the benefits, the drawbacks and the implications of off-shoring and outsourcing. [Knowledge] 337 5. Investigate and defend ways to address limitations on access to computing. [Application] 338 339 - 171 - 340 SP/ Security Policies, Laws and Computer Crimes 341 [Elective] 342 Topics: 343 • Examples of computer crimes and legal redress for computer criminals 344 • Social engineering and identity theft (cross-reference: HCI/Human Factors and Security/social engineering) 345 • Issues surrounding the misuse of access and breaches in security 346 • Motivations and ramifications of cyber terrorism and criminal hacking, “cracking” 347 • Effects of malware, such as viruses, worms and Trojan horses 348 • Crime prevention strategies 349 • Security policies 350 351 Learning Outcomes: 352 1. List examples of classic computer crimes and social engineering incidents with societal impact. 353 [Knowledge] 354 2. Identify laws that apply to computer crimes [Knowledge] 355 3. Describe the motivation and ramifications of cyber terrorism and criminal hacking [Knowledge] 356 4. Examine the ethical and legal issues surrounding the misuse of access and various breaches in security 357 [Application] 358 5. Discuss the professional's role in security and the trade-offs involved. [Knowledge] 359 6. Investigate measures that can be taken by both individuals and organizations including governments to 360 prevent or mitigate the undesirable effects of computer crimes and identity theft [Application] 361 7. Write a company-wide security policy, which includes procedures for managing passwords and employee 362 monitoring. [Application] - 172 -