Introduction to Data Structures and Algorithms

Comprehensive flashcards covering introductory data structures, primitive and non-primitive classifications, array representations and operations, algorithm design approaches, control structures, complexity analysis, and recursion types.

Data

Information that can be interpreted and used by computers, consisting of a collection of facts such as numbers, words, measurements, observations, or descriptions of things.

Data Structures

The well organized collection of data to perform the required operations to generate the desired results, or a storage used to organize data on a computer for efficient access and updating.

Primitive Data Structure

A type of data structure that allows you to store only single data type values and does not allow for NULL values.

Integer

A primitive data type containing numeric whole numbers that can be either negative or positive.

Float

A primitive data type used to hold decimal values; when higher precision is needed, the Double data type is utilized.

Boolean

A data type that can hold either a True or a False value, mainly used for checking conditions.

Character

A primitive data type that holds a single character value, which can be either uppercase or lowercase.

Pointers

Variables used to store the memory address of another variable rather than holding a value itself.

Non-Primitive Data Structure

A data structure defined by the programmer that allows the storage of multiple data type values (homogeneous or heterogeneous) and can store NULL values.

Linear Data Structures

Data structures where data is stored in a sequence (one after another) and preserves a linear connection among its data elements.

Static Data Structures

Data structures with a fixed size where memory is allocated at compiler time and cannot be changed by the user after compilation.

Array

A non-primitive linear data structure which is a collection of data elements of similar data types stored at contiguous memory locations.

Dynamic Data Structures

Data structures where memory is allocated at run time, allowing the size to vary during the execution of the code.

Stack

A non-primitive linear data structure that follows the LIFO (Last In First Out) principle.

LIFO

An acronym for 'Last In First Out', meaning the last element added to the stack is the first one to be removed.

Push Operation

The process of inserting an element into a stack.

Pop Operation

The process of removing an element from a stack.

Queue

A non-primitive linear data structure that follows the 'First in, First out' (FIFO) principle.

FIFO

An acronym for 'First in, First out', where the first element added to the data structure is the first one to be removed.

Linked List

A non-primitive linear data structure where each element, known as a node, is connected to the next using pointers.

Singly Linked List

A linked list where each node contains data and one pointer field containing the address of the next node.

Doubly Linked List

A linked list where each node contains an information field and two pointer fields: one for the address of the previous node and one for the next node.

Circular Linked List

A variation of a linked list where the last node contains the address of the first node, forming a circular loop.

Non-Linear Data Structures

Data structures where data elements are not arranged sequentially and cannot be traversed in a single run.

Trees

A hierarchical non-linear data structure consisting of nodes linked together to form parent-child relationships.

Graph

A non-linear data structure consisting of a definite quantity of vertices (nodes) and edges that show their relationships, without specific rules for connection.

Traversal

The basic operation of accessing each data element in a data structure exactly once so it can be administered.

Sorting

The operation of arranging data elements in either Ascending or Descending order.

Merge

The operation of combining data elements of two sorted lists to form a single list of sorted data elements.

Abstract Data Type (ADT)

A conceptual model that defines a set of operations and behaviors for a data structure without specifying implementation details or memory organization.

Brute Force Approach

A fundamental algorithm design approach that involves trying all possible solutions until the correct one is found.

Divide and Conquer

A design approach that divides a problem into smaller subproblems, solves each subproblem recursively, and combines the results.

Greedy Algorithms

Algorithms that make a series of choices by selecting the best available option at each step to find a global optimum.

Dynamic Programming

A technique that solves problems by breaking them into overlapping subproblems and storing subproblem solutions to avoid redundant calculations.

Backtracking

An algorithmic technique for solving problems incrementally by exploring possibilities and eliminating those that are not viable when a dead end is reached.

Sequential Control Structure

The simplest form of control flow where instructions are executed in a linear sequence one after another.

Selection Control Structure

Structures that make decisions based on conditions; if a condition is true, one set of operations is performed, otherwise another is executed (e.g., If-Else).

Repetition Control Structure

Also known as looping, it allow operations to be repeated multiple times based on a condition (e.g., For Loop, While Loop).

Jump Structures

Structures used to alter the flow of execution, such as Break (exits a loop), Continue (skips an iteration), or Return (exits a function).

Space Complexity

The amount of memory required by an algorithm to solve a given problem as a function of the length of the input.

Time Complexity

The amount of time taken by an algorithm to run as a function of the length of the input.

Address of 1D Array Element (Page 19)

$$\text{ADDRESS}(\text{ARRAY}[K]) = \text{BASEADDRESS}(\text{ARRAY}) + \text{WORDLENGTH} \times (\text{LOWERBOUND} - K)$$

Address of 1D Array Element (Linear Representation)

$$\text{LOC}(\text{LA}[K]) = \text{Base}(\text{LA}) + w \times (K - \text{LB})$$

Row Major Representation Address

$$\text{ADDRESS}(\text{ARRAY}[I, J]) = \text{BASEADDRESS}(\text{ARRAY}) + \text{WORDLENGTH} \times (N \times (I - 1) + (J - 1))$$

Column Major Representation Address

$$\text{ADDRESS}(\text{ARRAY}[K]) = \text{BASEADDRESS}(\text{ARRAY}) + \text{WORDLENGTH} \times (M \times (J - 1) + (I - 1))$$

Recursion

The process in which a function calls itself directly or indirectly up to n-number of times.

Direct Recursion

A type of recursion where a function calls itself within the same function repeatedly.

Indirect Recursion

When a function is mutually called by another function in a circular manner (e.g., Fun1 calls Fun2 which calls Fun3 which calls Fun1).

Tail Recursion

A recursive function in which the recursive call is the last statement executed by the function.

Non-Tail / Head Recursion

A recursive function where the recursive call is the first statement in the function, and operations are performed during the return time.

Linear Recursion

A recursive function that makes exactly one call to itself each time it runs, growing linearly in proportion to problem size.

Tree Recursion

A recursive function that makes more than one call to itself within the same function.