Data structure and algorithm analysis

(Difference between revisions)

Current revision as of 11:12, 21 September 2019

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.

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 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.