CS #02 | Algorithm

2019-09-01 1. Computer Science Comments

Introduction

1. Sorting
- Bubble Sort, Insertion Sort, Selection Sort, O(n^2)
- Merge Sort, O(nlogn) : Divide & Conquer
- Quick Sort, O(nlogn)
- Heap Sort: Based on heap data structure
1. Searching
- Linear Search, O(n)
- Binary Search, O(logn)
1. Recursion (Divide and Conquer)
- Binary Search
- Merge Sort, Quick Sort
1. Greedy Algorithm
- Huffman Coding
- Activity Selection
1. Dynamic Programming
- Fibonacci Sequence (memoization, tabulation)
- Longest Common Subsequences
- Longest Increasing Subsequences
1. Graph Algorithm
- Depth First Search
- Breadth Fisrt Search

1. Sorting

Bubble Sort
- Concept : repeatedly compares adjacent elements and swaps them if they are in the wrong order
  - Large elements bubble up to the end of the array after each pass
  - Repeat until no swaps are needed
  - Think of it like sorting bubbles in water, the biggest bubble floats to the top first
- Algorithm Steps
  - Start at the beginning of the list
  - Compare each pair of adjacent items
  - Swap them if they are in the wrong order
  - Repeat until the list is sorted
- Complexity
  - Best Case : O(n)
  - Worst Case : O(n^2)
  - Space Complexity : O(1)

def bubble_sort(arr: list[int]) -> list[int]:
    for i in range(len(arr)):  # number of passes
        swapped = False
        for j in range(0, len(arr) - i - 1):  # last i elements are sorted
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # swap
                swapped = True
        if not swapped:  # optimization: stop if already sorted
            break
    return arr

# Example
print(bubble_sort([5, 3, 8, 4, 2]))

Selection Sort
- Concept :
  - repeatedly find the minimum element from the unsorted part of the array
  - and put it at the beginning
- Algorithm Steps
  - Start with the first element
  - Find the smallest element in the unsorted part of the array
  - Swap it with the first unsorted element
  - Move to the next index and repeat until the whole array is sorted
- Complexity
  - Best Case : O(n^2)
  - Worst Case : O(n^2)
  - Space Complexity : O(1)

Insertion Sort
- Concept : works like how uou arrnage cards in your hand while playing cares
  - Take the next card
  - Insert it into its correct position among the already sorted cards
- Algorithm Steps
  - Start with the second element
  - Compare it with the elements before it
  - Shift larger elements one position to the right
  - Insert the current element into its correct spot
  - Repeat for all elements until the array is sorted
- Complexity
  - Best Case : O(n)
  - Worst Case : O(n^2)
  - Space Complexity : O(1)

Merge Sort
- Concept : Uses divide and conquer strategy
  - Divide : Split the array into two halves
  - Conquer : Recursively sort each half
  - Combine : Merge the two sorted halves into one sorted array
- Algorithm Steps
  - If the array has only 1 element, it’s already sorted
  - Otherwise, split the array into two halves
  - Recursively sort both halves
  - Merge the two sorted halves by comparing elements
- Complexity
  - Best Case : O(n logn)
  - Worst Case : O(n logn)
  - Space Complexity : O(n)

def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge2(left, right)


def merge(left: list[int], right: list[int]) -> list[int]:
    result = []
    while left or right:
        if left and right:
            if left[0] < right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        elif left:
            result.append(left.pop(0))
        elif right:
            result.append(right.pop(0))
    return result

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))

Quick Sort
- Concept : another divide and conquer algorithm, but partitions first and then sorts recursively
- Algorithm Steps
  - Pick a pivot(center) element
  - Rearrange the array so that:
    - Elements smaller than pivot -> left side
    - Elements larger than pivot -> right side
  - Recursively apply Quick Sort to left and right parts
- Complexity
  - Best Case : O(n logn)
  - Worst Case : O(n^2)
  - Space Complexity : O(logn)
  - Stable : No, equal elements may change order

def quick_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = [x for x in arr[1:] if x < pivot]
    right = [x for x in arr[1:] if x >= pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

arr = [38, 27, 43, 3, 9, 82, 10]
print(quick_sort(arr))

Heap Sort
- Concept : Heap Sort uses a binary heap data strcuture to sort elements
- Algorithm Steps
  - Build a max heap from the array
  - Swap the root(max element) with the last element
  - Reduce heap size by 1
  - Heapify
  - Repeat until heap size becomes 1.
- Complexity
  - Heapify : O(log n)
  - Build Heap : O(n)
  - Sorting : O(nlogn)
  - Space Complexity : O(1)
  - Stable : No

import heapq
def heap_sort(arr):
    heapq.heapify(arr)
    result = []
    while arr:
        arr[0], arr[-1] = arr[-1], arr[0]
        result.append(heapq.heappop(arr))
    return result

arr = [4, 10, 3, 5, 1]
print(heap_sort(arr))

2. Searching

Linear Search
- Concept : scans the list element by element until the target is found or the list ends.
- Complexity
  - Best Case : O(1)
  - Worst Case : O(n)
  - Space Complexity : O(n)
Binary Search
- Concept : is an efficient algorithm for finding an element in a sorted array
  - Looks at the middle element
  - If the target is smaller : search the left half
  - If the target is larget : search right half
  - Repeat until found or interval becomes empty
- Algorithm Steps
  - Start with two pointers (low = 0, high = n-1)
  - Find mid
  - if arr[mid] == target : finish
  - if arr[mid] < target : move to right half
  - if arr[mid] > target : move to left half
  - Repeat until low > high : not found
- Complexity
  - Best Case : O(1)
  - Worst Case : O(logn)
  - Space Complexity : O(1)

# Method1: recursive
def bsearch(arr, target, low, high):
    if low > high:
        return -1  # not found
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return bsearch(arr, target, mid + 1, high)
    else:
        return bsearch(arr, target, low, mid - 1)

# Example
arr = [2, 3, 4, 10, 40]
print(bsearch(arr, 10, 0, len(arr) - 1))  # Output: 3

# Method2: use pointer
def bsearch2(arr, target):
    l, r = 0, len(arr)-1
    while l <= r:
        m = (l + r) // 2
        if arr[m] == target:
            return m
        elif arr[m] < target:
            l = mid + 1
        else:
            r = mid - 1
    return -1

3. Recursion

Recursive Algorithm
- Concept : Recursion is when a function calls itself directly or indirectly until a base condition is met
- Algorithm Steps
  - Base case -> stops recursion
  - Recursive Case -> function calls itself with a smaller input
- Complexity
  - Not efficient, often replaced with DP or iteration to optimize
- When to use
  - Divide and conquer : Problems naturally defined in terms of subproblems
    - Merge Sort, Quick Sort, Binary Search Tree traversal
  - Tree/graph traversals (DFS)
  - Backtracking (maze, N-queens)
  - Mathematical Decisions (factorial)

5. Dynamic Programming

Dynamic Programming
- Concept :
  - a method to solve complex problems by breaking them into smaller overlapping subproblmes, solving each subproblem once, and storing the results for resuse.
  - basically, Divide & Conquer + Memoization (caching)
  - Memoization (Top-down)
    - Start with the original problem
    - Recursively solve subproblems
    - Store results in a cache so repeated calls don’t recompute
  - Tabulation (Bottom-up)
    - Start solving from the smallest subproblems
    - Build a DP table iteratively until reaching the final solution
- Algorithm Steps
  - Identify if it’s a DP problem
  - Define the state
    - What does dp[i] (or dp[i][j]) represent
  - Define the recurrence relation
    - Express the big problem in terms of smaller ones.
  - Decide on Top-Down or Bottom-Up approach
- Examples
  - Longest Increasing Subsequence
  - Longest Common Subsequences

# Top-down (memoization)
memo = {}

def fibonacci(n: int) -> int:
    if n<3:
        memo[n] = 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = fibonacci(n-1) + fibonacci(n-2)
    return memo[n]

print(fibonacci(5))

# Bottom-Up (Tabulation)

def fibonacci_tab(n:int) -> int:
    dp = [0] * (n+1)
    dp[1] = 1
    dp[2] = 1

    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fibonacci_tab(5))

6. Graph Algorithm

Depth First Search (traversal)
- Concept : DFS explores a graph by going as deep as possible along each branch before backtracking
- Algorithm Steps (Stack or Recurive)
  - Initialize a set/array visited to keep track of visited nodes
  - Start DFS from the given source node s
  - Mark the current node as visited
  - Process the current node
- Complexity
  - Time Complexity : O(V+E)
  - Space Complexity : O(v)
- Key Application Areas:
  - Graph Traversal: Visiting every vertex (node) in a graph structure.
  - Pathfinding / Maze Exploration: Searching for a specific path or finding the exit in a maze.
  - Combinations & Permutations: Exploring all possible cases or arrangements in a set.
  - Backtracking: Solving problems by trying out possible cases and “returning” (backtracking) if a path leads to a dead end.
Breadth First Search (traversal)
- Concept : BFS explores a graph level by level (neighbors first, then their neighbors)
- Algorithm Steps
  - Initialize an empth queue and a visited set.
  - Enque the starting node and mark it visited
  - While the queue is not empty,
    - Dequeue a node from the front of the queue
    - Process it (print)
    - For each neighbor, if the neighbor is not visited, mark it visited and enqueue it
- Complexity
  - Time Complexity: O(V+E)
  - Space Complexity: O(V)