Terms

• Problem: maps inputs ➝ outputs
• Algorithm: step-by-step procedure to solve problems; cost = resources used
• Program: implementation of algorithms in a programming language

Data type

• Primitive: system-defined (int, char)
• Non-Primitive: user-defined (e.g. stack, heap)
• Abstract Data Type (ADT): defined by operations, not implementation (e.g. dictionary)

Data Structure

• Organize data efficiently; used to implement ADTs
• Linear: ordered collection of values (Array, Linked List, Stack, Queue)
• Non-linear: hierarchical nodes connected via edges (Trees, Graphs)
• static: compile time memory allocation. Stored on stack.
• dynamic: run-time memory allocation. Stored on Heap. e.g. Linked List

Algo-efficiency

• Measured w.r.t. input size N
• Time complexity: Big-O of all steps
• Space complexity: input + local + recursive space
• Asymptotic notations: mathematical tools to represent time-space complexity. E.g. Big O (worst case), Omega (best), Theta (average)
• O(1): constant