Appendix A Overview of the Body of Knowledge DS. Discrete Structures (43 core hours) DS/FunctionsRelationsAndSets (6) DS/BasicLogic (10) DS/ProofTechniques (12) DS/BasicsOfCounting (5) DS/GraphsAndTrees (4) DS/DiscreteProbability (6) PF. Programming Fundamentals (47 core hours) PF/FundamentalConstructs (9) PF/AlgorithmicProblemSolving (6) PF/DataStructures (10) PF/Recursion (4) PF/EventDrivenProgramming (4) PF/ObjectOriented (8) PF/FoundationsInformationSecurity (4) PF/SecureProgramming (2) AL. Algorithms and Complexity (31 core hours) AL/BasicAnalysis (4) AL/AlgorithmicStrategies (6) AL/FundamentalAlgorithms (12) AL/DistributedAlgorithms (3) AL/BasicComputability (6) AL/PversusNP AL/AutomataTheory AL/AdvancedAnalysis AL/CryptographicAlgorithms AL/GeometricAlgorithms AL/ParallelAlgorithms AR. Architecture and Organization (36 core hours) AR/DigitalLogicAndDataRepresentation (7) AR/ComputerArchitectureAndOrganization (9) AR/InterfacingAndI/OStrategies (3) AR/MemoryArchitecture (5) AR/FunctionalOrganization (6) AR/Multiprocessing (6) AR/PerformanceEnhancements AR/DistributedArchitectures AR/Devices AR/DirectionsInComputing OS. Operating Systems (18 core hours) OS/OverviewOfOperatingSystems (2) OS/OperatingSystemPrinciples (2) OS/Concurrency (6) OS/SchedulingandDispatch (3) OS/MemoryManagement (3) OS/DeviceManagement OS/SecurityAndProtection (2) OS/FileSystems OS/RealTimeAndEmbeddedSystems OS/FaultTolerance OS/SystemPerformanceEvaluation OS/Scripting OS/DigitalForensics OS/SecurityModels NC. Net-Centric Computing (15 core hours) NC/Introduction(2) NC/NetworkCommunication (7) NC/NetworkSecurity (6) NC/WebOrganization NC/NetworkedApplications NC/NetworkManagement NC/Compression NC/MultimediaTechnologies NC/MobileComputing PL. Programming Languages (21 core hours) PL/Overview(2) PL/VirtualMachines(1) PL/BasicLanguageTranslation(2) PL/DeclarationsAndTypes(3) PL/AbstractionMechanisms(3) PL/ObjectOrientedProgramming(10) PL/FunctionalProgramming PL/LanguageTranslationSystems PL/TypeSystems PL/ProgrammingLanguageSemantics PL/ProgrammingLanguageDesign HC. Human-Computer Interaction (8 core hours) HC/Foundations (6) HC/BuildingGUIInterfaces (2) HC/UserCcenteredSoftwareEvaluation HC/UserCenteredSoftwareDevelopment HC/GUIDesign HC/GUIProgramming HC/MultimediaAndMultimodalSystems HC/CollaborationAndCommunication HC/InteractionDesignForNewEnvironments HC/HumanFactorsAndSecurity GV. Graphics and Visual Computing (3 core hours) GV/FundamentalTechniques (2) GV/GraphicSystems (1) GV/GraphicCommunication GV/GeometricModeling GV/BasicRendering GV/AdvancedRendering GV/AdvancedTechniques GV/ComputerAnimation GV/Visualization GV/VirtualReality GV/ComputerVision GV/ComputationalGeometry GV/GameEngineProgramming IS. Intelligent Systems (10 core hours) IS/FundamentalIssues (1) IS/BasicSearchStrategies (5) IS/KnowledgeBasedReasoning (4) IS/AdvancedSearch IS/AdvancedReasoning IS/Agents IS/NaturaLanguageProcessing IS/MachineLearning IS/PlanningSystems IS/Robotics IS/Perception IM. Information Management (11 core hours) IM/InformationModels (4) IM/DatabaseSystems (3) IM/DataModeling (4) IM/Indexing IM/RelationalDatabases IM/QueryLanguages IM/RelationalDatabaseDesign IM/TransactionProcessing IM/DistributedDatabases IM/PhysicalDatabaseDesign IM/DataMining IM/InformationStorageAndRetrieval IM/Hypermedia IM/MultimediaSystems IM/DigitalLibraries SP. Social and Professional Issues (16 core hours) SP/HistoryOfComputing (1) SP/SocialContext (3) SP/AnalyticalTools (2) SP/ProfessionalEthics (3) SP/Risks (2) SP/SecurityOperations SP/IntellectualProperty (3) SP/PrivacyAndCivilLiberties (2) SP/ComputerCrime SP/EconomicsOfComputing SP/PhilosophicalFrameworks SE. Software Engineering (31 core hours) SE/SoftwareDesign (8) SE/UsingAPIs (5) SE/ToolsAndEnvironments (3) SE/SoftwareProcesses (2) SE/RequirementsSpecifications (4) SE/SoftwareVerificationValidation (3) SE/SoftwareEvolution (3) SE/SoftwareProjectManagement (3) SE/ComponentBasedComputing SE/FormalMethods SE/SoftwareReliability SE/SpecializedSystems SE/RiskAssessment SE/RobustAndSecurity- EnhancedProgramming CN. Computational Science (no core hours) CN/ModelingAndSimulation CN/OperationsResearch CN/ParallelComputation Note: The numbers in parentheses represent the minimum number of hours required to cover this material in a lecture format. It is always appropriate to include more. Appendix B Detailed Body of Knowledge Discrete Structures (DS) Discrete structures are foundational material for computer science. By foundational we mean that relatively few computer scientists will be working primarily on discrete structures, but that many other areas of computer science require the ability to work with concepts from discrete structures. Discrete structures include important material from such areas as set theory, logic, graph theory, and combinatorics. The material in discrete structures is pervasive in the areas of data structures and algorithms but appears elsewhere in computer science as well. For example, an ability to create and understand a proof—either a formal symbolic proof or a less formal but still mathematically rigorous argument—is essential in formal specification, in verification, in databases, and in cryptography. Graph theory concepts are used in networks, operating systems, and compilers. Set theory concepts are used in software engineering and in databases. As the field of computer science matures, more and more sophisticated analysis techniques are being brought to bear on practical problems. To understand the computational techniques of the future, today’s students will need a strong background in discrete structures. Finally, we note that while areas often have somewhat fuzzy boundaries, this is especially true for discrete structures. We have gathered together here a body of material of a mathematical nature that computer science education must include, and that computer science educators know well enough to specify in great detail. However, the decision about where to draw the line between this area and the Algorithms and Complexity area (AL) on the one hand, and topics left only as supporting mathematics on the other hand, was inevitably somewhat arbitrary. We remind readers that there are vital topics from those two areas that some schools will include in courses with titles like "discrete structures" and "discrete mathematics"; some will require one course, others two. In April 2007, the SIGCSE Committee on the Implementation of a Discrete Mathematics Course released a report detailing three models for a one-semester discrete mathematics course to meet the criteria articulated in CS2001; these models remain applicable under the slightly revised suggestions in this interim report. See SIGCSE Committee Report On the Implementation of a Discrete Mathematics Course. DS. Discrete Structures (43 core hours) DS/FunctionsRelationsAndSets [core] DS/BasicLogic [core] DS/ProofTechniques [core] DS/BasicsOfCounting [core] DS/GraphsAndTrees [core] DS/DiscreteProbability [core] DS/FunctionsRelationsAndSets [core] Minimum core coverage time: 6 hours Topics: • Functions (surjections, injections, inverses, composition) • Relations (reflexivity, symmetry, transitivity, equivalence relations) • Sets (Venn diagrams, complements, Cartesian products, power sets) • Pigeonhole principle • Cardinality and countability Learning Objectives: 1. Explain with examples the basic terminology of functions, relations, and sets. 2. Perform the operations associated with sets, functions, and relations. 3. Relate practical examples to the appropriate set, function, or relation model, and interpret the associated operations and terminology in context. DS/BasicLogic [core] Minimum core coverage time: 10 hours Topics: • Propositional logic • Logical connectives • Truth tables • Normal forms (conjunctive and disjunctive) • Validity • Predicate logic • Universal and existential quantification • Modus ponens and modus tollens • Limitations of predicate logic Learning Objectives: 1. Apply formal methods of symbolic propositional and predicate logic. 2. Describe how formal tools of symbolic logic are used to model real-life situations, including those arising in computing contexts such as program correctness, database queries, and algorithms. 3. Use formal logic proofs and/or informal but rigorous logical reasoning to, for example, predict the behavior of software or to solve problems such as puzzles. 4. Describe the importance and limitations of predicate logic. DS/ProofTechniques [core] Minimum core coverage time: 12 hours Topics: • Notions of implication, converse, inverse, contrapositive, negation, and contradiction • The structure of mathematical proofs • Direct proofs • Proof by counterexample • Proof by contradiction • Mathematical induction • Strong induction • Recursive mathematical definitions • Well orderings Learning Objectives: 1. Outline the basic structure of and give examples of each proof technique described in this unit. 2. Discuss which type of proof is best for a given problem. 3. Relate the ideas of mathematical induction to recursion and recursively defined structures. 4. Identify the difference between mathematical and strong induction and give examples of the appropriate use of each. DS/BasicsOfCounting [core] Minimum core coverage time: 5 hours Topics: • Counting arguments • Sum and product rule • Inclusion-exclusion principle • Arithmetic and geometric progressions • Fibonacci numbers • The pigeonhole principle • Permutations and combinations • Basic definitions • Pascal’s identity • The binomial theorem • Solving recurrence relations • Common examples • The Master theorem Learning Objectives: 1. Compute permutations and combinations of a set, and interpret the meaning in the context of the particular application. 2. State the definition of the Master theorem. 3. Solve a variety of basic recurrence equations. 4. Analyze a problem to create relevant recurrence equations or to identify important counting questions. DS/GraphsAndTrees [core] Minimum core coverage time: 4 hours Topics: • Trees • Undirected graphs • Directed graphs • Spanning trees/forests • Traversal strategies Learning Objectives: 1. Illustrate by example the basic terminology of graph theory, and some of the properties and special cases of each. 2. Demonstrate different traversal methods for trees and graphs. 3. Model problems in computer science using graphs and trees. 4. Relate graphs and trees to data structures, algorithms, and counting. DS/DiscreteProbability [core] Minimum core coverage time: 6 hours Topics: • Finite probability space, probability measure, events • Conditional probability, independence, Bayes’ theorem • Integer random variables, expectation • Law of large numbers Learning Objectives: 1. Calculate probabilities of events and expectations of random variables for elementary problems such as games of chance. 2. Differentiate between dependent and independent events. 3. Apply the binomial theorem to independent events and Bayes’ theorem to dependent events. 4. Apply the tools of probability to solve problems in areas such as the Monte Carlo method, the average case analysis of algorithms, and hashing. Programming Fundamentals (PF) Fluency in a programming language is prerequisite to the study of most of computer science. Undergraduate computer science programs must teach students how to use at least one programming language well; furthermore, computer science programs should teach students to become competent in languages that make use of the object-oriented and event-driven programming paradigms. This knowledge area includes those skills and concepts that are essential to programming practice independent of the underlying paradigm. As a result, this area includes units on fundamental programming concepts, basic data structures, algorithmic processes, and basic security. These units, however, by no means cover the full range of programming knowledge that a computer science undergraduate must know. Many of the other areas—most notably Programming Languages (PL) and Software Engineering (SE)—also contain programming-related units that are part of the undergraduate core. In most cases, these units could equally well have been assigned to either Programming Fundamentals or the more advanced area. PF. Programming Fundamentals (47 core hours) PF/FundamentalConstructs [core] PF/AlgorithmicProblemSolving [core] PF/DataStructures [core] PF/Recursion [core] PF/EventDrivenProgramming [core] PF/ObjectOriented [core] PF/FoundationsInformationSecurity [core] PF/SecureProgramming [core] PF/FundamentalConstructs [core] Minimum core coverage time: 9 hours Topics: • Basic syntax and semantics of a higher-level language • Variables, types, expressions, and assignment • Simple I/O • Conditional and iterative control structures • Functions and parameter passing • Structured decomposition Learning Objectives: 1. Analyze and explain the behavior of simple programs involving the fundamental programming constructs covered by this unit. 2. Modify and expand short programs that use standard conditional and iterative control structures and functions. 3. Design, implement, test, and debug a program that uses each of the following fundamental programming constructs: basic computation, simple I/O, standard conditional and iterative structures, and the definition of functions. 4. Choose appropriate conditional and iteration constructs for a given programming task. 5. Apply the techniques of structured (functional) decomposition to break a program into smaller pieces. 6. Describe the mechanics of parameter passing. PF/AlgorithmicProblemSolving [core] Minimum core coverage time: 6 hours Topics: • Problem-solving strategies • The role of algorithms in the problem-solving process • Implementation strategies for algorithms • Debugging strategies • The concept and properties of algorithms Learning Objectives: 7. Discuss the importance of algorithms in the problem-solving process. 8. Identify the necessary properties of good algorithms. 9. Create algorithms for solving simple problems. 10. Use pseudocode or a programming language to implement, test, and debug algorithms for solving simple problems. 11. Describe strategies that are useful in debugging. PF/DataStructures [core] Minimum core coverage time: 10 hours Topics: • Representation of numeric data • Range, precision, and rounding errors • Arrays • Representation of character data • Strings and string processing • Runtime storage management • Pointers and references • Linked structures • Implementation strategies for stacks, queues, and hash tables • Implementation strategies for graphs and trees • Strategies for choosing the right data structure Learning Objectives: 1. Describe the representation of numeric and character data. 2. Understand how precision and round-off can affect numeric calculations. 3. Discuss the use of primitive data types and built-in data structures. 4. Describe common applications for each data structure in the topic list. 5. Implement the user-defined data structures in a high-level language. 6. Compare alternative implementations of data structures with respect to performance. 7. Write programs that use each of the following data structures: arrays, strings, linked lists, stacks, queues, and hash tables. 8. Compare and contrast the costs and benefits of dynamic and static data structure implementations. 9. Choose the appropriate data structure for modeling a given problem. PF/Recursion [core] Minimum core coverage time: 4 hours Topics: • The concept of recursion • Recursive mathematical functions • Simple recursive functions • Divide-and-conquer strategies • Recursive backtracking Learning Objectives: 1. Describe the concept of recursion and give examples of its use. 2. Identify the base case and the general case of a recursively defined problem. 3. Compare iterative and recursive solutions for elementary problems such as factorial. 4. Describe the divide-and-conquer approach. 5. Implement, test, and debug simple recursive functions and procedures. 6. Determine when a recursive solution is appropriate for a problem. PF/EventDrivenProgramming[core] Minimum core coverage time: 4 hours Topics: • Event-handling methods • Event propagation • Exception handling Learning Objectives: 1. Explain the difference between event-driven programming and command-line programming. 2. Design, code, test, and debug simple event-driven programs that respond to user events. 3. Develop code that responds to exception conditions raised during execution. PF/ObjectOriented [core] Minimum core coverage time: 8 hours Topics: • Object-oriented design • Encapsulation and information-hiding • Separation of behavior and implementation • Classes and subclasses • Inheritance (overriding, dynamic dispatch) • Polymorphism (subtype polymorphism vs. inheritance) Learning Objectives: 1. Justify the philosophy of object-oriented design and the concepts of encapsulation, abstraction, inheritance, and polymorphism. 2. Design, implement, test, and debug simple programs in an object-oriented programming language. 3. Describe how the class mechanism supports encapsulation and information hiding. 4. Design, implement, and test the implementation of “is-a” relationships among objects using a class hierarchy and inheritance. 5. Compare and contrast the notions of overloading and overriding methods in an object-oriented language. PF/FoundationsInformationSecurity [core] Minimum core coverage time: 4 hours Topics: • Role and purpose of computer and network security • Security goals: confidentiality, integrity, availability triad • Security standards and policies • Security mindset • Defense in depth • Common threats: worms, viruses, trojans, denial of service • Risk assessment and cost-benefit analyses • Security versus usability, time, and/or money tradeoffs Learning Objectives: 1. Explain the objectives of information security 2. Analyze the tradeoffs inherent in security 3. Explain the importance and application of each of confidentiality, integrity, and availability 4. Understand the basic categories of threats to computers and networks 5. Discuss issues for creating security policy for a large organization 6. Defend the need for protection and security, and the role of ethical considerations in computer use 7. Add a very simple risk-assessment learning outcome here PF/SecureProgramming [core] Minimum core coverage time: 2 hour Topics • Important of checking for and avoiding array and string overflows • Programming language constructs to avoid and alternatives • How attackers use overflows to smash the run-time stack Learning Objectives: 1. Rewrite a simple program to remove a simple vulnerability 2. Explain why or why not a buffer overflow is possible in the programming language you know best 3. Explain why one or more language constructs may lead to security problems such as overflows. Algorithms and Complexity Algorithms are fundamental to computer science and software engineering. The real-world performance of any software system depends on only two things: (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 well-defined problems, recognizing their strengths and weaknesses, and their suitability in particular contexts. Efficiency is a pervasive theme throughout this area. With the emergence of multicore processors, issues related to parallel algorithms have become more relevant. While the parallelism topics remain listed here as elective, the committee believes that the role of parallelism throughout the curriculum needs to be considered. AL. Algorithms and Complexity (31 core hours) AL/Basic Analysis [core] AL/AlgorithmicStrategies [core] AL/FundamentalAlgorithms [core] AL/DistributedAlgorithms [core] AL/BasicComputability [core] AL/PversusNP [elective] AL/AutomataTheory [elective] AL/AdvancedAnalysis [elective] AL/CryptographicAlgorithms [elective] AL/GeometricAlgorithms [elective] AL/ParallelAlgorithms [elective] AL/BasicAnalysis [core] Minimum core coverage time: 4 hours Topics: • Asymptotic analysis of upper and average complexity bounds • Identifying differences among best, average, and worst case behaviors • Big O, little o, omega, and theta notation • Standard complexity classes • Empirical measurements of performance • Time and space tradeoffs in algorithms • Using recurrence relations to analyze recursive algorithms Learning Objectives: 1. Explain the use of big O, omega, and theta notation to describe the amount of work done by an algorithm. 2. Use big O, omega, and theta notation to give asymptotic upper, lower, and tight bounds on time and space complexity of algorithms. 3. Determine the time and space complexity of simple algorithms. 4. Deduce recurrence relations that describe the time complexity of recursively defined algorithms. 5. Solve elementary recurrence relations. AL/AlgorithmicStrategies [core] Minimum core coverage time: 6 hours Topics: • Brute-force algorithms • Greedy algorithms • Divide-and-conquer • Backtracking • Branch-and-bound • Heuristics • Pattern matching and string/text algorithms • Numerical approximation algorithms Learning Objectives: 1. Describe the shortcoming of brute-force algorithms. 2. For each of several kinds of algorithm (brute force, greedy, divide-and-conquer, backtracking, branch-and-bound, and heuristic), identify an example of everyday human behavior that exemplifies the basic concept. 3. Implement a greedy algorithm to solve an appropriate problem. 4. Implement a divide-and-conquer algorithm to solve an appropriate problem. 5. Use backtracking to solve a problem such as navigating a maze. 6. Describe various heuristic problem-solving methods. 7. Use pattern matching to analyze substrings. 8. Use numerical approximation to solve mathematical problems, such as finding the roots of a polynomial. AL/FundamentalAlgorithms [core] Minimum core coverage time: 12 hours Topics: • Simple numerical algorithms • Sequential and binary search algorithms • Quadratic sorting algorithms (selection, insertion) • O(N log N) sorting algorithms (Quicksort, heapsort, mergesort) • Hash tables, including collision-avoidance strategies • Binary search trees • Representations of graphs (adjacency list, adjacency matrix) • Depth- and breadth-first traversals • Shortest-path algorithms (Dijkstra’s and Floyd’s algorithms) • Transitive closure (Floyd’s algorithm) • Minimum spanning tree (Prim’s and Kruskal’s algorithms) • Topological sort Learning Objectives: 1. Implement the most common quadratic and O(NlogN) sorting algorithms. 2. Design and implement an appropriate hashing function for an application. 3. Design and implement a collision-resolution algorithm for a hash table. 4. Discuss the computational efficiency of the principal algorithms for sorting, searching, and hashing. 5. Discuss factors other than computational efficiency that influence the choice of algorithms, such as programming time, maintainability, and the use of application-specific patterns in the input data. 6. Solve problems using the fundamental graph algorithms, including depth-first and breadth-first search, single-source and all-pairs shortest paths, transitive closure, topological sort, and at least one minimum spanning tree algorithm. 7. Demonstrate the following capabilities: to evaluate algorithms, to select from a range of possible options, to provide justification for that selection, and to implement the algorithm in programming context. AL/DistributedAlgorithms [core] Minimum core coverage time: 3 hours Topics: • Consensus and election • Termination detection • Fault tolerance • Stabilization Learning Objectives: 1. Explain the distributed paradigm. 2. Explain one simple distributed algorithm. 3. Determine when to use consensus or election algorithms. 4. Distinguish between logical and physical clocks. 5. Describe the relative ordering of events in a distributed algorithm. AL/BasicComputability [core] Minimum core coverage time: 6 hours Topics: • Finite-state machines • Context-free grammars • Tractable and intractable problems • Uncomputable functions • The halting problem • Implications of uncomputability Learning Objectives: 1. Discuss the concept of finite state machines. 2. Explain context-free grammars. 3. Design a deterministic finite-state machine to accept a specified language. 4. Explain how some problems have no algorithmic solution. 5. Provide examples that illustrate the concept of uncomputability. AL/PversusNP [elective] Topics: • Definition of the classes P and NP • NP-completeness (Cook’s theorem) • Standard NP-complete problems • Reduction techniques Learning Objectives: 1. Define the classes P and NP. 2. Explain the significance of NP-completeness. 3. Prove that a problem is NP-complete by reducing a classic known NP-complete problem to it. AL/AutomataTheory [elective] Topics: • Deterministic finite automata (DFAs) • Nondeterministic finite automata (NFAs) • Equivalence of DFAs and NFAs • Regular expressions • The pumping lemma for regular expressions • Push-down automata (PDAs) • Relationship of PDAs and context-free grammars • Properties of context-free grammars • Turing machines • Nondeterministic Turing machines • Sets and languages • Chomsky hierarchy • The Church-Turing thesis Learning Objectives: 1. Determine a language’s location in the Chomsky hierarchy (regular sets, context-free, context-sensitive, and recursively enumerable languages). 2. Prove that a language is in a specified class and that it is not in the next lower class. 3. Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs. 4. Explain at least one algorithm for both top-down and bottom-up parsing. 5. Explain the Church-Turing thesis and its significance. AL/AdvancedAnalysis [elective] Topics: • Amortized analysis • Online and offline algorithms • Randomized algorithms • Dynamic programming • Combinatorial optimization Learning Objectives: 1. Use the potential method to provide an amortized analysis of previously unseen data structure, given the potential function. 2. Explain why competitive analysis is an appropriate measure for online algorithms. 3. Explain the use of randomization in the design of an algorithm for a problem where a deterministic algorithm is unknown or much more difficult. 4. Design and implement a dynamic programming solution to a problem. AL/CryptographicAlgorithms [elective] Topics: • Historical overview of cryptography • Private-key cryptography and the key-exchange problem • Public-key cryptography • Digital signatures • Security protocols • Applications (zero-knowledge proofs, authentication, and so on) Learning Objectives: 1. Describe efficient basic number-theoretic algorithms, including greatest common divisor, multiplicative inverse mod n, and raising to powers mod n. 2. Describe at least one public-key cryptosystem, including a necessary complexity-theoretic assumption for its security. 3. Create simple extensions of cryptographic protocols, using known protocols and cryptographic primitives. AL/GeometricAlgorithms [elective] Topics: • Line segments: properties, intersections • Convex hull finding algorithms Learning Objectives: 1. Describe and give time analysis of at least two algorithms for finding a convex hull. 2. Justify the Omega(N log N) lower bound on finding the convex hull. 3. Describe at least one additional efficient computational geometry algorithm, such as finding the closest pair of points, convex layers, or maximal layers. AL/ParallelAlgorithms [elective] Topics: • PRAM model • Exclusive versus concurrent reads and writes • Pointer jumping • Brent’s theorem and work efficiency Learning Objectives: 1. Describe implementation of linked lists on a PRAM. 2. Use parallel-prefix operation to perform simple computations efficiently in parallel. 3. Explain Brent’s theorem and its relevance. See also algorithm topics related to security, cryptography and compression. Architecture and Organization The computer lies at the heart of computing. Without it most of the computing disciplines today would be a branch of theoretical mathematics. A professional in any field of computing should not regard the computer as just a black box that executes programs by magic. All students of computing should acquire some understanding and appreciation of a computer system's functional components, their characteristics, their performance, and their interactions. Students need to understand computer architecture in order to make best use of the software tools and computer languages they use to create programs. In this introduction the term architecture is taken to include instruction set architecture (the programmer’s abstraction of a computer), organization or microarchitecture (the internal implementation of a computer at the register and functional unit level), and system architecture (the organization of the computer at the cache, and bus level). Students should also understand the complex tradeoffs between CPU clock speed, cache size, bus organization, number of core processors, and so on. Computer architecture also underpins other areas of the computing curriculum such as operating systems (input/output, memory technology) and high-level languages (pointers, parameter passing). The learning objectives specified for these topics correspond primarily to the core and are intended to support programs that require only the minimum 36 hours of computer architecture. For programs that want to teach more than the minimum, the same topics (AR1-AR6) 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 AR. Architecture and Organization (36 core hours) AR/DigitalLogicandDataRepresentation [core] AR/ ComputerArchitectureandOrganization [core] AR/ InterfacingandI/OStrategies [core] AR/MemoryArchitecture [core] AR/FunctionalOrganization [core] AR/Multiprocessing [core] AR/PerformanceEnhancements [elective] AR/DistributedArchitectures [elective] AR/Devices [elective] AR/DirectionsInComputing [elective] AR/DigitalLogicandDataRepresentation [core] Minimum core coverage time: 7 hours (was Digital logic and digital systems AR1 and Machine level representation of data AR2. ) Topics: • Introduction to digital logic (logic gates, flip-flops, circuits) • Logic expressions and Boolean functions • Representation of numeric data • Signed and unsigned arithmetic • Range, precision, and errors in floating-point arithmetic • Representation of text, audio, and images • Data compression Learning Objectives: 1. Design a simple circuit using fundamental building blocks. 2. Appreciate the effect of AND, OR, NOT and EOR operations on binary data 3. Understand how numbers, text, images, and sound can be represented in digital form and the limitations of such representations 4. Understand how errors due to rounding effects and their propagation affect the accuracy of chained calculations. 5. Appreciate how data can be compressed to reduce storage requirements including the concepts of lossless and lossy compression. AR/ComputerArchitectureandOrganization [core] Minimum core coverage time: 9 hours (was Assembly level machine organization AR3) Topics: • Overview of the history of the digital computer • Introduction to instruction set architecture, microarchitecture and system architecture • Processor architecture – instruction types, register sets, addressing modes • Processor structures – memory-to-register and load/store architectures • Instruction sequencing, flow-of-control, subroutine call and return mechanisms • Structure of machine-level programs • Limitations of low-level architectures • Low-level architectural support for high-level languages Learning Objectives: 1. Describe the progression of computers from vacuum tubes to VLSI. 2. Appreciate the concept of an instruction set architecture, ISA, and the nature of a machine-level instruction in terms of its functionality and use of resources (registers and memory). 3. To understand the relationship between instruction set architecture, microarchitecture, and system architecture and their roles in the development of the computer. 4. Be aware of the various classes of instruction: data movement, arithmetic, logical, and flow control. 5. Appreciate the difference between register-to-memory ISAs and load/store ISAs. 6. Appreciate how conditional operations are implemented at the machine level. 7. Understand the way in which subroutines are called and returns made. 8. Appreciate how a lack of resources in ISPs has an impact on high-level languages and the design of compilers. 9. Understand how, at the assembly language level, how parameters are passed to subroutines and how local workplace is created and accessed. AR/InterfacingandI/OStrategies [core] Minimum core coverage time: 3 hours (was Interfacing and communication AR5) Topics: • I/O fundamentals: handshaking and buffering • Interrupt mechanisms: vectored and prioritized, interrupt acknowledgment • Buses: protocols, arbitration, direct-memory access (DMA) • Examples of modern buses: e.g., PCIe, USB, Hypertransport Learning Objectives: 1. Appreciate the need of open- and closed-loop communications and the use of buffers to control dataflow. 2. Explain how interrupts are used to implement I/O control and data transfers. 3. Identify various types of buses in a computer system and understand how devices compete for a bus and are granted access to the bus. 4. Be aware of the progress in bus technology and understand the features and performance of a range of modern buses (both serial and parallel). AR/MemoryArchitecture [core] Minimum core coverage time: 5 hours (was Memory system organization AR4) Topics: • Storage systems and their technology (semiconductor, magnetic) • Storage standards (CD-ROM, DVD) • Memory hierarchy, latency and throughput • Cache memories - operating principles, replacement policies, multilevel cache, cache coherency Learning Objectives: 1. Identify the memory technologies found in a computer and be aware of the way in which memory technology is changing. 2. Appreciate the need for storage standards for complex data storage mechanisms such as DVD. 3. Understand why a memory hierarchy is necessary to reduce the effective memory latency. 4. Appreciate that most data on the memory bus is cache refill traffic 5. Describe the various ways of organizing cache memory and appreciate the cost-performance tradeoffs for each arrangement. 6. Appreciate the need for cache coherency in multiprocessor systems AR/FunctionalOrganization [core] Minimum core coverage time: 6 hours (was Functional organization AR6) Topics: • Review of register transfer language to describe internal operations in a computer • Microarchitectures - hardwired and microprogrammed realizations • Instruction pipelining and instruction-level parallelism (ILP) • Overview of superscalar architectures • Processor and system performance • Performance – their meeasures and their limitations • The significance of power dissipation and its effects on computing structures Learning Objectives: 1. Review of the use of register transfer language to describe internal operations in a computer 2. Understand how a CPU’s control unit interprets a machine-level instruction – either directly or as a microprogram. 3. Appreciate how processor performance can be improved by overlapping the execution of instruction by pipelining. 4. Understand the difference between processor performance and system performance (i.e., the effects of memory systems, buses and software on overall performance). 5. Appreciate how superscalar architectures use multiple arithmetic units to execute more than one instruction per clock cycle. 6. Understand how computer performance is measured by measurements such as MIPS or SPECmarks and the limitations of such measurements. 7. Appreciate the relationship between power dissipation and computer performance and the need to minimize power consumption in mobile applications. AR/Multiprocessing [core] Minimum core coverage time: 6 hours (was Multiprocessing and alternative architectures AR7) Topics: • Amdahl’s law • Short vector processing (multimedia operations) • Multicore and multithreaded processors • Flynn’s taxonomy: Multiprocessor structures and architectures • Programming multiprocessor systems • GPU and special-purpose graphics processors • Introduction to reconfigurable logic and special-purpose processors Learning Objectives: 1. Discuss the concept of parallel processing and the relationship between parallelism and performance. 2. Appreciate that multimedia values (e.g., 8-/16-bit audio and visual data) can be operated on in parallel in 64-bit registers to enhance performance. 3. Understand how performance can be increased by incorporating multiple processors on a single chip. 4. Appreciate the need to express algorithms in a form suitable for execution on parallel processors. 5. Understand how special-purpose graphics processors, GPUs, can accelerate performance in graphics applications. 6. Understand the organization of computer structures that can be electronically configured and reconfigured AR/PerformanceEnhancements [elective] (was performance enhancements AR8) Topics: • Branch prediction • Speculative execution • Superscalar architecture • Out-of-order execution • Multithreading • Scalability • Introduction to VLIW and EPIC architectures • Memory access ordering Learning Objectives: 1. Explain the concept of branch prediction its use in enhancing the performance of pipelined machines. 2. Understand how speculative execution can improve performance. 3. Provide a detailed description of superscalar architectures and the need to ensure program correctness when executing instructions out-of-order. 4. Explain speculative execution and identify the conditions that justify it. 5. Discuss the performance advantages that multithreading can offer along with the factors that make it difficult to derive maximum benefits from this approach. 6. Appreciate the nature of VLIW and EPIC architectures and the difference between them (and between superscalar processors) 7. Understand how a processor re-orders memory loads and stores to increase performance AR/DistributedArchitectures [elective] (was Architecture for networks and distributed systems AR9) Topics: • Introduction to LANs and WANs and the history of networking and the Internet • Layered protocol design, network standards and standardization bodies • Network computing and distributed multimedia • Mobile and wireless computing • Streams and datagrams • Physical layer networking concepts • Data link layer concepts (framing, error control, flow control, protocols) • Internetworking and routing (routing algorithms, internetworking, congestion control) • Transport layer services (connection establishment, performance issues) Learning Objectives: 1. Explain the basic components of network systems and distinguish between LANs and WANs. 2. Discuss the architectural issues involved in the design of a layered network protocol. 3. Explain how architectures differ in network and distributed systems. 4. Appreciate the special requirements of wireless computing. 5. Understand the difference between the roles of the physical layer and data link layer and appreciate how imperfections in the physical layer are handled by the data link layer. 6. Describe emerging technologies in the net-centric computing area and assess their current capabilities, limitations, and near-term potential. 7. Understand how the network layer can detect and correct errors. AR/Devices [elective] (new material) Topics: • Representing analog values digitally – quantization and sampling • Sound and audio, image and graphics, animation and video • Multimedia standards (audio, music, graphics, image, telephony, video, TV) • Input transducers (temperature, pressure, position, movement) • Input devices: mice, keyboards (text and musical), scanners, touch-screen, voice • Output devices: displays, printers • Encoding and decoding of multimedia systems including compression and decompression • Example of computer-based systems: GPS, MP3 players, digital cameras Learning Objectives: 1. Understand how analog quantities such as pressure can be represented in digital form and how the use of a finite representation leads to quantization errors. 2. Appreciate the need for multimedia standards and be able to explain in non-technical language what the standard calls for. 3. Understand how multimedia signals usually have to be compressed to conserve bandwidths using lossless or lossy encoding. 4. Discuss the design, construction, and operating principles of transducers such as Hall-effect devices and strain gauges 5. Appreciate how typical input devices operate. 6. Understand the principles of operation and performance of various display devices. 7. Study the operation of high-performance computer-based devices such as digital cameras AR/Directions in Computing [elective] 7 hours (New topic) Topics: • Semiconductor technology and Moore’s law • Limitations to semiconductor technology • Quantum computing • Optical computing • Molecular (biological) computing • New memory technologies Learning Objectives: 1. To appreciate the underlying physical basic of modern computing. 2. Understand how the physical properties of matter impose limitations on computer technology 3. Appreciate how the quantum nature of matter can be exploited to permit massive parallelism 4. Appreciate how light can be used to perform certain types of computation 5. Understand how the properties of complex molecules can be exploited by organic computers 6. To get an insight into trends in memory design such as ovonic memory and ferromagnetic memories Operating Systems An operating system defines an abstraction of hardware behavior with which programmers can control the hardware. It also manages resource sharing among the computer’s users. The topics in this area explain the issues that influence the design of contemporary operating systems. Courses that cover this area will typically include a laboratory component to enable students to experiment with operating systems. Over the years, operating systems and their abstractions have become complex relative to typical application software. It is necessary to ensure that the student understands the extent of the use of an operating system prior to a detailed study of internal implementation algorithms and data structures. Therefore these topics address both the use of operating systems (externals) and their design and implementation (internals). Many of the ideas involved in operating system use have wider applicability across the field of computer science, such as concurrent programming. Studying internal design has relevance in such diverse areas as dependable programming, algorithm design and implementation, modern device development, building virtual environments, caching material across the web, building secure and safe systems, network management, and many others. OS. Operating Systems (20 core hours) OS/OverviewOfOperatingSystems [core] OS/OperatingSystemPrinciples [core] OS/Concurrency [core] OS/SchedulingandDispatch [core] OS/MemoryManagement [core] OS/DeviceManagement [elective] OS/SecurityAndProtection [core] OS/FileSystems [elective] OS/RealTimeAndEmbeddedSystems [elective] OS/FaultTolerance [elective] OS/SystemPerformanceEvaluation [elective] OS/Scripting [elective] OS/DigitalForensics [elective] OS/SecurityModels [elective] OS/OverviewOfOperatingSystems [core] Minimum core coverage time: 2 hours Topics: • Role and purpose of the operating system • History of operating system development • Functionality of a typical operating system • Mechanisms to support client-server models, hand-held devices • Design issues (efficiency, robustness, flexibility, portability, security, compatibility) • Influences of security, networking, multimedia, windows Learning Objectives: 1. Explain the objectives and functions of modern operating systems. 2. Describe how operating systems have evolved over time from primitive batch systems to sophisticated multiuser systems. 3. Analyze the tradeoffs inherent in operating system design. 4. Describe the functions of a contemporary operating system with respect to convenience, efficiency, and the ability to evolve. 5. Discuss networked, client-server, distributed operating systems and how they differ from single user operating systems. 6. Identify potential threats to operating systems and the security features design to guard against them. 7. Describe how issues such as open source software and the increased use of the Internet are influencing operating system design. OS/OperatingSystemPrinciples [core] Minimum core coverage time: 2 hours Topics: • Structuring methods (monolithic, layered, modular, micro-kernel models) • Abstractions, processes, and resources • Concepts of application program interfaces (APIs) • Application needs and the evolution of hardware/software techniques • Device organization • Interrupts: methods and implementations • Concept of user/system state and protection, transition to kernel mode Learning Objectives: 1. Explain the concept of a logical layer. 2. Explain the benefits of building abstract layers in hierarchical fashion. 3. Defend the need for APIs and middleware. 4. Describe how computing resources are used by application software and managed by system software. 5. Contrast kernel and user mode in an operating system. 6. Discuss the advantages and disadvantages of using interrupt processing. 7. Compare and contrast the various ways of structuring an operating system such as object-oriented, modular, micro-kernel, and layered. 8. Explain the use of a device list and driver I/O queue. OS/Concurrency [core] Minimum core coverage time: 6 hours Topics: • States and state diagrams • Structures (ready list, process control blocks, and so forth) • Dispatching and context switching • The role of interrupts • Concurrent execution: advantages and disadvantages • The “mutual exclusion” problem and some solutions • Deadlock: causes, conditions, prevention • Models and mechanisms (semaphores, monitors, condition variables, rendezvous) • Producer-consumer problems and synchronization • Multiprocessor issues (spin-locks, reentrancy) Learning Objectives: 1. Describe the need for concurrency within the framework of an operating system. 2. Demonstrate the potential run-time problems arising from the concurrent operation of many separate tasks. 3. Summarize the range of mechanisms that can be employed at the operating system level to realize concurrent systems and describe the benefits of each. 4. Explain the different states that a task may pass through and the data structures needed to support the management of many tasks. 5. Summarize the various approaches to solving the problem of mutual exclusion in an operating system. 6. Describe reasons for using interrupts, dispatching, and context switching to support concurrency in an operating system. 7. Create state and transition diagrams for simple problem domains. 8. Discuss the utility of data structures, such as stacks and queues, in managing concurrency. 9. Explain conditions that lead to deadlock. OS/SchedulingAndDispatch [core] Minimum core coverage time: 3 hours Topics: • Preemptive and nonpreemptive scheduling • Schedulers and policies • Processes and threads • Deadlines and real-time issues Learning Objectives: 1. Compare and contrast the common algorithms used for both preemptive and non-preemptive scheduling of tasks in operating systems, such as priority, performance comparison, and fair-share schemes. 2. Describe relationships between scheduling algorithms and application domains. 3. Discuss the types of processor scheduling such as short-term, medium-term, long-term, and I/O. 4. Describe the difference between processes and threads. 5. Compare and contrast static and dynamic approaches to real-time scheduling. 6. Discuss the need for preemption and deadline scheduling. 7. Identify ways that the logic embodied in scheduling algorithms are applicable to other domains, such as disk I/O, network scheduling, project scheduling, and other problems unrelated to computing. OS/MemoryManagement [core] Minimum core coverage time: 3 hours Topics: • Review of physical memory and memory management hardware • Paging and virtual memory • Working sets and thrashing • Caching Learning Objectives: 1. Explain memory hierarchy and cost-performance trade-offs. 2. Explain the concept of virtual memory and how it is realized in hardware and software. 3. Summarize the principles of virtual memory as applied to caching and paging. 4. Evaluate the trade-offs in terms of memory size (main memory, cache memory, auxiliary memory) and processor speed. 5. Defend the different ways of allocating memory to tasks, citing the relative merits of each. 6. Describe the reason for and use of cache memory. 7. Discuss the concept of thrashing, both in terms of the reasons it occurs and the techniques used to recognize and manage the problem. OS/DeviceManagement [elective] Topics: • Characteristics of serial and parallel devices • Abstracting device differences • Buffering strategies • Direct memory access • Recovery from failures Learning Objectives: 1. Explain the key difference between serial and parallel devices and identify the conditions in which each is appropriate. 2. Identify the relationship between the physical hardware and the virtual devices maintained by the operating system. 3. Explain buffering and describe strategies for implementing it. 4. Differentiate the mechanisms used in interfacing a range of devices (including hand-held devices, networks, multimedia) to a computer and explain the implications of these for the design of an operating system. 5. Describe the advantages and disadvantages of direct memory access and discuss the circumstances in which its use is warranted. 6. Identify the requirements for failure recovery. 7. Implement a simple device driver for a range of possible devices. OS/SecurityAndProtection [core] Minimum coverage time: 2 hours Topics: • Overview of system security • Policy/mechanism separation • Security methods and devices • Protection, access control, and authentication • Backups Learning Objectives: 1. Defend the need for protection and security, and the role of ethical considerations in computer use. 2. Summarize the features and limitations of an operating system used to provide protection and security. 3. Explain the mechanisms available in an OS to control access to resources. 4. Carry out simple sysadmin tasks according to a security policy, for example creating accounts, setting permissions, applying patches, and arranging for regular backups. OS/FileSystems [elective] Topics: • Files: data, metadata, operations, organization, buffering, sequential, nonsequential • Directories: contents and structure • File systems: partitioning, mount/unmount, virtual file systems • Standard implementation techniques • Memory-mapped files • Special-purpose file systems • Naming, searching, access, backups Learning Objectives: 1. Summarize the full range of considerations that support file systems. 2. Compare and contrast different approaches to file organization, recognizing the strengths and weaknesses of each. 3. Summarize how hardware developments have lead to changes in our priorities for the design and the management of file systems. OS/RealTimeAndEmbeddedSystems [elective] Topics: • Process and task scheduling • Memory/disk management requirements in a real-time environment • Failures, risks, and recovery • Special concerns in real-time systems Learning Objectives: 1. Describe what makes a system a real-time system. 2. Explain the presence of and describe the characteristics of latency in real-time systems. 3. Summarize special concerns that real-time systems present and how these concerns are addressed. OS/FaultTolerance [elective] Topics: • Fundamental concepts: reliable and available systems • Spatial and temporal redundancy • Methods used to implement fault tolerance • Examples of reliable systems Learning Objectives: 1. Explain the relevance of the terms fault tolerance, reliability, and availability. 2. Outline the range of methods for implementing fault tolerance in an operating system. 3. Explain how an operating system can continue functioning after a fault occurs. OS/SystemPerformanceEvaluation [elective] Topics: • Why system performance needs to be evaluated • What is to be evaluated • Policies for caching, paging, scheduling, memory management, security, and so forth • Evaluation models: deterministic, analytic, simulation, or implementation-specific • How to collect evaluation data (profiling and tracing mechanisms) Learning Objectives: 1. Describe the performance measurements used to determine how a system performs. 2. Explain the main evaluation models used to evaluate a system. OS/Scripting [elective] Topics: • Scripting and the role of scripting languages • Basic system commands • Creating scripts, parameter passing • Executing a script • Influences of scripting on programming Learning Objectives: 1. Summarize a typical set of system commands provided by an operating system. 2. Demonstrate the typical functionality of a scripting language, and interpret the implications for programming. 3. Demonstrate the mechanisms for implementing scripts and the role of scripts on system implementation and integration. 4. Implement a simple script that exhibits parameter passing. OS/DigitalForensics [elective] Topics: • Digital forensics and its relationship to other forensic disciplines • Incident response responsibilities • Forensic procedures • Digital evidence and tracking • Rules/Standards of Evidence • Evidence gathering and analysis • Forensic mechanisms • Profiling • Tools to support investigative work Learning Objectives: 1. To explain the problems addressed by digital forensics and to outline the basic principles involved in its practice 2. To outline the basic processes of information gathering and analysis in line with best practices in digital forensics 3. To recognize the role that tools can play in digital forensics and to demonstrate their use in simple examples the use of tools and to demonstrate their use 4. To explain what questions must be asked and answered to determine if the interpretation of forensic evidence is valid or questionable. OS/SecurityModels [elective] Topics: • Models of protection • Memory protection • Encryption • Recovery management • Types of access control: mandatory, discretionary, originator-controlled, role-based • Access control matrix model • Harrison-Russo-Ullman model and undecidability of security • Confidentiality models such as Bell-LaPadula • Integrity models such as Biba and Clark-Wilson • Conflict of interest models such as the Chinese Wall Learning Objectives: 1. Compare and contrast current methods for implementing security. 2. Compare and contrast the strengths and weaknesses of two or more currently popular operating systems with respect to security. 3. Compare and contrast the security strengths and weaknesses of two or more currently popular operating systems with respect to recovery management. 4. Describe the access control matrix and how it relates to ACLs and C-Lists 5. Apply Biba's model to the checking of inputs in a program (tainted v. untainted, for example) 6. Describe how the Bell-LaPadula model combines mandatory and discretionary access control mechanisms, and explain the lattice formulation of Bell-LaPadula and Biba 7. Compare and contrast two security models 8. Relate particular security models to the models of the software life cycle 9. Apply particular models to different environments and select the model that best captures the environment Net Centric Computing Recent advances in computer and telecommunications networking, particularly those based on TCP/IP, have increased the importance of networking technologies in the computing discipline. Net-centric computing covers a range of sub-specialties including: computer communication network concepts and protocols, multimedia systems, Web standards and technologies, network security, wireless and mobile computing, and distributed systems. Mastery of this subject area involves both theory and practice. Learning experiences that involve hands-on experimentation and analysis are strongly recommended as they reinforce student understanding of concepts and their application to real-world problems. Laboratory experiments should involve data collection and synthesis, empirical modeling, protocol analysis at the source code level, network packet monitoring, software construction, and evaluation of alternative design models. All of these are important concepts that can best understood by laboratory experimentation. NC. Net Centric Computing (18 core hours) NC/Introduction [core] NC/NetworkCommunication [core] NC/NetworkSecurity [core] NC/WebOrganization [elective] NC/NetworkedApplications [elective] NC/NetworkManagement [elective] NC/Compression [elective] NC/MultimediaTechnologies [elective] NC/MobileComputing [elective] NC/Introduction [core] Minimum core coverage time: 2 hours Topics: • Background and history of networking and the Internet • Network architectures • The range of specializations within net-centric computing • Networks and protocols • Networked multimedia systems • Distributed computing • Client/server and Peer to Peer paradigms • Mobile and wireless computing Learning Objectives: 1. Discuss the evolution of early networks and the Internet. 2. Demonstrate the ability to use effectively a range of common networked applications including e-mail, telnet, FTP, wikis, and web browsers, online web courses, and instant messaging. 3. Explain the hierarchical, layered structure of a typical network architecture. 4. Describe emerging technologies in the net-centric computing area and assess their current capabilities, limitations, and near-term potential. NC/NetworkCommunication [core] Minimum core coverage time: 7 hours Topics: • Network standards and standardization bodies • The ISO 7-layer reference model in general and its instantiation in TCP/IP • Overview of Physical and Data Link layer concepts (framing, error control, flow control, protocols) • Data Link layer access control concepts • Internetworking and routing (routing algorithms, internetworking, congestion control) • Transport layer services (connection establishment, performance issues, flow and error control) Learning Objectives: 1. Discuss important network standards in their historical context. 2. Describe the responsibilities of the first (lowest) four layers of the ISO reference model. 3. Explain how a network can detect and correct transmission errors. 4. Explain how a packet is routed over the Internet. 5. Install a simple network with two clients and a single server using standard host configuration software tools such as DHCP. NC/NetworkSecurity [core] Minimum core coverage time: 6 hours Topics: • Fundamentals of cryptography o Secret-key algorithms o Public-key algorithms • Authentication protocols • Digital signatures o Examples • Network attack types: Denial of service, flooding, sniffing and traffic redirection, message integrity attacks, identity hijacking, exploit attacks (buffer overruns, Trojans, backdoors), inside attacks, infrastructure (DNS hijacking, route blackholing, misbehaving routers that drop traffic), etc.) • Use of passwords and access control mechanisms • Basic network defense tools and strategies o Intrusion Detection o Firewalls o Detection of malware o Kerberos o IPSec o Virtual Private Networks o Network Address Translation • Network Resource Management policies • Auditing and logging Learning Objectives: 1. Describe the enhancements made to IPv4 by IPSec 2. Identify protocols used to enhance Internet communication, and choose the appropriate protocol for a particular case. 3. Understand Intrusions and intrusion detection 4. Discuss the fundamental ideas of public-key cryptography. 5. Describe how public-key cryptography works. 6. Distinguish between the use of private- and public-key algorithms. 7. Summarize common authentication protocols. 8. Generate and distribute a PGP key pair and use the PGP package to send an encrypted e-mail message. 9. Summarize the capabilities and limitations of the means of cryptography that are conveniently available to the general public. 10. Describe and discuss recent successful security attacks. 11. Summarize the strengths and weaknesses associated with different approaches to security. NC/WebOrganization [Elective] Topics: • Web technologies o Server-side programs o Client-side scripts o The applet concept • Characteristics of web servers o Handling permissions o File management o Capabilities of common server architectures • Role of client computers • Nature of the client-server relationship • Web protocols • Support tools for web site creation and web management • Developing Internet information servers • Publishing information and applications • Grid Computing, cluster, mesh • Web Services, Web 2.0, ajax Learning Objectives: 1. Explain the different roles and responsibilities of clients and servers for a range of possible applications. 2. Select a range of tools that will ensure an efficient approach to implementing various client-server possibilities. 3. Design and build a simple interactive web-based application (e.g., a simple web form that collects information from the client and stores it in a file on the server, and a server process to respond to the form data and produce a result). NC/NetworkedApplications [elective] Topics: • Protocols at the application layer • Web interfaces: Browsers and APIs • Web Search Technologies • Principles of web engineering • Database-driven web sites • Remote procedure calls (RPC) • Lightweight distributed objects • The role of middleware • Support tools • Security issues in distributed object systems • Enterprise-wide web-based applications o Service-oriented Architectures Learning Objectives: 1. Illustrate how interactive client-server web applications of medium size can be built using different types of Web technologies. 2. Demonstrate how to implement a database-driven web site, explaining the relevant technologies involved in each tier of the architecture and the accompanying performance tradeoffs. 3. Illustrate the current status of Web search effectiveness. 4. Implement an application that invokes the API of a web-based application. 5. Implement a distributed system using any two distributed object frameworks and compare them with regard to performance and security issues. 6. Discuss security issues and strategies in an enterprise-wide web-based application. NC/NetworkManagement [elective] Topics: • Overview of the issues of network management • Use of passwords and access control mechanisms • Domain names and name services • Issues for Internet service providers (ISPs) • Security issues and firewalls • Quality of service issues: performance, failure recovery Learning Objectives: 1. Explain the issues for network management arising from a range of security threats, including viruses, worms, Trojan horses, and denial-of-service attacks 2. Develop a strategy for ensuring appropriate levels of security in a system designed for a particular purpose. 3. Implement a network firewall. NC/Compression [Elective] Topics: • Analog and digital representations • Encoding and decoding algorithms • Lossless and lossy compression • Data compression: Huffman coding and the Ziv-Lempel algorithm • Audio compression and decompression • Image compression and decompression • Video compression and decompression • Performance issues: timing, compression factor, suitability for real-time use Learning Objectives: 1. Summarize the basic characteristics of sampling and quantization for digital representation. 2. Select, giving reasons that are sensitive to the specific application and particular circumstances, the most appropriate compression techniques for text, audio, image, and video information. 3. Explain the asymmetric property of compression and decompression algorithms. 4. Illustrate the concept of run-length encoding. 5. Illustrate how a program like the UNIX compress utility, which uses Huffman coding and the Ziv-Lempel algorithm, would compress a typical text file. NC/MultimediaTechnologies] [elective] Topics: • Sound and audio, image and graphics, animation and video • Multimedia standards (audio, music, graphics, image, telephony, video, TV) • Capacity planning and performance issues • Input and output devices (scanners, digital camera, touch-screens, voice-activated) • MIDI keyboards, synthesizers • Storage standards (Magneto Optical disk, CD-ROM, DVD) • Multimedia servers and file systems • Tools to support multimedia development Learning Objectives: 1. For each of several media or multimedia standards, describe in non-technical language what the standard calls for, and explain how aspects of human perception might be sensitive to the limitations of that standard. 2. Evaluate the potential of a computer system to host one of a range of possible multimedia applications, including an assessment of the requirements of multimedia systems on the underlying networking technology. 3. Describe the characteristics of a computer system (including identification of support tools and appropriate standards) that has to host the implementation of one of a range of possible multimedia applications. 4. Implement a multimedia application of modest size. NC/MobileComputing [elective] Topics: • Overview of the history, evolution, and compatibility of wireless standards • The special problems of wireless and mobile computing • Wireless local area networks and satellite-based networks • Wireless local loops • Mobile Internet protocol • Mobile aware adaption • Extending the client-server model to accommodate mobility • Mobile data access: server data dissemination and client cache management • Software package support for mobile and wireless computing • The role of middleware and support tools • Performance issues • Emerging technologies Learning Objectives: 1. Describe the main characteristics of mobile IP and explain how differs from IP with regard to mobility management and location management as well as performance. 2. Illustrate (with home agents and foreign agents) how e-mail and other traffic is routed using mobile IP. 3. Implement a simple application that relies on mobile and wireless data communications. 4. Describe areas of current and emerging interest in wireless and mobile computing, and assess the current capabilities, limitations, and near-term potential of each. Programming Languages A programming language is a programmer's principal interface with the computer. More than just knowing how to program in a single language, programmers need to understand the different styles of programming promoted by different languages. In their professional life, they will be working with many different languages and styles at once, and will encounter many different languages over the course of their careers. Understanding the variety of programming languages and the design tradeoffs between the different programming paradigms makes it much easier to master new languages quickly. Understanding the pragmatic aspects of programming languages also requires a basic knowledge of programming language translation and runtime features such as storage allocation. PL. Programming Languages (21 core hours) PL/Overview [core] PL/VirtualMachines [core] PL/BasicLanguageTranslation [core] PL/DeclarationsAndTypes [core] PL/AbstractionMechanisms [core] PL/ObjectOrientedProgramming [core]) PL/FunctionalProgramming [elective] PL/LanguageTranslationSystems [elective] PL/TypeSystems [elective] PL/ProgrammingLanguageSemantics [elective] PL/ProgrammingLanguageDesign [elective] PL/Overview [core] Minimum core coverage time: 2 hours Topics: • History of programming languages • Brief survey of programming paradigms • Procedural languages • Object-oriented languages • Functional languages • Declarative, non-algorithmic languages • Scripting languages • The effects of scale on programming methodology Learning Objectives: 1. Summarize the evolution of programming languages illustrating how this history has led to the paradigms available today. 2. Identify at least one distinguishing characteristic for each of the programming paradigms covered in this unit. 3. Evaluate the tradeoffs between the different paradigms, considering such issues as space efficiency, time efficiency (of both the computer and the programmer), safety, and power of expression. 4. Distinguish between programming-in-the-small and programming-in-the-large. PL/VirtualMachines [core] Minimum core coverage time: 1 hour Topics: • The concept of a virtual machine • Hierarchy of virtual machines • Intermediate languages • Security issues arising from running code on an alien machine • Learning Objectives: 1. Describe the importance and power of abstraction in the context of virtual machines. 2. Explain the benefits of intermediate languages in the compilation process. 3. Evaluate the tradeoffs in performance vs. portability. 4. Explain how executable programs can breach computer system security by accessing disk files and memory. PL/BasicLanguageTranslation [core] Minimum core coverage time: 2 hours Topics: • Comparison of interpreters and compilers • Language translation phases (lexical analysis, parsing, code generation, optimization) • Machine-dependent and machine-independent aspects of translation Learning Objectives: 1. Compare and contrast compiled and interpreted execution models, outlining the relative merits of each. 2. Describe the phases of program translation from source code to executable code and the files produced by these phases. 3. Explain the differences between machine-dependent and machine-independent translation and where these differences are evident in the translation process. PL/DeclarationsAndTypes [core] Minimum core coverage time: 3 hours Topics: • The conception of types as a set of values with together with a set of operations • Declaration models (binding, visibility, scope, and lifetime) • Overview of type-checking • Garbage collection • Learning Objectives: 1. Explain the value of declaration models, especially with respect to programming-in-the-large. 2. Identify and describe the properties of a variable such as its associated address, value, scope, persistence, and size. 3. Discuss type incompatibility. 4. Demonstrate different forms of binding, visibility, scoping, and lifetime management. 5. Defend the importance of types and type-checking in providing abstraction and safety. 6. Evaluate tradeoffs in lifetime management (reference counting vs. garbage collection). PL/AbstractionMechanisms [core] Minimum core coverage time: 3 hours Topics: • Procedures, functions, and iterators as abstraction mechanisms • Parameterization mechanisms (reference vs. value) • Activation records and storage management • Type parameters and parameterized types • Modules in programming languages Learning Objectives: 1. Explain how abstraction mechanisms support the creation of reusable software components. 2. Demonstrate the difference between call-by-value and call-by-reference parameter passing. 3. Defend the importance of abstractions, especially with respect to programming-in-the-large. 4. Describe how the computer system uses activation records to manage program modules and their data. PL/ObjectOrientedProgramming [core] Minimum core coverage time: 10 hours Topics: • Object-oriented design • Encapsulation and information-hiding • Separation of behavior and implementation • Classes and subclasses • Inheritance (overriding, dynamic dispatch) • Polymorphism (subtype polymorphism vs. inheritance) • Class hierarchies • Collection classes and iteration protocols • Internal representations of objects and method tables Learning Objectives: 1. Justify the philosophy of object-oriented design and the concepts of encapsulation, abstraction, inheritance, and polymorphism. 2. Design, implement, test, and debug simple programs in an object-oriented programming language. 3. Describe how the class mechanism supports encapsulation and information hiding. 4. Design, implement, and test the implementation of "is-a" relationships among objects using a class hierarchy and inheritance. 5. Compare and contrast the notions of overloading and overriding methods in an object-oriented language. 6. Explain the relationship between the static structure of the class and the dynamic structure of the instances of the class. 7. Describe how iterators access the elements of a container. PL/ FunctionalProgramming [elective] Topics: • Overview and motivation of functional languages • Recursion over lists, natural numbers, trees, and other recursively-defined data • Pragmatics (debugging by divide and conquer; persistency of data structures) • Amortized efficiency for functional data structures • Closures and uses of functions as data (infinite sets, streams) Learning Objectives: 1. Outline the strengths and weaknesses of the functional programming paradigm. 2. Design, code, test, and debug programs using the functional paradigm. 3. Explain the use of functions as data, including the concept of closures. PL/LanguageTranslationSystems [elective] Topics: • Application of regular expressions in lexical scanners • Parsing (concrete and abstract syntax, abstract syntax trees) • Application of context-free grammars in table-driven and recursive-descent parsing • Symbol table management • Code generation by tree walking • Architecture-specific operations: instruction selection and register allocation • Optimization techniques • The use of tools in support of the translation process and the advantages thereof • Program libraries and separate compilation • Building syntax-directed tools Learning Objectives: 1. Describe the steps and algorithms used by language translators. 2. Recognize the underlying formal models such as finite state automata, push-down automata and their connection to language definition through regular expressions and grammars. 3. Discuss the effectiveness of optimization. 4. Explain the impact of a separate compilation facility and the existence of program libraries on the compilation process. PL/TypeSystems [elective] Topics: • Data type as set of values with set of operations • Data types • Elementary types • Product and coproduct types • Algebraic types • Recursive types • Arrow (function) types • Parameterized types • Type-checking models • Semantic models of user-defined types • Type abbreviations • Abstract data types • Type equality • Parametric polymorphism • Subtype polymorphism • Type-checking algorithms Learning Objectives: 1. Formalize the notion of typing. 2. Describe each of the elementary data types. 3. Explain the concept of an abstract data type. 4. Recognize the importance of typing for abstraction and safety. 5. Differentiate between static and dynamic typing. 6. Differentiate between type declarations and type inference. 7. Evaluate languages with regard to typing. PL/ProgrammingLanguageSemantics [elective] Topics: • Informal semantics • Overview of formal semantics • Denotational semantics • Axiomatic semantics • Operational semantics Learning Objectives: 1. Explain the importance of formal semantics. 2. Differentiate between formal and informal semantics. 3. Describe the different approaches to formal semantics. 4. Evaluate the different approaches to formal semantics. PL/ProgrammingLanguageDesign [elective] Topics: • General principles of language design • Design goals • Typing regimes • Data structure models • Control structure models • Abstraction mechanisms Learning Objectives: 1. Evaluate the impact of different typing regimes on language design, language usage, and the translation process. 2. Explain the role of different abstraction mechanisms in the creation of user-defined facilities Human­Computer Interaction Human-computer interaction is an important area of computing knowledge. As more people conduct more of their daily activities interacting with a computer, the construction of interfaces that ease that interaction is critical for increasing satisfaction and improving productivity. As more software requires a user interface, knowing how to create a usable interface and testing the usability of that interface become required skills for all computer science students. The design of human-computer interfaces impacts the software life-cycle. Where interfaces used to be designed after the functionality was completed, we now know that the design of a usable interface should occur early in the cycle. We know that the design and implementation of the core functionality can influence the user interface. Human- computer interfaces are themselves software components, and the development and reuse of those components become an important part of the development of most software today. Human-Computer Interactions (8 core hours) HC/BuildingGUIInterfaces [core] HC/UserCcenteredSoftwareEvaluation [elective] HC/UserCenteredSoftwareDevelopment [elective] HC/GUIDesign [elective] HC/GUIProgramming [elective] HC/MultimediaAndMultimodalSystems [elective] HC/CollaborationAndCommunication [elective] HC/InteractionDesignForNewEnvironments [elective] HC/HumanFactorsAndSecurity [elective] HC/Foundations [core] Minimum core coverage time: 6 hours Topics: • Motivation: Why the study of how people interact with technology is vital for the development of most usable and acceptable systems • Contexts for HCI (mobile devices, consumer devices, business applications, web, business applications, collaboration systems, games, etc.) • Process for user-centered development: early focus on users, empirical testing, iterative design. • Different measures for evaluation: utility, efficiency, learnability, user satisfaction. • Models that inform human-computer interaction (HCI) design: attention, perception and recognition, movement, and cognition. • Social issues influencing HCI design and use: culture, communication, and organizations. • Accommodating human diversity, including universal design and accessibility and designing for multiple cultural and linguistic contexts. • The most common interface design mistakes. • User interface standards Learning Objectives: 1. Discuss why user-centered product development is important. 2. Explain why both individual human models and social models are important to consider in design of human- computer interaction. 3. Define a user-centered design process that explicitly recognizes that the user is not like the developer or her acquaintances. 4. Describe ways in which a user-centered design process may fail, including examples. 5. Define different processes for defining interfaces for different contexts. 6. Differentiate between the role of hypotheses and experimental results vs. correlations. 7. Choose between qualitative and quantitative evaluation methods for a given evaluation question. 8. Use vocabulary for analyzing human interaction with software: perceived affordance, conceptual model, mental model, metaphor, interaction design, feedback, and so forth. 9. Provide examples of how different interpretations that a given icon, symbol, word, or color can have in (a) two different human cultures and (b) in a culture and one of its subcultures. 10. Be able to describe at least one national or international user interface design standard HC/BuildingGUIInterfaces [core] Minimum core coverage time: 2 hours Topics: • Principles of graphical user interfaces (GUIs). • Action-object versus object-action. • User interface events. • Constructing a user-interface for a native system vs. the web. Learning Objectives: 1. Explain principles for design of user interfaces, such as learnability, flexibility, and robustness. 2. Describe examples of bad navigation, bad screen layout, and incomprehensible interface design. 3. Create a simple application that supports a graphical user interface, for either the Web or a windowing system. 4. Observe a user attempting to use the application and have the user critique the application. 5. Explain how careful user evaluation goes beyond the simple observation of a single user. HC/UserCenteredSoftwareEvaluation [elective] Topics: • Evaluation without typical users: walkthroughs, KLM, expert-based analysis, heuristics, guidelines, and standards • Evaluation with typical users: observation, think-aloud, interview, survey, experiment. • Challenges to effective evaluation: sampling, generalization. • Reporting the results of evaluations Learning Objectives: 1. Discuss evaluation criteria: task time/completion, time to learn, retention, errors, and user satisfaction. 2. Conduct a walkthrough, expert-based analysis, and a Keystroke Level Model (KLM) analysis. 3. Compare a given user interface to a set of guidelines or standards to identify inadequacies. 4. Conduct a usability test with more than one user, gathering results using at least two different methods. 5. Compare a laboratory test to a field test. 6. Explain a usability problem that is supported by results from a usability test. Recommend a solution to the usability problem. 7. Critique a user evaluation, to point out threats to validity. 8. Given an evaluation context (e.g. amount of time, availability of test users, place in the design process, evaluation goals), recommend and justify an evaluation method. HC/UserCenteredSoftwareDevelopment [elective] Topics: • Approaches, characteristics, and overview of product development process, with special emphasis on software development process. • Functionality and usability requirements • Techniques for gathering requirements: task analysis, interviews, surveys • Notations for specifying user interfaces • Prototyping techniques and tools • Sketching • Paper storyboards • Low-fidelity or paper prototyping • Medium fidelity prototyping • Prototyping tools and GUI builders • User-interface software techniques: • Inheritance and dynamic dispatch • Prototyping languages and GUI builders Learning Objectives: 1. Compare user-centered development to traditional software engineering methods. 2. Gather requirements for a user interface, using both task analysis and interview with a user. 3. Identify from requirements analysis at least three functional requirements and at least three usability requirements. 4. Create a specification for a user interface based on requirements. 5. Create two different prototypes at different levels of specificity from the specification. 6. Implement the prototype using some GUI toolkit. HC/GUIDesign [elective] Topics: • Choosing interaction styles (command line, menu, voice, gestural, WIMP) and interaction techniques • Choosing the right widget for users and tasks • HCI aspects of screen design: layout, color, fonts, labeling • Handling human/system failure. • Beyond simple screen design: visualization, representation, metaphor • Multi-modal interaction: graphics, sound, and haptics. • 3D interaction and virtual reality • Designing for small devices, e.g., cell phones. • Multi-cultural interaction and communication Learning Objectives: 7. Summarize common interaction styles. 8. Explain good design principles of each of the following: common widgets; sequenced screen presentations; simple error-trap dialog; a user manual. 9. Design, prototype, and evaluate a simple 2D GUI illustrating knowledge of the concepts taught in HC3 and HC4. 10. Identify the challenges that exist in moving from 2D to 3D interaction. 11. Identify the challenges that exist in moving from desktop or laptop screen to a mobile device. HC/GUIProgramming [elective] Topics: • UIMS, dialogue independence and levels of analysis, Seeheim model • Widget classes and libraries • Event management and user interaction • Web design vs. native application design • Geometry management • GUI builders and UI programming environments • Cross-platform design • Design for small, mobile devices Learning Objectives: 1. Differentiate between the responsibilities of the UIMS and the application. 2. Differentiate between kernel-based and client-server models for the UI. 3. Compare the event-driven paradigm with more traditional procedural control for the UI. 4. Describe aggregation of widgets and constraint-based geometry management. 5. Explain callbacks and their role in GUI builders. 6. Identify at least three differences common in cross-platform (e.g., desktop, Web, and cell phone) UI design. 7. Identify as many commonalities as you can that are found in UIs across different platforms. HC/MultimediaAndMultimodalSystems [elective] Topics: • Categorization and information architectures: hierarchies, grids, hypermedia , networks • Information retrieval and human performance • Web search • Usability of database query languages • Graphics • Sound • HCI design of multimedia information systems • Speech recognition and natural language processing • Information appliances and mobile computing • Interactive visualizations • Information design and navigation • Touch interfaces Learning Objectives: 1. Discuss how information retrieval differs from transaction processing. 2. Explain how the organization of information supports retrieval. 3. Describe the major usability problems with database query languages. 4. Explain the current state of speech recognition technology in particular and natural language processing in general. 5. Design, prototype, and evaluate a simple Multimedia Information System illustrating knowledge of the concepts taught in HC4, HC5, and HC7. HC/CollaborationAndCommunication [elective] Topics: • Groupware to support specialized tasks: document preparation, multi-player games • Asynchronous group communication: e-mail, bulletin boards, listservs, wikis, ... • Synchronous group communication: chat rooms, conferencing • Online communities: MUDs/MOOs, • Software characters and intelligent agents, virtual worlds and avatars • Social psychology • Social networking • Social Computing • Collaborative usability techniques. Learning Objectives: 1. Compare the HCI issues in individual interaction with group interaction. 2. Discuss several issues of social concern raised by collaborative software. 3. Discuss the HCI issues in software that embodies human intention. 4. Describe the difference between synchronous and asynchronous communication. 5. Design, prototype, and evaluate a simple groupware or group communication application illustrating knowledge of the concepts taught in HC4, HC5, and HC8. 6. Participate in a team project for which some interaction is face-to-face and other interaction occurs via a mediating software environment. 7. Describe the similarities and differences between face-to-face and software-mediated collaboration. HC/InteractionDesignForNewEnvironments [elective] Topics: • Interaction design for engaging interactive experiences • Presence, tele-presence and immersive environments • Affective interaction and emotion • Ambient intelligence • Physical computing and embodied interaction Learning Objectives: 1. Compare the methodological and philosophical issues involved with designing for usability and designing for engagement. 2. Discuss several issues of social and ethical concern raised by immersive environments and high levels of emotion in HCI. 3. Discuss the HCI issues involved in interactive software that embodies a level of intelligence. 4. Describe the difference between interaction design and traditional HCI. 5. Design, prototype, and evaluate an engaging interactive system for entertainment or education. 6. Evaluate the experiences or people in immersive environments. 7. Describe the issues involved with tangible user interfaces, gesture and full body interaction. 8. Describe the issues involved with engaging all the senses in interactive experiences. HC/HumanFactorsAndSecurity [elective] Topics: • Applied psychology and security policies • Usability design and security • Social engineering • Identity theft • Phishing Learning Objectives: 1. To explain the concept of phishing, and how to recognize it 2. To explain the concept of identity theft is and how to hinder it 3. To design a user interface for a security mechanism 4. To discuss procedures that counter a social engineering attack 5. To analyze a security policy and/or procedures to show where they meet, or fail to meet, usability considerations Graphics and Visual Computing (GV) The area encompassed by Graphics and Visual Computing (GV) is divided into four interrelated fields: • Computer graphics. Computer graphics is the art and science of communicating information using images that are generated and presented through computation. This requires (a) the design and construction of models that represent information in ways that support the creation and viewing of images, (b) the design of devices and techniques through which the person may interact with the model or the view, (c) the creation of techniques for rendering the model, and (d) the design of ways the images may be preserved The goal of computer graphics is to engage the person's visual centers alongside other cognitive centers in understanding. • Visualization. The field of visualization seeks to determine and present underlying correlated structures and relationships in both scientific (computational and medical sciences) and more abstract datasets. The prime objective of the presentation should be to communicate the information in a dataset so as to enhance understanding. Although current techniques of visualization exploit visual abilities of humans, other sensory modalities, including sound and haptics (touch), are also being considered to aid the discovery process of information. • Virtual reality. Virtual reality (VR) enables users to experience a three-dimensional environment generated using computer graphics, and perhaps other sensory modalities, to provide an environment for enhanced interaction between a human user and a computer-created world. • Computer vision. The goal of computer vision (CV) is to deduce the properties and structure of the three- dimensional world from one or more two-dimensional images. The understanding and practice of computer vision depends upon core concepts in computing, but also relates strongly to the disciplines of physics, mathematics, and psychology. GV. Graphic and Visual Computing (3 core hours) GV/FundamentalTechniques [core] GV/GraphicSystems [core] GV/GraphicCommunication [elective] GV/GeometricModeling [elective] GV/BasicRendering [elective] GV/AdvancedRendering [elective] GV/AdvancedTechniques [elective] GV/ComputerAnimation [elective] GV/Visualization [elective] GV/VirtualReality [elective] GV/ComputerVision [elective] GV/ComputationalGeometry [elective] GV/GameEngineProgramming [elective] GV/FundamentalTechniques [core] Minimum core coverage time: 2 hours Topics: • Hierarchy of graphics software • Using a graphics API • Simple color models (RGB, HSB, CMYK) • Homogeneous coordinates • Affine transformations (scaling, rotation, translation) • Viewing transformation • Clipping Learning Objectives: 1. Distinguish the capabilities of different levels of graphics software and describe the appropriateness of each. 2. Create images using a standard graphics API. 3. Use the facilities provided by a standard API to express basic transformations such as scaling, rotation, and translation. 4. Implement simple procedures that perform transformation and clipping operations on a simple 2-dimensional image. 5. Discuss the 3-dimensional coordinate system and the changes required to extend 2D transformation operations to handle transformations in 3D GV/GraphicSystems [core] Minimum core coverage time: 1 hour Topics: • Raster and vector graphics systems • Video display devices • Physical and logical input devices • Issues facing the developer of graphical systems Learning Objectives: 1. Describe the appropriateness of graphics architectures for given applications. 2. Explain the function of various input devices. 3. Compare and contrast the techniques of raster graphics and vector graphics. 4. Use current hardware and software for creating and displaying graphics. 5. Discuss the expanded capabilities of emerging hardware and software for creating and displaying graphics. GV/GeometricModeling [elective] Topics: • Polygonal representation of 3D objects • Parametric polynomial curves and surfaces • Constructive Solid Geometry (CSG) representation • Implicit representation of curves and surfaces • Spatial subdivision techniques • Procedural models • Deformable models • Subdivision surfaces • Multiresolution modeling • Reconstruction Learning Objectives: 1. Create simple polyhedral models by surface tessellation. 2. Construct CSG models from simple primitives, such as cubes and quadric surfaces. 3. Generate a mesh representation from an implicit surface. 4. Generate a fractal model or terrain using a procedural method. 5. Generate a mesh from data points acquired with a laser scanner. GV/BasicRendering [elective] Topics: • Line generation algorithms (Bresenham) • Font generation: outline vs. bitmap • Light-source and material properties • Ambient, diffuse, and specular reflections • Phong reflection model • Rendering of a polygonal surface; flat, Gouraud, and Phong shading • Texture mapping, bump texture, environment map • Introduction to ray tracing • Image synthesis, sampling techniques, and anti-aliasing Learning Objectives: 1. Explain the operation of the Bresenham algorithm for rendering a line on a pixel-based display. 2. Explain the concept and applications of each of these techniques. 3. Demonstrate each of these techniques by creating an image using a standard API. 4. Describe how a graphic image has been created. GV/AdvancedRendering [elective] Topics: • Transport equations • Ray tracing algorithms • Photon tracing • Radiosity for global illumination computation, form factors • Efficient approaches to global illumination • Monte Carlo methods for global illumination • Image-based rendering, panorama viewing, plenoptic function modeling • Rendering of complex natural phenomenon • Non-photorealistic rendering Learning Objectives: 1. Describe several transport equations in detail, noting all comprehensive effects. 2. Describe efficient algorithms to compute radiosity and explain the tradeoffs of accuracy and algorithmic performance. 3. Describe the impact of meshing schemes. 4. Explain image-based rendering techniques, light fields, and associated topics. GV/AdvancedTechniques [elective] Topics: • Color quantization • Scan conversion of 2D primitive, forward differencing • Tessellation of curved surfaces • Hidden surface removal methods • Z-buffer and frame buffer, color channels (a channel for opacity) • Advanced geometric modeling techniques Learning Objectives: 1. Describe the techniques identified in this section. 2. Explain how to recognize the graphics techniques used to create a particular image. 3. Implement any of the specified graphics techniques using a primitive graphics system at the individual pixel level. 4. Use common animation software to construct simple organic forms using metaball and skeleton. GV/ComputerAnimation [elective] Topics: • Key-frame animation • Camera animation • Scripting system • Animation of articulated structures: inverse kinematics • Motion capture • Procedural animation • Deformation Learning Objectives: 1. Explain the spline interpolation method for producing in-between positions and orientations. 2. Compare and contrast several technologies for motion capture. 3. Use the particle function in common animation software to generate a simple animation, such as fireworks. 4. Use free-form deformation techniques to create various deformations. GV/Visualization [elective] Topics: • Basic viewing and interrogation functions for visualization • Visualization of vector fields, tensors, and flow data • Visualization of scalar field or height field: isosurface by the marching cube method • Direct volume data rendering: ray-casting, transfer functions, segmentation, hardware • Information visualization: projection and parallel-coordinates methods Learning Objectives: 1. Describe the basic algorithms behind scalar and vector visualization. 2. Describe the tradeoffs of the algorithms in terms of accuracy and performance. 3. Employ suitable theory from signal processing and numerical analysis to explain the effects of visualization operations. 4. Describe the impact of presentation and user interaction on exploration. GV/VirtualReality [elective] Topics: • Stereoscopic display • Force feedback simulation, haptic devices • Viewer tracking • Collision detection • Visibility computation • Time-critical rendering, multiple levels of details (LOD) • Image-base VR system • Distributed VR, collaboration over computer network • Interactive modeling • User interface issues • Applications in medicine, simulation, and training Learning Objectives: 1. Describe the optical model realized by a computer graphics system to synthesize stereoscopic view. 2. Describe the principles of different viewer tracking technologies. 3. Explain the principles of efficient collision detection algorithms for convex polyhedra. 4. Describe the differences between geometry- and image-based virtual reality. 5. Describe the issues of user action synchronization and data consistency in a networked environment. 6. Determine the basic requirements on interface, hardware, and software configurations of a VR system for a specified application. GV/ComputerVision [elective] Topics: • Image acquisition • The digital image and its properties • Image preprocessing • Segmentation (thresholding, edge- and region-based segmentation) • Shape representation and object recognition • Motion analysis • Case studies (object recognition, object tracking) Learning Objectives: 1. Explain the image formation process. 2. Explain the advantages of two and more cameras, stereo vision. 3. Explain various segmentation approaches, along with their characteristics, differences, strengths, and weaknesses. 4. Describe object recognition based on contour- and region-based shape representations. 5. Explain differential motion analysis methods. 6. Describe the differences in object tracking methods. GV/ComputationalGeometry [elective] Topics: • Purpose and nature of computational geometry • Application areas – convex hull, line intersection issues, Delauney triangulation, polgygon triangulation, Voroni diagrams • Combinatorial computational geometry: static problems such as developing efficient algorithms for certain geometric situations; dynamic problems including • Numerical computational geometry: gmodeling, computer-aided geometric design; curve and surface modeling including representation of these: Bezier curves, spline curves and surfaces; level set method. Learning Objectives: 1. Be aware of algorithms for certaoin geometric tasks 2. Be able to select algorithms appropriate to particular situations GV/GameEngineProgramming [elective] Topics: • The nature of games engines (as an integrated development environment) and their purpose • Hardware support including use of threading; performance issues; input devices • Typical components including 3D rendering, and support for real-time graphics and interaction; also physics simulation, collision detaection, sound, artificial intelligence; terrain rendering Learning Objectives: 1. To be aware of the range of possibilities for games engines, including their potential and their limitations 2. To use a games engine to construct a simple game Intelligent Systems (IS) The field of artificial intelligence (AI) is concerned with the design and analysis of autonomous agents. These are software systems and/or physical machines, with sensors and actuators, embodied for example within a robot or an autonomous spacecraft. An intelligent system has to perceive its environment, to act rationally towards its assigned tasks, to interact with other agents and with human beings. These capabilities are covered by topics such as computer vision, planning and acting, robotics, multiagents systems, speech recognition, and natural language understanding. They rely on a broad set of general and specialized knowledge representations and reasoning mechanisms, on problem solving and search algorithms, and on machine learning techniques. Furthermore, artificial intelligence provides a set of tools for solving problems that are difficult or impractical to solve with other methods. These include heuristic search and planning algorithms, formalisms for knowledge representation and reasoning, machine learning techniques, and methods applicable to sensing and action problems such as speech and language understanding, computer vision, and robotics, among others. The student needs to be able to determine when an AI approach is appropriate for a given problem, and to be able to select and implement a suitable AI method. IS. Intelligent Systems (10 core hours) IS/FundamntalIssues [core] IS/BasicSearchStrategies [core] IS/KnowledgeBasedReasoning [core] IS/AdvancedSearch [elective] IS/AdvancedReasoning [elective] IS/Agents [elective] IS/NaturaLanguageProcessing [elective] IS/MachineLearning [elective] IS/PlanningSystems [elective] IS/Robotics [elective] IS/Perception [elective] IS/FundamentalIssues [core] Minimum core coverage time: 1 hour Topics: • History of artificial intelligence • Philosophical questions • The Turing test • Searle’s “Chinese Room” thought experiment • Ethical issues in AI • Fundamental definitions • Optimal vs. human-like reasoning • Optimal vs. human-like behavior • Philosophical questions • Modeling the world • The role of heuristics Learning Objectives: 1. Describe the Turing test and the “Chinese Room” thought experiment. 2. Differentiate the concepts of optimal reasoning and human-like reasoning. 3. Differentiate the concepts of optimal behavior and human-like behavior. 4. List examples of intelligent systems that depend on models of the world. 5. Describe the role of heuristics and the need for tradeoffs between optimality and efficiency. IS/BasicSearchStrategies [core] Minimum core coverage time: 5 hours Topics: • Problem spaces; problem solving by search • Brute-force search (breadth-first, depth-first, depth-first with iterative deepening) • Best-first search (generic best-first, Dijkstra’s algorithm, A*, admissibility of A*) • Two-player games (minimax search, alpha-beta pruning • Constraint satisfaction (backtracking and local search methods) Learning Objectives: 1. Formulate an efficient problem space for a problem expressed in English by expressing that problem space in terms of states, operators, an initial state, and a description of a goal state. 2. Describe the problem of combinatorial explosion and its consequences. 3. Select an appropriate brute-force search algorithm for a problem, implement it, and characterize its time and space complexities. 4. Select an appropriate heuristic search algorithm for a problem and implement it by designing the necessary heuristic evaluation function. 5. Describe under what conditions heuristic algorithms guarantee optimal solution. 6. Implement minimax search with alpha-beta pruning for some two-player game. 7. Formulate a problem specified in English as a constraint-satisfaction problem and implement it using a chronological backtracking algorithm. IS/KnowledgeBasedReasoning [core] Minimum core coverage time: 4 hours Topics: • Review of propositional and predicate logic • Resolution and theorem proving • Nonmonotonic inference; unification and lifting, forward chaining, backward chaining, resolution • Probabilistic reasoning • Bayes theorem Learning Objectives: 1. Explain the operation of the resolution technique for theorem proving. 2. Explain the distinction between monotonic and non-monotonic inference. 3. Discuss the advantages and shortcomings of probabilistic reasoning. 4. Apply Bayes theorem to determine conditional probabilities. IS/AdvancedSearch [elective] Topics: • Heuristics • Local search and optimization • Hill climbing • Genetic algorithms • Simulated annealing • Local beam search • Adversarial search for games Learning Objectives: 1. Explain what genetic algorithms are and constrastcontrast their effectiveness with the classic problem-solving and search techniques. 2. Explain how simulated annealing can be used to reduce search complexity and contrast its operation with classic search techniques. 3. Apply local search techniques to a classic domain. IS/AdvancedReasoning [elective] Topics: • Structured representation o Frames and objects o Description logics o Inheritance systems • Non-monotonic reasoning o Nonclassical logics o Default reasoning o Belief revision o Preference logics o Integration of knowledge sources o Aggregation of conflicting belief • Reasoning on action and change o Situation calculus o Event calculus o Ramification problems • Temporal and spatial reasoning • Uncertainty o Probabilistic reasoning o Bayesian nets o Decision theory • Knowledge representation for diagnosis, qualitative representation • Ontology engineering • Semantic networks Learning Objectives: 1. Compare and contrast the most common models used for structured knowledge representation, highlighting their strengths and weaknesses. 2. Characterize the components of nonmonotonic reasoning and its usefulness as a representational mechanisms for belief systems. 3. Apply situation and event calculus to problems of action and change. 4. Articulate the distinction between temporal and spatial reasoning, explaining how they interrelate. 5. Describe and contrast the basic techniques for representing uncertainty. 6. Describe and contrast the basic techniques for diagnosis and qualitative representation. IS/Agents [elective] Topics: • Definition of agents • Successful applications and state-of-the-art agent-based systems • Agent architectures o Simple reactive agents o Reactive planners o Layered architectures o Example architectures and applications • Agent theory o Commitments o Intentions o Decision-theoretic agents o Markov decision processes (MDP) • Software agents, personal assistants, and information access o Collaborative agents o Information-gathering agents • Believable agents (synthetic characters, modeling emotions in agents) o Learning agents o Multi-agent systems o Economically inspired multi-agent systems o Collaborating agents o Agent teams o Agent modeling o Multi-agent learning • Introduction to robotic agents • Mobile agents Learning Objectives: 1. Explain how an agent differs from other categories of intelligent systems. 2. Characterize and contrast the standard agent architectures. 3. Describe the applications of agent theory, to domains such as software agents, personal assistants, and believable agents. 4. Describe the distinction between agents that learn and those that don’t. 5. Demonstrate using appropriate examples how multi-agent systems support agent interaction. 6. Describe and contrast robotic and mobile agents. IS/NaturalLanguageProcessing [elective] Topics: • Deterministic and stochastic grammar • Parsing algorithms • Corpus-based methods • Information retrieval and information extraction • Language translation • Speech recognition Learning Objectives: 1. Define and contrast deterministic and stochastic grammars, providing examples to show the adequacy of each. 2. Identify the classic parsing algorithms for parsing natural language. 3. Defend the need for an established corpus. 4. Give examples of catalog and look up procedures in a corpus-based approach. 5. Articulate the distinction between techniques for information retrieval, language translation, and speech recognition. IS/MachineLearning [elective] Topics: • Definition and examples of machine learning • Inductive learning, statistical based learning, reinforcement learning • Supervised learning • Learning decision trees • Learning neural networks • Learning belief networks • The nearest neighbor algorithm • Learning theory • The problem of overfitting • Unsupervised learning • Reinforcement learning Learning Objectives: 1. Explain the differences among the three main styles of learning: supervised, reinforcement, and unsupervised. 2. Implement simple algorithms for supervised learning, reinforcement learning, and unsupervised learning. 3. Determine which of the three learning styles is appropriate to a particular problem domain. 4. Compare and contrast each of the following techniques, providing examples of when each strategy is superior: decision trees, neural networks, and belief networks.. 5. Implement a simple learning system using decision trees, neural networks and/or belief networks, as appropriate. 6. Characterize the state of the art in learning theory, including its achievements and its shortcomings. 7. Explain the nearest neighbor algorithm and its place within learning theory. 8. Explain the problem of overfitting, along with techniques for detecting and managing the problem. IS/PlanningSystems [elective] Topics: • Definition and examples of planning systems< • Planning as search • Operator-based planning • Planning graphs • Propositional planning • Extending planning systems (case-based, learning, and probabilistic systems) • Static world planning systems • Planning and execution including conditional planning and continuous planning • Mobile agent planning • Planning and robotics Learning Objectives: 1. Define the concept of a planning system. 2. Explain how planning systems differ from classical search techniques. 3. Articulate the differences between planning as search, operator-based planning, and propositional planning, providing examples of domains where each is most applicable. 4. Define and provide examples for each of the following techniques: case-based, learning, and probabilistic planning. 5. Compare and contrast static world planning systems with those need dynamic execution. 6. Explain the impact of dynamic planning on robotics. IS/Robotics [elective] Topics: • Overview • State-of-the-art robot systems • Planning vs. reactive control • Uncertainty in control • Sensing • World models • Configuration space< • Planning • Sensing • Robot programming • Navigation and control • Robotic software and its architecture Learning Objectives: 1. Outline the potential and limitations of today’s state-of-the-art robot systems. 2. Implement configuration space algorithms for a 2D robot and complex polygons. 3. Implement simple motion planning algorithms. 4. Explain the uncertainties associated with sensors and how to deal with those uncertainties. 5. Design a simple control architecture. 6. Describe various strategies for navigation in unknown environments, including the strengths and shortcomings of each. 7. Describe various strategies for navigation with the aid of landmarks, including the strengths and shortcomings of each. IS/Perception [elective] Topics: • Perception: role and applications • Image formation: light, colour, shades • Image and object detection: feature recognition, object recognition • Technologies • Software characteristics Learning Objectives: 1. Describe the importance of image and object recognition in Ai and indicate significant applications of this technology. 2. Outline the main approaches to object recognition 3. Describe the distinguishing characteristics of the technologies used for perception. Information Management Information Management (IM) plays a critical role in almost all areas where computers are used. This area includes the capture, digitization, representation, organization, transformation, and presentation of information; algorithms for efficient and effectiveaccess and updating of stored information, data modeling and abstraction, and physical file storage techniques. It also encompasses information security, privacy, integrity, and protection in a shared environment. The student needs to be able to develop conceptual and physical data models, determine what IM methods and techniques are appropriate for a given problem, and be able to select and implement an appropriate IM solution that reflects all suitable constraints, including scalability and usability. IM. Information Management (11 core hours) IM/InformationModels [core] IM/DatabaseSystems [core] IM/DataModeling [core] IM/Indexing [elective] IM/RelationalDatabases [elective] IM/QueryLanguages [elective] IM/RelationalDatabaseDesign [elective] IM/TransactionProcessing [elective] IM/DistributedDatabases [elective] IM/PhysicalDatabaseDesign [elective] IM/DataMining [elective] IM/InformationStorageAndRetrieval [elective] IM/Hypermedia [elective] IM/MultimediaSystems [elective] IM/DigitalLibraries [elective] IM/InformationModels [core] Minimum core coverage time: 4 hours Topics: • Information storage and retrieval (IS&R) • Information management applications • Information capture and representation • Metadata/schema association with data • Analysis and indexing • Search, retrieval, linking, navigation • Declarative and navigational queries • Information privacy, integrity, security, and preservation • Scalability, efficiency, and effectiveness • Concepts of Information Assurance (data persistence, integrity) Learning Objectives: 1. Compare and contrast information with data and knowledge. 2. Critique/defend a small- to medium-size information application with regard to its satisfying real user information needs. 3. Show uses of explicitly stored metadata/schema associated with data 4. Explain uses of declarative queries 5. Give a declarative version for a navigational query 6. Describe several technical solutions to the problems related to information privacy, integrity, security, and preservation. 7. Explain measures of efficiency (throughput, response time) and effectiveness (recall, precision). 8. Describe approaches to ensure that information systems can scale from the individual to the global. 9. Identify issues of data persistence to an organization. 10. Describe vulnerabilities to data integrity in specific scenarios. IM/DatabaseSystems [core] Minimum core coverage time: 3 hours Topics: • History and motivation for database systems • Components of database systems • DBMS functions • Database architecture and data independence • Use of a declarative query language Learning Objectives: 1. Explain the characteristics that distinguish the database approach from the traditional approach of programming with data files. 2. Cite the basic goals, functions, models, components, applications, and social impact of database systems. 3. Describe the components of a database system and give examples of their use. 4. Identify major DBMS functions and describe their role in a database system. 5. Explain the concept of data independence and its importance in a database system. 6. Use a declarative query language to elicit information from a database. IM/DataModeling [core] Minimum core coverage time: 4 hours Topics: • Data modeling • Conceptual models (such as entity-relationship or UML) • Object-oriented model • Relational data model • Semistructured data model (expressed using DTD or XMLSchema, for example) Learning Objectives: 1. Categorize data models based on the types of concepts that they provide to describe the database structure—that is, conceptual data model, physical data model, and representational data model. 2. Describe the modeling concepts and notation of the entity-relationship model and UML, including their use in data modeling. 3. Describe the main concepts of the OO model such as object identity, type constructors, encapsulation, inheritance, polymorphism, and versioning. 4. Define the fundamental terminology used in the relational data model . 5. Describe the basic principles of the relational data model. 6. Illustrate the modeling concepts and notation of the relational data model. 7. Describe the differences between relational and semistructured data models 8. Give a semistructured equivalent (eg in DTD or XMLSchema) for a given relational schema IM/Indexing [Elective] Topics: • The massive impact of indexes on query performance • The basic structure of an index; • Keeping a buffer of data in memory; • Creating indexes with SQL; • Indexing text; • Indexing the web (how search engines work) Learning objectives: 1. Generate an index file for a collection of resources. 2. Explain the role of an inverted index in locating a document in a collection 3. Explain how stemming and stop words affect indexing 4. Identify appropriate indices for given relational schema and query set 5. Estimate time to retrieve information, when indices are used compared to when they are not used. IM/RelationalDatabases [elective] Topics: • Mapping conceptual schema to a relational schema • Entity and referential integrity • Relational algebra and relational calculus Learning Objectives: 1. Prepare a relational schema from a conceptual model developed using the entity- relationship model 2. Explain and demonstrate the concepts of entity integrity constraint and referential integrity constraint (including definition of the concept of a foreign key). 3. Demonstrate use of the relational algebra operations from mathematical set theory (union, intersection, difference, and cartesian product) and the relational algebra operations developed specifically for relational databases (select (restrict), project, join, and division). 4. Demonstrate queries in the relational algebra.. 5. Demonstrate queries in the tuple relational calculus. IM/QueryLanguages [elective] Topics: • Overview of database languages • SQL (data definition, query formulation, update sublanguage, constraints, integrity) • QBE and 4th-generation environments • Embedding non-procedural queries in a procedural language • Introduction to Object Query Language • Stored procedures Learning Objectives: 1. Create a relational database schema in SQL that incorporates key, entity integrity, and referential integrity constraints. 2. Demonstrate data definition in SQL and retrieving information from a database using the SQL SELECT statement. 3. Evaluate a set of query processing strategies and select the optimal strategy. 4. Create a non-procedural query by filling in templates of relations to construct an example of the desired query result. 5. Embed object-oriented queries into a stand-alone language such as C++ or Java (e.g., SELECT Col.Method() FROM Object). 6. Write a stored procedure that deals with parameters and has some control flow, to provide a given functionality IM/RelationalDatabaseDesign[elective] Topics: • Database design • Functional dependency • Decomposition of a schema; lossless-join and dependency-preservation properties of a decomposition • Candidate keys, superkeys, and closure of a set of attributes • Normal forms (1NF, 2NF, 3NF, BCNF) • Multivalued dependency (4NF) • Join dependency (PJNF, 5NF) • Representation theory Learning Objectives: 1. Determine the functional dependency between two or more attributes that are a subset of a relation. 2. Connect constraints expressed as primary key and foreign key, with functional dependencies 3. Compute the closure of a set of attributes under given functional dependencies 4. Determine whether or not a set of attributes form a superkey and/or candidate key for a relation with given functional dependencies 5. Evaluate a proposed decomposition, to say whether or not it has lossless-join and dependency-preservation 6. Describe what is meant by 1NF, 2NF, 3NF, and BCNF. 7. Identify whether a relation is in 1NF, 2NF, 3NF, or BCNF. 8. Normalize a 1NF relation into a set of 3NF (or BCNF) relations and denormalize a relational schema. 9. Explain the impact of normalization on the efficiency of database operations, especially query optimization. 10. Describe what is a multivalued dependency and what type of constraints it specifies. 11. Explain why 4NF is useful in schema design. IM/TransactionProcessing [elective] Topics: • Transactions • Failure and recovery • Concurrency control Learning Objectives: 1. Create a transaction by embedding SQL into an application program. 2. Explain the concept of implicit commits. 3. Describe the issues specific to efficient transaction execution. 4. Explain when and why rollback is needed and how logging assures proper rollback. 5. Explain the effect of different isolation levels on the concurrency control mechanisms. 6. Choose the proper isolation level for implementing a specified transaction protocol. IM/DistributedDatabases [elective] Topics: • Distributed data storage • Distributed query processing • Distributed transaction model • Concurrency control • Homogeneous and heterogeneous solutions • Client-server Learning Objectives: 1. Explain the techniques used for data fragmentation, replication, and allocation during the distributed database design process. 2. Evaluate simple strategies for executing a distributed query to select the strategy that minimizes the amount of data transfer. 3. Explain how the two-phase commit protocol is used to deal with committing a transaction that accesses databases stored on multiple nodes. 4. Describe distributed concurrency control based on the distinguished copy techniques and the voting method. 5. Describe the three levels of software in the client-server model. IM/PhysicalDatabaseDesign [elective] Topics: • Storage and file structure • Indexed files • Hashed files • Signature files • B-trees • Files with dense index • Files with variable length records • Database efficiency and tuning Learning Objectives: 1. Explain the concepts of records, record types, and files, as well as the different techniques for placing file records on disk. 2. Give examples of the application of primary, secondary, and clustering indexes. 3. Distinguish between a nondense index and a dense index. 4. Implement dynamic multilevel indexes using B-trees. 5. Explain the theory and application of internal and external hashing techniques. 6. Use hashing to facilitate dynamic file expansion. 7. Describe the relationships among hashing, compression, and efficient database searches. 8. Evaluate costs and benefits of various hashing schemes. 9. Explain how physical database design affects database transaction efficiency. IM/DataMining [elective] Topics: • The usefulness of data mining • Associative and sequential patterns • Data clustering • Market basket analysis • Data cleaning • Data visualization Learning Objectives: 1. Compare and contrast different conceptions of data mining as evidenced in both research and application. 2. Explain the role of finding associations in commercial market basket data. 3. Characterize the kinds of patterns that can be discovered by association rule mining. 4. Describe how to extend a relational system to find patterns using association rules. 5. Evaluate methodological issues underlying the effective application of data mining. 6. Identify and characterize sources of noise, redundancy, and outliers in presented data. 7. Identify mechanisms (on-line aggregation, anytime behavior, interactive visualization) to close the loop in the data mining process. 8. Describe why the various close-the-loop processes improve the effectiveness of data mining. IM/InformationStorageAndRetrieval [elective] Topics: • Characters, strings, coding, text • Documents, electronic publishing, markup, and markup languages • Tries, inverted files, PAT trees, signature files, indexing • Morphological analysis, stemming, phrases, stop lists • Term frequency distributions, uncertainty, fuzziness, weighting • Vector space, probabilistic, logical, and advanced models • Information needs, relevance, evaluation, effectiveness • Thesauri, ontologies, classification and categorization, metadata • Bibliographic information, bibliometrics, citations • Routing and (community) filtering • Search and search strategy, information seeking behavior, user modeling, feedback • Information summarization and visualization • Integration of citation, keyword, classification scheme, and other terms • Protocols and systems (including Z39.50, OPACs, WWW engines, research systems) Learning Objectives: 1. Explain basic information storage and retrieval concepts. 2. Describe what issues are specific to efficient information retrieval. 3. Give applications of alternative search strategies and explain why the particular search strategy is appropriate for the application. 4. Perform Internet-based research. 5. Design and implement a small to medium size information storage and retrieval system. IM/Hypermedia [elective] Topics: • Hypertext models (early history, web, Dexter, Amsterdam, HyTime) • Link services, engines, and (distributed) hypertext architectures • Nodes, composites, and anchors • Dimensions, units, locations, spans • Browsing, navigation, views, zooming • Automatic link generation • Presentation, transformations, synchronization • Authoring, reading, and annotation • Protocols and systems (including web, HTTP) Learning Objectives: 1. Summarize the evolution of hypertext and hypermedia models from early versions up through current offerings, distinguishing their respective capabilities and limitations. 2. Explain basic hypertext and hypermedia concepts. 3. Demonstrate a fundamental understanding of information presentation, transformation, and synchronization. 4. Compare and contrast hypermedia delivery based on protocols and systems used. 5. Design and implement web-enabled information retrieval applications using appropriate authoring tools. IM/MultimediaSystems [elective] Topics: • Devices, device drivers, control signals and protocols, DSPs • Applications, media editors, authoring systems, and authoring • Streams/structures, capture/represent/transform, spaces/domains, compression/coding • Content-based analysis, indexing, and retrieval of audio, images, and video • Presentation, rendering, synchronization, multi-modal integration/interfaces • Real-time delivery, quality of service, audio/video conferencing, video-on-demand Learning Objectives: 1. Describe the media and supporting devices commonly associated with multimedia information and systems. 2. Explain basic multimedia presentation concepts. 3. Demonstrate the use of content-based information analysis in a multimedia information system. 4. Critique multimedia presentations in terms of their appropriate use of audio, video, graphics, color, and other information presentation concepts. 5. Implement a multimedia application using a commercial authoring system. IM/DigitalLibraries [elective] Topics: • Digitization, storage, and interchange • Digital objects, composites, and packages • Metadata, cataloging, author submission • Naming, repositories, archives • Spaces (conceptual, geographical, 2/3D, VR) • Architectures (agents, buses, wrappers/mediators), interoperability • Services (searching, linking, browsing, and so forth) • Intellectual property rights management, privacy, protection (watermarking) • Archiving and preservation, integrity Learning Objectives: 1. Explain the underlying technical concepts in building a digital library. 2. Describe the basic service requirements for searching, linking, and browsing. 3. Critique scenarios involving appropriate and inappropriate use of a digital library, and determine the social, legal, and economic consequences for each scenario. 4. Describe some of the technical solutions to the problems related to archiving and preserving information in a digital library. 5. Design and implement a small digital library. Social and Professional Issues (SP) Although technical issues are obviously central to any computing curriculum, they do not by themselves constitute a complete educational program in the field. Students must also develop an understanding of the social and professional context in which computing is done. This need to incorporate the study of social issues into the curriculum was recognized in the following excerpt from Computing Curricula 1991 [Tucker91]: 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 long-term commitment to remaining current in their chosen specialties and in the discipline of computing as a whole. The material in this knowledge 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—in particular, SP2, SP3, SP4, and SP6—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 considerations are covered only in the standalone course and not “in context,” it will reinforce the false notion that technical processes are void of ethical issues. Thus it is important that several traditional courses include modules that analyze ethical considerations in the context of the technical subject matter of the course. Courses in areas such as software engineering, databases, computer networks, 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 computer 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. There is an unresolved pedagogical conflict between having the core course at the lower (freshman-sophomore) level versus the upper (junior-senior) level. Having the course at the lower level 1. Allows for coverage of methods and tools of analysis (SP3) prior to analyzing ethical issues in the context of different technical areas 2. Assures that students who drop out early to enter the workforce will still be introduced to some professional and ethical issues. On the other hand, placing the course too early may lead to the following problems: 1. Lower-level students may not have the technical knowledge and intellectual maturity to support in-depth ethical analysis. Without basic understanding of technical alternatives, it is difficult to consider their ethical implications. 2. Students need a certain level of maturity and sophistication to appreciate the background and issues involved. For that reason, students should have completed at least the discrete mathematics course and the second computer science course. Also, if students take a technical writing course, it should be a prerequisite or corequisite for the required course in the SP area. 3. Some programs may wish to use the course as a “capstone” experience for seniors. Although items SP2 and SP3 are listed with a number of hours associated, they are fundamental to all the other topics. Thus, when covering the other areas, instructors should continually be aware of the social context issues and the ethical analysis skills. In practice, this means that the topics in SP2 and SP3 will be continually reinforced as the material in the other areas is covered. SP. Social and Professional issues (16 hours) SP/HistoryOfComputing [core] SP/SocialContext [core] SP/AnalyticalTools [core] SP/ProfessionalEthics [core] SP/Risks [core] SP/SecurityOperations [elective] SP/IntellectualProperty [core] SP/PrivacyAndCivilLiberties [core] SP/ComputerCrime [elective] SP/EconomicsOfComputing [elective] SP/PhilosophicalFrameworks [elective] SP/HistoryOfComputing [core] Minimum core coverage time: 1 hour Topics: • Prehistory—the world before 1946 • History of computer hardware, software, networking • Pioneers of computing Learning Objectives: 1. List the contributions of several pioneers in the computing field. 2. Compare daily life before and after the advent of personal computers and the Internet. 3. Identify significant continuing trends in the history of the computing field. SP/SocialContext [core] Minimum core coverage time: 3 hours Topics: • Introduction to the social implications of computing • Social implications of networked communication • Growth of, control of, and access to the Internet • Gender-related issues • Cultural issues • International issues • Accessibility issues (e.g. underrepresentation of minorities, women and the disabled in the computing profession) • Public policy issues (e.g. electronic voting) Learning Objectives: 1. Interpret the social context of a particular implementation. 2. Identify assumptions and values embedded in a particular design including those of a cultural nature. 3. Evaluate a particular implementation through the use of empirical data. 4. Describe positive and negative ways in which computing alters the modes of interaction between people. 5. Explain why computing/network access is restricted in some countries. 6. Indicate the role of cultural issues in considering team-work. 7. Analyze the role and risks of computing in the implementation of public policy and government (e.g. electronic voting). 8. Articulate the impact of the input deficit from diverse populations in the computing profession. SP/AnalyticalTools [core] Minimum core coverage time: 2 hours Topics: • Making and evaluating ethical arguments • Identifying and evaluating ethical choices • Understanding the social context of design • Identifying assumptions and values Learning Objectives: 1. Analyze an argument to identify premises and conclusion. 2. Illustrate the use of example, analogy, and counter-analogy in ethical argument. 3. Detect use of basic logical fallacies in an argument. 4. Identify stakeholders in an issue and our obligations to them. 5. Articulate the ethical tradeoffs in a technical decision. SP/ProfessionalEthics [core] Minimum core coverage time: 3 hours Topics: • Community values and the laws by which we live • The nature of professionalism (including care, attention and discipline, fiduciary responsibility, and mentoring) • Keeping up-to-date as a professional (in terms of knowledge, tools, skills, legal and professional framework as well as the ability to self-assess and computer fluency) • Various forms of professional credentialing and the advantages and disadvantages • The role of the professional in public policy • Maintaining awareness of consequences • Ethical dissent and whistle-blowing • Codes of ethics, conduct, and practice (IEEE, ACM, SE, AITP, and so forth) • Dealing with harassment and discrimination • “Acceptable use” policies for computing in the workplace • Healthy computing environment (ergonomics) Learning Objectives: 1. Identify progressive stages in a whistle-blowing incident. 2. Specify the strengths and weaknesses of relevant professional codes as expressions of professionalism and guides to decision-making. 3. Identify ethical issues that arise in software development and determine how to address them technically and ethically. 4. Develop a computer use policy with enforcement measures. 5. Analyze a global computing issue, observing the role of professionals and government officials in managing the problem. 6. Evaluate the professional codes of ethics from the ACM, the IEEE Computer Society, and other organizations. 7. Describe the mechanisms that typically exist for a professional to keep up-to-date. 8. Identify the social implications of ergonomic devices and the workplace environment to people’s health. SP/Risks [core] Minimum core coverage time: 2 hours Topics: • Historical examples of software risks (such as the Therac-25 case) Implications of software complexity • Risk assessment and risk management; risk removal, risk reduction and risk control Learning Objectives: 1. Explain the limitations of testing as a means to ensure correctness. 2. Describe the differences between correctness, reliability, and safety. 3. Discuss the potential for hidden problems in reuse of existing components. 4. Describe current approaches to managing risk, and characterize the strengths and shortcomings of each. 5. Outline the role of risk management in systems design and construction. SP/SecurityOperations [elective] Topics: • Physical security • Physical access controls • Personnel access controls • Operational security • Security policies for systems/networks • Recovery and response • Dealing with problems (both technical and human) Learning Objectives: 1. Develop an incident-recovery plan for handling system compromises for an organization 2. Analyze stated security procedures for "weak points" that an attacker could exploit, and explain how they could (or will) fail 3. Propose appropriate security measures for different situations 4. Explain to a non-security community of users what measures they must follow and why, in a situation where their jobs are not security-related SP/IntellectualProperty [core] Minimum core coverage time: 3 hours Topics: • Foundations of intellectual property • Copyrights, patents, and trade secrets • Software piracy • Software patents • Transnational issues concerning intellectual property Learning Objectives: 1. Distinguish among patent, copyright, and trade secret protection. 2. Discuss the legal background of copyright in national and international law. 3. Explain how patent and copyright laws may vary internationally. 4. Outline the historical development of software patents. 5. Discuss the consequences of software piracy on software developers and the role of relevant enforcement organizations. SP/PrivacyAndCivilLiberties [core] Minimum core coverage time: 2 hours Topics: • Ethical and legal basis for privacy protection • Ethical and legal framework for freedom of information • Privacy implications of database systems (e.g. data gathering, storage, and sharing, massive data collecting, computer surveillance systems) • Technological strategies for privacy protection • Freedom of expression in cyberspace • International and intercultural implications Learning Objectives: 1. Summarize the legal bases for the right to privacy and freedom of expression in one’s own nation and how those concepts vary from country to country. 2. Describe current computer-based threats to privacy. 3. Explain how the Internet may change the historical balance in protecting freedom of expression. 4. Describe trends in privacy protection as exemplified in technology. 5. Clarify the apparent conflict between the requirements of freedom of information and the protection of the rights of the individual. SP/ComputerCrime [elective] Topics: • History and examples of computer crime • “Cracking” (“hacking”) and its effects • Viruses, worms, and Trojan horses • Identity theft • Crime prevention strategies Learning Objectives: 1. Describe trends in privacy protection as exemplified in technologyOutline the technical basis of viruses and denial-of-service attacks. 2. Enumerate techniques to combat “cracker” attacks. 3. Discuss several different “cracker” approaches and motivations. 4. Identify the professional’s role in security and the tradeoffs involved. 5. Indicate measure to be taken both by individuals themselves and by organizations (including government) to prevent identity theft. SP/EconomicsOfComputing [elective] Topics: • Monopolies and their economic implications • Effect of skilled labor supply and demand on the quality of computing products • Pricing strategies in the computing domain • The phenomenon of outsourcing and offshoring; impacts on employment and on economics • Differences in access to computing resources and the possible effects thereof • Environmental sustainability Learning Objectives: 1. Summarize the rationale for antimonopoly efforts. 2. Describe several ways in which the information technology industry is affected by shortages in the labor supply. 3. Suggest and defend ways to address limitations on access to computing. 4. Outline the evolution of pricing strategies for computing goods and services. 5. Discuss the benefits, the drawbacks and the implications of offshoring and outsourcing. 6. Identify ways to support environmental computing (e.g. green operations, recyclable products, reduced green house emissions). SP/PhilosophicalFrameworks [elective] Topics: • Philosophical frameworks, particularly utilitarianism and deontological theories • Problems of ethical relativism • Scientific ethics in historical perspective • Differences in scientific and philosophical approaches Learning Objectives: 1. Summarize the basic concepts of relativism, utilitarianism, and deontological theories. 2. Recognize the distinction between ethical theory and professional ethics. 3. Identify the weaknesses of the “hired agent” approach, strict legalism, naοve egoism, and naοve relativism as ethical frameworks. Software Engineering (SE) Software engineering is the discipline concerned with the application of theory, knowledge, and practice for effectively and efficiently building software systems that satisfy the requirements of users and customers. Software engineering is applicable to small, medium, and large-scale systems. It encompasses all phases of the life cycle of a software system. The life cycle includes requirements analysis and specification, design, construction, testing, deployment, and operation and maintenance. Software engineering employs engineering methods, processes, techniques, and measurement. It benefits from the use of tools for managing software development; analyzing and modeling software artifacts; assessing and controlling quality; and for ensuring a disciplined, controlled approach to software evolution and reuse. Software development, which can involve an individual developer or a team of developers, requires choosing the tools, methods, and approaches that are most applicable for a given development environment. The SE toolbox has evolved over the years; for instance, the use of contracts (such as a ‘requires’ clause, an ‘ensures’ clause, class invariants, etc.) is now regarded as good practice. The elements of software engineering are applicable to the development of software in any computing application domain where professionalism, quality, schedule, and cost are important in producing a software system. (Software Engineering (31 core hours) SE/SoftwareDesign [core] SE/UsingAPIs [core] SE/ToolsAndEnvironments [core] SE/SoftwareProcesses [core] SE/RequirementsSpecifications [core] SE/SoftwareVerificationValidation [core] SE/SoftwareEvolution [core] SE/SoftwareProjectManagement [core] SE/ComponentBasedComputing [elective] SE/FormalMethods [elective] SE/SoftwareReliability [elective] SE/SpecializedSystems [elective] SE/RiskAssessment [elective] SE/RobustAndSecurity-EnhancedProgramming [elective] SE/SoftwareDesign [core] Minimum core coverage time: 8 hours Topics: • Fundamental design concepts and principles • The role and the use of contracts • Design patterns • Software architecture • Structured design • Object-oriented analysis and design • Component-level design • Design qualities • Internal including low coupling, high cohesion, information hiding, efficiency • External including reliability, maintainability, usability, performance • Other approaches: data-structured centered, aspect oriented, function oriented, service oriented, agile • Design for reuse • Use of open-source materials Learning Objectives: 1. Discuss the properties of good software design including the nature and the role of associated documentation. 2. Evaluate the quality of multiple software designs based on key design principles and concepts. 3. Select and apply appropriate design patterns in the construction of a software application. 4. Create and specify the software design for a medium-size software product using a software requirement specification, an accepted program design methodology (e.g., structured or object-oriented), and appropriate design notation. 5. Conduct a software design review of open-source materials using appropriate guidelines. 6. Evaluate a software design at the component level. 7. Evaluate a software design from the perspective of reuse. SE/UsingAPIs [core] Minimum core coverage time: 5 hours Topics: • Programming using APIs • Design of APIs • Class browsers and related tools • Debugging in the API environment Introduction to component-based computing • Introduction to Component-based Computing Note: see also SE/RequirementsSpecifications and SE/ComponentBasedComputing Learning Objectives: 1. Explain the value of application programming interfaces (APIs) in software development. 2. Use class browsers and related tools during the development of applications using APIs. 3. Design, implement, test, and debug programs that use large-scale API packages. SE/ToolsAndEnvironments [core] Minimum core coverage time: 3 hours Topics: • Programming environments • Requirements analysis and design modeling tools • Testing tools including static and dynamic analysis tools • Tools for source control, and their use in particular in team-work • Configuration management and version control tools • Tool integration mechanisms Learning Objectives: 1. Select, with justification, an appropriate set of tools to support the development of a range of software products. 2. Analyze and evaluate a set of tools in a given area of software development (e.g., management, modeling, or testing). 3. Demonstrate the capability to use a range of software tools in support of the development of a software product of medium size. SE/SoftwareProcesses [core] Minimum core coverage time: 2 hours Topics: • Software life-cycle and process models • Software process capability maturity models • Approaches to process improvement • Process assessment models • Software process measurements Learning Objectives: 1. Explain the concept of a software life cycle and provide an example, illustrating its phases including the deliverables that are produced. 2. Select, with justification the software development models and process elements most appropriate for the development and maintenance of a diverse range of software products. 3. Explain the role of process maturity models. 4. Compare the traditional waterfall model to the incremental model, the agile model, and other appropriate models. 5. For each of various software project scenarios, describe the project’s place in the software life cycle, identify the particular tasks that should be performed next, and identify measurements appropriate to those tasks. SE/RequirementsSpecifications [core] Minimum core coverage time: 4 hours Topics: • Systems level considerations • Software requirements elicitation • Requirements analysis modeling techniques • Functional and non-functional requirements • Acceptability of certainty / uncertainty considerations regarding software / system behaviour • Prototyping • Basic concepts of formal specification techniques Learning Objectives: 1. Apply key elements and common methods for elicitation and analysis to produce a set of software requirements for a medium-sized software system. 2. Discuss the challenges of maintaining legacy software. 3. Use a common, non-formal method to model and specify (in the form of a requirements specification document) the requirements for a medium-size software system. 4. Conduct a review of a software requirements document using best practices to determine the quality of the document. 5. Translate into natural language a software requirements specification (e.g., a software component contract) written in a formal specification language. SE/SoftwareVerificationValidation [core] Minimum core coverage time: 3 hours Topics: • Distinguishing between verification and validation • Static approaches and dynamic approaches • Validation planning; documentation for validation • Different kinds of testing – human computer interface, usability, reliability, security, conforman to specification • Testing fundamentals, including test plan creation and test case generation black-box and white-box testing techniques • Defect seeding • Unit, integration, validation, and system testing • Object-oriented testing; systems testing • Measurements: process, design, program • Verification and validation of non-code (documentation, help files, training materials) • Fault logging, fault tracking and technical support for such activities • Regression testing • Inspections, reviews, audits Learning Objectives: 1. Distinguish between program validation and verification. 2. Describe the role that tools can play in the validation of software. 3. Distinguish between the different types and levels of testing (unit, integration, systems, and acceptance) for medium-size software products and related materials. 4. Create, evaluate, and implement a test plan for a medium-size code segment. 5. Undertake, as part of a team activity, an inspection of a medium-size code segment. 6. Discuss the issues involving the testing of object-oriented software. SE/SoftwareEvolution [core] Minimum core coverage time: 3 hours Topics: • Software maintenance • Characteristics of maintainable software • Reengineering Legacy systems • Refactoring • Software reuse Learning Objectives: 1. Identify the principal issues associated with software evolution and explain their impact on the software life cycle. 2. Discuss the challenges of maintaining legacy systems and the need for reverse engineering. 3. Outline the process of regression testing and its role in release management. 4. Estimate the impact of a change request to an existing product of medium size. 5. Develop a plan for re-engineering a medium-sized product in response to a change request. 6. Discuss the advantages and disadvantages of software reuse. 7. Exploit opportunities for software reuse in a given context. 8. Identify weaknesses in a given simple design, and highlight how they can be removed through refactoring. SE/SoftwareProjectManagement [core] Minimum core coverage time: 3 hours Topics: • Team management o Team processes o Team organization and decision-making o Roles and responsibilities in a software team o Role identification and assignment o Project tracking o Team problem resolution • Project scheduling • Software measurement and estimation techniques • Risk analysis o The issue of security o High integrity systems, safety critical systems o The role of risk in the life cycle • Software quality assurance o The role of measurements • Software configuration management and version control; release management • Project management tools • Software process models and process measurements Learning Objectives: 1. Demonstrate through involvement in a team project the central elements of team building and team management. 2. Prepare a project plan for a software project that includes estimates of size and effort, a schedule, resource allocation, configuration control, change management, and project risk identification and management. 3. Indicate an approach to risk that will help to secure the on-time delivery of software. 4. Compare and contrast the different methods and techniques used to assure the quality of a software product. SE/ComponentBasedComputing [elective] Topics: • Fundamentals o The definition and nature of components o Components and interfaces o Interfaces as contracts o The benefits of components o Basic techniques o Component design and assembly o Relationship with the client-server model and with patterns o Use of objects and object lifecycle services o Use of object brokers o Marshalling • Applications (including the use of mobile components) • Patterns as used in analysis and design; context of use including enterprise architectures • Architecture of component-based systems • Component-oriented design • Application frameworks • Event handling: detection, notification, and response • Middleware o The object-oriented paradigm within middleware o Object request brokers o Transaction processing monitors o Workflow systems o State-of-the-art tools Learning Objectives: 1. Explain and apply recognized principles to the building of high-quality software components. 2. Discuss and select an architecture for a component-based system suitable for a given scenario. 3. Identify the kind of event handling implemented in one or more given APIs. 4. Explain the role of objects in middleware systems and the relationship with components. 5. Apply component-oriented approaches to the design of a range of software including those required for concurrency and transactions, reliable communication services, database interaction including services for remote query and database management, secure communication and access. SE/FormalMethods [elective] Topics: • Formal methods concepts • Formal specification languages • Model checking • Executable and non-executable specifications • Pre and post assertions • Formal verification • Tools in support of formal methods Learning Objectives: 1. Apply formal verification techniques to software segments with low complexity. 2. Discuss the role of formal verification techniques in the context of software validation and testing, and compare the benefits with those of model checking. 3. Explain the potential benefits and drawbacks of using formal specification languages. 4. Create and evaluate pre- and post-assertions for a variety of situations ranging from simple through complex. 5. Using a common formal specification language, formulate the specification of a simple software system and demonstrate the benefits from a quality perspective. SE/SoftwareReliability [elective] Topics: • Software reliability models • Redundancy and fault tolerance • Defect classification • Probabilistic methods of analysis Learning Objectives: 1. Demonstrate the ability to apply multiple methods to develop reliability estimates for a software system. 2. Identify and apply redundancy and fault tolerance for a medium-sized application. 3. Explain the problems that exist in achieving very high levels of reliability. 4. Identify methods that will lead to the realization of a software architecture that achieves a specified reliability level. SE/SpecializedSystems [elective] Topics: • Real-time systems • Client-server systems • Distributed systems • Parallel systems • Web-based systems • High-integrity systems Learning Objectives: 1. Identify and discuss different specialized systems. 2. Discuss life cycle and software process issues in the context of software systems designed for a specialized context, including systems that may have to operate in a degraded mode of operation. 3. Select, with appropriate justification, approaches that will result in the efficient and effective development and maintenance of specialized software systems. 4. Given a specific context and a set of related professional issues, discuss how a software engineer involved in the development of specialized systems should respond to those issues. 5. Outline the central technical issues associated with the implementation of specialized systems development. SE/RiskAssessment [Elective] Topics: • Definition of terms: in security, vulnerability, threat, security breach; in safety, hazard. • The concept of risk; hazard and risk identification • Risk analysis including evaluation • Need for a system-wide approach including hazards associated with tools • Risk and immature technologies • Cost/benefit analysis • Principles of risk management Learning Objectives: 1. To define the concepts of hazard and risk, hazard 2. To recognize common security risks in at least two operating systems 3. To describe the categories of threats to networked computing systems 4. To display a systematic approach to the task of identifying hazards and risks in a particular situation 5. To apply the basic principles of risk management in a variety of simple scenarios including a security situation SE/RobustAndSecurity­EnhancedProgramming [elective] Topics: • Defensive programming o Principles of secure design and coding: o Principle of least privilege o Principle of fail-safe defaults • Principle of psychological acceptability o How to detect potential security problems in programs o Buffer and other types of overflows o Race conditions o Improper initialization, including choice of privileges o Checking input o Assuming success and correctness o Validating assumptions • How to document security considerations in using a program Learning Objectives: 1. Rewrite a simple program to remove common vulnerabilities, such as buffer overflows, integer overflows, and race conditions 2. State and apply the principles of least privilege and fail-safe defaults. 3. Write a simple library that performs some non-trivial task and will not terminate the calling program regardless of how it is called Computational Science (CN) From the earliest days of the discipline, the techniques of computational science have constituted a major area of computer science research. As computers increase in their problem-solving power, this area—like much of the discipline—has grown in both breadth and importance. At the present time, scientific computational science stands as an intellectual discipline in its own right, closely related to but nonetheless distinct from computer science. Although courses in computational science are extremely valuable components of an undergraduate program in computer science, the CS2001 Task Forces believe that none of the topics in this area represent core knowledge. From our surveys of curricula and interaction with the computer science education community, we are convinced no consensus exists that this material is essential for all CS undergraduates. It remains a vital part of the discipline, but need not be a part of every program. For those who choose to pursue it, this area offers exposure to many valuable ideas and techniques, including precision of numerical representation, error analysis, numerical techniques, parallel architectures and algorithms, modeling and simulation, and scientific visualization. At the same time, students who take courses in this area have an opportunity to apply these techniques in a wide range of application areas, such as the following: • Molecular dynamics • Fluid dynamics • Celestial mechanics • Economic forecasting • Optimization problems • Structural analysis of materials • Bioinformatics • Computational biology • Geologic modeling • Computerized tomography Each of the units in this area corresponds to a full-semester course at most institutions. The level of specification of the topic descriptions and the Learning Objectives is therefore different from that used in other areas in which the individual units typically require smaller blocks of time. CN. Computational Science (no core hours) CN/ModeligAndSimulation [elective] CN/OperationsResearch [elective] CN/ParallelComputation [elective] CN/ModelingAndSimulation [elective] Topics: • Definition of simulation and modeling; relationship between simulation and modeling • Purpose including benefits and limitations: role – addressing performance, optimization; supporting decision making, forecasting, safety considerations; for training and education • Important application areas: healthcare (including assisting with diagnostics); economics and finance; classroom of the future; training and education; city and urban simulations; simulation in science and in engineering; games; military simulation • Different kinds of simulations – physical, human in the loop, interaction, computer, virtual reality • The simulation process – sound basis, identification of key characteristics or behaviors, simplifying assumptions; validation of outcomes. Model building: use of mathematical formula or equation, graphs, constraints. Methodologies and techniques. Use of time stepping for dynamic systems • Theoretical considerations; Monte Carlo methods, stochastic processes, queuing theory • Technologies in support of simulation and modeling: graphics processors; Haptic feedback devices. Human computer interaction considerations. • Assessing and evaluating simulations in a variety of contexts. • Software in support of simulation and modeling; packages, languages Learning Objectives: 1. Explain the benefits of simulation and modeling in a range of important application areas. 2. Demonstrate the ability to apply the techniques of modeling and simulation to a range of problem areas. 3. Evaluate a simulation, highlighting the benefits and the drawbacks. CN/OperationsResearch [elective] Topics: • Linear programming o Integer programming o The Simplex method • Probabilistic modeling • Queuing theory o Petri nets o Markov models and chains • Optimization • Network analysis and routing algorithms • Prediction and estimation o Decision analysis o Forecasting o Risk management o Econometrics, microeconomics o Sensitivity analysis • Dynamic programming • Sample applications • Software tools Learning Objectives: 1. Apply the fundamental techniques of operations research. 2. Describe several established techniques for prediction and estimation. 3. Design, code, test, and debug application programs to solve problems in the domain of operations research. CN/ParallelComputation [elective] Topics: • Overview of topics • Models of computation • Kinds of computation • Task parallelism • Data parallelism • Event parallelism • Properties of computation • Bandwidth • Latency • Scalability • Granularity • Parallel architectures • Processor architectures including multi-core • Memory systems for high performance • Caching and coherence • Clusters • Parallel programming paradigms • Threading • Message passing • Event driven techniques • Parallel software architectures o MapReduce • Grid computing • Open community distributed computing (BOINC, SETI, …) Learning Objectives: 1. Compare and contrast architectures for parallel computing, recognizing the strengths and weaknesses of each 2. Compare and contrast parallel programming paradigms recognizing the strengths and weaknesses of each 3. Identify the basic properties of bandwidth, latency, scalability and granularity 4. Design, code, test and debug programs for parallel computation Appendix C ­ Course Guidance By way of guidance, the Review Task Force is providing guidance in two different areas: • An introduction to security • An introduction to computer security In some sense these are intended to reflect areas of concern in the curriculum and changes in emphasis since 2001. C.1 Introduction to Security This course is a survey of the fundamentals of information assurance and computer security. Topics include: security standards, policies and best practices; principles of ethical and professional behavior; regulatory compliance and legal investigations; information assurance; risk management and threat assessment; business continuity and disaster recovery planning; security architecture and design; elements of cryptography; digital forensics; physical (environmental) security; networking fundamentals; access control and authentication; network and application security; exploiting network, web, software and insider vulnerabilities. CS3xx Introduction to Computer Security Prerequisite: a course that provides an introduction to programming building on a broad introduction to computer science; in the context of CS2001 such a course would be CS 102 Co-requisite: a programming course that provides an introduction to data structures and algorithms; in the context of CS2001 such a course would be CS 103 Syllabus: • Security Goals, Fundamentals (confidentiality, integrity, availability, etc.) • Introduction to risk assessment and management • Security standards in government and industry (Common Criteria/Orange Book, sample corporate and institutional security policies) • Computer system protection principles (UNIX and Windows) • Access controls, including MAC, DAC, and role-based • Networking fundamentals (Internet, TCP/IP network services) • Cryptography fundamentals • Authentication, passwords, introduction to protocols, Kerberos • Security operations • Attacks: software attacks, malicious code, buffer overflows, social engineering, injection attacks, and related defense tools • Network attacks: Denial of service, flooding, sniffing and traffic redirection, defense tools and strategies • Attacking web sites: cross-site scripting • IPSec, Virtual Private networks and Network Address Translation • Ethics, SP issues that are related • Drop on Forensics C.2 Course on Parallelism The class is a suitable prerequisite to a capstone project class focusing on creating a complex parallel system. It cuts across several advance courses of CS2001, repackaging the material to eliminate more specialized information and emphasizing content that is most applicable to current students: CS314 Parallel Algorithms, Parallel Architectures, CS326 Concurrent and Distributed Systems, CS333 Cluster Computing, CS343 Programming Paradigms, CS344 Functional Programming, CS372 Transaction Processing, CS390 Advanced Software Development. CS3xx Parallel Computation A survey of parallel computation across hardware, software, programming languages, algorithms and applications areas. The emphasis is on learning enough context in each topic area to support effective parallel programming. Prerequisites: CS112A Programming Methodology, CS210 Algorithm Design and Analysis, CS221 Architecture and Operating Systems Syllabus: • Context for present day parallel computing, including everyday parallelism, parallelism in processor architecture, parallel computer structures from multicore to huge clusters, etc. • Basic concepts: models of parallel computers, differences (and similarities) between parallel and distributed computation, data and task parallelism, threads and processes, latency and bandwidth, locality, concurrent and exclusive reads and writes, dependences, MIMD/SIMD, Amdahl’s Law, performance measurements, true speed-up, relative speed-up, efficiency, super-linear speed-up • Shared memory parallel machine architecture concepts, multi-threading, multi-core, SMP, snooping and directory-based coherency protocols, sequential consistency, private and shared memory • Distributed memory parallel machine architecture concepts, disjoint address spaces, globalization of address spaces, message passing, synchronous and asynchronous communication • Interconnection networks, common topologies, bisection bandwidth, bus and cross-bar connectivity • Basics of threaded parallel computation, including problem partitioning, hazards of concurrency, locking, lock contention, thrashing, privatization, false sharing, serialization • Algorithmic issues including problem decomposition, memory reference costs, techniques for improving locality, parallel prefix, controlling granularity and dependences, block and cyclic storage organization, tree decompositions, static and dynamic task assignment • Languages and libraries for threaded parallel programming, POSIX threads, Java threads and memory model, automatic threading systems (OpenMP) • Languages and libraries for distributed memory parallel programming, PVM and MPI, partitioned global address space languages (PGAS) • Higher-level approaches including array-based, functional, domain-specific • Transaction approach to memory consistency, hardware techniques, software techniques, rollback • Emerging languages including high-productivity parallel languages • Co-processor techniques including GPU, Cell, FPGA, characteristics of co-processor programming methodologies • Experimental techniques, measuring performance, computing speed-up, experimental precautions, controlling variation, experimental dangers, reporting performance