Data Structures and Algorithms – Vocabulary Flashcards

Vocabulary flashcards covering key concepts from Pages 1–4 of the lecture notes.

Data Structure

A way of storing and organizing data in a computer, based on the ability of the computer to retrieve and store data in memory.

Primitive Data Structure

Basic data structures that are directly operated upon by machine instructions (e.g., integer, char).

Non-Primitive Data Structure

Derived from primitive data structures (e.g., array, stack).

Homogeneous

All elements are of the same type (e.g., an array).

Heterogeneous

Elements are of different types (e.g., a structure).

Linear

Maintains a linear relationship between its elements (e.g., array).

Non-Linear

Does not maintain a linear relationship among elements (e.g., trees).

Main Memory (RAM)

Volatile memory where instructions and data are stored; contents lost when power is turned off.

Cache Memory

Memory that stores frequently used instructions and data to speed up access.

Register (Cache Memory)

A small, fast storage location found in cache memory, used to temporarily hold instructions and data.

Persistent Memory (External Storage)

Non-volatile storage used to store instructions and data outside main memory; often used as virtual memory by the OS.

Reserving Memory

Process of allocating memory for a program and manipulating data with data structure techniques.

Abstract Data Type (ADT)

A keyword that specifies the amount of memory needed to store data and the kind of data that will be stored.

Static

This data structure size cannot be changed after initial allocation, e.g matrices

Byte ADT

8 bits; smallest in the integer group; used when sending/receiving data from a file or network.

Short ADT

16 bits; least used in the integer group; used on very old computers.

Int ADT

32-bit integer; most frequently used; used to control variables in loops and array indices.

Long ADT

64-bit integer; used when whole numbers exceed the range of int.

Dynamic

This data structure size can change dynamically, e.g. lists

Float ADT

32-bit floating point; single precision; about 7 decimal digits.

Double ADT

64-bit floating point; used for very large/small real numbers; more precision than float.

Char ADT

16-bit character type; represented as an integer value corresponding to a character set.

ASCII

American Standard Code for Information Interchange; 8-bit character set, up to 256 characters.

Unicode

Character set using 2 bytes per character; supports languages with more than 256 characters.

Boolean ADT

Stores a true/false value using 1 bit.

Memory Address

A unique identifier for a memory location; memory is organized in bytes (8-bit groups). Holds 0 or 1.

Algorithm

A step-by-step procedure that defines a set of instructions to produce the desired output.

Search (Algorithm Categories)

A category of algorithm that finds a specific item within a data structure.

Sort (Algorithm Categories)

A category of algorithm that arranges items in a particular order.

Insert (Algorithm Categories)

A category of algorithm that inserts an item into a data structure.

Update (Algorithm Categories)

A category of algorithm that updates an existing item.

Delete (Algorithm Categories)

A category of algorithm that removes an item from a data structure.

Unambiguous (Algorithm Characteristics)

Each step and input/output must lead to one clear meaning.

Input (Algorithm Characteristics)

Defined inputs; 0 or more well-defined inputs.

Output (Algorithm Characteristics)

Well-defined outputs; 1 or more, matching the desired outputs.

Finiteness (Algorithm Characteristics)

Algorithm must terminate after a finite number of steps.

Feasibility (Algorithm Characteristics)

Algorithm should be feasible with available resources.

Independent (Algorithm Characteristics)

Steps should be independent of any particular programming code.

Priori Analysis (Algorithm Analysis)

Theoretical analysis of algorithm efficiency assuming other factors are constant.

Posterior Analysis

Empirical analysis of an algorithm implemented and run on target hardware; measures actual time and space.

Time Factor

Measure of time by counting key operations (e.g., comparisons).

Space Factor

Measure of memory usage by counting maximum memory required.

Space Complexity

Amount of memory required by the algorithm.

Fixed Part (Space)

Space required that is independent of problem size.

Variable Part (Space)

Space required by variables that depends on problem size.

Time Complexity

Amount of time required to run to completion; often denoted as T(n).

T(n)

Notation representing the running time as a function of input size n.

Asymptotic Analysis

Analyzing running time performance for best, average, and worst cases as input size grows.

Best Case

Minimum time required for a program to run.

Average Case

Average time required for a program to run.

Worst Case

Maximum time required for a program to run.

O-Notation (O(n))

Formal notation expressing the upper bound (worst-case) of time complexity.

Omega (Ω(n))

Notation expressing a lower bound (best-case) of time complexity.

Theta (Θ(n))

Notation expressing both upper and lower bounds (average case) of time complexity.

Data Structure Types

Primitive and Non-Primitive

Data Structure Elements

Homogeneous and Heterogeneous

Data Structure Relationship

Linear and Non-Linear

Array

A collection of items of the same type stored in contiguous memory locations.

Array instantiation

int ages1[] = new int[100]; or ages = new int[100];

Array-index-out-of-bounds exception

Attempting to access an array element beyond its defined index range will result in this error

arrayName.length

returns the total number of elements.

Two-Dimensional Array

An array that can be seen as a table with 'x' rows and 'y' columns,

ArrayList

A part of the collection framework in the java.util package that provides a dynamic way of manipulating data.

Dynamic manipulation

The ability of an ArrayList to have its size increase if the collection grows or shrink if objects are removed.

Random access

The ability that ArrayList allows to directly access any element in the list.

Arraylist instantiation

new ArrayList<>(); or new ArrayList<>(Collection c); or new ArrayList<>(int capacity);

Stack

Abstract data type and data structure where elements are added and removed from the top.

LIFO

Last-In, First-Out; the fundamental ordering principle of a stack. The last element added is the first one removed.

push(element)

The operation that adds a new element to the top of the stack.

pop()

The operation that removes and returns the element from the top of the stack.

Infix Expression

An expression where the operator is between every pair of operands (e.g., A + B). It follows the <operand> <operator> <operand> scheme.

Postfix Expression

An expression where the operator follows both of its operands (e.g., A B +). It follows the <operand> <operand> <operator> scheme.