MODULE 1: FUNDAMENTALS OF CODING AND ALGORITHMS

Session 2: Programming Concepts 2 – Data Structures Techniques

Recap from Previous Session

A data structure organizes and stores data efficiently, facilitating quick access and modification. Various techniques optimize data organization, storage, and access.

Common Data Structure Techniques

1. Array and Linked List Techniques

   • Arrays: Fixed-size, sequential structures allowing quick index access. Limitations include fixed size and inefficient insertions/deletions.
   • Linked Lists: Dynamic structures where each node points to the next. They allow efficient insertions/deletions but slower access.

   Example: Singly Linked List Implementation

   python

   Copy code

   class Node:
   def __init__(self, data):
   self.data = data
   self.next = None

   class LinkedList:
   def __init__(self):
   self.head = None

   def append(self, data):
   if not self.head:
   self.head = Node(data)
   return
   current = self.head
   while current.next:
   current = current.next
   current.next = Node(data)

   def display(self):
   current = self.head
   while current:
   print(current.data, end="-> ")
   current = current.next
   print("None")

   # Example Usage
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.display() # Output: 10-> 20-> 30-> None


2. Stack and Queue Techniques

   • Stacks: Last-In-First-Out (LIFO) structures. Elements are pushed and popped from the top.
   • Queues: First-In-First-Out (FIFO) structures. Elements are enqueued at the back and dequeued from the front.

   Example: Stack and Queue Implementation

   python

   Copy code

   # Stack Implementation Using List
   stack = []
   stack.append(1) # Push elements
   stack.append(2)
   stack.append(3)
   print(stack.pop()) # Output: 3

   # Queue Implementation Using Collections
from collections import deque
queue = deque()
queue.append(1) # Enqueue elements
queue.append(2)
queue.append(3)
print(queue.popleft()) # Output: 1


3. Hashing Techniques (Hash Tables)

   • Hash tables use a hash function to map data to a fixed-size table, enabling efficient average time complexity of O(1) for search, insertion, and deletion.
   • Key Techniques: Collision handling (chaining or open addressing) and hash function design.

   Example: Hash Table in Python

   python

   Copy code

   hash_table = {}
hash_table["name"] = "Alice" # Insertion
print(hash_table["name"]) # Access: Output: Alice
del hash_table["name"] # Deletion


4. Tree and Graph Techniques

   • Trees: Hierarchical structures with nodes connected by edges (e.g., binary trees, heaps).
   • Graphs: Composed of nodes (vertices) and edges, can be directed or undirected, used in various applications.

   Example: Binary Tree In-Order Traversal

   python

   Copy code

   class Node:
   def __init__(self, key):
   self.left = None
   self.right = None
   self.val = key

   def inorder(root):
   if root:
   inorder(root.left)
   print(root.val, end=" ")
   inorder(root.right)

   root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder(root) # Output: 2 1 3


5. Dynamic Programming and Greedy Techniques

   • Dynamic Programming: Solves problems by breaking them into simpler subproblems and storing results to avoid redundant calculations.
   • Greedy Algorithms: Make the best choice at each step, hoping for a global optimum.

   Example: Fibonacci using Dynamic Programming

   python

   Copy code

   def fibonacci(n, memo={}):
   if n in memo:
   return memo[n]
   if n <= 1:
   return n
   memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
   return memo[n]

   print(fibonacci(6)) # Output: 8


Activity: Task Management System

1. Appropriate Data Structure: Stack

A stack is ideal due to its LIFO nature, allowing quick retrieval of the most recent task.

2. Using Stack Techniques:

• Adding a Task (Push): Each task is added on top, efficient at O(1).
• Removing a Task (Pop): The most recent task is removed from the top, also O(1).
• Retrieving the Most Recent Task (Peek): Access the top task without removal, O(1).

3. Time Complexity Analysis:

• Adding a Task (Push): O(1)
• Removing a Task (Pop): O(1)
• Retrieving the Most Recent Task (Peek): O(1)

This concludes the lesson. Next, we will explore Object-Oriented Programming (OOP) concepts.

THANK YOU!