Programación Avanzada

AL/Basic Analysis

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

Learning Outcomes:

1. [k] Explain what is meant by “best”, “average”, and “worst” case behavior of an algorithm.
2. [e] In the context of specific algorithms, identify the characteristics of data and/or other conditions or assumptions that lead to different behaviors.
3. [a] Determine informally the time and space complexity of simple algorithms.
4. [k] Understand the formal definition of big O.
5. [k] List and contrast standard complexity classes.
6. [e] Perform empirical studies to validate hypotheses about runtime stemming from mathematical analysis. Run algorithms on input of various sizes and compare performance.
7. [k] Give examples that illustrate time-space trade-offs of algorithms.
8. [a] Use big O notation formally to give asymptotic upper bounds on time and space complexity of algorithms.
9. [a] Use big O notation formally to give average case bounds on time complexity of algorithms.
10. [k] Explain the use of big omega, big theta, and little o notation to describe the amount of work done by an algorithm.
11. [a] Use recurrence relations to determine the time complexity of recursively defined algorithms.
12. [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)

[Elective]

• Parallel graph algorithms (e.g., parallel shortest path, parallel spanning tree) (cross-reference AL/Algorithmic Strategies/Divide-and-conquer)
• Producer-consumer and pipelined algorithms

Learning Outcomes:

1. [k] Define “critical path”, “work”, and “span”
2. [a] Compute the work and span, and determine the critical path with respect to a parallel execution diagram
3. [k] Define “speed-up” and explain the notion of an algorithm’s scalability in this regard
4. [a] Identify independent tasks in a program that may be parallelized
5. [k] Characterize features of a workload that allow or prevent it from being naturally parallelized
6. [a] Implement a parallel divide-and-conquer and/or graph algorithm and empirically measure its performance relative to its sequential analog
7. [a] Decompose a problem (e.g., counting the number of occurrences of some word in a document) via map and reduce operations
8. [k] Provide an example of a problem that fits the producer-consumer paradigm
9. [k] Give examples of problems where pipelining would be an effective means of parallelization
10. [k] Identify issues that arise in producer-consumer algorithms and mechanisms that may be used for addressing them

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.

HC/Designing Interaction

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

Learning Outcomes:

1. [a] Create a simple application, together with help & documentation, that supports a user interface.
2. [a] Conduct a quantitative evaluation and discuss/report the results.
3. [k] Discuss at least one national or international user interface design standard.

HC/Foundations

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,+)

Learning Outcomes:

1. [k] Discuss why human-centered software development is important.
2. [k] Summarize the basic precepts of psychological and social interaction.
3. [k] Develop and use a conceptual vocabulary for analyzing human interaction with software: affordance, conceptual model, feedback, and so forth.
4. [k] Define a user-centered design process that explicitly recognizes that the user is not like the developer or her acquaintances.
5. [a] Create and conduct a simple usability test for an existing software application.

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.