Unit 2: Data Organiza on Techniques

Linear Data Structures

Linked Lists

 Singly Linked List:

o A linked list where each node contains data and a pointer to the next node.

o Opera ons: Insert (at beginning, end, or specific posi on), Delete (by posi on or
value), Search, Update, and Display.

 Doubly Linked List:

o A linked list where each node has pointers to both the previous and next nodes.

o Allows bidirec onal traversal and makes certain opera ons (like delete) more
efficient.

 Queue and Stack using Linked Lists:

o Queue: Implemented with a singly linked list using a front pointer (dequeue) and
rear pointer (enqueue).

o Stack: Implemented as a singly linked list with opera ons on the top node.

Non-Linear Data Structures

Trees

 Binary Tree:

o Each node has at most two children. Used in various applica ons for efficient
searching, sor ng, and storing hierarchical data.

 Binary Search Tree (BST):

o A binary tree where each le child has a value less than the parent, and each right
child has a value greater than the parent.

 Tree Traversals:

o Pre-order: Visit root, le subtree, right subtree.

o In-order: Visit le subtree, root, right subtree (used in BST for sorted output).

o Post-order: Visit le subtree, right subtree, root.

 Balanced Search Trees: Trees that maintain a balanced structure, ensuring O(log n)
complexity for opera ons. Examples include AVL and Red-Black Trees.

 B-Tree: A self-balancing tree used for managing large amounts of data efficiently in
databases and file systems.

 Heap Sort: Uses a binary heap data structure to perform an in-place sor ng algorithm. First
builds a max heap, then repeatedly extracts the maximum element.

Hashing
  Introduc on to Hashing:

o A technique to map large data sets to smaller fixed-sized slots, enabling quick data
access.

 Collision Avoidance Mechanisms:

o Separate Chaining: Each slot in the hash table contains a linked list to store mul ple
elements.

o Open Addressing: Finds another slot when a collision occurs, including techniques
like linear probing, quadra c probing, and double hashing.

Experiments

 Experiment 4: Create a Binary Tree and display it graphically. Perform pre-order, in-order,
and post-order traversals using recursion.

 Experiment 5: Find the union and intersec on of two linked lists using hashing. Use hashing
to check for duplicates efficiently.

 Experiment 6: Implement BFS and DFS, two graph traversal algorithms where BFS explores
all nodes layer by layer and DFS goes as deep as possible along each branch before
backtracking.

Unit 3: Graph Representa on and Algorithms

Graph Representa on

 Adjacency Matrix: A 2D array where matrix[i][j] = 1 indicates an edge from node i to node j.

 Adjacency List: An array of linked lists where each list represents nodes adjacent to a
par cular vertex.

Graph Traversal

 BFS (Breadth-First Search): Visits all nodes at the current depth before moving to the next
level.

 DFS (Depth-First Search): Follows a path to its end, then backtracks to explore other paths.

Greedy Technique

Shortest Path Algorithms

 Dijkstra’s Algorithm: A greedy algorithm to find the shortest path from a source node to all
other nodes in a graph with non-nega ve weights.

 Applica ons: Commonly used in rou ng and as part of network pathfinding algorithms.

Huffman Coding

 A method for crea ng prefix-free binary codes based on frequencies of characters,

commonly used in compression algorithms.

Minimum Spanning Trees (MST)

  Prim’s Algorithm: A greedy algorithm that starts from any node and adds the lowest-cost
edge to form the MST.

 Kruskal’s Algorithm: A greedy algorithm that sorts all edges by weight and adds them to the
MST if they don’t form a cycle.

Dynamic Programming

Bellman-Ford Algorithm

 A dynamic programming algorithm that finds the shortest paths from a source node to all
nodes, accoun ng for possible nega ve weights.

Knapsack Problem

 0/1 Knapsack: Uses dynamic programming to maximize the value within a fixed weight
capacity.

 Knapsack with Repe on: Allows items to be chosen mul ple mes.

Experiments

 Experiment 7: Implement a program for finding the shortest path in a mul stage graph using
dynamic programming.

 Experiment 8: Compare Prim’s and Kruskal’s algorithms for MST, showing differences in
approach and performance.

 Experiment 9: Implement a recursive dynamic programming solu on for the 0/1 knapsack
problem.

 Experiment 10: Implement the Bellman-Ford algorithm.

Viva Ques ons with Answers

Unit 2 Ques ons

1. What is a linked list, and how is it different from an array?

o A linked list is a dynamic data structure where elements are linked using pointers.
Unlike arrays, linked lists don’t need con guous memory and allow easy
inser on/dele on of elements.

2. Explain the difference between singly and doubly linked lists.

o A singly linked list has nodes poin ng to the next node only, whereas a doubly linked
list has nodes poin ng to both the previous and next nodes.

3. What is a binary tree traversal?

o Tree traversal is the process of visi ng all nodes in a specific order, like pre-order, in-
order, or post-order.

4. What is hashing?
 o Hashing is a technique to map data to a fixed-size value, allowing efficient search,
inser on, and dele on opera ons.

5. Explain separate chaining in hashing.

o Separate chaining uses a linked list to store mul ple items in the same slot, resolving
collisions effec vely.

Unit 3 Ques ons

1. Describe the difference between BFS and DFS.

o BFS explores nodes level by level using a queue, while DFS explores as far as possible
along one path using a stack (or recursion).

2. What is a minimum spanning tree?

o A minimum spanning tree is a subset of the graph that connects all ver ces with the
minimum possible total edge weight and without cycles.

3. Why is Huffman coding important in computer science?

o Huffman coding reduces file size by encoding frequently used characters with shorter
codes, improving data compression.

4. What is the Bellman-Ford algorithm used for?

o It’s used to find the shortest path in graphs with nega ve weights and can detect
nega ve weight cycles.

5. What is dynamic programming, and where is it used?

o Dynamic programming is an op miza on technique for solving complex problems by

breaking them into overlapping subproblems, used in algorithms like Knapsack and
Bellman-Ford.

Unit 2: Data Organiza on Techniques

Linear Data Structures

1. Linked Lists

 Singly Linked List:

o Structure: Each node contains data and a next pointer.

o Example: Storing a sequence of integers.

o Opera ons:

 Inser on: Adding nodes at the beginning, end, or at a specified posi on.

 Dele on: Removing a node by its value or posi on.

  Search: Finding a specific element by traversing from the head to the desired
element.

 Example: Dele ng a node with a given value involves upda ng the next
pointer of the previous node.

 Doubly Linked List:

o Structure: Each node contains data, a next pointer, and a prev pointer.

o Example: Browser history, where each page has links to both the previous and next
pages.

o Opera ons:

 Inser on/Dele on: More efficient than singly linked lists, as we can navigate
backward.

 Use Case: Useful for applica ons where two-way traversal is needed.

 Queue and Stack Implementa ons Using Linked Lists:

o Queue with Linked List: The front pointer handles dequeue opera ons, and the rear
pointer handles enqueue opera ons.

o Example: Customer queue management in a service center.

o Stack with Linked List: The top pointer allows adding/removing nodes from the top.

o Example: Undo func onality in text editors, where each opera on is a stack node.

Non-Linear Data Structures

2. Trees

 Binary Tree:

o Defini on: Each node has a maximum of two children.

o Types of Binary Trees:

 Full Binary Tree: Every node has 0 or 2 children.

 Complete Binary Tree: All levels, except possibly the last, are fully filled.

 Perfect Binary Tree: All internal nodes have two children, and all leaf nodes
are at the same level.

o Example: Organiza onal hierarchy or family tree.

 Binary Search Tree (BST):

o Property: Le child < Parent < Right child.

o Inser on and Dele on: Follows the BST property to maintain order.

o Example: Contact list on a phone, where searching is op mized.

 Tree Traversals:
 o Pre-order: Used for crea ng copies of the tree.

o In-order: Used for binary search trees to get sorted output.

o Post-order: Used for dele ng or freeing the nodes.

o Example: In a BST of [4, 2, 5, 1, 3], in-order traversal yields [1, 2, 3, 4, 5].

 Balanced Search Trees: Ensure O(log n) for opera ons by balancing automa cally.

o Examples: AVL and Red-Black Trees, commonly used in databases.

 B-Trees: A self-balancing search tree ideal for handling large data.

o Proper es: B-trees reduce the number of disk accesses, making them efficient for
databases.

 Heap Sort:

o Defini on: A sor ng algorithm based on the binary heap data structure.

o Process: Build a max heap, then repeatedly extract the maximum element and
adjust the heap.

o Example: Sor ng [4, 10, 3, 5, 1] using heap sort yields [1, 3, 4, 5, 10].

3. Hashing

 Basics of Hashing:

o Hash Func on: Maps keys to specific indices in a table.

o Example: Hashing student IDs to quickly access student records.

 Collision Avoidance Mechanisms:

o Separate Chaining: Each slot holds a linked list for mul ple entries with the same
hash.

 Example: Storing mul ple email accounts sharing the same ini als.

o Open Addressing: Uses techniques like linear probing, quadra c probing, and double
hashing to find empty slots.

Unit 3: Graph Representa on and Algorithms

Graph Representa on

 Adjacency Matrix:

o Structure: A 2D matrix where cell [i][j] indicates the presence (1) or absence (0) of an
edge.

o Example: Represen ng a graph with nodes A, B, C, where A is connected to B and C,

B is connected to C.

 Adjacency List:
 o Structure: An array of lists, where each list corresponds to a node’s connec ons.

o Example: In a social network, each person has a list of friends (connec ons).

Graph Traversal

 BFS (Breadth-First Search):

o Defini on: Explores nodes level by level.

o Example: Used in shortest path algorithms, like finding the shortest route in a map.

o Implementa on: Uses a queue to track visited nodes.

 DFS (Depth-First Search):

o Defini on: Explores as far as possible along a branch before backtracking.

o Example: Useful in detec ng cycles within graphs.

o Implementa on: Uses a stack or recursion.

Greedy Technique

Shortest Path Algorithms

 Dijkstra’s Algorithm:

o Purpose: Finds the shortest path in a graph with non-nega ve weights.

o Example: Google Maps finding the shortest route from point A to B.

o Steps: Uses a priority queue to itera vely select the minimum distance node.

 Applica ons of Shortest Path: Rou ng protocols, GPS naviga on.

Huffman Coding

 Purpose: Creates efficient prefix codes based on character frequency, minimizing storage
space.

 Example: Text compression, where frequently used characters are assigned shorter binary
codes.

Minimum Spanning Trees (MST)

 Prim’s Algorithm:

o Concept: Start from any node, add the lowest-cost edge un l MST is formed.

o Example: Connec ng ci es with minimum road costs.

 Kruskal’s Algorithm:

o Concept: Sorts edges by weight, adding them one by one if they don’t form a cycle.

o Example: Op mizing cable connec ons between buildings.

Dynamic Programming

Bellman-Ford Algorithm
  Purpose: Finds shortest paths in graphs with nega ve weights.

 Example: Determining op mal currency exchange rates with poten al nega ve cycles.

 Steps: Itera vely updates distances by considering all edges up to V-1 mes.

Knapsack Problem

 0/1 Knapsack: Each item can be picked only once, with a goal to maximize value within
weight capacity.

o Example: Selec ng items to fit into a limited-capacity backpack for a hiking trip.

 Knapsack with Repe on: Items can be selected mul ple mes.

o Example: Unbounded inventory selec on in a store.

Experiments

1. Experiment 4:

o Binary Tree Crea on and Display: Use graphics to represent nodes and connec ons.
Implement pre-order, post-order, and in-order traversals using recursion.

o Example: For a binary tree with nodes [4, 2, 5, 1, 3], in-order traversal would yield [1,
2, 3, 4, 5].

2. Experiment 5:

o Union and Intersec on of Linked Lists: Use a hash set to quickly check for
duplicates.

o Example: For linked lists {1, 2, 3} and {2, 3, 4}, the union is {1, 2, 3, 4}, and the
intersec on is {2, 3}.

3. Experiment 6:

o BFS and DFS Implementa on: Implement graph traversals using an adjacency list.
Use a queue for BFS and recursion or a stack for DFS.

o Example: Finding a path from node A to D in a network graph.

4. Experiment 7:

o Shortest Path for Mul stage Graph Using Dynamic Programming: Implement
shortest path using stages for a directed, weighted graph.

o Example: Op mizing the travel route between a series of ci es.

5. Experiment 8:

o Comparing Prim’s & Kruskal’s Algorithm: Code and analyze the efficiency of both
algorithms in crea ng a minimum spanning tree.

6. Experiment 9:
 o Recursive Dynamic Programming for 0/1 Knapsack: Implement recursion to find the
maximum value achievable within the weight limit.

7. Experiment 10:

o Bellman-Ford Algorithm Implementa on: Implement this to find shortest paths and
detect nega ve cycles in directed graphs.

1. General Tree

 Defini on: A tree structure in which each node can have any number of child nodes.

 Characteris cs:

o No restric on on the number of children per node.

o Commonly used to represent hierarchical structures, such as file directories.

2. Binary Tree

 Defini on: A tree in which each node has at most two children, commonly referred to as the
le and right child.

 Characteris cs:

o Binary trees are the basis for many specialized types, like binary search trees.

o Common uses include represen ng expression trees, decision trees, etc.

3. Full Binary Tree

 Defini on: A binary tree in which every node has either 0 or 2 children, meaning no node
has only one child.

 Characteris cs:

o Also known as a proper or strict binary tree.

o If a tree has N leaves, it has exactly 2N - 1 nodes.

4. Complete Binary Tree

 Defini on: A binary tree in which all levels are fully filled except possibly the last level, which
is filled from le to right.

 Characteris cs:

o O en represented as an array because of its predictable structure.

 o Example use: Binary Heaps, which are used in priority queues.

5. Perfect Binary Tree

 Defini on: A binary tree in which all internal nodes have exactly two children, and all leaf
nodes are at the same level.

 Characteris cs:

o The number of nodes at level l is 2^l.

o If a tree has L levels, it has (2^L - 1) nodes.

o Symmetrical and balanced, with all leaves at the same depth.

6. Balanced Binary Tree

 Defini on: A binary tree in which the difference in height between the le and right subtrees
of any node is at most one.

 Characteris cs:

o Helps maintain O(log n) me complexity for search, inser on, and dele on.

o Examples include AVL Trees and Red-Black Trees.

8. Binary Search Tree (BST)

 Defini on: A binary tree with an addi onal condi on where the le subtree of a node
contains only nodes with values less than the node’s value, and the right subtree contains
only nodes with values greater.

 Characteris cs:

o Efficient for search, insert, and delete opera ons (average case O(log n)).

o Widely used in searching and sor ng applica ons.

9. AVL Tree

 Defini on: A self-balancing binary search tree where the height difference between the le
and right subtrees of any node is at most one.

 Characteris cs:

o Named a er inventors Adelson-Velsky and Landis.

o Requires rota ons to maintain balance a er inser ons and dele ons.

o Guarantees O(log n) me complexity for search, inser on, and dele on.
10. Red-Black Tree

 Defini on: A balanced binary search tree with nodes colored red or black to ensure the tree
remains balanced.

 Characteris cs:

o Ensures that no path from root to leaf is more than twice as long as any other.

o Rules: Root is black, red nodes have black children, and each path from root to leaf
has the same number of black nodes.

o Commonly used in applica ons needing sorted data, like associa ve arrays.

11. B-Tree

 Defini on: A self-balancing tree structure where each node can have mul ple children and
keys, designed to minimize disk reads and writes.

 Characteris cs:

o Widely used in databases and file systems.

o Each node has a range of children (determined by a predefined minimum and

maximum), ensuring balance.