Data structure and algorithm analysis

From

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.