Data Structures Fundamentals

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.