Core-Tier1 topics [2 hours]:
- Differences among best, average, and worst case behaviors of an algorithm
- Asymptotic analysis of upper and average complexity bounds
- Big O notation: formal definition
- Complexity classes, such as constant, logarithmic, linear, quadratic, and exponential
- Empirical measurements of performance
- Time and space trade-offs in algorithms
Core-Tier2 topics [2 hours]:
- Big O notation: use
- Little o, big omega and big theta notation
- Recurrence relations and analysis of recursive algorithms
- Some version of a Master Theorem
- [k] Explain what is meant by “best”, “average”, and “worst” case behavior of an algorithm.
- [e] In the context of specific algorithms, identify the characteristics of data and/or other conditions or assumptions that lead to different behaviors.
- [a] Determine informally the time and space complexity of simple algorithms.
- [k] Understand the formal definition of big O.
- [k] List and contrast standard complexity classes.
- [e] Perform empirical studies to validate hypotheses about runtime stemming from mathematical analysis. Run algorithms on input of various sizes and compare performance.
- [k] Give examples that illustrate time-space trade-offs of algorithms.
- [a] Use big O notation formally to give asymptotic upper bounds on time and space complexity of algorithms.
- [a] Use big O notation formally to give average case bounds on time complexity of algorithms.
- [k] Explain the use of big omega, big theta, and little o notation to describe the amount of work done by an algorithm.
- [a] Use recurrence relations to determine the time complexity of recursively defined algorithms.
- [a] Solve elementary recurrence relations, e.g., using some form of a Master Theorem.
PD/Parallel Algorithms, Analysis, and Programming
Core-Tier2 topics [3 hours]:
- Critical paths, work and span, and the relation to Amdahl’s law (cross-reference SF/Performance)
- Speed-up and scalability
- Naturally (embarassingly) parallel algorithms
- Parallel algorithmic patterns (divide-and-conquer, map and reduce, others)
- Specific algorithms (e.g., parallel MergeSort)
- Parallel graph algorithms (e.g., parallel shortest path, parallel spanning tree) (cross-reference AL/Algorithmic Strategies/Divide-and-conquer)
- Producer-consumer and pipelined algorithms
- [k] Define “critical path”, “work”, and “span”
- [a] Compute the work and span, and determine the critical path with respect to a parallel execution diagram
- [k] Define “speed-up” and explain the notion of an algorithm’s scalability in this regard
- [a] Identify independent tasks in a program that may be parallelized
- [k] Characterize features of a workload that allow or prevent it from being naturally parallelized
- [a] Implement a parallel divide-and-conquer and/or graph algorithm and empirically measure its performance relative to its sequential analog
- [a] Decompose a problem (e.g., counting the number of occurrences of some word in a document) via map and reduce operations
- [k] Provide an example of a problem that fits the producer-consumer paradigm
- [k] Give examples of problems where pipelining would be an effective means of parallelization
- [k] Identify issues that arise in producer-consumer algorithms and mechanisms that may be used for addressing them
AL/Fundamental Data Structures and Algorithms
This knowledge unit builds directly on the foundation provided by Software Development Fundamentals (SDF), particularly the material in SDF/Fundamental Data Structures and SDF/Algorithms and Design. .
Core-Tier1 topics [9 hours]:
- Simple numerical algorithms, such as computing the average of a list of numbers, finding the min, max, and mode in a list, approximating the square root of a number, or finding the greatest common divisor
- Sequential and binary search algorithms
- Worst case quadratic sorting algorithms (selection, insertion)
- Worst or average case O(N log N) sorting algorithms (quicksort, heapsort, mergesort)
- Hash tables, including strategies for avoiding and resolving collisions
- Binary search trees
- Common operations on binary search trees such as select min, max, insert, delete, iterate over tree
- Graphs and graph algorithms
- Representations of graphs (e.g., adjacency list, adjacency matrix)
- Depth- and breadth-first traversals
Core-Tier2 topics [3 hours]:
- Graphs and graph algorithms
- Shortest-path algorithms (Dijkstra’s and Floyd’s algorithms)
- Minimum spanning tree (Prim’s and Kruskal’s algorithms)
- Pattern matching and string/text algorithms (e.g., substring matching, regular expression matching, longest common subsequence algorithms)
- [a] Implement basic numerical algorithms.
- [a] Implement simple search algorithms and explain the differences in their time complexities.
- [a] Be able to implement common quadratic and O(N log N) sorting algorithms.
- [k] Understand the implementation of hash tables, including collision avoidance and resolution.
- [k] Discuss the runtime and memory efficiency of principal algorithms for sorting, searching, and hashing.
- [k] 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.
- [a] Solve problems using fundamental graph algorithms, including depth-first and breadth-first search.
- [a] Demonstrate the ability to evaluate algorithms, to select from a range of possible options, to provide justification for that selection, and to implement the algorithm in a particular context.
- [a] Solve problems using graph algorithms, including single-source and all-pairs shortest paths, and at least one minimum spanning tree algorithm.
- [a] Be able to implement a string-matching algorithm.
CS students need a minimal set of well-established methods and tools to bring to interface construction.
Core-Tier2 topics [4 hours]:
- Principles of different styles of interface: e.g. command line, graphical tangible.
- Basic two-dimensional design fundamentals as applied to the visual interface, including use of grid, typography, color and contrast, scale, ordering and hierarchy.)
- Task analysis
- Paper prototyping
- Basic statistics and techniques for controlled experimentation (especially in regard to web data)
- KLM evaluation
- Help & documentation
- Handling human/system failure
- User interface standards
- [a] Create a simple application, together with help & documentation, that supports a user interface.
- [a] Conduct a quantitative evaluation and discuss/report the results.
- [k] Discuss at least one national or international user interface design standard.
For end-users, the interface is the system. So design in this domain must be interaction-focused and human-centered. Students need a different repertoire of techniques to address interaction design than is provided elsewhere in the curriculum.
Core-Tier1 topics [4 hours]:
- Contexts for HCI (anything with a user interface: webpage, business applications, mobile applications, games, etc.)
- Processes for user-centered development: early focus on users, empirical testing, iterative design.
- Different measures for evaluation: utility, efficiency, learnability, user satisfaction.
- Physical capabilities that inform interaction design: color perception, ergonomics
- Cognitive models that inform interaction design: attention, perception and recognition, movement, and memory. Gulfs of expectation and execution.
- Social models that inform interaction design: culture, communication, networks and organizations.
- Principles of good design and good designers; engineering tradeoffs
- Accessibility: interfaces for differently-abled populations (e.g. blind, motion-impaired)
- Interfaces for differently-aged population groups (e.g. children,+)
- [k] Discuss why human-centered software development is important.
- [k] Summarize the basic precepts of psychological and social interaction.
- [k] Develop and use a conceptual vocabulary for analyzing human interaction with software: affordance, conceptual model, feedback, and so forth.
- [k] Define a user-centered design process that explicitly recognizes that the user is not like the developer or her acquaintances.
- [a] Create and conduct a simple usability test for an existing software application.
Core-Tier1 topics [4 hours]:
- Object-oriented design
- ----->Decomposition into objects carrying state and having behavior
- ----->Class-hierarchy design for modeling
- Definition of classes: fields, methods, and constructors
- Subclasses, inheritance, and overriding
- Dynamic dispatch: definition of method-call
Core-Tier2 topics [6 hours]:
- Subtyping (cross-reference PL/Type Systems)
- ----->Subtype polymorphism; implicit upcasts in typed languages
- ----->Notion of behavioral replacement
- ----->Relationship between subtyping and inheritance
- Object-oriented idioms for encapsulation
- ----->Private fields
- ----->Interfaces revealing only method signatures
- ----->Abstract base classes
- Using collection classes, iterators, and other common library components
Generated by ACMgen v1.2 (c) 2012 Allan Lopez Hernandez allanlh (at) Gmail.com
- [e] Compare and contrast (1) the procedural/functional approach—defining a function for each operation with the function body providing a case for each data variant—and (2) the object-oriented approach—defining a class for each data variant with the class definition providing a method for each operation. Understand both as defining a matrix of operations and variants.
- [a] Use subclassing to design simple class hierarchies that allow code to be reused for distinct subclasses.
- [a] Use multiple encapsulation mechanisms, such as function closures, object-oriented interfaces, and support for abstract datatypes, in multiple programming languages.
- [a] Define and use iterators and other operations on aggregates using idioms most natural in multiple programming languages, including taking functions as arguments.
- [a] Write basic algorithms that avoid assigning to mutable state or considering object identity.
- [a] Write event handlers for use in reactive systems, such as GUIs.
- [k] Explain the relationship between object-oriented inheritance (code-sharing and overriding) and subtyping (the idea of a subtype being usable in a context that expects the supertype).
- [k] Explain benefits and limitations of static typing.
- [a] For multiple programming languages, identify program properties checked statically and program properties checked dynamically. Use this knowledge when writing and debugging programs.
- [k] Distinguish a language definition (what constructs mean) from a particular language implementation (compiler vs. interpreter, run-time representation of data objects, etc.).
- [k] Explain how programming language implementations typically organize memory into global data, text, heap, and stack sections and how features such as recursion and memory management map to this memory model.
- [a] Reason about memory leaks, dangling-pointer dereferences, and the benefits and limitations of garbage collection.
- [a] Process some representation of code for some purpose, such as an interpreter, an expression optimizer, a documentation generator, etc.