Algorithm Design

Steps:

1. Formulate the problem precisely
2. Design an algorithm
3. Prove the algorithm is correct
4. Analyze its runtime

Algothrm design techniques:

• Greedy Algorithm
• Divide and Conquer
• Dynamic Programming
• Network Flow Problem

Computational Intractability

P vs NP Problem

Approximation Algorithm

0. Foundational Concepts & Analysis

Asymptotic Analysis:

• Complexity:
  • An algorithm is efficient if its running time is a polynomial in the input size $T$
    • The running time is upper bounded by $c.T^d$ for some constants $c,d>0$
    • ex: brute force can solve Gale Shapley Algorithm in $n!$
  • 2 main complexities:
    • Time Complexity
    • Space Complexity
• Algorithm’s running time:
  • To measure a Efficient Algorithm
  • $f(n)$ is asymptotically bounded by $g(n)$
    • if $g(n)$ is asymptotically upper bound: Big O Notation
    • if $g(n)$ is asymptotically lower bound: Big Omega Notation
    • if $g(n)$ is asymptotically tight bound: Big Theta Notation
  • Propositions:
    1. if $\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=c$ for some constant $c>0$ then $f(n)=\Theta (g(n))$
       • Proof: $c-ϵ\le \frac{f(n)}{g(n)}\le c+ϵ$ by definition
       • $(c-ϵ)g(n)\le f(n)\le (c+ϵ)g(n)$
       • by definition of Big Theta notation, it is true
    2. if $\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=0$ then $f(n)=O(g(n))$
    3. if $\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=\infty$ then $f(n)=\Omega (g(n))$
  • To find which notation a function belongs to, do $\frac{f(n)}{g(n)}$
• Some classes of function:
  • Polynomials:
    • $f(n)={\sum }_{k=0}^d{a}_k{n}^k=O(n^d),a_d>0$
    • as $\underset{n\to \infty }{\lim }\frac{f(n)}{n^d}=a_d>0$
  • Logarithms:
    • ${\log }_a(n)=\Theta ({\log }_{b}n)$ for every $a>1$ and $b>1$
    • as $\underset{n\to \infty }{\lim }\frac{{\log }_{a}n}{{\log }_{b}n}=\frac{1}{{\log }_{b}a}=c$
  • Logarithms and Polynomials:
    • ${\log }_{a}n=O(n^d)$ for every $a>1$ and every $d>0$
    • as $\underset{n\to \infty }{\lim }\frac{{\log }_{a}n}{n^d}=0$
  • Exponentials:
    • $n^d=O(r^n)$ for every $r>1$ and every $d>0$
    • as $\underset{n\to \infty }{\lim }\frac{n^d}{r^n}=0$
  • Factorials:
    • $n!=2^{\Theta (n\log n)}$
    • as by Stirling’s Fomula $n!\approx \sqrt{2\pi n}(\frac{r}{e}{)}^n$

Recursion: Techniques like tail recursion and its relationship with Divide and Conquer.

- Sorting Algorithms: Comparison sorts (Merge Sort, Quick Sort, Heap Sort) and non-comparison sorts (Counting Sort, Radix Sort).

- Searching Algorithms: Linear Search and Binary Search.

Basic & Linear Data Structures

• Arrays: Static and dynamic arrays.
• Linked Lists: Singly, doubly, and circular linked lists.
• Stacks and Queues: FIFO and LIFO principles, including Deques (Double-ended Queues) and Priority Queues(often implemented with Heaps).
• Hash Tables / Maps: Hashing techniques and collision resolution (chaining, open addressing).

🌳 Tree Structures

• Trees and Binary Trees: Traversal methods (Pre-order, In-order, Post-order), tree properties (height, depth).

• Binary Search Trees (BSTs): Insertion, deletion, and searching.

• Self-Balancing Trees: Structures like AVL Trees and Red-Black Trees for guaranteed logarithmic time complexity.

• Tries (Prefix Trees): Used for efficient string retrieval and prefix matching.

• Heaps: Min-Heaps and Max-Heaps (used in Priority Queues and Heap Sort).

Graph Algorithms & DSU (Union-Find)

- Graph Representations: Adjacency Matrix and Adjacency List.

- Graph Traversal: Breadth-First Search (BFS) and Depth-First Search (DFS).

- Shortest Path Algorithms:

• Dijkstra’s Algorithm (Single Source Shortest Path for non-negative weights).

• Bellman-Ford Algorithm (Handles negative weights).

• Floyd-Warshall Algorithm (All-Pairs Shortest Path).

Minimum Spanning Tree (MST):

• Kruskal’s Algorithm (which heavily relies on DSU for cycle detection).

• Prim’s Algorithm.

- Topological Sorting: Ordering nodes in a Directed Acyclic Graph (DAG).

- Flow Networks: Max-Flow Min-Cut Theorem and algorithms like Edmonds-Karp.

Disjoint Set Union

Algorithmic Paradigms

Greedy Algorithms: Making locally optimal choices in the hope of finding a global optimum.

• Examples: Fractional Knapsack, Activity Selection.

- Divide and Conquer: Breaking a problem into smaller, independent subproblems and combining the solutions.

• Examples: Merge Sort, Quick Sort, Karatsuba Multiplication.

- Dynamic Programming (DP): Solving overlapping subproblems by storing the results of intermediate computations.

• Examples: 0/1 Knapsack, Longest Common Subsequence, Fibonacci Sequence.

- Backtracking: A general algorithm for finding all (or some) solutions to computational problems, typically building a solution step by step and abandoning partial solutions if they lead to a dead end.

• Examples: N-Queens, Sudoku Solver, finding all Hamiltonian Paths.

- Branch and Bound: Similar to Backtracking but uses bounding functions to discard sub-trees in the search space early.

🔬 Advanced Data Structures & Techniques

• Segment Trees: Efficiently handling range queries and point updates on an array (or vice-versa, with lazy propagation).

• Fenwick Trees (Binary Indexed Trees - BIT): Another structure for range queries/updates, often simpler to implement than a Segment Tree.

• String Matching Algorithms: Knuth-Morris-Pratt (KMP), Rabin-Karp.

• Computational Geometry: Convex Hull, Line Intersection.

• Network Flow: Advanced applications like Min Cost Max Flow.