CST-370 Week 7

 This week, I learned about Dynamic programming, which is algorithm design technique for improving the efficiency of certain recursive algorithms, such as Warshall's algorithm and Floyd's algorithm. I also learned about the Greedy technique, which is used to solve optimization problems, such as the Prim algorithm

Dynamic Programming

To avoid multiple calls for a sub-problem (ex: base case for fib), use an array to keep solutions of sub-problems.

Example:

Fib(n):

    F[0] = 0;

    F[1] = 1;

    for (i = 2 to n):

        F[i] = F[i-1] + F[i-2]

    return F[n];

In General:

    1. Set up a recurrence relation that describes a solution to a problem with smaller sub-problems.

    2. Solve the smaller sub-problems and record the solutions in a table.

    3. Solve the original problem using the table.

Dynamic Programming - Solving Coin-Row Problem

Coin-row problem: There is a row of n coins whose values are some positive integers (c_1 ... c_n). The goal is to pick up the maximum amount of money, subject to the constraint that no two adjacent coins can be picked up.

Define subproblems: Let F(k) be the maximum amount of money we can pick with the first k coins (k = 0, ..., n). To calculate F(n), consider 2 cases:

    1. The nth coin is included: c_n + F(n-2)

    2. The nth coin is not included: F(n-1)

Set up the recurrence:

    F(n) = max { c_n + F(n-2), F(n-1)} for n > 1

    F(0) = 0, F(1) = c_1

Warshall's Algorithm

Warshall's Algorithm: Computes the transitive closure of a directed graph.

Example of transitive closure:

Recurrense: Define n+1 adjacency matric: R1, R2, ..., R(K), ..., R(n-1), and R(n). R(K)[i,j] = 1 if and only if there is a path from i to j with only first k vertices allowed as intermediate.

O(N^3)

Greedy Technique

Greedy technique: Used to solve problems with a sequence of choices. Each choice must be feasible (satisfy the problem's constraints), locally optimal (select best choice among all feasible choices available at that step), and irrevocable (the choice cannot be changed later). Useful for optimal or fast approximation

Prim's Algorithm to find MST (Minimum Spanning Tree)

MST: A spanning tree of a connected graph is its connected acyclic subgraph that contains all the vertices in the graph. The MST is the smallest weight among all possible spanning trees of a graph

Example MST (While keeping all nodes connected):

Prim's MST Algo:

    1. Start with a tree T_1 consisting of a vertex.

    2. Grow T_1 by adding one vertex at a time such as T_2, T_3, ..., T_n.

    3. Construct T_i+1 from T_i by adding a vertex not in T_i, that is closest to those already in T_i     (greedy step -- pick closest one).

    4. Stop when all verticies are included.

Example: