Data Structures Fundamentals

Study Notes

Data Structures

Data structures are formats for storing and organizing data.
Two main types exist: Linear (sequential access, possibly unsystematic storage) and Non-Linear (non-sequential access).
Abstract Data Type (ADT) provides a logical description of data and operations, independent of implementation.

Benefits of ADTs

Enhances code readability.
Changes in ADT implementation do not impact programs using them.
Promotes reuse in future applications.

Components of ADTs

Public or external components include data and operations.
Private or internal components include representation and implementation.

Common Abstract Data Types

Linked List: Stores elements as separate objects.
Stack: Last-In, First-Out (LIFO) structure where the last added element is the first removed.
Queue: First-In, First-Out (FIFO) structure where the first added element is the first removed.
Tree: Hierarchical representation in a graphical format.
Priority Queue: Processes elements based on a defined order (natural or custom).
Heap: A complete binary tree with parent nodes having values either higher or lower than their children.
Set: Collection of unique elements.
Map: A collection of ordered pairs consisting of keys (identifiers) and values (content).
Graph: Comprises vertices (nodes) and edges (relations).

Operations of ADTs

Key operations include initialization, adding, accessing, and removing data.

Algorithms

An algorithm is a sequential set of instructions designed to solve a problem.

Characteristics of Algorithms

Finiteness: Must terminate after a defined number of steps.
Definiteness: Instructions should be clear and unambiguous.
Input: Can accept zero or more well-defined data before execution.
Output: Must produce one or more results related to the input.
Uniqueness: Each step's result is determined by inputs and/or previous results.

Elements of Algorithms

Sequential operations to progress through steps.
State-based actions influenced by data structures.
Iteration: Repetitive execution of an action.
Recursion: A function calls itself to address problems.

Algorithm Design Paradigms

Divide and Conquer: Decomposes a problem into smaller subproblems.
Greedy Algorithms: Selects the best immediate option at each step.
Dynamic Programming: Similar to Divide and Conquer, but reuses results from overlapping subproblems.

Recursion Fundamentals

Recursion is when a function calls itself to solve a problem, allowing for direct or indirect recursive methods.
Direct recursion occurs when a method calls itself directly, while indirect recursion involves method calls to another method, leading back to the original method.
Infinite recursion happens when a recursive function lacks a stopping condition, potentially causing a stack overflow.

Characteristics of Recursive Algorithms

A recursive algorithm must include a base case to determine when to stop recurring.
It must change state to gradually progress toward reaching the base case, which involves modifying some operational data.
The algorithm must call itself as part of its processing to continue the recursion.

Recursion vs. Iteration

Recursion terminates when a base case is achieved; iteration continues until a condition is false.
Each recursive call uses additional memory space, whereas iterations do not allocate extra memory for each cycle.
Infinite recursion may lead to memory depletion and stack overflow, while an infinite loop runs indefinitely without producing extra memory.
Solutions to certain problems are often simpler when framed in recursive terms, whereas iterative approaches may appear less clear.

Types of Recursion

Linear Recursion: Occurs when the function calls itself once per invocation, e.g., calculating factorials.
Tail Recursion: The last operation in the function is the recursive call, e.g., finding the greatest common divisor.
Binary Recursion: The function calls itself twice during execution, e.g., generating the Fibonacci series.
Mutual Recursion: Involves pairs or groups of functions that call each other, e.g., checking if an integer is even or odd.

Description

This quiz explores the fundamental concepts of data structures, including the definition, types, and characteristics of linear and non-linear data structures. Additionally, it covers abstract data types and their importance in organizing and storing data efficiently.