• Table of Contents

<aside> <img src="/icons/map-pin_gray.svg" alt="/icons/map-pin_gray.svg" width="40px" /> This is just a collection of equations, running time, probabilities, and etc. covered throughout the course.

</aside>

Greedy Algorithms

• In this context, assume $V$ is the number of vertices and $E$ is the number of edges.
• Shortest path:
  • Dijkstra's algorithm works by relaxing each edge exactly once.
    • All edge weights must be non-negative.
    • Time complexity of $O(E\log V)$.
  • Bellman-Ford’s algorithm works by relaxing all edges repeatedly for a maximum of $|V|-1$ iterations.
    • Can detect negative cycles.
    • Time complexity of $O(VE)$.
• Minimum spanning tree:
  • Kruskal’s algorithm iteratively adds the smallest weighted edge that does not form a cycle.
    • Uses union-find.
    • Time complexity of $O(E\log V)$.
  • Prim’s algorithm starts with an arbitrary vertex and iteratively adding the smallest weighted edge that does not form a cycle until $|V|-1$ edges.
    • Time complexity of $O[(E+V)\log V]$ and $O(E\log V)$ using adjaceny list.

Backtracking

• $N$-Queens problem:

  • Placing $N$ chess queens on an $N \times N$ chessboard so that no two share the same row, column, or diagonal.

    1) Start in the leftmost column
    2) If all queens are placed
    		return true
    3) Try all rows in the current column. Do following for every tried row.
    		a) If the queen can be placed safely in this row then mark 
    			 this [row, column] as part of the solution and recursively 
    			 check if placing queen here leads to a solution.
        b) If placing the queen in [row, column] leads to a solution 
    			 then return true.
        c) If placing queen doesn't lead to a solution then unmark 
    			 this [row, column] (Backtrack) and go to step (a) to try 
    			 other rows.
    4) If all rows have been tried and nothing worked,
       return false to trigger backtracking.
    

• Rat in a maze problem:

  • Finding a path from the starting position to the end position in a maze.

    1) Create a solution matrix, initially filled with 0’s.
    2) Create a recursive function, which takes initial matrix, output 
    	 matrix and position of rat (i, j). 
    3) If the position is out of the matrix or the position is not valid 
    	 then return.
    4) Mark the position output[i][j] as 1 and check if the current 
    	 position is destination or not. If destination is reached print the 
    	 output matrix and return.
    5) Recursively call for position (i+1, j) and (i, j+1).
    6) Unmark position (i, j), i.e output[i][j] = 0.
    

• $M$-coloring problem:

  • Assign colors to the vertices of a graph in a way that no two adjacent vertices have the same color.

    1) Create a recursive function that takes the current index, number of 
    	 vertices and output color array.
    2) If the current index is equal to number of vertices. Print the 
    	 color configuration in output array and break.
    3) Assign a color to a vertex (1 to m).
    4) For every assigned color, check if the configuration is safe, 
    	 recursively call the function with next index and number of 
    	 vertices.
    5) If any recursive function returns true, break the loop and return true.
    6) If no recursive function returns true, then return false.
    

Dynamic Programming

• Algorithm paradigms:
  • Greedy incrementally build up solution optimizing local criterion.
  • Divide-and-conquer break problem into sub-problems, solve each independently, combine to form solution.
  • Dynamic programming break problem into overlapping sub-problems, build up solutions to larger sub-problems.
• Sequence alignment:

  • Computing edit distance.

    $$ D(i,j) = \textrm{min} \begin{cases} {\color{darkblue} D(i,j - 1) + 1} \\ {\color{green} D(i - 1,j) + 1} \\ {\color{purple} D(i - 1,j - 1) + 1} & \textrm{if } A[i] \neq B[i] \\ {\color{orange} D(i - 1,j - 1)} & \textrm{if } A[i] = B[i]\\ \end{cases} $$

    • If $A[i] \neq B[i]$, you take the minimum of the value on the left, diagonally up, and at the top, then add $1$.
    • If $A[i] = B[i]$, you take the value diagonally up.

  • Deriving the operations by backtracking from the answer.

    

    • An insertion means a gap in $A[i]$.
    • A deletion means a gap in $B[j]$.
• Knapsack problem:
  • Greedy algorithm can work on fractional knapsack, but not for discrete knapsack with repetition or without repetition.

Divide-and Conquer

• Merge sort:
  • Recursively splits an array into halves, sorts each half, and then merge.
  • Time complexity of $O(N\log N)$.
• Quick sort:
  • Selects a pivot element, partitions the array around the pivot, and then recursively sorts.
  • Reduces the space complexity of merge sort.
  • Time complexity of $O(N\log N)$.
• Counting inversions:
  • Counting the number of times that two elements in a list are out of order.
  • $r_A + r_B + r$
    • Count the number of inversions in each half, $r_A$ and $r_B$, respectively.
    • Count the number of inversions combining both half, $r$.
    • Add them all together.

NP-Complete Problems