Core Algorithmic Concepts

We started with understanding what algorithms are and how to evaluate their efficiency using recurrence relations and Big-O notation.

• Insertion Sort
  Shifts elements to place values in order. Good for small datasets.
  Time Complexity: O(n²)
• Bubble Sort
  Compares adjacent elements repeatedly.
  Time Complexity: O(n²)
• Linear Search
  Sequentially checks each element in the list.
  Time Complexity: O(n)

Consider array: [5, 2, 4, 6, 1, 3]
Pass 1: [2, 5, 4, 6, 1, 3]
Pass 2: [2, 4, 5, 6, 1, 3]
Pass 3: [2, 4, 5, 6, 1, 3]
Pass 4: [1, 2, 4, 5, 6, 3]
Pass 5: [1, 2, 3, 4, 5, 6]

This paradigm breaks a problem into smaller parts, solves them recursively, and merges results. The "divide and conquer" technique leads to efficient algorithms for a wide range of problems.

• Binary Search
  Efficient for sorted data.
  O(log n)
• Merge Sort
  Uses recursion and merging.
  O(n log n)
• Quick Sort
  Partition-based sorting. Fast on average.
  Avg: O(n log n), Worst: O(n²)
• Strassen's Matrix Multiplication
  Reduces complexity from O(n³) to O(n^2.81).
  O(n^2.81)
• Karatsuba Algorithm
  Fast multiplication of large integers.
  O(n^log₂3)

Make the best choice at each step hoping for an overall optimal solution. While not always guaranteed to find the global optimum, greedy algorithms are efficient for many problems.

• Kruskal's Algorithm
  Uses Disjoint Set for MST.
  O(E log E)
• Prim's Algorithm
  Grows MST from a starting vertex.
  O(E log V)
• Dijkstra's Algorithm
  Finds shortest paths in weighted graphs.
  O((V+E) log V)
• Huffman Coding
  Creates optimal prefix codes for data compression.
  O(n log n)
• Fractional Knapsack
  Selects items with highest value-to-weight ratio.
  O(n log n)

Overlapping subproblems and optimal substructure are solved by storing past results (memoization). DP is powerful for optimization problems where brute force would be exponential.

• Longest Common Subsequence (LCS)
  Dynamic string comparison.
  O(m×n)
• Matrix Chain Multiplication
  Optimal parenthesis placement.
  O(n³)
• 0/1 Knapsack
  Select items to maximize profit with a weight constraint.
  O(n×W)
• Floyd-Warshall
  All-pairs shortest paths.
  O(V³)
• Edit Distance
  Minimum operations to transform one string to another.
  O(m×n)

DP Table (Partial):
   | "" | B  | D  | C  | A  | B  | A
---+----+----+----+----+----+----+----
"" | 0  | 0  | 0  | 0  | 0  | 0  | 0
A  | 0  | 0  | 0  | 0  | 1  | 1  | 1
B  | 0  | 1  | 1  | 1  | 1  | 2  | 2
C  | 0  | 1  | 1  | 2  | 2  | 2  | 2

Systematically tries all options and backtracks if a solution fails. Backtracking is essential for solving constraint satisfaction problems and combinatorial optimization.

• N-Queens
  Place queens such that no two threaten each other.
  O(n!)
• Subset Sum
  Identify subsets with a given total.
  O(2ⁿ)
• Hamiltonian Path
  Find a path visiting each vertex exactly once.
  O(n!)
• Graph Coloring
  Assign colors to vertices with constraints.
  O(m^n)
• Sudoku Solver
  Common backtracking application.
  O(9^(n²))

. Q . .  
. . . Q  
Q . . .  
. . Q .  

Graphs model complex systems like networks, cities, and social connections. From traversal to pathfinding and network flow, graph algorithms are foundational in computer science.

• DFS/BFS
  Graph traversal techniques.
  O(V+E)
• Dijkstra's Algorithm
  Single-source shortest path.
  O((V+E) log V)
• Bellman-Ford
  Handles negative edge weights.
  O(V×E)
• Floyd-Warshall
  All-pairs shortest path using DP.
  O(V³)
• Topological Sort
  Linear ordering of vertices in a DAG.
  O(V+E)
• Ford-Fulkerson
  Maximum flow in a flow network.
  O(E×max_flow)