DSA

Data

A collection of facts from which conclusions may be drawn (example: temperature = 35°C → it is hot).

Variable

Placeholder for representing data; in CS, variables hold data in programs.

Data Type

A set of data with predefined values (int, float, char, string, etc.).

System-Defined Data Types

Primitive types built into a language (int, float, char, double, bool).

User-Defined Data Types

Types defined by the user (structures in C/C++, classes in Java).

Data Structure

A particular way of storing and organizing data in a computer for efficient use.

Linear Data Structure

Elements are accessed in sequential order (e.g., arrays, linked lists, stacks, queues).

Non-Linear Data Structure

Elements are accessed in a non-sequential way (e.g., trees, graphs).

Abstract Data Type (ADT)

Combination of data structures with operations (e.g., Stack, Queue, Tree).

Need for Data Structures

Organize data for efficient storage, retrieval, and manipulation.

Characteristics of Data Structures

Correctness, Time Complexity, Space Complexity.

Algorithm

A step-by-step unambiguous procedure to solve a problem.

Good Algorithm Criteria

Correct, finite, terminates, unambiguous, efficient.

Program

An implementation of an algorithm written in a specific programming language.

Algorithm Analysis

Determines which algorithm is most efficient in terms of time/space.

Running Time

Time an algorithm takes, usually dependent on input size n.

Asymptotic Analysis

Describes algorithm performance for large input sizes independent of hardware.

Pseudocode

Plain English representation of an algorithm, less detailed than code.

Control Flow in Pseudocode

if-then-else, while, repeat-until, for-do, indentation.

Asymptotic Notations

Mathematical notations describing running time as input grows.

Big-O Notation

O(n), upper bound; worst-case complexity.

Omega Notation (Ω)

Lower bound; best-case complexity.

Theta Notation (Θ)

Tight bound; average-case complexity.

Rate of Growth

How runtime increases as input size increases.

Common Complexities

Constant O(1), Logarithmic O(log n), Linear O(n), Linearithmic O(n log n), Quadratic O(n^2), Cubic O(n^3), Exponential O(2^n).

Rules of Big-O

Drop constants, drop lower-order terms.

Recursion

A function calling itself to solve a problem.

Base Case

Condition where recursion stops.

Recursive Case

Step where function calls itself on smaller input.

Iteration vs Recursion

Iteration uses loops, recursion uses function calls and base cases.

Backtracking

Algorithmic technique that searches all possibilities, abandoning invalid ones.

Applications of Backtracking

Sudoku, crossword puzzles, mazes, N-Queens problem.

Linked List

Data structure of nodes connected by pointers.

Singly Linked List

Each node points to the next; last node points to NULL.

Doubly Linked List

Each node points to both next and previous.

Circular Linked List

Last node points back to the head, forming a circle.

Linked List Operations

Insert, delete, traverse, count nodes.

Advantages of Linked Lists

Can grow/shrink dynamically, no wasted memory allocation.

Disadvantages of Linked Lists

Slower access O(n), extra memory for pointers.

Stack

Linear data structure; Last In, First Out (LIFO).

Stack Operations

Push (insert), Pop (remove), Peek/Top (view last item).

Stack Exceptions

Underflow (pop from empty), Overflow (push to full).

Applications of Stacks

Expression evaluation, undo in text editors, backtracking, balancing symbols.

Queue

Linear data structure; First In, First Out (FIFO).

Queue Operations

Enqueue (insert at rear), Dequeue (remove from front).

Queue Exceptions

Underflow (remove from empty), Overflow (insert to full).

Applications of Queues

Print queue, call center simulation, async data transfer.

Types of Queues

Simple, Circular, Priority, Deque.

Tree

Non-linear data structure with hierarchical nodes (root, children).

Binary Tree

A tree where each node has at most two children.

Strict Binary Tree

Every node has either 2 children or none.

Full/Perfect Binary Tree

Every node has 2 children, and all leaves are at the same level.

Complete Binary Tree

All levels filled except possibly last, filled from left.

Tree Operations

Insert, delete, search, traverse.

Properties of Binary Trees

Height, number of nodes, leaf count, null links.

Tree Traversal

Visiting all nodes in a tree.

Preorder Traversal (DLR)

Visit root, then left, then right.

Inorder Traversal (LDR)

Visit left, then root, then right.

Postorder Traversal (LRD)

Visit left, then right, then root.

Level Order Traversal

Visit nodes level by level using a queue.

Generic Tree (N-ary)

Tree where each node can have many children.

First Child / Next Sibling Representation

Stores first child and next sibling links; memory efficient.

Threaded Binary Tree

Binary tree using NULL pointers to store predecessor/successor info for traversal.

Types of Threaded Binary Trees

Left-threaded, Right-threaded, Fully-threaded.

Expression Tree

Tree where leaves are operands and internal nodes are operators.