PadhaikoAll subjects

Introduction

Data Structure and Algorithms (ENCT 252)

Open in the Padhaiko app

1.1 Introduction to data structures

A data structure is a specialized format for organizing, storing, accessing, and modifying data in computer memory so that algorithms can operate on it efficiently. Before selecting a data structure, we distinguish between a data type and a data structure:

Definition

Key Specifications of a Data Structure

Every data structure is characterized by four specifications:

  1. Organization of Data: The logical arrangement of elements and how each element relates to others.
  2. Accessing Methods: The operations used to retrieve, insert, update, or delete elements.
  3. Degree of Associativity: The structural links or neighborhood relationships connecting data items.
  4. Processing Alternatives: The algorithmic strategies supported for traversing, searching, or sorting the stored information.

1.1.1 Need of data structures

In software engineering, program design follows Niklaus Wirth's classic principle:

Choosing the right data structure is essential because the representation of data directly determines how fast an algorithm runs and how much memory it consumes.

1.1.2 Types of data structures and its characteristics

Data structures are classified along two primary axes: primitive vs. non-primitive (with non-primitive further split into linear and non-linear) and static vs. dynamic.

Classification Hierarchy of Data StructuresText
                           Data Structure
                                 |
          +----------------------+----------------------+
          |                                             |
   Primitive Data Types                     Non-Primitive Data Structures
(int, char, float, double)                              |
                                         +--------------+--------------+
                                         |                             |
                              Linear Data Structures        Non-Linear Data Structures
                         (Array, Linked List, Stack, Queue)  (Tree, Graph, Hash Table)
AspectLinear Data StructuresNon-Linear Data Structures
ArrangementElements are arranged sequentially on a single levelElements are organized hierarchically or as general networks
AdjacencyEach element has at most one predecessor and one successorOne element can connect to zero, one, or many other elements
TraversalTraversed completely in a single sequential passRequires multi-level or branching traversal (e.g., DFS, BFS, tree orders)
Memory UtilizationContiguous (arrays) or singly/doubly linked nodesTypically pointer-based or adjacency representations
ExamplesArray, Linked List, Stack, QueueTree, Binary Search Tree, Graph, Hash Table

Based on memory allocation and capacity flexibility, data structures are also grouped as static or dynamic:

Static vs. Dynamic Data Structures
CharacteristicStatic Data StructureDynamic Data Structure
CapacityFixed at compile time or creation timeExpands and shrinks dynamically at runtime
Memory AllocationContiguous block (compile-time or fixed allocation)Non-contiguous nodes allocated via pointers (malloc/free)
Access PatternDirect random access by indexSequential or pointer-following access
Insertion / DeletionCostly in the middle (requires shifting elements)Efficient once position is located (pointer re-linking)
ExamplesStatic ArrayLinked List, Dynamic Stack/Queue, Binary Tree

1.2 Abstract data type (ADT)

Definition

Abstract Data Type (ADT)

An Abstract Data Type (ADT) is a mathematical model for a data structure that specifies:

  1. The domain of data values stored (value definition), and
  2. The set of valid operations along with their input parameters, preconditions, and behavioral outcomes (operator definition),

without specifying how the data is stored in memory or how the operations are implemented in code.

As a concrete illustration, a List ADT storing elements of type Element is defined purely by its abstract interface:


1.3 Basics of algorithm design techniques

An algorithm is a finite, unambiguous step-by-step procedure for solving a computational problem. Every valid algorithm must satisfy five fundamental properties:

Definition

Five Properties of an Algorithm

  1. Input: Accepts zero or more well-defined quantities externally.
  2. Output: Produces at least one verifiable result.
  3. Definiteness: Every instruction is clear, precise, and unambiguous.
  4. Finiteness: Terminates after a finite number of steps for all valid inputs.
  5. Effectiveness: Every operation is basic enough to be executed mechanically in finite time.

Complex problems are solved systematically using eight standard algorithm design techniques:

  1. Brute Force: Directly enumerates all candidate solutions based on the problem statement and selects the valid or optimal one. Simple to implement for small inputs, though often slow ( or ). Examples: Linear search, exhaustive Traveling Salesman Problem (TSP) over all permutations.
  2. Divide and Conquer: Splits the problem into independent smaller sub-problems of the same type, solves each recursively, and combines their results. Examples: Binary search (), Merge Sort (), Quick Sort (average ).
  3. Greedy Algorithms: Builds a solution piece by piece, always choosing the locally optimal option available at that step without reconsidering earlier choices. Fast and simple, though guaranteed globally optimal only for problems with the greedy-choice property. Examples: Kruskal's and Prim's MST algorithms, Dijkstra's shortest path, Huffman coding, activity selection.
  4. Dynamic Programming (DP): Solves problems exhibiting overlapping subproblems and optimal substructure by solving each unique subproblem once and storing its result—either top-down (memoization) or bottom-up (tabulation). Examples: Fibonacci sequence (), Knapsack, Longest Common Subsequence (LCS).
  5. Backtracking: Constructs a candidate solution incrementally and abandons (prunes) a partial path as soon as it violates a problem constraint, returning to the previous decision point. Examples: -Queens problem, Sudoku solver, Subset Sum.
  6. Branch and Bound: Similar to backtracking for combinatorial optimization problems, but computes a cost bound (lower or upper bound) at each node of the state-space tree and prunes branches that cannot improve upon the best solution found so far. Examples: Knapsack optimization, TSP with lower-bound pruning.
  7. Recursive Algorithms: Expresses the solution of a problem in terms of smaller instances of itself until reaching a terminating base case. Serves as the foundation for divide and conquer, tree traversals, and backtracking. Examples: Factorial, Tower of Hanoi, BST traversals.
  8. Randomized Algorithms: Incorporates random choices during execution to simplify logic or avoid worst-case inputs.
    • Las Vegas: Always returns the exact correct result, while runtime is a random variable (e.g., Randomized QuickSort).
    • Monte Carlo: Runs in bounded time, with a small bounded probability of an incorrect result (e.g., Miller–Rabin primality test).
Summary of Algorithm Design Techniques
TechniqueCore StrategyTypical Use CaseClassic Examples
Brute ForceTest all candidatesSmall inputs, baseline solutionLinear search, exhaustive TSP
Divide & ConquerSplit solve independently mergeIndependent subproblemsMerge Sort, Quick Sort, Binary Search
GreedyPick best local choice at each stepMatroid / greedy-choice optimizationPrim's, Kruskal's, Dijkstra's
Dynamic ProgrammingCache overlapping subproblemsOptimization with overlapping subproblems Knapsack, LCS, Floyd–Warshall
BacktrackingIncremental search; prune on constraint violationConstraint satisfaction-Queens, Sudoku
Branch & BoundState-space search; prune using cost boundsOptimal combinatorial searchTSP branch-and-bound, Knapsack
RecursiveSelf-referential decomposition + base caseNaturally self-similar structuresTower of Hanoi, tree traversals
RandomizedRandom pivot / sampling choicesAvoiding adversarial worst casesRandomized QuickSort, Miller–Rabin
AspectBacktrackingBranch and Bound
Primary GoalFind any or all feasible solutions satisfying constraintsFind the optimal (minimum or maximum cost) solution
Pruning CriterionPrunes when constraints are violated (infeasible state)Prunes both on infeasibility and when cost bound is worse than current best
Traversal OrderTypically Depth-First Search (DFS)BFS, Best-First (least-cost), or DFS

1.4 Algorithm analysis

Algorithm analysis estimates the computational resources—primarily execution time and memory—required by an algorithm as a function of the input size . Expressing resource usage as a growth function allows us to compare algorithms independently of CPU speed, compiler optimizations, or programming language.

1.4.1 Time and space complexity

Definition

Time Complexity and Space Complexity

To analyze an algorithm systematically:

  1. Identify the basic operation (the most frequently executed statement, e.g., element comparison in searching/sorting).
  2. Count how many times the basic operation executes in terms of .
  3. Express the dominant growth using asymptotic notation (, , ).
Common Time and Space Complexity Classes
ComplexityNameTypical Algorithm / Structure
ConstantArray index access a[i], stack push/pop, fixed scalar variables
LogarithmicBinary search on a sorted array of items
LinearLinear search, array traversal, storing an array of elements
LinearithmicMerge Sort, Heap Sort, Quick Sort (average case)
QuadraticBubble Sort, Insertion Sort, Selection Sort, matrix storage
CubicStandard matrix multiplication, Floyd–Warshall all-pairs shortest path
ExponentialRecursive Tower of Hanoi ( moves), naive recursive Fibonacci
FactorialGenerating all permutations of items

1.4.2 Best, worst and average case analysis

Because an algorithm's execution time can depend not only on input size but also on the arrangement of input data, we analyze three distinct cases:

Definition

Best, Worst, and Average Case Analysis

  1. Best Case: The minimum number of operations required for any input of size (most favorable arrangement).
    • Linear search: Target is at index comparison .
    • Bubble sort (with early-exit flag): Array is already sorted comparisons .
  2. Worst Case: The maximum number of operations required over all inputs of size (least favorable arrangement). This provides an upper-bound guarantee for every possible input.
    • Linear search: Target is at the last index or absent comparisons .
    • Bubble sort: Array is reverse-sorted comparisons .
  3. Average Case: The expected number of operations averaged over a probability distribution of all valid inputs of size .
    • Linear search (assuming uniform probability and key present):

1.4.3 Rate of growth

The rate of growth describes how rapidly increases as input size becomes large. For large , the highest-order (dominant) term overwhelms lower-order terms and constant multipliers. For example, in :

Hence, standard asymptotic analysis drops constant factors and lower-order terms, ordering common growth rates from slowest-growing (most efficient) to fastest-growing:

Numeric Comparison of Growth Functions
Input Size

1.4.4 Asymptotic notations: Big Oh, Big Omega and Big Theta

Asymptotic notations provide formal mathematical bounds on positive growth functions as .

Definition

Big Oh (O), Big Omega (Ω), and Big Theta (Θ)

Let and be positive-valued functions defined on positive integers :

  1. Big Oh Notation — (Asymptotic Upper Bound):

grows no faster than beyond threshold . Used primarily to express worst-case upper bounds.

  1. Big Omega Notation — (Asymptotic Lower Bound):

grows at least as fast as beyond threshold . Used to express best-case or inherent lower bounds.

  1. Big Theta Notation — (Asymptotic Tight Bound):

Equivalently, if and only if and . is sandwiched tightly between and .

Asymptotic Bound Curves for O, Omega, and ThetaText
Big-O: f(n) <= c*g(n)        Big-Omega: f(n) >= c*g(n)     Big-Theta: c1*g(n) <= f(n) <= c2*g(n)
  |       / c*g(n)             |         / f(n)              |         / c2*g(n)
  |      /                     |        /                    |        /  / f(n)
  |     /  f(n)                |       /  c*g(n)             |       /  /  / c1*g(n)
  |    / /                     |      / /                    |      /  /  /
  +---+-+-------------> n      +-----+-+-------------> n     +-----+-+-------------> n
      n0                             n0                            n0
Summary of Asymptotic Notations
NotationBound TypeFormal Inequality ()Typical InterpretationExample
Upper bound ()Worst-case guaranteeLinear search:
Lower bound ()Best-case / minimum workLinear search:
Tight bound ()Exact asymptotic orderBinary search:

Worked Examples

Example 1

1

Using the formal definition of Big-O notation, prove that is , and find valid positive constants and . Verify your bound at and .

Applying the Big-O definition: We must find constants and such that

Bounding each lower-order term by :

Choosing and , the inequality holds for all .

Checking at and :

  • At : and , so holds.
  • At : holds.
Answer:

with and (note that smaller constants such as work for larger thresholds like ).

Example 2

2

Prove using the formal definition of Big-Theta () that , specifying explicit constants , , and .

Stating the condition: We require constants , , and such that

Finding the lower-bound constant : For all , the terms and are strictly positive (), so:

Thus holds for all .

Finding the upper-bound constant : For all , since and :

Thus holds for all .

Answer:

with , , and , since for all .

Example 3

3

Analyze the best-case, worst-case, and average-case time complexity (counting key comparisons arr[i] == key) and the space complexity of the C linearSearch function below for an array of size . Also compute the exact average number of comparisons for when the key is equally likely to be at any index.

Linear Search in CC
int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key)
            return i;
    }
    return -1;
}

Best-case and worst-case time complexity:

  • Best Case: key is located at arr[0]. The loop terminates on the first iteration after comparison .
  • Worst Case: key is at arr[n - 1] or absent from the array. The loop checks all elements .

Average-case time complexity (assuming key is present with uniform probability at each index):

For :

Auxiliary space complexity: The function allocates only the loop variable i (the array pointer arr, n, and key occupy constant parameter space), regardless of . Therefore, auxiliary space complexity is .

Answer:
  • Best case: comparison,
  • Worst case: comparisons,
  • Average case: comparisons, (for , comparisons)
  • Auxiliary space complexity:
Example 4

4

Determine the exact number of times count++ executes as a function of in the nested loop below, express its tight asymptotic bound (), and verify the exact count for .

Triangular Nested LoopC
int count = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
        count++;
    }
}

Counting inner-loop iterations per outer iteration:

  • When , runs from to : execution.
  • When , runs from to : executions.
  • In general, for outer index , the inner loop executes times.

Summing over to :

Finding the asymptotic bound and evaluating at : Dropping the constant factor and the lower-order term gives . For :

Answer:

count++ executes times, which is ; for , it executes times.


Exercises

Exercises

Question 1

Define data structure and distinguish between primitive vs. non-primitive and linear vs. non-linear data structures with two examples of each.

Definition of data structure: A data structure is a systematic way of organizing, storing, and managing data in memory so that operations such as access, insertion, deletion, and searching can be performed efficiently.

Primitive vs. non-primitive data structures:

  • Primitive data types are built-in atomic types provided directly by the programming language (e.g., int, char, float, double).
  • Non-primitive data structures are derived structures composed of primitive or other non-primitive elements to represent relationships among data (e.g., arrays, linked lists, trees, graphs).

Linear vs. non-linear data structures:

  • Linear data structures store elements in a sequential, single-level order where each element (except the first and last) has a unique predecessor and successor. Examples: Array, Stack (also Linked List, Queue).
  • Non-linear data structures store elements hierarchically or as general networks where an element can connect to multiple elements across levels. Examples: Tree, Graph.
Answer:

A data structure organizes and stores data for efficient access and manipulation. Primitive types (int, char) are language-built atomic values, whereas non-primitive structures compose multiple elements into linear sequences (Array, Stack) or non-linear hierarchies/networks (Tree, Graph).

Question 2

What is an Abstract Data Type (ADT)? Explain why Stack or List is called an ADT by specifying its value definition and operator definition.

Definition of ADT: An Abstract Data Type (ADT) is a mathematical model that defines a data domain and the permissible operations on that data—along with their preconditions and effects—completely independent of any concrete memory representation or implementation language.

Why Stack is an ADT (Value & Operator Definition):

  • Value Definition: A finite ordered collection of elements of a given type arranged such that insertions and deletions occur only at one end called top.
  • Operator Definition:
    • push(S, x): inserts element x at the top of stack S (provided S is not full).
    • pop(S): removes and returns the top element of S (provided S is not empty).
    • peek(S): returns the top element without removing it.
    • isEmpty(S) / isFull(S): returns boolean status of stack emptiness or capacity.

Implementation independence: Whether Stack is implemented using a static array (items[MAX]) or a singly linked list, the external behavior of these operations remains identical to the caller.

Answer:

An ADT defines data values and operations independently of implementation. A Stack is an ADT because its LIFO behavior (push, pop, peek, isEmpty, isFull) is fully specified mathematically without committing to an array or linked-list implementation.

Question 3

Compare Divide and Conquer, Greedy Algorithms, and Dynamic Programming, giving one classical problem solved by each technique.

Divide and Conquer: Divides a problem into independent (non-overlapping) smaller subproblems, solves each recursively, and merges their solutions. Example: Merge Sort ().

Greedy Algorithms: Makes the locally optimal choice at each step and never backtracks or re-evaluates earlier choices. Works when the problem satisfies the greedy-choice property and optimal substructure. Example: Kruskal's Minimum Spanning Tree or Dijkstra's shortest path.

Dynamic Programming: Solves problems with overlapping subproblems and optimal substructure by solving each subproblem once and storing results in a table (tabulation) or cache (memoization) to avoid recomputation. Example: Knapsack or Longest Common Subsequence.

Answer:
  • Divide & Conquer: Independent subproblems solved recursively and combined (e.g., Merge Sort).
  • Greedy: Single locally best choice at every step without backtracking (e.g., Kruskal's MST).
  • Dynamic Programming: Caches solutions to overlapping subproblems (e.g., Knapsack).
Question 4

Define Big-Oh (), Big-Omega (), and Big-Theta () notations formally. Prove that by finding explicit constants and .

Formal definitions (for positive functions ):

  • : such that for all .
  • : such that for all .
  • : such that for all .

Proving : For all , and . Hence:

Choosing and (which is tight at where , and holds strictly for larger such as : and : ) satisfies .

Answer:

, , and specify asymptotic upper, lower, and tight bounds respectively. For , choosing and proves .

Question 5

Explain best-case, worst-case, and average-case analysis using Bubble Sort (with an early-exit swapped flag) on an array of elements. Calculate the exact number of element comparisons in the worst case for .

Best case (already sorted array): In the first pass ( comparisons), no swaps occur. The early-exit flag stops the algorithm immediately, giving comparisons .

Worst and average cases:

  • Worst case (reverse-sorted array): Pass makes comparisons, pass makes , ..., pass makes comparison. Total comparisons:
  • Average case (random order): Roughly half as many swaps and comparisons overall.

Evaluating the worst case for :

Answer:

Bubble Sort (with early exit) has best case , average case , and worst case with comparisons. For , the worst case performs comparisons.

Question 6

Arrange the following growth functions in ascending asymptotic order of growth rate: , , , , , , , . Briefly explain why rate of growth ignores constant factors when is large.

Ascending order of growth rates: Comparing values as (for instance, at , , , , , and ):

Why constant factors are ignored for large : Suppose Algorithm A takes steps and Algorithm B takes steps. Although A is slower for , for all , and the ratio grows without bound. Thus the growth-rate class ( vs. ) dominates performance at scale.

Answer:

Ascending order: . Constant factors only affect small inputs; for large , the dominant growth-rate class determines scalability.

Past exam questions for Data Structure and Algorithms

Definition of stack and its operations · Array implementation of… →