Introduction to Data Structures and Algorithm Analysis Flashcards

A comprehensive vocabulary list covering data structures, algorithm definitions, classification of types, complexity components, and asymptotic notations based on the lecture transcript.

Data Structure (DS)

The way data is stored; represented by the formula $DS = \text{Organized Data} + \text{allowed operations}$.

Algorithm

A step-by-step procedure that provides a solution to a given problem; it describes the way data is processed.

Program

A representation defined by the formula $\text{Program} = \text{Algorithm} + \text{DS}$.

Data

Raw facts and figures before they have been processed, or a known fact that can be recorded and have implicit meaning.

Atomic Data

A single or non–decomposable entity, such as the integer $3241$.

Non-Atomic Data (Composite Data)

Also called structured data, it can be broken into subfields that have meaning, such as a date consisting of day, month, and year.

Information

An organized and processed form of data that is meaningful and logical.

Data Types

The information type that can be processed by the computer and supported by the programming language; refers to the kind of data variables may hold.

void

A data type that specifies an empty set of values; used as the type returned by functions that generate no value.

User-defined data types

Data types defined by the user as per requirement, such as typedef, enum, structure, and union.

Enumeration (enum)

A way of defining constants where members are automatically assigned integer values starting with $0$ and increasing by one.

Structure

A tool for packing together logically related data items of different (heterogeneous) types.

Array

A collection of memory elements (homogeneous) where data is stored sequentially in a continuous manner.

Pointer

A memory location that holds the address of another variable, accessed using the operators $*$ and $\&$.

Data Object

A container for data values characterized by a set of attributes; they are runtime instances of data structures.

Abstract Data Types (ADT)

A programmer's own data type defined by the formula $\text{ADT} = \text{Type} + \text{Function Names} + \text{Behaviour of each Function}$.

Abstraction

The generalization of operations where the essence of the process is captured while the implementation details remain hidden.

Encapsulation

The mapping where the definition of the type and all operations on that type are put together as one section of the program.

Primitive Data Structure

A set of atomic elements which do not involve any other elements as subparts, such as int, float, and char.

Non-Primitive Data Structure

A set of derived elements such as arrays, files, and structures.

Linear Data Structure

A structure where all elements form a sequence or linear ordering, and every element has a unique successor and predecessor.

Non-linear Data Structure

A structure representing hierarchical or network relationships where every element may have more than one predecessor or successor.

Static Data Structure

A structure where memory is allocated at the beginning of the program execution and freed only after the program terminates (e.g., array).

Dynamic Data Structure

A structure created at runtime where memory is allocated and destroyed during program execution (e.g., linked list).

Persistent Data Structure

A data structure that supports operations on the most recent version as well as previous versions.

Ephemeral Data Structure

A data structure that supports operations only on the most recent version.

Definiteness

The algorithm criterion stating that each instruction must be clear, unambiguous, and precisely defined.

Effectiveness

The algorithm criterion stating that every instruction must be basic enough to be carried out by a person using only paper and pencil.

Finiteness

The algorithm criterion stating that the algorithm must terminate after a finite number of steps for all cases.

Space Complexity

The amount of memory an algorithm needs for running; denoted as $S(p) = c + sp$, where $c$ is the fixed part and $sp$ is the variable part.

Time Complexity

The amount of time taken by a program for execution, calculated as the sum of the time taken by each executable statement; denoted by $t(p)$.

Best Case Complexity

A measure of the minimum time an algorithm will require for an input of size $n$.

Worst Case Complexity

The maximum time required for $n$ inputs or the time taken on the worst possible set of inputs.

Big O Notation (O)

Notation used to denote the upper bound or worst case of an algorithm's time complexity, defined as $f(n) \text{ is } O(g(n))$ if $f(n) \times c \times g(n)$ for all $n \times n_0$.

Big Omega Notation (Ω)

Notation used to denote the lower bound or best case of an algorithm's time complexity, defined as $f(n) \times \text{ Ω }(g(n))$ if $f(n) \times c \times g(n)$ for all $n \times n_0$.

Theta Notation (Θ)

A formal method of expressing the average bound of an algorithm's running time where $c_1 \times g(n) \times f(n) \times c_2 \times g(n)$ for all $n \times n_0$.