DSA Examples

Welcome to TheCodingCollege.com! In this post, we’ll explore examples of various Data Structures and Algorithms (DSA) concepts applied to real-world problems. These examples will cover multiple problem-solving approaches, including brute force, greedy algorithms, dynamic programming, and graph traversal.

1. Sorting Algorithms

Example: Sorting Student Marks

You are given an array of student marks. Sort them in ascending order.

Python Implementation (Bubble Sort):

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# Example Usage
marks = [45, 78, 12, 89, 33]
print(bubble_sort(marks))  # Output: [12, 33, 45, 78, 89]

2. Searching Algorithms

Example: Find a Specific Book in a Library

Given a sorted list of books by ID, find the position of a specific book.

Python Implementation (Binary Search):

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Example Usage
books = [101, 203, 345, 456, 567]
target = 345
print(binary_search(books, target))  # Output: 2

3. Greedy Algorithms

Example: Fractional Knapsack Problem

Maximize the total value in a bag of capacity W by taking fractional items.

Python Implementation:

def fractional_knapsack(values, weights, capacity):
    items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
    total_value = 0

    for value, weight in items:
        if capacity >= weight:
            total_value += value
            capacity -= weight
        else:
            total_value += value * (capacity / weight)
            break

    return total_value

# Example Usage
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(fractional_knapsack(values, weights, capacity))  # Output: 240.0

4. Graph Algorithms

Example: Shortest Path in a Road Network

Find the shortest path between two cities using Dijkstra’s Algorithm.

Python Implementation:

import heapq

def dijkstra(graph, start):
    pq = []
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heapq.heappush(pq, (0, start))

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

# Example Usage
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'C': 2, 'D': 6},
    'C': {'D': 3},
    'D': {}
}
start_node = 'A'
print(dijkstra(graph, start_node))  # Output: {'A': 0, 'B': 1, 'C': 3, 'D': 6}

5. Dynamic Programming

Example: The 0/1 Knapsack Problem

Given a set of items with weights and values, maximize the value in a knapsack of capacity W without taking fractional items.

Python Implementation:

def knapsack(values, weights, capacity):
    n = len(values)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]

# Example Usage
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(knapsack(values, weights, capacity))  # Output: 220

6. Tree Traversal

Example: Print a Directory Structure

Traverse a directory tree using Pre-order Traversal.

Python Implementation:

class Node:
    def __init__(self, name):
        self.name = name
        self.children = []

def pre_order_traversal(node):
    if not node:
        return
    print(node.name)
    for child in node.children:
        pre_order_traversal(child)

# Example Usage
root = Node("root")
child1 = Node("child1")
child2 = Node("child2")
root.children.extend([child1, child2])
child1.children.append(Node("child1.1"))
pre_order_traversal(root)
# Output:
# root
# child1
# child1.1
# child2

Conclusion

These examples demonstrate the versatility and power of Data Structures and Algorithms (DSA) in solving real-world problems. By mastering these concepts, you can develop efficient solutions for a wide range of applications.

Leave a Comment