Applications in Computer Science

import time
import random

def measure_time(func, *args, runs=100):
    total = 0
    for _ in range(runs):
        start = time.time()
        func(*args)
        total += time.time() - start
    return total / runs

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

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

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

sizes = [100, 1000, 5000]
for n in sizes:
    arr = random.sample(range(n * 10), n)
    t_bubble = measure_time(bubble_sort, arr.copy(), runs=10)
    t_merge = measure_time(merge_sort, arr.copy(), runs=10)
    print(f"n={n}: Bubble={t_bubble:.4f}s, Merge={t_merge:.4f}s")

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x, y = extended_gcd(b % a, a)
    return g, y - (b // a) * x, x

def mod_inverse(a, m):
    g, x, _ = extended_gcd(a % m, m)
    if g != 1:
        raise ValueError("No inverse")
    return x % m

def rsa_demo():
    p, q = 61, 53
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 17
    d = mod_inverse(e, phi)

    message = 65
    encrypted = pow(message, e, n)
    decrypted = pow(encrypted, d, n)

    print(f"Public key: ({n}, {e})")
    print(f"Private key: {d}")
    print(f"Original: {message}")
    print(f"Encrypted: {encrypted}")
    print(f"Decrypted: {decrypted}")

rsa_demo()

def hamming_encode(data_bits):
    m = len(data_bits)
    r = 0
    while (1 << r) < m + r + 1:
        r += 1
    total = m + r
    code = [0] * (total + 1)

    j = 0
    for i in range(1, total + 1):
        if i & (i - 1) != 0:
            code[i] = int(data_bits[j])
            j += 1

    for i in range(r):
        pos = 1 << i
        parity = 0
        for j in range(1, total + 1):
            if j & pos:
                parity ^= code[j]
        code[pos] = parity

    return code[1:]

def hamming_count_errors(received):
    r = 0
    while (1 << r) < len(received):
        r += 1
    error_pos = 0
    for i in range(r):
        pos = 1 << i
        parity = 0
        for j in range(len(received)):
            if (j + 1) & pos:
                parity ^= received[j]
        if parity:
            error_pos += pos
    return error_pos

data = [1, 0, 1, 1]
encoded = hamming_encode(data)
print(f"Data: {data}")
print(f"Encoded: {encoded}")

received = encoded.copy()
received[3] = 1 - received[3]
error = hamming_count_errors(received)
print(f"Error position: {error}")

from collections import defaultdict, deque

def topological_sort_dfs(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    order = []
    visited = set()

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        order.append(node)

    for i in range(n):
        if i not in visited:
            dfs(i)

    return order[::-1]

def topological_sort_kahn(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque([i for i in range(n) if in_degree[i] == 0])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == n else []

edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
print("DFS order:", topological_sort_dfs(5, edges))
print("Kahn order:", topological_sort_kahn(5, edges))

import heapq

def dijkstra(graph, start, n):
    dist = [float('inf')] * n
    dist[start] = 0
    prev = [-1] * n
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                prev[v] = u
                heapq.heappush(pq, (dist[v], v))

    return dist, prev

def get_path(prev, target):
    path = []
    current = target
    while current != -1:
        path.append(current)
        current = prev[current]
    return path[::-1]

graph = defaultdict(list)
edges = [(0, 1, 4), (0, 2, 1), (1, 3, 1), (2, 1, 2), (2, 3, 5)]
for u, v, w in edges:
    graph[u].append((v, w))

dist, prev = dijkstra(graph, 0, 4)
for i in range(4):
    path = get_path(prev, i)
    print(f"Distance to {i}: {dist[i]}, Path: {path}")