Applications in Computer Science

Applications in Computer Science

---

Algorithm Analysis

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")

---

Cryptography

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()

---

Coding Theory

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}")

---

Scheduling

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))

---

Networking

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}")

---

Applications in AI/ML

---

Common Mistakes

---

Interview Questions

1. What is the time complexity of common sorting algorithms? Bubble: $O(n^2)$, Merge: $O(n \log n)$, Quick: $O(n \log n)$ average, Heap: $O(n \log n)$. Merge and heap are guaranteed; quick is fastest in practice.

2. How does RSA encryption work? Choose primes $p, q$, compute $n = pq$ and $\phi(n)$. Pick $e$ coprime to $\phi(n)$. Private key $d = e^{-1} \pmod{\phi(n)}$. Encrypt: $c = m^e \pmod{n}$. Decrypt: $m = c^d \pmod{n}$. Security relies on factoring difficulty.

3. What is dynamic programming and when should you use it? DP solves problems with overlapping subproblems and optimal substructure. Store subproblem results to avoid recomputation. Use when a naive recursive solution has exponential complexity.

4. How does Dijkstra's algorithm work? Greedily relax edges from the closest unvisited vertex using a priority queue. Correct only for non-negative weights. For negative weights, use Bellman-Ford.

5. What is the difference between BFS and DFS for shortest path? BFS finds shortest paths in unweighted graphs. Dijkstra handles weighted graphs. DFS does not guarantee shortest paths but is useful for cycle detection and topological sorting.

6. What is network flow and where is it used? Maximum flow from source to sink in a capacity-constrained network. Applications: transportation, communication bandwidth, bipartite matching, image segmentation.

7. How do error-correcting codes work? Add redundancy bits so errors can be detected and corrected. Hamming distance determines error capability: $d$ distance detects $d-1$ errors and corrects $\lfloor(d-1)/2\rfloor$ errors.

8. What is the relationship between P and NP? P: problems solvable in polynomial time. NP: problems verifiable in polynomial time. P is a subset of NP. Whether P = NP is the most important open problem in computer science.

---

Practice Problems

---

Quick Reference

---

Cross-References

• Graph Theory → 074-discrete-graphs.mdx: Networks, social graphs, routing algorithms
• Trees → 075-discrete-trees.mdx: Decision trees, spanning trees, search trees
• Recurrence Relations → 076-discrete-recurrence.mdx: Algorithm complexity analysis, Master theorem
• Number Theory → 077-discrete-number-theory.mdx: Cryptography, modular arithmetic, hashing
• Boolean Algebra → 078-discrete-boolean.mdx: Circuit design, logic optimization, search queries
• Automata Theory → 079-discrete-automata.mdx: Compilers, pattern matching, protocol verification