Knowledge Areas

Algorithms and Complexity (AL)

Algorithms are fundamental to computer science and software engineering. The real-world performance of any software system depends on: (1) the algorithms chosen and (2) the suitability and efficiency of the various layers of implementation. Good algorithm design is therefore crucial for the performance of all software systems. Moreover, the study of algorithms provides insight into the intrinsic nature of the problem as well as possible solution techniques independent of programming language, programming paradigm, computer hardware, or any other implementation aspect.

An important part of computing is the ability to select algorithms appropriate to particular purposes and to apply them, recognizing the possibility that no suitable algorithm may exist. This facility relies on understanding the range of algorithms that address an important set of welldefined problems, recognizing their strengths and weaknesses, and their suitability in particular contexts. Efficiency is a pervasive theme throughout this area. This knowledge area defines the central concepts and skills required to design, implement, and analyze algorithms for solving problems. Algorithms are essential in all advanced areas of computer science: artificial intelligence, databases, distributed computing, graphics, networking, operating systems, programming languages, security, and so on. Algorithms that have specific utility in each of these are listed in the relevant knowledge areas. Cryptography, for example, appears in the new Knowledge Area on Information Assurance and Security (IAS), while parallel and distributed algorithms appear the Knowledge Area in Parallel and Distributed Computing (PD).

As with all knowledge areas, the order of topics and their groupings do not necessarily correlate to a specific order of presentation. Different programs will teach the topics in different courses and should do so in the order they believe is most appropriate for their students.

  • ★ ★ Core ★ Core
  • AL / Basic Analysis
    Topics
      Learning Outcomes
      1. ★ ★ Core ★ Core
      2. AL / Algorithmic Strategies
        Topics
          Learning Outcomes
          1. ★ ★ Core ★ Core
          2. AL / Fundamental Data Structures and Algorithms
            Topics
              Learning Outcomes
              1. ★ ★ Core ★ Core
              2. AL / Basic Automata, Computability and Complexity
                Topics
                  Learning Outcomes
                  1. Elective
                  2. AL / Advanced Computational Complexity
                    Topics
                      Learning Outcomes
                      1. Elective
                      2. AL / Advanced Automata Theory and Computability
                        Topics
                          Learning Outcomes
                          1. Elective
                          2. AL / Advanced Data Structures, Algorithms, and Analysis
                            Topics
                              Learning Outcomes

                              Architecture and Organization (AR)

                              Computing professionals should not regard the computer as just a black box that executes programs by magic. The knowledge area Architecture and Organization builds on Systems Fundamentals (SF) to develop a deeper understanding of the hardware environment upon which all computing is based, and the interface it provides to higher software layers. Students should acquire an understanding and appreciation of a computer system’s functional components, their characteristics, performance, and interactions, and, in particular, the challenge of harnessing parallelism to sustain performance improvements now and into the future. Students need to understand computer architecture to develop programs that can achieve high performance through a programmer’s awareness of parallelism and latency. In selecting a system to use, students should be able to understand the tradeoff among various components, such as CPU clock speed, cycles per instruction, memory size, and average memory access time.

                              The learning outcomes specified for these topics correspond primarily to the core and are intended to support programs that elect to require only the minimum 16 hours of computer architecture of their students. For programs that want to teach more than the minimum, the same AR topics can be treated at a more advanced level by implementing a two-course sequence. For programs that want to cover the elective topics, those topics can be introduced within a two-course sequence and/or be treated in a more comprehensive way in a third course.

                              • ★ Core
                              • AR / Digital Logic and Digital Systems
                                Topics
                                1. Overview and history of computer architecture ★
                                2. Combinational vs. sequential logic/Field programmable gate arrays as a fundamental combinational + sequential logic building block ★
                                3. Multiple representations/layers of interpretation (hardware is just another layer) ★
                                4. Computer-aided design tools that process hardware and architectural representations ★
                                5. Register transfer notation/Hardware Description Language (Verilog/VHDL) ★
                                6. Physical constraints (gate delays, fan-in, fan-out, energy/power) ★
                                Learning Outcomes
                                1. Describe the progression of computer technology components from vacuum tubes to VLSI, from mainframe computer architectures to the organization of warehouse-scale computers. [Familiarity] ★
                                2. Comprehend the trend of modern computer architectures towards multi-core and that parallelism is inherent in all hardware systems. [Familiarity] ★
                                3. Explain the implications of the “power wall” in terms of further processor performance improvements and the drive towards harnessing parallelism. [Familiarity] ★
                                4. Articulate that there are many equivalent representations of computer functionality, including logical expressions and gates, and be able to use mathematical expressions to describe the functions of simple combinational and sequential circuits. [Familiarity] ★
                                5. Design the basic building blocks of a computer: arithmetic-logic unit (gate-level), registers (gate-level), central processing unit (register transfer-level), memory (register transfer-level). [Usage] ★
                                6. Use CAD tools for capture, synthesis, and simulation to evaluate simple building blocks (e.g., arithmeticlogic unit, registers, movement between registers) of a simple computer design. [Usage] ★
                                7. Evaluate the functional and timing diagram behavior of a simple processor implemented at the logic circuit level. [Assessment] ★
                              • ★ Core
                              • AR / Machine Level Representation of Data
                                Topics
                                1. Bits, bytes, and words ★
                                2. Numeric data representation and number bases ★
                                3. Fixed- and floating-point systems ★
                                4. Signed and twos-complement representations ★
                                5. Representation of non-numeric data (character codes, graphical data) ★
                                6. Representation of records and arrays ★
                                Learning Outcomes
                                1. Explain why everything is data, including instructions, in computers. [Familiarity] ★
                                2. Explain the reasons for using alternative formats to represent numerical data. [Familiarity] ★
                                3. Describe how negative integers are stored in sign-magnitude and twos-complement representations. [Familiarity] ★
                                4. Explain how fixed-length number representations affect accuracy and precision. [Familiarity] ★
                                5. Describe the internal representation of non-numeric data, such as characters, strings, records, and arrays. [Familiarity] ★
                                6. Convert numerical data from one format to another. [Usage] ★
                                7. Write simple programs at the assembly/machine level for string processing and manipulation. [Usage] ★
                              • ★ Core
                              • AR / Assembly Level Machine Organization
                                Topics
                                  Learning Outcomes
                                  1. ★ Core
                                  2. AR / Memory System Organization and Architecture
                                    Topics
                                      Learning Outcomes
                                      1. ★ Core
                                      2. AR / Interfacing and Communication
                                        Topics
                                          Learning Outcomes
                                          1. Elective
                                          2. AR / Functional Organization
                                            Topics
                                              Learning Outcomes
                                              1. Elective
                                              2. AR / Multiprocessing and Alternative Architectures
                                                Topics
                                                  Learning Outcomes
                                                  1. Elective
                                                  2. AR / Performance Enhancements
                                                    Topics
                                                      Learning Outcomes

                                                      Computational Science (CN)

                                                      one

                                                      two

                                                      Graphics and Visualization (GV)

                                                      one

                                                      two

                                                      Human-Computer Interaction (HCI)

                                                      Human-computer interaction (HCI) is concerned with designing interactions between human activities and the computational systems that support them, and with constructing interfaces to afford those interactions.

                                                      Interaction between users and computational artefacts occurs at an interface that includes both software and hardware. Thus interface design impacts the software life-cycle in that it should occur early; the design and implementation of core functionality can influence the user interface — for better or worse.

                                                      Because it deals with people as well as computational systems, as a knowledge area HCI demands the consideration of cultural, social, organizational, cognitive and perceptual issues. Consequently it draws on a variety of disciplinary traditions, including psychology, ergonomics, computer science, graphic and product design, anthropology and engineering

                                                      • ★ ★ Core
                                                      • HCI / Foundations
                                                        Motivation

                                                        For end-users, the interface is the system. So design in this domain must be interaction-focused and human-centered. Students need a different repertoire of techniques to address this than is provided elsewhere in the curriculum.

                                                        Topics
                                                        1. Contexts for HCI (anything with a user interface, e.g., webpage, business applications, mobile applications, and games) ★★
                                                        2. Processes for user-centered development, e.g., early focus on users, empirical testing, iterative design ★★
                                                        3. Different measures for evaluation, e.g., utility, efficiency, learnability, user satisfaction ★★
                                                        4. Usability heuristics and the principles of usability testing ★★
                                                        5. Physical capabilities that inform interaction design, e.g., color perception, ergonomics ★★
                                                        6. Cognitive models that inform interaction design, e.g., attention, perception and recognition, movement, and memory; gulfs of expectation and execution ★★
                                                        7. Social models that inform interaction design, e.g., culture, communication, networks and organizations ★★
                                                        8. Principles of good design and good designers; engineering tradeoffs ★★
                                                        9. Accessibility, e.g., interfaces for differently-abled populations (e.g., blind, motion-impaired) ★★
                                                        10. Interfaces for differently-aged population groups (e.g., children, 80+) ★★
                                                        Learning Outcomes
                                                        1. Discuss why human-centered software development is important. [Familiarity] ★★
                                                        2. Summarize the basic precepts of psychological and social interaction. [Familiarity] ★★
                                                        3. Develop and use a conceptual vocabulary for analyzing human interaction with software: affordance, conceptual model, feedback, and so forth. [Usage] ★★
                                                        4. Define a user-centered design process that explicitly takes account of the fact that the user is not like the developer or their acquaintances. [Usage] ★★
                                                        5. Create and conduct a simple usability test for an existing software application. [Assessment] ★★
                                                      • ★ Core
                                                      • HCI / Designing Interaction
                                                        Motivation

                                                        CS students need a minimal set of well-established methods and tools to bring to interface construction.

                                                        Topics
                                                        1. Principles of graphical user interfaces (GUIs) 
                                                        2. Elements of visual design (layout, colour, fonts, labelling) 
                                                        3. Task analysis, including qualitative aspects of generating task analytic models 
                                                        4. Low-fidelity (paper) prototyping 
                                                        5. Quantitative evaluation techniques, e.g., keystroke-level evaluation 
                                                        6. Help and documentation 
                                                        7. Handling human/system failure 
                                                        8. User interface standards 
                                                        Learning Outcomes
                                                        1. For an identified user group, undertake and document an analysis of their needs. [Assessment] 
                                                        2. Create a simple application, together with help and documentation, that supports a graphical user interface. [Usage] 
                                                        3. Conduct a quantitative evaluation and discuss/report the results. [Usage] 
                                                        4. Discuss at least one national or international user interface design standard. [Familiarity] 
                                                      • Elective
                                                      • HCI / Programming Interactive Systems
                                                        Motivation

                                                        To take a user-experience-centered view of software development and then cover approaches and technologies to make that happen.

                                                        Topics
                                                        1. Software Architecture Patterns, e.g., Model-View controller; command objects, online, offline (cross reference PL/Event Driven and Reactive Programming, where MVC is used in the context of event-driven programming) 
                                                        2. Interaction Design Patterns: visual hierarchy, navigational distance 
                                                        3. Event management and user interaction 
                                                        4. Geometry management (cross-reference GV/Geometric Modelling) 
                                                        5. Choosing interaction styles and interaction techniques 
                                                        6. Presenting information: navigation, representation, manipulation 
                                                        7. Interface animation techniques (e.g., scene graphs) 
                                                        8. Widget classes and libraries 
                                                        9. Modern GUI libraries (e.g. iOS, Android, JavaFX) GUI builders and UI programming environments (cross reference PBD/Mobile Platforms) 
                                                        10. Declarative Interface Specification: Stylesheets and DOM 
                                                        11. Data-driven applications (database-backed web pages) 
                                                        12. Cross-platform design 
                                                        13. Design for resource-constrained devices (e.g. small, mobile devices) 
                                                        Learning Outcomes
                                                        1. Explain the importance of Model-View controller to interface programming. [Familiarity] 
                                                        2. Create an application with a modern graphical user interface. [Usage] 
                                                        3. Identify commonalities and differences in UIs across different platforms. [Familiarity] 
                                                        4. Explain and use GUI programming concepts: event handling, constraint-based layout management, etc. [Familiarity] 
                                                      • Elective
                                                      • HCI / User-Centered Design and Testing
                                                        Motivation

                                                        An exploration of techniques to ensure that end-users are fully considered at all stages of the design process, from inception to implementation.

                                                        Topics
                                                        1. Approaches to, and characteristics of, the design process 
                                                        2. Functionality and usability requirements (cross-reference to SE/Requirements Engineering) 
                                                        3. Techniques for gathering requirements, e.g., interviews, surveys, ethnographic and contextual enquiry 
                                                        4. Techniques and tools for the analysis and presentation of requirements, e.g., reports, personas 
                                                        5. Prototyping techniques and tools, e.g., sketching, storyboards, low-fidelity prototyping, wireframes 
                                                        6. Evaluation without users, using both qualitative and quantitative techniques, e.g., walkthroughs, GOMS, expert-based analysis, heuristics, guidelines, and standards 
                                                        7. Evaluation with users, e.g., observation, think-aloud, interview, survey, experiment 
                                                        8. Challenges to effective evaluation, e.g., sampling, generalization 
                                                        9. Reporting the results of evaluations 
                                                        10. Internationalization, designing for users from other cultures, cross-cultural 
                                                        Learning Outcomes
                                                        1. Explain how user-centered design complements other software process models. [Familiarity] 
                                                        2. Use lo-fi (low fidelity) prototyping techniques to gather, and report, user responses. [Usage] 
                                                        3. Choose appropriate methods to support the development of a specific UI. [Assessment] 
                                                        4. Use a variety of techniques to evaluate a given UI. [Assessment] 
                                                        5. Compare the constraints and benefits of different evaluative methods. [Assessment] 
                                                      • Elective
                                                      • HCI / New Interactive Technologies
                                                        Motivation

                                                        As technologies evolve, new interaction styles are made possible. This knowledge unit should be considered extensible, to track emergent technology.

                                                        Topics
                                                        1. Choosing interaction styles and interaction techniques 
                                                        2. Representing information to users: navigation, representation, manipulation 
                                                        3. Approaches to design, implementation and evaluation of non-mouse interaction 
                                                        4. Touch and multi-touch interfaces 
                                                        5. Shared, embodied, and large interfaces 
                                                        6. New input modalities (such as sensor and location data) 
                                                        7. New Windows, e.g., iPhone, Android 
                                                        8. Speech recognition and natural language processing (cross reference IS/Natural Language Processing) 
                                                        9. Wearable and tangible interfaces 
                                                        10. Persuasive interaction and emotion 
                                                        11. Ubiquitous and context-aware interaction technologies (Ubicomp) 
                                                        12. Bayesian inference (e.g. predictive text, guided pointing) 
                                                        13. Ambient/peripheral display and interaction 
                                                        Learning Outcomes
                                                        1. Describe when non-mouse interfaces are appropriate. [Familiarity] 
                                                        2. Understand the interaction possibilities beyond mouse-and-pointer interfaces. [Familiarity] 
                                                        3. Discuss the advantages (and disadvantages) of non-mouse interfaces. [Assessment] 
                                                      • Elective
                                                      • HCI / Collaboration and Communication
                                                        Motivation

                                                        Computer interfaces not only support users in achieving their individual goals but also in their interaction with others, whether that is task-focused (work or gaming) or task-unfocused (social networking).

                                                        Topics
                                                        1. Asynchronous group communication, e.g., e-mail, forums, social networks 
                                                        2. Synchronous group communication, e.g., chat rooms, conferencing, online games 
                                                        3. Social media, social computing, and social network analysis 
                                                        4. Online collaboration, 'smart' spaces, and social coordination aspects of workflow technologies 
                                                        5. Online communities 
                                                        6. Software characters and intelligent agents, virtual worlds and avatars (cross-reference IS/Agents) 
                                                        7. Social psychology 
                                                        Learning Outcomes
                                                        1. Describe the difference between synchronous and asynchronous communication. [Familiarity] 
                                                        2. Compare the HCI issues in individual interaction with group interaction. [Assessment] 
                                                        3. Discuss several issues of social concern raised by collaborative software. [Familiarity] 
                                                        4. Discuss the HCI issues in software that embodies human intention. [Familiarity] 
                                                      • Elective
                                                      • HCI / Statistical Methods for HCI
                                                        Motivation

                                                        Much HCI work depends on the proper use, understanding and application of statistics. This knowledge is often held by students who join the field from psychology, but less common in students with a CS background.

                                                        Topics
                                                        1. t-tests 
                                                        2. ANOVA 
                                                        3. Randomization (non-parametric) testing, within vs. between-subjects design 
                                                        4. Calculating effect size 
                                                        5. Exploratory data analysis 
                                                        6. Presenting statistical data 
                                                        7. Combining qualitative and quantitative results 
                                                        Learning Outcomes
                                                        1. Explain basic statistical concepts and their areas of application. [Familiarity] 
                                                        2. Extract and articulate the statistical arguments used in papers that quantitatively report user studies. [Usage] 
                                                        3. Design a user study that will yield quantitative results. [Usage] 
                                                        4. Conduct and report on a study that utilizes both qualitative and quantitative evaluation. [Usage] 
                                                      • Elective
                                                      • HCI / Human Factors and Security
                                                        Motivation

                                                        Effective interface design requires basic knowledge of security psychology. Many attacks do not have a technological basis, but exploit human propensities and vulnerabilities. “Only amateurs attack machines; professionals target people” (Bruce Schneier, see Phishing Has Gotten Very Good)

                                                        Topics
                                                        1. Applied psychology and security policies 
                                                        2. Security economics 
                                                        3. Regulatory environments – responsibility, liability and self-determination 
                                                        4. Organizational vulnerabilities and threats 
                                                        5. Usability design and security 
                                                        6. Pretext, impersonation and fraud, e.g., phishing and spear phishing (cross-reference IAS/Threats and Attacks) 
                                                        7. Trust, privacy and deception 
                                                        8. Biometric authentication (camera, voice) 
                                                        9. Identity management 
                                                        Learning Outcomes
                                                        1. Explain the concepts of phishing and spear phishing, and how to recognize them. [Familiarity] 
                                                        2. Describe the issues of trust in interface design with an example of a high and low trust system. [Assessment] 
                                                        3. Design a user interface for a security mechanism. [Assessment] 
                                                        4. Explain the concept of identity management and its importance. [Familiarity] 
                                                        5. Analyze a security policy and/or procedures to show where they consider, or fail to consider, human factors. [Usage] 
                                                      • Elective
                                                      • HCI / Design-Oriented HCI
                                                        Motivation

                                                        Some curricula will want to emphasize an understanding of the norms and values of HCI work itself as emerging from, and deployed within specific historical, disciplinary and cultural contexts.

                                                        Topics
                                                        1. Intellectual styles and perspectives to technology and its interfaces 
                                                        2. Consideration of HCI as a design discipline 
                                                          • Sketching
                                                          • Participatory design
                                                        3. Critically reflective HCI 
                                                          • Critical technical practice
                                                          • Technologies for political activism
                                                          • Philosophy of user experience
                                                          • Ethnography and ethnomethodology
                                                        4. Indicative domains of application 
                                                          • Sustainability
                                                          • Arts-informed computing
                                                        Learning Outcomes
                                                        1. Explain what is meant by “HCI is a design-oriented discipline”. [Familiarity] 
                                                        2. Detail the processes of design appropriate to specific design orientations. [Familiarity] 
                                                        3. Apply a variety of design methods to a given problem. [Usage] 
                                                      • Elective
                                                      • HCI / Mixed, Augmented and Virtual Reality
                                                        Motivation

                                                        Some curricula will want to emphasize an understanding of the norms and values of HCI work itself as emerging from, and deployed within specific historical, disciplinary and cultural contexts.

                                                        Topics
                                                        1. Intellectual styles and perspectives to technology and its interfaces 
                                                        2. Consideration of HCI as a design discipline 
                                                          • Sketching
                                                          • Participatory design
                                                        3. Critically reflective HCI 
                                                          • Critical technical practice
                                                          • Technologies for political activism
                                                          • Philosophy of user experience
                                                          • Ethnography and ethnomethodology
                                                        4. Indicative domains of application 
                                                          • Sustainability
                                                          • Arts-informed computing
                                                        Learning Outcomes
                                                        1. Explain what is meant by “HCI is a design-oriented discipline”. [Familiarity] 
                                                        2. Detail the processes of design appropriate to specific design orientations. [Familiarity] 
                                                        3. Apply a variety of design methods to a given problem. [Usage] 

                                                      Information Management (IM)

                                                      one

                                                      two

                                                      Platform-Based Development (PBD)

                                                      one

                                                      two

                                                      Social Issues and Professional Practice (SP)

                                                      While technical issues are central to the computing curriculum, they do not constitute a complete educational program in the field. Students must also be exposed to the larger societal context of computing to develop an understanding of the relevant social, ethical, legal and professional issues. This need to incorporate the study of these non-technical issues into the ACM curriculum was formally recognized in 1991, as can be seen from the following excerpt [2]

                                                      Undergraduates also need to understand the basic cultural, social, legal, and ethical issues inherent in the discipline of computing. They should understand where the discipline has been, where it is, and where it is heading. They should also understand their individual roles in this process, as well as appreciate the philosophical questions, technical problems, and aesthetic values that play an important part in the development of the discipline.

                                                      Students also need to develop the ability to ask serious questions about the social impact of computing and to evaluate proposed answers to those questions. Future practitioners must be able to anticipate the impact of introducing a given product into a given environment. Will that product enhance or degrade the quality of life? What will the impact be upon individuals, groups, and institutions?

                                                      Finally, students need to be aware of the basic legal rights of software and hardware vendors and users, and they also need to appreciate the ethical values that are the basis for those rights. Future practitioners must understand the responsibility that they will bear, and the possible consequences of failure. They must understand their own limitations as well as the limitations of their tools. All practitioners must make a longterm commitment to remaining current in their chosen specialties and in the discipline of computing as a whole.

                                                      As technological advances continue to significantly impact the way we live and work, the critical importance of social issues and professional practice continues to increase; new computer-based products and venues pose ever more challenging problems each year. It is our students who must enter the workforce and academia with intentional regard for the identification and resolution of these problems.

                                                      Computer science educators may opt to deliver this core and elective material in stand-alone courses, integrated into traditional technical and theoretical courses, or as special units in capstone and professional practice courses. The material in this familiarity area is best covered through a combination of one required course along with short modules in other courses. On the one hand, some units listed as Core Tier-1 (in particular, Social Context, Analytical Tools, Professional Ethics, and Intellectual Property) do not readily lend themselves to being covered in other traditional courses. Without a standalone course, it is difficult to cover these topics appropriately. On the other hand, if ethical and social considerations are covered only in the standalone course and not “in context,” it will reinforce the false notion that technical processes are void of these other relevant issues. Because of this broad relevance, it is important that several traditional courses include modules with case studies that analyze the ethical, legal, social and professional considerations in the context of the technical subject matter of the course. Courses in areas such as software engineering, databases, computer networks, information assurance and security, and introduction to computing provide obvious context for analysis of ethical issues. However, an ethics-related module could be developed for almost any course in the curriculum. It would be explicitly against the spirit of the recommendations to have only a standalone course. Running through all of the issues in this area is the need to speak to the computing practitioner’s responsibility to proactively address these issues by both moral and technical actions. The ethical issues discussed in any class should be directly related to and arise naturally from the subject matter of that class. Examples include a discussion in the database course of data aggregation or data mining, or a discussion in the software engineering course of the potential conflicts between obligations to the customer and obligations to the user and others affected by their work. Programming assignments built around applications such as controlling the movement of a laser during eye surgery can help to address the professional, ethical and social impacts of computing. Computing faculty who are unfamiliar with the content and/or pedagogy of applied ethics are urged to take advantage of the considerable resources from ACM, IEEE-CS, SIGCAS (special interest group on computers and society), and other organizations.

                                                      It should be noted that the application of ethical analysis underlies every subsection of this Social and Professional knowledge area in computing. The ACM Code of Ethics and Professional Conduct (http://www.acm.org/about/code-of-ethics) provides guidelines that serve as the basis for the conduct of our professional work. The General Moral Imperatives provide an understanding of our commitment to personal responsibility, professional conduct, and our leadership roles.