Programación I

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

Learning Outcomes:

1. [k] Explain the objectives and functions of modern operating systems.
2. [a] Analyze the tradeoffs inherent in operating system design.
3. [k] Describe the functions of a contemporary operating system with respect to convenience, efficiency, and the ability to evolve.
4. [k] Discuss networked, client-server, distributed operating systems and how they differ from single user operating systems.
5. [k] Identify potential threats to operating systems and the security features design to guard against them.

SDF/Fundamental Programming Concepts

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

Learning Outcomes:

1. [e] Analyze and explain the behavior of simple programs involving the fundamental programming constructs covered by this unit.
2. [k] Identify and describe uses of primitive data types.
3. [a] Write programs that use each of the primitive data types.
4. [a] Modify and expand short programs that use standard conditional and iterative control structures and functions.
5. [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.
6. [e] Choose appropriate conditional and iteration constructs for a given programming task.
7. [k] Describe the concept of recursion and give examples of its use.
8. [e] Identify the base case and the general case of a recursively-defined problem.

AL/Fundamental Data Structures and Algorithms

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)

Learning Outcomes:

1. [a] Implement basic numerical algorithms.
2. [a] Implement simple search algorithms and explain the differences in their time complexities.
3. [a] Be able to implement common quadratic and O(N log N) sorting algorithms.
4. [k] Understand the implementation of hash tables, including collision avoidance and resolution.
5. [k] Discuss the runtime and memory efficiency of principal algorithms for sorting, searching, and hashing.
6. [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.
7. [a] Solve problems using fundamental graph algorithms, including depth-first and breadth-first search.
8. [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.
9. [a] Solve problems using graph algorithms, including single-source and all-pairs shortest paths, and at least one minimum spanning tree algorithm.
10. [a] Be able to implement a string-matching algorithm.

PL/Object-Oriented Programming

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

Learning Outcomes:

1. [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.
2. [a] Use subclassing to design simple class hierarchies that allow code to be reused for distinct subclasses.
3. [a] Use multiple encapsulation mechanisms, such as function closures, object-oriented interfaces, and support for abstract datatypes, in multiple programming languages.
4. [a] Define and use iterators and other operations on aggregates using idioms most natural in multiple programming languages, including taking functions as arguments.
5. [a] Write basic algorithms that avoid assigning to mutable state or considering object identity.
6. [a] Write event handlers for use in reactive systems, such as GUIs.
7. [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).
8. [k] Explain benefits and limitations of static typing.
9. [a] For multiple programming languages, identify program properties checked statically and program properties checked dynamically. Use this knowledge when writing and debugging programs.
10. [k] Distinguish a language definition (what constructs mean) from a particular language implementation (compiler vs. interpreter, run-time representation of data objects, etc.).
11. [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.
12. [a] Reason about memory leaks, dangling-pointer dereferences, and the benefits and limitations of garbage collection.
13. [a] Process some representation of code for some purpose, such as an interpreter, an expression optimizer, a documentation generator, etc.