Data Structures and Algorithms

Infix to postfix using a stack

Operands stay in the order they appear; operators are held on a stack until operators of higher or equal precedence above them are popped. Precedence: ^ highest, then * /, then + -; ( has the lowest precedence while on the stack.

Algorithm

1. Create an empty stack and an empty output string.
2. Scan the infix expression from left to right.
3. If the symbol is an operand, append it to the output.
4. If the symbol is (, push it.
5. If the symbol is ), pop operators to the output until ( is found; discard both parentheses.
6. If the symbol is an operator, while the stack is not empty and the top is an operator of precedence greater than or equal to the current one (left associative), pop it to the output; then push the current operator.
7. After the scan, pop all remaining operators to the output.

Conversion of $(A+B)*C-D$

Postfix expression: $AB+C*D-$

Queue using a linked list

A queue follows FIFO order. With a singly linked list, keep two pointers: front (the first node, where deletion occurs) and rear (the last node, where insertion occurs). The queue can grow dynamically, so there is no overflow except when memory is exhausted.

struct node { int data; struct node *next; };
struct node *front = NULL, *rear = NULL;

Enqueue (insert at rear):

1. Create a new node, set its data and next = NULL.
2. If the queue is empty, set front = rear = new.
3. Otherwise set rear->next = new and rear = new.

Dequeue (delete from front):

1. If front == NULL, report underflow.
2. Otherwise save temp = front, set front = front->next.
3. If front becomes NULL, set rear = NULL.
4. Free temp and return its data.

Both operations take $O(1)$ time. Memory is allocated only as needed, at the cost of one extra pointer per element.

Applications of binary tree

A binary tree is a tree in which each node has at most two children (left and right).

Applications

1. Binary search tree (BST): searching, insertion and deletion in $O(\log n)$ on average.
2. Expression trees: evaluating and converting arithmetic expressions; traversals give prefix, infix and postfix forms.
3. Heap and priority queue: a complete binary tree used for heap sort and priority queues.
4. Huffman coding: a binary tree of character frequencies gives prefix codes for data compression.
5. Decision trees and game trees: each node represents a decision or a game state with two outcomes.
6. Routing and symbol tables: binary tries in routers, balanced trees (AVL, red-black) in compilers and databases.
7. Sorting: tree sort by inorder traversal of a BST.

Queue using a linked list

A queue (FIFO) can be built from a singly linked list with two pointers: front at the first node (deletion) and rear at the last node (insertion). It grows and shrinks dynamically with no fixed size.

struct node { int data; struct node *next; };
struct node *front = NULL, *rear = NULL;

Enqueue(x): allocate a node with data = x, next = NULL. If rear == NULL, set front = rear = node; else rear->next = node; rear = node.

Dequeue(): if front == NULL, underflow. Otherwise temp = front; front = front->next; if front == NULL set rear = NULL; free temp.

Both operations are $O(1)$. Unlike an array queue, no space is wasted and overflow occurs only when memory runs out; each node needs an extra pointer.

Applications of binary tree

A binary tree is a tree in which each node has at most two children (left and right).

Applications

1. Binary search tree (BST): searching, insertion and deletion in $O(\log n)$ on average.
2. Expression trees: evaluating and converting arithmetic expressions; traversals give prefix, infix and postfix forms.
3. Heap and priority queue: a complete binary tree used for heap sort and priority queues.
4. Huffman coding: a binary tree of character frequencies gives prefix codes for data compression.
5. Decision trees and game trees: each node represents a decision or a game state with two outcomes.
6. Routing and symbol tables: binary tries in routers, balanced trees (AVL, red-black) in compilers and databases.
7. Sorting: tree sort by inorder traversal of a BST.

Infix: $7 * 8 + 10 - 2$

Precedence: * is higher than + and -. + and - have equal precedence and are left associative.

Scan left to right. Operands go straight to the output. An operator pops from the stack every operator of greater or equal precedence, and is then pushed.

Postfix: 7 8 * 10 + 2 -

Check: $7\times 8=56$, $56+10=66$, $66-2=64$. This equals the value of the infix expression.

Shortest path algorithm

A shortest path algorithm finds a path between two vertices of a weighted graph such that the sum of the edge weights along the path is minimum. Dijkstra's algorithm solves the single-source shortest path problem for graphs with non-negative edge weights, in $O(V^2)$ with an array or $O((V+E)\log V)$ with a priority queue.

Dijkstra's algorithm

1. Set $dist(a)=0$ and $dist(v)=\infty$ for all other vertices; mark all vertices unvisited.
2. Pick the unvisited vertex $u$ with the smallest $dist$ and mark it visited (permanent).
3. For every unvisited neighbour $v$ of $u$: if $dist(u)+w(u,v) < dist(v)$, set $dist(v)=dist(u)+w(u,v)$ and $pred(v)=u$.
4. Repeat steps 2-3 until $z$ is visited (or all vertices are visited).
5. Trace the path back from $z$ using $pred$.

Worked example (graph with edges a-b 4, a-c 2, b-c 1, b-d 5, c-d 8, c-e 10, d-e 2, d-z 6, e-z 3)

Tracing predecessors: $z \leftarrow e \leftarrow d \leftarrow b \leftarrow c \leftarrow a$.

Shortest path: $a \to c \to b \to d \to e \to z$ with total length $2+1+5+2+3 = 13$.

Merge sort

Merge sort is a divide-and-conquer sorting algorithm.

1. Divide: split the array into two halves.
2. Conquer: recursively sort each half (an array of one element is already sorted).
3. Combine: merge the two sorted halves into one sorted array by repeatedly taking the smaller of the front elements of the two halves.

MergeSort(A, low, high)
  if low < high
     mid = (low + high) / 2
     MergeSort(A, low, mid)
     MergeSort(A, mid+1, high)
     Merge(A, low, mid, high)

Time complexity: the array is halved $\log_2 n$ times and each level needs $O(n)$ work to merge, so

$T(n) = 2T(n/2) + n \;\Rightarrow\; T(n) = O(n\log n)$

This holds for the best, average and worst cases. It needs $O(n)$ extra space and is stable.

Sorting 25, 37, 48, 25, 23, 17, 31, 45, 7, 21, 15, 8, 11

Divide:

• [25 37 48 25 23 17 31] and [45 7 21 15 8 11]
• [25 37 48 25] [23 17 31] and [45 7 21] [15 8 11]
• [25 37] [48 25] [23 17] [31] and [45 7] [21] [15 8] [11]

Merge:

• [25 37], [25 48], [17 23], [31], [7 45], [21], [8 15], [11]
• [25 25 37 48], [17 23 31], [7 21 45], [8 11 15]
• [17 23 25 25 31 37 48], [7 8 11 15 21 45]
• Final merge: 7, 8, 11, 15, 17, 21, 23, 25, 25, 31, 37, 45, 48

Data structure

A data structure is a way of organising, storing and managing data in a computer so that it can be accessed and modified efficiently. Examples: array, stack, queue, linked list, tree, graph. They are classified as primitive (int, char, float) and non-primitive (linear: array, list, stack, queue; non-linear: tree, graph).

Array as an abstract data type

An abstract data type (ADT) specifies a set of data and the operations on it, without saying how they are implemented. The array ADT is a fixed-size collection of elements of the same type, each identified by an index.

• Data: a sequence of $n$ elements of one type, stored in contiguous memory, with indices $0 \dots n-1$.
• Operations:
  • create(n): make an array of size $n$
  • get(i): return the element at index $i$
  • set(i, x): store $x$ at index $i$
  • insert(i, x), delete(i): add or remove an element, shifting others
  • traverse(), search(x), length()

Address of element $i$ is $\text{base} + i \times \text{size}$, so access is $O(1)$; insertion and deletion are $O(n)$ because of shifting. The user only uses the operations and need not know how the array is stored, which is what makes it an ADT.

Big O notation

Big O gives an asymptotic upper bound on the growth of a function, used for the worst-case running time of an algorithm.

$f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that

$f(n) \le c\,g(n) \quad \text{for all } n \ge n_0$

Example: $f(n) = 3n + 2$. For $n \ge 2$, $3n + 2 \le 3n + n = 4n$, so with $c = 4$ and $n_0 = 2$ we get $f(n) = O(n)$.

Similarly $5n^2 + 3n + 1 = O(n^2)$, since $5n^2 + 3n + 1 \le 9n^2$ for $n \ge 1$.

Common orders: $O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n)$. For example linear search is $O(n)$ and binary search is $O(\log n)$. Constants and lower-order terms are ignored.

Priority queue

A priority queue is a queue in which each element has a priority, and the element with the highest priority (or lowest, in a min-priority queue) is removed first, regardless of its arrival order. Elements of equal priority are served in FIFO order.

Implementation

1. Unsorted array or list: insert at the end in $O(1)$; deletion searches for the highest-priority element in $O(n)$.
2. Sorted array or list: insert at the correct position in $O(n)$; deletion removes the front element in $O(1)$.
3. Multiple queues: one ordinary queue per priority level; always dequeue from the non-empty queue with the highest priority.
4. Heap: a binary heap gives insertion and deletion both in $O(\log n)$. This is the most efficient implementation.

Basic operations: insert(item, priority), deleteHighest(), peek(), isEmpty().

Applications: CPU scheduling, Dijkstra's algorithm, Huffman coding, event simulation.

Recursion

Recursion is a technique in which a function calls itself, directly or indirectly, to solve a smaller instance of the same problem. A recursive function must have a base case (which stops the recursion) and a recursive case that moves towards the base case. Each call is kept on the call stack.

Tower of Hanoi

There are three pegs (source A, auxiliary B, destination C) and $n$ disks of different sizes stacked on A with the smallest on top. Move all the disks to C so that:

• only one disk is moved at a time,
• only the top disk of a peg can be moved,
• a larger disk is never placed on a smaller one.

Recursive solution:

1. Move the top $n-1$ disks from A to B using C.
2. Move the largest disk from A to C.
3. Move the $n-1$ disks from B to C using A.

TOH(n, A, B, C)
  if n == 1
     print "Move disk 1 from A to C"; return
  TOH(n-1, A, C, B)
  print "Move disk n from A to C"
  TOH(n-1, B, A, C)

Number of moves: $T(n) = 2T(n-1) + 1$, $T(1) = 1$, giving

$T(n) = 2^n - 1$

For $n=3$ the 7 moves are: A→C, A→B, C→B, A→C, B→A, B→C, A→C. The time complexity is $O(2^n)$.

Binary tree

A binary tree is a tree in which every node has at most two children, called the left child and the right child. It is either empty or consists of a root and a left and right subtree, each itself a binary tree. Types include full, complete, almost complete and binary search trees.

Applications

1. Binary search tree (BST): searching, insertion and deletion in $O(\log n)$ on average.
2. Expression trees: evaluating and converting arithmetic expressions; traversals give prefix, infix and postfix forms.
3. Heap and priority queue: a complete binary tree used for heap sort and priority queues.
4. Huffman coding: a binary tree of character frequencies gives prefix codes for data compression.
5. Decision trees and game trees: each node represents a decision or a game state with two outcomes.
6. Routing and symbol tables: binary tries in routers, balanced trees (AVL, red-black) in compilers and databases.
7. Sorting: tree sort by inorder traversal of a BST.

Sequential (linear) search

Sequential search examines the elements of a list one by one from the beginning, comparing each with the key, until a match is found or the list ends.

LinearSearch(A, n, key)
  for i = 0 to n-1
     if A[i] == key return i
  return -1

Time: best case $O(1)$, average and worst $O(n)$. It works on unsorted data and on linked lists.

Difference from binary search

Hashing

Hashing is a technique that maps a key to an index in a table using a hash function, $h(k)$, so that records can be stored and retrieved in $O(1)$ average time. For example $h(k) = k \bmod m$ for table size $m$.

Collision and quadratic probing

A collision occurs when two keys map to the same index. Quadratic probing is an open addressing method: if slot $h(k)$ is occupied, probe

$(h(k) + i^2) \bmod m, \quad i = 1, 2, 3, \dots$

This reduces the primary clustering of linear probing.

Example: table size $m = 10$, insert 23, 43, 13, 33 with $h(k)=k \bmod 10$.

• 23 goes to index 3.
• 43: index 3 is full; $i=1$: $(3+1) \bmod 10 = 4$, so it goes to index 4.
• 13: index 3 full; index 4 full; $i=2$: $(3+4) = 7$, so it goes to index 7.
• 33: index 3 full; 4 full; 7 full; $i=3$: $(3+9) \bmod 10 = 2$, so it goes to index 2.

Final table: index 2 = 33, 3 = 23, 4 = 43, 7 = 13.

Graph traversal

Graph traversal is visiting every vertex of a graph exactly once in a systematic way, starting from a given vertex. The two standard methods are breadth first search (BFS) and depth first search (DFS).

Breadth first search (BFS)

BFS visits the start vertex, then all its neighbours, then all their unvisited neighbours, and so on, level by level. It uses a queue and a visited array.

1. Mark the start vertex visited and enqueue it.
2. While the queue is not empty: dequeue a vertex $v$ and process it; for each unvisited neighbour $w$ of $v$, mark it visited and enqueue it.

Example: edges A-B, A-C, B-D, C-D, C-E, starting at A.

• Queue: A. Visit A; enqueue B, C.
• Visit B; enqueue D. Visit C; enqueue E.
• Visit D, then E.

BFS order: A, B, C, D, E.

Time complexity is $O(V+E)$ with an adjacency list. BFS finds the shortest path (fewest edges) in an unweighted graph.

Stack in recursion

Each recursive call creates an activation record (parameters, local variables and return address) that is pushed on the system stack. When a call finishes, its record is popped and control returns to the caller. This LIFO behaviour is what allows nested calls to return correctly. For example, fact(3) pushes fact(3), fact(2), fact(1), fact(0) and then pops them in reverse while multiplying.

Stack and its operations

A stack is a linear data structure in which insertion and deletion take place only at one end, the top (LIFO).

• push(x): add $x$ at the top (overflow if full).
• pop(): remove and return the top element (underflow if empty).
• peek()/top(): return the top element without removing it.
• isEmpty(), isFull().

All operations take $O(1)$ time.

Infix to postfix algorithm

1. Scan the infix expression left to right with an empty operator stack.
2. Operand: append to output.
3. (: push.
4. ): pop to output until (; discard the parentheses.
5. Operator: while the top of the stack is an operator with precedence greater than or equal to the current one, pop it to output; then push the current operator.
6. At the end, pop all remaining operators to output.

Example: $A+B*C$ becomes $ABC*+$, because * has higher precedence than + and stays above it on the stack.

Complete binary tree

A complete binary tree of height $h$ is a binary tree in which every level is completely filled, and every internal node has exactly two children. It has $2^{h+1}-1$ nodes (and $2^h$ leaves). A tree with all levels full is also called perfect.

Example, height 2:

        A
      /   \
     B     C
    / \   / \
   D   E F   G

Building the BST: 47, 50, 25, 27, 17, 61, 5, 26

• 47 is the root.
• 50 > 47: right of 47.
• 25 < 47: left of 47.
• 27 < 47, > 25: right of 25.
• 17 < 47, < 25: left of 25.
• 61 > 47, > 50: right of 50.
• 5 < 47, < 25, < 17: left of 17.
• 26 < 47, > 25, < 27: left of 27.

          47
        /    \
      25      50
     /  \       \
   17    27      61
   /    /
  5   26

Traversals

• Pre-order (root, left, right): 47, 25, 17, 5, 27, 26, 50, 61
• In-order (left, root, right): 5, 17, 25, 26, 27, 47, 50, 61
• Post-order (left, right, root): 5, 17, 26, 27, 25, 61, 50, 47

Quick sort

Quick sort is a divide-and-conquer algorithm.

1. Choose a pivot element (here, the first element).
2. Partition: rearrange so that all elements smaller than the pivot are before it and all larger ones after it; the pivot is now in its final place.
3. Recursively sort the left and right parts.

QuickSort(A, low, high)
  if low < high
     p = Partition(A, low, high)
     QuickSort(A, low, p-1)
     QuickSort(A, p+1, high)

Time: average and best $O(n\log n)$, worst $O(n^2)$ (already sorted input with first-element pivot). It sorts in place.

Sorting 35, 82, 18, 54, 13, 31, 20, 69, 19

• Pivot 35: smaller [18, 13, 31, 20, 19], larger [82, 54, 69] gives [18, 13, 31, 20, 19] 35 [82, 54, 69]
• Left part, pivot 18: [13] 18 [31, 20, 19]
• [31, 20, 19], pivot 31: [20, 19] 31
• [20, 19], pivot 20: [19] 20
• Right part [82, 54, 69], pivot 82: [54, 69] 82
• [54, 69], pivot 54: 54 [69]

Joining the pieces gives the sorted list:

13, 18, 19, 20, 31, 35, 54, 69, 82

Abstract data type (ADT)

An ADT is a mathematical model of a data structure defined by its data and the operations on it, with the implementation hidden from the user. Only what is done is specified, not how. Examples: stack, queue, list.

Array as an ADT

• Data: a fixed-size, ordered collection of $n$ elements of the same type, accessed by index $0 \dots n-1$ and stored in contiguous memory.
• Operations:
  • create(n): create an array of size $n$
  • get(i) / set(i, x): read or write the element at index $i$
  • insert(i, x) and delete(i): add or remove with shifting
  • search(x), traverse(), size()

Element address $= \text{base} + i \times \text{element size}$, giving $O(1)$ access; insertion and deletion are $O(n)$. Users work only through these operations, so the array's internal layout can change without affecting programs.

Time complexity

Time complexity of an algorithm is the amount of time it needs to run as a function of the input size $n$, measured by counting basic operations rather than seconds. It is expressed asymptotically as best, average and worst case.

Big O notation

$f(n) = O(g(n))$ if there are constants $c > 0$ and $n_0$ such that

$f(n) \le c\,g(n) \quad \text{for all } n \ge n_0$

It gives an upper bound (worst case).

Example: $f(n) = 2n^2 + 3n + 5$. For $n \ge 1$, $2n^2 + 3n + 5 \le 2n^2 + 3n^2 + 5n^2 = 10n^2$, so $c = 10$, $n_0 = 1$ and $f(n) = O(n^2)$.

A loop running $n$ times has $O(n)$; a nested double loop has $O(n^2)$; binary search has $O(\log n)$.

Priority queue

A priority queue is a queue in which every element has a priority and the element with the highest priority is removed first; equal priorities follow FIFO. It can be implemented using a sorted list, an unsorted list or (best) a heap.

Example: insert (task, priority): (A, 2), (B, 5), (C, 1). With larger number meaning higher priority, deletion returns B, then A, then C, although A arrived first. In an operating system, an interrupt handler gets served before a normal process.

Circular queue

A circular queue is a linear queue in which the last position is connected back to the first, forming a circle. Insertion is done at rear = (rear + 1) % n and deletion at front = (front + 1) % n. The queue is full when (rear + 1) % n == front. It reuses the space freed by deletions, which a simple linear array queue wastes.

Benefits of recursion

• Code is short, clear and closely mirrors the mathematical definition.
• Natural for problems with recursive structure: trees, graphs, divide-and-conquer (merge sort, quick sort), Tower of Hanoi, backtracking.
• Complex problems break into smaller identical subproblems, which makes them easier to design and prove correct.
• Reduces the need for explicit loops and extra variables.

(Drawbacks: stack overhead and possible stack overflow.)

Recursive function for the nth Fibonacci number

The sequence is $F_0 = 0$, $F_1 = 1$, $F_n = F_{n-1} + F_{n-2}$.

int fib(int n) {
    if (n == 0) return 0;      /* base case */
    if (n == 1) return 1;      /* base case */
    return fib(n - 1) + fib(n - 2);
}

Example: fib(5) = 5 (sequence 0, 1, 1, 2, 3, 5). This version takes $O(2^n)$ time because subproblems are recomputed.

Singly linked list

A singly linked list is a dynamic linear collection of nodes; each node contains data and a pointer to the next node. A head pointer holds the first node and the last node's next is NULL. Traversal is possible only in the forward direction.

struct node { int data; struct node *next; };

Example: head → [10|•] → [20|•] → [30|NULL]. Inserting 15 after 10 only changes two pointers: new->next = 10's next, then 10->next = new.

Singly vs doubly linked list

Collision

In hashing, a collision occurs when two different keys give the same hash value, $h(k_1) = h(k_2)$, so they compete for the same table slot.

Collision resolution

1. Separate chaining (open hashing): each slot holds a linked list of all keys that hash to it.
2. Open addressing (closed hashing): the key is placed in another empty slot of the table found by probing:
   • linear probing: $(h(k)+i) \bmod m$
   • quadratic probing: $(h(k)+i^2) \bmod m$
   • double hashing

Double hashing

Double hashing uses a second hash function to decide the step size of the probe sequence:

$(h_1(k) + i\cdot h_2(k)) \bmod m, \quad i = 0, 1, 2, \dots$

where $h_2(k) \neq 0$, for example $h_2(k) = 7 - (k \bmod 7)$. Different keys get different step sizes, which removes both primary and secondary clustering.

Example: $m = 10$, $h_1 = k \bmod 10$, $h_2 = 7 - (k \bmod 7)$. Insert 23 at index 3. Insert 43: index 3 is full; $h_2(43) = 7 - 1 = 6$, so try $(3+6) \bmod 10 = 9$, which is free.

Adjacency matrix representation

For a graph with $n$ vertices, the adjacency matrix is an $n \times n$ matrix $A$ where $A[i][j] = 1$ if there is an edge from vertex $i$ to vertex $j$, and $0$ otherwise. For a weighted graph, $A[i][j]$ stores the weight of the edge (with $\infty$ or 0 for no edge). The matrix of an undirected graph is symmetric.

Example: vertices 1, 2, 3, 4 with edges 1-2, 1-3, 2-4, 3-4.

$A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}$

For a directed graph with edges 1→2, 2→3, 3→1 the matrix has 1 only at positions (1,2), (2,3), (3,1).

• Checking whether an edge exists takes $O(1)$.
• Space is $O(n^2)$ regardless of the number of edges, so it suits dense graphs.
• The degree of a vertex is the sum of its row (undirected).

(a) Linear search

Linear search checks the elements of a list one after another from the first until the key is found or the list ends. It needs no sorted data.

for i = 0 to n-1
   if A[i] == key return i
return -1

Best case $O(1)$, average and worst case $O(n)$.

(b) Minimum spanning tree

A spanning tree of a connected weighted graph with $V$ vertices is a subgraph that is a tree containing all vertices, with $V-1$ edges. The minimum spanning tree (MST) is the spanning tree with the smallest total edge weight. It is found by Kruskal's algorithm (add the lightest edges that do not form a cycle) or Prim's algorithm (grow the tree from a vertex by the cheapest edge). Applications: laying cable, road and pipeline networks, network design.

Stack

A stack is a linear data structure in which insertion and deletion take place only at one end, called the top. It follows LIFO (last in, first out). It can be implemented with an array or a linked list.

Operations

• push(x): insert $x$ at the top; if the stack is full, report overflow.
• pop(): remove and return the top element; if empty, report underflow.
• peek(): return the top element without removing it.
• isEmpty() and isFull().

Each operation takes $O(1)$ time.

Algorithm to evaluate a postfix expression

1. Create an empty operand stack.
2. Scan the postfix expression left to right.
3. If the symbol is an operand, push it.
4. If it is an operator, pop two operands: first b (top) then a; compute a op b; push the result.
5. At the end, the single value on the stack is the result.

Example: $5\ 3\ 2\ *\ +\ 4\ -$

• Push 5, 3, 2.
• *: pop 2 and 3, push $3 \times 2 = 6$. Stack: 5, 6.
• +: pop 6 and 5, push 11.
• Push 4. -: pop 4 and 11, push $11 - 4 = 7$.

Result: 7.

Almost complete binary tree

An almost complete binary tree is a binary tree in which every level except possibly the last is completely filled, and the nodes of the last level are as far left as possible. A binary heap is such a tree, and it can be stored in an array (children of node $i$ at $2i+1$ and $2i+2$).

        10
      /    \
     20     30
    /  \   /
   40  50 60

Binary search tree (BST) operations

In a BST, for every node, all keys in the left subtree are smaller and all keys in the right subtree are larger.

Search(key): start at the root; if equal, found; if smaller go left, else go right; if NULL is reached, not found. Time $O(h)$.

Insert(key): search for the key; the NULL position where the search ends is where the new node is attached. Example: inserting 50, 30, 70, 20, 40 gives root 50, left 30 (children 20, 40), right 70. Inserting 35 goes 50 → left to 30 → right to 40 → left of 40.

Delete(key): three cases.

1. Leaf node: remove it.
2. One child: replace the node by its child.
3. Two children: replace the node's key by its inorder successor (smallest in the right subtree) or predecessor, then delete that node.

Example: deleting 30 (children 20 and 40) in the tree above replaces it by its successor 35 (or 40), then removes the successor node.

All three operations take $O(h)$: $O(\log n)$ for a balanced tree and $O(n)$ in the worst (skewed) case.

Limitation of choosing the first element as pivot

If the array is already sorted (ascending or descending), or nearly so, the first element is the smallest or largest, so each partition splits the array into parts of sizes $0$ and $n-1$. The recursion depth becomes $n$ and the running time degrades to

$T(n) = T(n-1) + n = O(n^2)$

instead of $O(n\log n)$. It also causes deep recursion (stack overflow risk). Remedies: choose a random pivot, the median of three, or the middle element.

Merge sort of 40, 6, 5, 21, 3, 100, 90, 7, 8, 12, 30

Divide:

• [40 6 5 21 3 100] and [90 7 8 12 30]
• [40 6 5] [21 3 100] and [90 7 8] [12 30]
• [40 6] [5] [21 3] [100] and [90 7] [8] [12] [30]

Merge:

• [6 40], [5] gives [5 6 40]; [3 21], [100] gives [3 21 100]
• [5 6 40] and [3 21 100] give [3 5 6 21 40 100]
• [7 90], [8] gives [7 8 90]; [12 30]
• [7 8 90] and [12 30] give [7 8 12 30 90]
• Final merge: 3, 5, 6, 7, 8, 12, 21, 30, 40, 90, 100

Data type

A data type defines a set of values and the operations allowed on them, for example int, float, char. It also fixes the memory size and representation.

Abstract data type (ADT)

An ADT is a logical description of data and the operations on it, independent of any implementation. The user knows what operations exist and what they do, not how they are coded. Examples: stack (push, pop), queue (enqueue, dequeue), list.

Benefits of using ADT

• Abstraction and information hiding: implementation details are hidden.
• Modularity: the implementation can be changed (array to linked list) without changing the code that uses it.
• Reusability: one ADT can be used in many programs.
• Easier maintenance and debugging: errors are localised.
• Clear specification that helps teamwork and correctness.

Space complexity

Space complexity is the amount of memory an algorithm needs as a function of input size $n$. It includes the fixed part (code, constants, simple variables) and the variable part (input data, recursion stack, dynamic memory): $S(P) = c + S_p(n)$. For example an iterative sum of an array needs $O(1)$ extra space; merge sort needs $O(n)$; a recursive factorial uses $O(n)$ stack space.

Omega ($\Omega$) notation

Omega gives an asymptotic lower bound. $f(n) = \Omega(g(n))$ if there are constants $c > 0$ and $n_0$ such that

$f(n) \ge c\,g(n) \quad \text{for all } n \ge n_0$

Example: $f(n) = 3n + 2$. Since $3n + 2 \ge 3n$ for all $n \ge 1$, with $c = 3$ and $n_0 = 1$ we get $f(n) = \Omega(n)$. It is used for best-case running time, for example linear search is $\Omega(1)$.

Circular queue

A circular queue is a queue in which the last position of the array is connected to the first, so the array is treated as a circle. It overcomes the wasted space of a linear array queue, where freed slots at the front cannot be reused after rear reaches the end.

Implementation using an array of size N

Initially front = rear = -1.

Enqueue(x):

1. If (rear + 1) % N == front, the queue is full: overflow.
2. If the queue is empty (front == -1), set front = 0.
3. rear = (rear + 1) % N; Q[rear] = x.

Dequeue():

1. If front == -1, the queue is empty: underflow.
2. x = Q[front].
3. If front == rear, the queue becomes empty: set front = rear = -1; otherwise front = (front + 1) % N.
4. Return x.

Both operations take $O(1)$ time. The modulus makes the indices wrap around to 0 after $N-1$.

Recursion

Recursion is a technique in which a function calls itself to solve smaller instances of the same problem. It needs a base case to stop and a recursive case that moves towards it. Example: $n! = n \times (n-1)!$ with $0! = 1$.

Tower of Hanoi (TOH)

Given three pegs A (source), B (auxiliary), C (destination) and $n$ disks of decreasing size on A, move all disks to C, moving one disk at a time, taking only the top disk, and never placing a larger disk on a smaller one.

Recursive idea: move $n-1$ disks A→B, move the largest disk A→C, move $n-1$ disks B→C.

TOH(n, A, B, C)
  if n == 0 return
  TOH(n-1, A, C, B)
  print "Move disk n from A to C"
  TOH(n-1, B, A, C)

Example, $n = 3$ (7 moves): disk 1 A→C, disk 2 A→B, disk 1 C→B, disk 3 A→C, disk 1 B→A, disk 2 B→C, disk 1 A→C.

Number of moves $= 2^n - 1$, so the time complexity is $O(2^n)$.

Need for hashing

Searching in an array or list takes $O(n)$ and in a balanced tree or sorted array $O(\log n)$. Hashing uses a hash function $h(k)$ to compute the table index of a key directly, giving $O(1)$ average time for insertion, search and deletion. It is used in symbol tables, databases, caches, password storage and dictionaries, especially for large data.

Quadratic probing

A collision happens when two keys hash to the same slot. Quadratic probing resolves it in an open addressing table of size $m$ by trying the slots

$(h(k) + i^2) \bmod m, \quad i = 0, 1, 2, \dots$

until an empty slot is found. It avoids the primary clustering of linear probing, but keys with the same initial hash follow the same probe sequence (secondary clustering).

Example: $m = 11$, $h(k) = k \bmod 11$; insert 22, 33, 44.

• 22 goes to index 0.
• 33: index 0 is full; $i=1$: index 1 is free, so 33 goes to index 1.
• 44: index 0 full; index 1 full; $i=2$: $(0+4) = 4$, so 44 goes to index 4.

Spanning tree

A spanning tree of a connected undirected graph $G$ with $V$ vertices is a subgraph that includes all vertices, is connected and has no cycles; it therefore has exactly $V - 1$ edges.

Minimum spanning tree (MST)

In a weighted graph, the MST is the spanning tree whose total edge weight is the smallest. Algorithms:

• Kruskal's: sort edges by weight and add each edge if it does not form a cycle.
• Prim's: start from any vertex and repeatedly add the cheapest edge connecting the tree to a new vertex.

Example: vertices A, B, C, D; edges AB = 1, AC = 4, BC = 2, BD = 5, CD = 3.

Kruskal: AB (1) added, BC (2) added, CD (3) added; the tree now has 3 edges $= V-1$, so stop. (AC would form a cycle.)

MST edges: AB, BC, CD with total weight $1 + 2 + 3 = 6$.

Applications: designing least-cost networks, such as electricity, telephone, water and road networks.

(a) Doubly circular linked list

A doubly circular linked list is a linked list in which each node has prev, data and next fields, and the last node's next points to the first node while the first node's prev points to the last. There is no NULL pointer. It can be traversed in both directions starting from any node, and insertion or deletion at either end is $O(1)$ if a pointer to the first node is kept. Used in playlists and round-robin scheduling.

struct node { struct node *prev; int data; struct node *next; };

(b) Breadth first search (BFS)

BFS is a graph traversal that visits the start vertex, then all of its neighbours, then their neighbours, level by level. It uses a queue: enqueue the start vertex and mark it visited; repeatedly dequeue a vertex, visit it, and enqueue its unvisited neighbours. Time is $O(V+E)$. For edges A-B, A-C, B-D, C-D starting at A, the order is A, B, C, D. It finds shortest paths in unweighted graphs.

Need for sorting

Sorting arranges data in ascending or descending order. It makes searching much faster (binary search needs sorted data, $O(\log n)$ against $O(n)$), makes duplicates and ranges easy to find, helps in merging data sets, and presents data in a readable form (reports, ranked lists, directories). Many other algorithms use sorted data.

Quick sort trace (first element as pivot) for {12, -9, 56, 23, 4, 8, 6, 9, 23, 21}

1. Pivot 12: smaller [-9, 4, 8, 6, 9], larger or equal [56, 23, 23, 21] gives [-9, 4, 8, 6, 9] 12 [56, 23, 23, 21]
2. Left part, pivot -9: -9 [4, 8, 6, 9]
3. [4, 8, 6, 9], pivot 4: 4 [8, 6, 9]
4. [8, 6, 9], pivot 8: [6] 8 [9]
5. Right part [56, 23, 23, 21], pivot 56: [23, 23, 21] 56
6. [23, 23, 21], pivot 23: [21] 23 [23]

Combining all parts in order:

-9, 4, 6, 8, 9, 12, 21, 23, 23, 56

Average time is $O(n\log n)$, worst case $O(n^2)$.

Primitive data type

A primitive data type is a basic type built into the language, which holds a single value and is not made from other types. Examples in C: int, float, double, char. (Non-primitive types such as arrays, structures and lists are built from these.)

Advantages of hashing

• Insertion, search and deletion in $O(1)$ average time.
• Far faster than linear or binary search for large data.
• Needs no sorted data.
• Efficient use in dictionaries, symbol tables, caches and databases.

Hash collision example and handling

Take table size $m = 7$ and $h(k) = k \bmod 7$. Insert 15, 22 and 29: $15 \bmod 7 = 1$, $22 \bmod 7 = 1$ and $29 \bmod 7 = 1$. All three keys map to index 1, which is a collision.

1. Separate chaining: each slot keeps a linked list. Index 1 holds 15 → 22 → 29.

2. Linear probing (open addressing): place the key in the next free slot, $(h(k) + i) \bmod m$.

• 15 goes to index 1.
• 22: index 1 full, so it goes to index 2.
• 29: indices 1 and 2 full, so it goes to index 3.

Other open addressing methods are quadratic probing and double hashing. Search follows the same probe sequence until the key or an empty slot is found.

Static and dynamic list structures

Stack using a linked list

Use a singly linked list with a top pointer to the first node; both push and pop happen at the head.

struct node { int data; struct node *next; };
struct node *top = NULL;

• push(x): create a node; node->next = top; top = node;
• pop(): if top == NULL, underflow; else temp = top; top = top->next; free temp and return its data.

Both take $O(1)$ and there is no overflow until memory is exhausted.

Queue using a linked list

Keep front (first node) and rear (last node).

• enqueue(x): create a node with next = NULL; if the queue is empty, front = rear = node; else rear->next = node; rear = node.
• dequeue(): if front == NULL, underflow; else temp = front; front = front->next; if front == NULL, set rear = NULL; free temp.

Both take $O(1)$. The structure grows dynamically and wastes no memory.

Need for circular queue

In a simple linear queue implemented with an array of size $N$, deletion advances front and insertion advances rear. Once rear reaches $N-1$ the queue is declared full, even if many slots at the front have been freed by deletions. Space is wasted and the queue cannot be used again unless all elements are shifted or the queue is reset.

A circular queue treats the array as a ring: after the last index, rear and front wrap round to index 0 using

$\text{rear} = (\text{rear}+1) \bmod N, \qquad \text{front} = (\text{front}+1) \bmod N$

Hence freed slots are reused and the queue is full only when all $N$ slots (or $N-1$, with the usual convention (rear+1) % N == front) are actually occupied.

Example: $N = 5$ holding 3 elements at indices 2, 3, 4 with front = 2. A linear queue says "full" at once; a circular queue can still insert at indices 0 and 1.

Advantages: efficient memory use, $O(1)$ insertion and deletion, no shifting. Used in CPU scheduling, buffers (keyboard, printer) and traffic systems.

Consider the graph with vertices A, B, C, D, E, F and edges A–B, A–C, B–D, B–E, C–F, E–F. Neighbours are visited in alphabetical order, and the start vertex is A.

BFS (queue based)

BFS visits all vertices at distance 1, then distance 2, and so on, using a queue.

1. Enqueue A and mark it visited. Queue: A.
2. Dequeue A, and enqueue its unvisited neighbours B, C. Queue: B, C.
3. Dequeue B, and enqueue D, E. Queue: C, D, E.
4. Dequeue C, and enqueue F. Queue: D, E, F.
5. Dequeue D, E, F. None has unvisited neighbours.

BFS order: A, B, C, D, E, F

DFS (stack or recursion based)

DFS goes as deep as possible along one path before backtracking.

1. Visit A, then go to B.
2. From B go to D. D is a dead end, so backtrack to B.
3. From B go to E, then to F (unvisited neighbour of E).
4. From F go to C (unvisited neighbour of F). C's neighbours A and F are already visited, so backtrack until the stack is empty.

DFS order: A, B, D, E, F, C

BFS uses a queue (FIFO) and DFS uses a stack (LIFO). Both run in $O(V+E)$ time when an adjacency list is used.

In a doubly circular linked list each node has prev, data and next fields. The next of the last node points to the first node, and the prev of the first node points to the last node. Let head point to the first node.

Insertion at the first position

1. Create a new node n with the given data.
2. If the list is empty, set n->next = n, n->prev = n and head = n.
3. Otherwise let last = head->prev.
   • n->next = head
   • n->prev = last
   • last->next = n
   • head->prev = n
   • head = n

Insertion at the last position

Steps 1 and 2 are the same. Otherwise let last = head->prev.

• n->next = head
• n->prev = last
• last->next = n
• head->prev = n

head is not changed. Both insertions take $O(1)$ time because the last node is reached through head->prev.

Deletion of the first node

1. If the list is empty, report underflow.
2. If head->next == head (one node), free it and set head = NULL.
3. Otherwise let last = head->prev and temp = head.
   • head = head->next
   • head->prev = last
   • last->next = head
   • free temp

Deletion of the last node

1. If the list is empty, report underflow.
2. If there is only one node, free it and set head = NULL.
3. Otherwise let last = head->prev.
   • last->prev->next = head
   • head->prev = last->prev
   • free last

All four operations take $O(1)$ time.

Time complexity is the amount of time an algorithm takes as a function of the input size $n$. It is usually expressed with asymptotic notation such as $O(n)$ or $O(n\log n)$. Space complexity is the total memory an algorithm needs as a function of $n$, including the input, auxiliary variables and stack space.

Round Robin algorithm for Minimum Spanning Tree

The round robin algorithm (Yao, Cheriton and Tarjan) builds an MST by growing many trees in turn. It uses the cut property: the cheapest edge leaving any tree of the forest belongs to some MST.

1. Make each vertex a separate tree. Put all the trees in a queue. Give each tree a priority queue of its incident edges.
2. Remove the tree $T$ at the front of the queue.
3. Find the minimum weight edge $e$ leaving $T$. Edges that join two vertices of the same tree are discarded.
4. Add $e$ to the MST, merge $T$ with the tree $T'$ at the other end of $e$, and merge their edge lists.
5. Put the merged tree at the back of the queue.
6. Repeat until only one tree remains.

Trees are taken in round robin (queue) order, so every tree gets a turn to grow and small trees are merged first. The result is a spanning tree of minimum total weight. With mergeable heaps the running time is $O(E\log\log V)$. Kruskal's and Prim's algorithms are $O(E\log V)$.

Take the binary tree with root 1, left child 2 and right child 3. Node 2 has children 4 (left) and 5 (right), and node 3 has left child 6.

Pre-order (Root, Left, Right)

Visit the root, then traverse the left subtree, then the right subtree.

1 → 2 → 4 → 5 → 3 → 6

Pre-order: 1, 2, 4, 5, 3, 6

In-order (Left, Root, Right)

Traverse the left subtree, then visit the root, then traverse the right subtree.

4 → 2 → 5 → 1 → 6 → 3

In-order: 4, 2, 5, 1, 6, 3

Recursive form:

void preorder(Node *t){ if(t){ printf("%d ",t->data); preorder(t->left); preorder(t->right);} }
void inorder(Node *t){ if(t){ inorder(t->left); printf("%d ",t->data); inorder(t->right);} }

For a binary search tree, in-order traversal gives the keys in sorted order.

Binary tree: a tree in which every node has at most two children, called the left child and the right child. It may be empty.

Binary search tree (BST): a binary tree in which, for every node, all keys in the left subtree are smaller than the node's key and all keys in the right subtree are larger. In-order traversal of a BST gives the keys in sorted order.

Applications of binary trees

• Expression trees, used by compilers to parse and evaluate expressions.
• Binary search trees, for fast searching, insertion and deletion.
• Heaps, used for priority queues and heap sort.
• Huffman coding trees for data compression.
• Decision trees and game trees.
• Routing tables and the hierarchical organisation of data.

Limitations of recursion

• Each call uses stack memory, so deep recursion can cause stack overflow.
• Function call overhead makes recursion slower than an equivalent loop.
• Repeated subproblems may be recomputed, as in naive Fibonacci, giving exponential time.
• It is harder to trace and debug.
• A missing or wrong base case causes infinite recursion.

Deleting a node from a BST

First search for the node with the given key. Then there are three cases.

1. Leaf node (no child): remove it by setting the parent's pointer to NULL.
2. One child: replace the node by its child. The parent now points to that child.
3. Two children: find the in-order successor (the smallest node in the right subtree) or the in-order predecessor (the largest node in the left subtree). Copy its key into the node being deleted. Then delete the successor from the right subtree. The successor has at most one child, so this reduces to case 1 or 2.

Example: deleting 50 from a BST with root 50, left child 30, right child 70, where 70 has left child 60. The successor is 60. Replace 50 by 60 and remove the old node 60.

The time taken is $O(h)$, where $h$ is the height of the tree.

Simple queue: a linear data structure that follows the FIFO (First In First Out) principle. Insertion (enqueue) takes place at the rear and deletion (dequeue) takes place at the front. It is implemented with an array or linked list using the pointers front and rear. In an array implementation the freed space at the front cannot be reused, which is a drawback.

Types of graphs (any three)

1. Undirected graph: the edges have no direction, so edge $(u,v)$ is the same as $(v,u)$. Example: a friendship network.
2. Directed graph (digraph): each edge is an ordered pair $(u,v)$ with a direction from $u$ to $v$. Example: web page links.
3. Weighted graph: each edge carries a weight such as distance or cost. It is used in shortest path and MST problems.
4. Complete graph: every pair of distinct vertices is joined by an edge. It has $n(n-1)/2$ edges when undirected.
5. Cyclic and acyclic graph: a cyclic graph contains a cycle. A directed acyclic graph (DAG) has none.

(a) Hash function

A hash function maps a key to an index of a hash table, $h(k)\to\{0,\dots,m-1\}$, so that the record can be stored and found in near constant time. A common choice is the division method $h(k)=k \bmod m$. A good hash function is quick to compute and spreads keys uniformly to reduce collisions. When two keys map to the same index, collisions are resolved by chaining or open addressing.

(b) Types of graph

• Undirected graph: edges have no direction.
• Directed graph: edges are ordered pairs showing direction.
• Weighted graph: edges have weights or costs.
• Complete graph: every pair of vertices is connected.
• Cyclic graph / DAG: a graph that contains a cycle, and a directed graph with no cycle.
• Connected and disconnected graph: whether there is a path between every pair of vertices.

(c) Working of BFS

Breadth First Search traverses a graph level by level from a source vertex, using a queue.

1. Mark the source visited and enqueue it.
2. While the queue is not empty, dequeue a vertex $u$ and process it.
3. For each unvisited neighbour of $u$, mark it visited and enqueue it.
4. Stop when the queue is empty.

For example, in a graph with edges A–B, A–C, B–D, C–D starting at A, the order is A, B, C, D.

BFS(G, s):
  mark s visited; enqueue(Q, s)
  while Q not empty:
     u = dequeue(Q); visit(u)
     for each neighbour v of u:
        if v not visited: mark v; enqueue(Q, v)

The time complexity is $O(V+E)$ with an adjacency list. BFS finds the shortest path (fewest edges) in an unweighted graph.

Conclusion: both have $O(n\log n)$ average time. Quick sort is in-place and usually faster, but its worst case is $O(n^2)$ and it is not stable. Merge sort guarantees $O(n\log n)$ and is stable, but it needs extra memory.

Balanced tree

A balanced tree is a tree in which the heights of the left and right subtrees of every node differ by a limited amount, for example at most 1 in an AVL tree. This keeps the height at $O(\log n)$, so search, insertion and deletion take $O(\log n)$ time. Examples are AVL trees and red-black trees. An unbalanced BST can degenerate into a linked list with height $n$.

Insertion in a BST

1. If the tree is empty, the new node becomes the root.
2. Otherwise compare the key with the current node. Go left if it is smaller and right if it is larger. Duplicates are usually rejected.
3. When a NULL position is reached, attach the new node there.

Node* insert(Node* root, int key){
  if(root==NULL) return newNode(key);
  if(key < root->data) root->left = insert(root->left, key);
  else if(key > root->data) root->right = insert(root->right, key);
  return root;
}

Inserting 50, 30, 70, 20 gives 50 as root, 30 as its left child, 70 as its right child, and 20 as the left child of 30.

Deletion in a BST

Search for the node, then handle three cases.

1. Leaf: remove the node and set the parent's link to NULL.
2. One child: link the parent directly to the node's only child and free the node.
3. Two children: replace the node's key with its in-order successor (the minimum of the right subtree), or its in-order predecessor. Then delete that successor node from the right subtree. It has at most one child.

Node* delete(Node* root, int key){
  if(!root) return NULL;
  if(key < root->data) root->left = delete(root->left, key);
  else if(key > root->data) root->right = delete(root->right, key);
  else {
    if(!root->left){ Node* t=root->right; free(root); return t; }
    if(!root->right){ Node* t=root->left; free(root); return t; }
    Node* s=root->right; while(s->left) s=s->left;
    root->data=s->data;
    root->right=delete(root->right, s->data);
  }
  return root;
}

Both operations take $O(h)$ time, which is $O(\log n)$ for a balanced tree and $O(n)$ in the worst case.

Merits of sequential search over binary search

• The data need not be sorted. Binary search needs sorted data.
• It is simple to understand and implement.
• It works on linked lists and on any sequential structure. Binary search needs random access, as in arrays.
• It is efficient for small lists and when the item is near the start.
• No time is spent sorting or maintaining order, so it suits data that changes often.

Demerits of sequential search over binary search

• It is slow for large data: $O(n)$ comparisons in the worst and average case, against $O(\log n)$ for binary search.
• It does not exploit any ordering of the data.
• For repeated searches on a large static data set it is far less efficient.

For example, in a sorted list of 1,000,000 items, sequential search may need up to 1,000,000 comparisons while binary search needs about 20.

Consider a tree with root A. A has children B and C. B has children D and E, and E has child F.

Level: the number of edges (or nodes, by convention) on the path from the root to the node. The root is at level 0 (some books use level 1). Here A is at level 0, B and C at level 1, D and E at level 2, and F at level 3.

Depth of a node: the number of edges on the path from the root to that node. The depth of the root is 0. Here depth(E) = 2 and depth(F) = 3. Depth is the same as level when levels start at 0.

Height of a node: the number of edges on the longest path from the node down to a leaf. Leaves have height 0. Here height(F) = 0, height(E) = 1, height(B) = 2, and height(C) = 0.

Height of the tree: the height of the root. Here the height of the tree is 3, which is the maximum level.

In short, depth and level are counted downward from the root, and height is counted upward from the leaves.

To insert a new node at the $n$th position in a singly linked list, traverse to the node at position $n-1$, then relink.

Steps

1. Create a new node newNode and store the data in it.
2. If $n=1$, insert at the beginning: newNode->next = head; head = newNode;.
3. Otherwise set temp = head and move it forward $n-2$ times, so that temp points to the $(n-1)$th node. If temp becomes NULL, the position is invalid.
4. Set newNode->next = temp->next.
5. Set temp->next = newNode.

The order of steps 4 and 5 matters. If temp->next is changed first, the rest of the list is lost.

void insertAt(Node **head, int data, int n){
  Node *nn = malloc(sizeof(Node)); nn->data = data;
  if(n==1){ nn->next=*head; *head=nn; return; }
  Node *t=*head;
  for(int i=1; i<n-1 && t; i++) t=t->next;
  if(!t){ printf("Invalid position"); free(nn); return; }
  nn->next=t->next; t->next=nn;
}

Example: for the list 10 → 20 → 40, inserting 30 at position 3 gives 10 → 20 → 30 → 40. The time complexity is $O(n)$.

Both lists use nodes with prev, data and next fields. The only structural difference is that the circular version links the ends together.

The Fibonacci series is 0, 1, 1, 2, 3, 5, 8, ... defined by $F(0)=0$, $F(1)=1$, $F(n)=F(n-1)+F(n-2)$.

#include <stdio.h>

int fib(int n){
    if(n == 0) return 0;      /* base case */
    if(n == 1) return 1;      /* base case */
    return fib(n-1) + fib(n-2);
}

int main(){
    int n, i;
    printf("Enter number of terms: ");
    scanf("%d", &n);
    printf("Fibonacci series: ");
    for(i = 0; i < n; i++)
        printf("%d ", fib(i));
    return 0;
}

For $n=7$ the output is 0 1 1 2 3 5 8.

The two base cases stop the recursion. This version recomputes values many times, so its time complexity is $O(2^n)$ and its stack depth is $O(n)$. Memoization or an iterative version brings the time down to $O(n)$.

A linear queue is a FIFO structure in which insertion occurs at the rear and deletion at the front, stored in a linear array.

Advantages

• It is simple to understand and implement.
• Enqueue and dequeue take $O(1)$ time.
• It processes elements in arrival order, which is fair. It is useful for scheduling, buffering and BFS.
• It is easy to check whether the queue is empty or full.

Disadvantages

• Memory is wasted. Space freed by dequeued elements at the front cannot be reused, because rear reaches the end of the array even when space is free at the front. This is false overflow.
• The size is fixed in an array implementation, so overflow can occur.
• Only the front can be removed. There is no random access or direct search.
• Reusing space requires shifting elements, which costs $O(n)$, or switching to a circular queue.

Stack: a linear data structure that follows the LIFO (Last In First Out) principle. Insertion (push) and deletion (pop) take place at one end only, called the top.

Evaluation of the prefix expression + * 3 4 2

Scan the expression from right to left. Push operands. For an operator, pop the top as operand 1 and the next as operand 2, compute (operand 1 operator operand 2), and push the result.

Result: 14

This is the prefix form of $(3\times 4)+2 = 14$.

Structure

A structure is a user-defined data type that groups variables of different data types under one name. Each variable is a member. It is declared with the struct keyword.

struct Student {
    int roll;
    char name[30];
    float marks;
};
struct Student s1;

Members are accessed with the dot operator, s1.roll. Structures are the basis of records and of nodes in linked lists and trees.

Time complexity

The amount of time an algorithm needs to run, as a function of the input size $n$. It counts the basic operations executed, not seconds. It is expressed in Big-O: $O(1)$ constant, $O(\log n)$ logarithmic, $O(n)$ linear, $O(n\log n)$, $O(n^2)$ quadratic. Cases are classified as best, average and worst.

Space complexity

The total memory an algorithm needs as a function of $n$. It includes the fixed part (code, constants, simple variables) and the variable part (input, dynamic memory, recursion stack). For example, iterative sum of an array uses $O(1)$ extra space, and merge sort uses $O(n)$.

Time and space are often in trade-off, and a good algorithm keeps both low.