Unit5 - Subjective Questions

Definition:
A Data Structure is a specialized format for organizing, processing, retrieving, and storing data. It enables efficient access and modification of data.

Classification:
Data structures are primarily classified into two categories based on data organization:

1. Linear Data Structures:

   • Data elements are arranged sequentially or linearly, where each element is attached to its previous and next adjacent elements.
   • Examples:
     • Arrays: Fixed-size collection of elements of the same type.
     • Linked Lists: Elements are stored in nodes containing data and a reference to the next node.
     • Stacks: Follows LIFO (Last In First Out).
     • Queues: Follows FIFO (First In First Out).

2. Non-Linear Data Structures:

   • Data elements are not arranged sequentially. There is a hierarchical relationship between individual elements.
   • Examples:
     • Trees: Represents hierarchical data (e.g., file systems).
     • Graphs: Represents a network of connected nodes (e.g., social networks).

Comparison between Singly Linked List (SLL) and Doubly Linked List (DLL):

Stack Definition:
A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The insertion and deletion of elements happen at only one end, known as the Top.

Operations:

1. PUSH Operation (Insertion):
   Adds an element to the top of the stack. Requires checking for Overflow (if stack is full).

   • Algorithm:
     1. Check if TOP == MAX_SIZE - 1. If yes, print "Stack Overflow" and exit.
     2. Increment TOP by 1 (TOP = TOP + 1).
     3. Insert new element at STACK[TOP].

2. POP Operation (Deletion):
   Removes the top element from the stack. Requires checking for Underflow (if stack is empty).

   • Algorithm:
     1. Check if TOP == -1. If yes, print "Stack Underflow" and exit.
     2. Store STACK[TOP] in a variable (to return value).
     3. Decrement TOP by 1 (TOP = TOP - 1).

Circular Queue:
A Circular Queue is a linear data structure in which the operations are performed based on the FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle.

Limitation of Linear Queue:
In a standard linear queue, once the Rear reaches the end of the array, no more elements can be inserted even if there is empty space at the beginning of the array (caused by dequeuing). This results in memory wastage.

Solution:
A Circular Queue utilizes this empty space by connecting the end to the beginning.

Logic for Insertion (EnQueue):
Instead of simply incrementing the rear pointer (), we use the modulo operator to wrap around:

Similarly for DeQueue:

Application of Stacks:
Stacks are essential for expression evaluation and conversion because they can reverse the order of operations and handle operator precedence and associativity.

Conversion Logic:

1. Operands (A, B, C...) are output immediately.
2. Operators (+, -, *, /) are pushed onto the stack based on precedence. Higher precedence operators push lower ones out.
3. Parentheses control the scope.

Step-by-Step Conversion of :

Final Postfix Expression:

Definition:
A Binary Search Tree (BST) is a node-based binary tree data structure which has the following properties:

1. The left subtree of a node contains only nodes with keys lesser than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtrees must also be binary search trees.

Insertion Process:
To insert a new key :

1. Start at the root.
2. Compare with the current node's key.
   • If , move to the left child.
   • If , move to the right child.
3. Repeat until a leaf is reached (NULL pointer).
4. Insert the new node at this position.

Example: Insert 40 into BST with Root 50.

• Root is 50. Compare 40 with 50.
• , so go Left.
• If Left is NULL, insert 40 there.

AVL Trees:
An AVL (Adelson-Velsky and Landis) tree is a self-balancing Binary Search Tree (BST). It ensures that the tree remains balanced to guarantee logarithmic time complexity for operations.

Need for AVL Trees:
In a standard BST, if data is inserted in sorted order (e.g., 1, 2, 3, 4, 5), the tree becomes skewed (resembling a Linked List). The time complexity for search/insert/delete degrades to . AVL trees keep the height close to , ensuring operations remain .

Balance Factor (BF):
The Balance Factor of a node is the difference between the height of the left subtree and the right subtree.

In an AVL tree, the Balance Factor of every node must be either -1, 0, or 1. If it goes outside this range, rotations are performed to restore balance.

Tree Traversal refers to the process of visiting each node in the tree exactly once.

1. Preorder Traversal (Root-Left-Right):

   • Visit the Root node.
   • Traverse the Left subtree recursively.
   • Traverse the Right subtree recursively.
   • Application: Used to create a copy of the tree.

2. Inorder Traversal (Left-Root-Right):

   • Traverse the Left subtree recursively.
   • Visit the Root node.
   • Traverse the Right subtree recursively.
   • Application: Used to get sorted data from a Binary Search Tree (BST).

3. Postorder Traversal (Left-Right-Root):

   • Traverse the Left subtree recursively.
   • Traverse the Right subtree recursively.
   • Visit the Root node.
   • Application: Used to delete the tree (delete children before parent) or evaluate postfix expressions.

1. Adjacency Matrix:
A 2D array of size where is the number of vertices. If an edge exists between vertex and , (or weight), otherwise $0$.

• Pros: Easy to implement; Checking if an edge exists takes time.
• Cons: Consumes space, regardless of the number of edges. Inefficient for sparse graphs.

2. Adjacency List:
An array of lists. The array index represents a vertex, and the linked list at that index contains all vertices adjacent to it.

• Pros: Space efficient, consumes space. Ideal for sparse graphs.
• Cons: Checking if an edge exists takes time, where is the number of neighbors (degree of the vertex).

Conclusion: Use Adjacency Lists for sparse graphs (fewer edges) and Adjacency Matrices for dense graphs.

Concept:
Dijkstra's Algorithm is a greedy algorithm used to find the shortest path from a source node to all other nodes in a weighted graph.

Mechanism (Relaxation):
It maintains a set of visited vertices and a set of unvisited vertices. Initially, all distances are infinite except the source (0).

1. Select the unvisited node with the smallest tentative distance.
2. For the current node, consider all of its unvisited neighbors.
3. Calculate the tentative distance through the current node.
   
4. If New Dist < Known Dist, update the distance (Relaxation).
5. Mark current node as visited.

Limitations:

1. Negative Weights: Dijkstra’s algorithm fails if the graph contains negative edge weights (it may enter an infinite loop or give incorrect results). Bellman-Ford is used in such cases.
2. Complexity: Standard implementation is , but with a Min-Priority Queue (Heap), it is .

Hashing:
Hashing is a technique used to map data of arbitrary size to fixed-size values (hash codes) to allow for average time complexity for search, insertion, and deletion.

Hash Function:
A function that converts a given key into a specific index in a hash table.
Example:

Hash Collision:
A collision occurs when two different keys generate the same hash index. i.e., where $k_1
eq k_2$.

Collision Resolution Techniques:

1. Chaining (Open Hashing): Each slot in the hash table points to a Linked List. Collided elements are added to the list.
2. Open Addressing (Closed Hashing): All elements are stored in the hash table array itself.
   • Linear Probing: Check next slot .
   • Quadratic Probing: Check .
   • Double Hashing: Use a second hash function.

Max-Heap Properties:
A Max-Heap is a complete binary tree where the value of the root node is greater than or equal to the values of its children. This property allows the recursive definition:

Insertion of 60:
Current Heap Array: [50, 30, 20, 15, 10, 8, 16]

1. Insert at end: Add 60 as the left child of 15 (next available position in Complete Binary Tree).
   Array: [50, 30, 20, 15, 10, 8, 16, 60]

2. Heapify Up (Bubble Up): Compare 60 with parent (15).

   • , swap.
     Array: [50, 30, 20, 60, 10, 8, 16, 15]

3. Compare with new parent (30):

   • , swap.
     Array: [50, 60, 20, 30, 10, 8, 16, 15]

4. Compare with new parent (50):

   • , swap.
     Array: [60, 50, 20, 30, 10, 8, 16, 15]

5. 60 is now at the root. The heap property is restored.

Heap Sort:
Heap sort is a comparison-based sorting technique based on the Binary Heap data structure.

Algorithm:

1. Build Heap: Build a Max-Heap from the input array. This places the largest element at the root (index 0).
2. Extract Max: Swap the root element (maximum) with the last element of the array. Reduce the heap size by 1 (effectively removing the max element from the heap and placing it in its sorted position).
3. Heapify: Call Max-Heapify on the root to restore the max-heap property for the remaining tree.
4. Repeat steps 2 and 3 until the heap size is 1.

Time Complexity:

• Building the heap: .
• Extraction and Heapifying: Performed times, each taking .
• Total Time Complexity: in all cases (Best, Average, and Worst).
• Space Complexity: (In-place sort).

1. Chaining (Open Hashing):

• Mechanism: Each cell in the hash table points to a linked list. If points to an occupied slot, the new key is appended to the linked list at that slot.
• Pros: Deletion is simple; Table never technically fills up (performance just degrades linearly).

2. Linear Probing (Open Addressing):

• Mechanism: If is full, check index . Keep checking the next slot sequentially until an empty one is found.
• Pros: Better cache performance (data is contiguous).
• Cons: Suffers from Primary Clustering (blocks of occupied cells merge, increasing search time).

Comparison when Table is Full:

• Chaining is better when the table is nearly full or the Load Factor () . Linear probing fails completely when the table is full, and performance degrades drastically as approaches 1.

Priority Queue:
A Priority Queue is an abstract data type similar to a regular queue or stack, but where each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.

Implementation using Heap:
A Binary Heap is the most efficient structure for implementing a Priority Queue.

• Enqueue (Insertion): Standard Heap Insertion. The new element bubbles up to its correct position based on priority. Time: .
• Dequeue (Extract Max/Min): Removes the root (highest priority). The last element replaces the root, and we bubble down (heapify). Time: .
• Peek: Returns the root element without removal. Time: .

Compared to Arrays (Insert , Delete ) or Sorted Arrays (Insert ), Heaps provide balanced performance.

Kruskal’s Algorithm:
Kruskal’s algorithm is a greedy algorithm that finds a Minimum Spanning Tree for a connected weighted graph. It adds increasing cost edges at each step, avoiding cycles.

Steps:

1. Sort Edges: Sort all the edges in the graph in non-decreasing order of their weights.
2. Initialize MST: Create a forest where each vertex is a separate tree.
3. Iterate: Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far.
   • If No Cycle: Add the edge to the MST.
   • If Cycle: Discard the edge.
     (Cycle detection is usually done using the Union-Find / Disjoint Set data structure).
4. Repeat: Continue until there are edges in the MST.

Complexity: or .

A good hash function is critical for the performance of a hash table. Its primary characteristics include:

1. Uniform Distribution: It should map keys as evenly as possible across the hash table slots to minimize collisions and clustering.
2. Determinism: For a given input , it must always generate the same hash value .
3. Efficiency: It should be computationally cheap and fast to calculate ( time).
4. Minimizes Collisions: While collisions are inevitable, a good function reduces the probability of distinct keys hashing to the same index.
5. Use of Whole Key: It should use all parts of the input key to calculate the hash, ensuring that small changes in the key result in different hash values (Avalanche Effect).

To reverse a singly linked list, we need to change the next pointer of each node to point to its previous node. This requires three pointers: prev, current, and next_node.

Algorithm:

1. Initialize three pointers:

   • prev = NULL
   • current = HEAD
   • next_node = NULL

2. Loop while current is not NULL:

   • Save the next node: next_node = current->next
   • Reverse the pointer: current->next = prev
   • Move prev one step forward: prev = current
   • Move current one step forward: current = next_node

3. After the loop finishes, prev will point to the last node of the original list.

4. Update HEAD to point to prev.

Result: The list direction is reversed.

Full Binary Tree:

• Definition: A Binary Tree is Full if every node has either 0 or 2 children. No node can have only 1 child.
• Also known as a proper or strict binary tree.

• Example:

  A

  / \
  B C
  / \
  D E

Complete Binary Tree:

• Definition: A Binary Tree is Complete if all levels are completely filled except possibly the last level, and the last level has all keys as left as possible.
• This structure is crucial for Heap implementation using arrays.

• Example:

  A

  / \
  B C
  /
  D

  (In the example above, if C had a child but B did not have D, it would not be complete).