View source

== Justify data structure and algorithm choices. ==

* Measure the performance of an implementation and optimize it.
* Identify the operations being counted and resources being measured.
* Discuss the choices made in asymptotic complexity analysis (best, average, worst, amortized; space, time).
* Calculate the asymptotic complexity of an algorithm and algebraically manipulate standard notations for complexity.
* Classify and rank common algorithms and data structure operations by asymptotic complexity.
* Discuss memory as a resource.
* Trade off resource use, such as space/time.
* Discuss the details suppressed by asymptotic complexity analysis (e.g. performance measurement to reveal large constants).
* Discuss factors other than computational efficiency that influence the choice of algorithms, such as programming time, maintainability, use of application-specific patterns in the input data ''(per ACM)'', and ease of correctness/debugging.
* Classify algorithms by strategy, such as greedy, brute force, divide-and-conquer, decrease-and-conquer, transform-and-conquer, and dynamic programming.

== Recognize data structures. ==

* Recall the data structures that are available to a program, by language, libraries, framework, and so forth.
* Recognize implicit structure, such as a heap implicit in an array, and the distinction between a list and a sorted list.

== Implement data structures appropriately. ==

* Implement a dynamic container and the operations to manipulate it.
* Implement a static container with the optimizations that are possible because its shape is constant.
* Implement a container for mutable items, including any required type annotations and operations that adapt the structure when data change.
* Implement a container for immutable items with the optimizations that are possible because each item is constant.
* Distinguish the mutability of a reference from the mutability of the location it refers to.
* Write an algorithm using in-place, copying, and memory-adaptive strategies, as appropriate.
* Adapt an implementation to serve a different abstraction, such as a list presented as a stack, while being mindful of leaky abstractions (e.g. query and reserve the capacity of the array underlying a vector).
* Use nested data structures, such as arrays of lists and dictionaries of sets of strings.
* Write a data structure that presents a slice or view into another data structure.
* When copying or moving a data structure, consider how its items are duplicated, e.g. shallow by reference or deep by recursive copy, and choose appropriately.
* Implement an algorithm using inversion of control, as in map, reduce, visitors, or event callbacks, and choose between inversion and traditional control structures appropriately.