OS/Overview of Operating Systems
Core-Tier1 topics [2 hours]:
- Role and purpose of the operating system
- 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
- [k] Explain the objectives and functions of modern operating systems.
- [a] Analyze the tradeoffs inherent in operating system design.
- [k] Describe the functions of a contemporary operating system with respect to convenience, efficiency, and the ability to evolve.
- [k] Discuss networked, client-server, distributed operating systems and how they differ from single user operating systems.
- [k] Identify potential threats to operating systems and the security features design to guard against them.
SDF/Fundamental Programming Concepts
This unit builds the foundation for core concepts in the Programming Languages knowledge area, most notably in the paradigm-specific units: Object-Oriented Programming, Functional Programming, and Event-Driven & Reactive Programming.
Core-Tier1 topics [10 hours]:
- Basic syntax and semantics of a higher-level language
- Variables and primitive data types (e.g., numbers, characters, Booleans)
- Expressions and assignments
- Simple I/O
- Conditional and iterative control structures
- Functions and parameter passing
- The concept of recursion
- [e] Analyze and explain the behavior of simple programs involving the fundamental programming constructs covered by this unit.
- [k] Identify and describe uses of primitive data types.
- [a] Write programs that use each of the primitive data types.
- [a] Modify and expand short programs that use standard conditional and iterative control structures and functions.
- [a] 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, the definition of functions, and parameter passing.
- [e] Choose appropriate conditional and iteration constructs for a given programming task.
- [k] Describe the concept of recursion and give examples of its use.
- [e] Identify the base case and the general case of a recursively-defined problem.
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.
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.