Algorithm Types

Many Algorithm types are to be considered:

Simple recursive algorithms
Example – Factorial Algorithm
unsigned int factorial(unsigned int n)
{
     if (n <= 1)
    {
        return 1;
    }
    else
   {
          return n * factorial(n-1);
   }
}

Backtracking algorithms
• Backtracking algorithms are based on a depth-first recursive search
• A backtracking algorithm:

• Tests to see if a solution has been found, and if so, returns it; otherwise
• For each choice that can be made at this point,
• Make that choice
• If the recursion returns a solution, return it
• If no choices remain, return failure
• Example – 8 Queen Problem

Divide and conquer algorithms
o Divide-and-conquer algorithms partition the problem into independent subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem
o Combine the solutions to the subproblems into a solution to the original problem
o Example – QuickSort, BinarySearch

Dynamic programming algorithms
o Like divide and conquer, DP solves problems by combining solutions to subproblems.
o Unlike divide and conquer, subproblems are not independent.

• Subproblems may share subsubproblems,
• However, solution to one subproblem may not affect the solutions to other subproblems of the same problem.

o DP reduces computation by
o Solving subproblems in a bottom-up fashion.
o Storing solution to a subproblem the first time it is solved.
o Looking up the solution when subproblem is encountered again.
o At this moment two dynamic programming hallmarks are stated:

• Optimal substructure: an optimal solution to a problem contains optimal solutions to subproblems.
• Overlapping subproblems: a recursive solution contains a “small” number of distinct subproblems repeated many times.

o Examples -Dynamic Programming Practice Problems - Video Tutorial

Greedy algorithms
o A greedy algorithm works in phases. At each phase:
o You take the best you can get right now, without regard for future consequences
o You hope that by choosing a local optimum at each step, you will end up at a global optimum
o Examples
o Dijkstra’s algorithm for finding the shortest path in a graph - Always takes the shortest edge connecting a known node to an unknown node
o Kruskal’s algorithm for finding a minimum-cost spanning tree - Always tries the lowest-cost remaining edge
o Prim’s algorithm for finding a minimum-cost spanning tree - Always takes the lowest-cost edge between nodes in the spanning tree and nodes not yet in the spanning tree

• Branch and bound algorithms
• Brute force algorithms
• Randomized algorithms

Reference – I relied purely on web search to refer to multiple sites and learn above details. My next plan is to take up one example at a time and learn and analyze the algorithm.

Practicing Programming
You Should Write Blogs

More Reads

Programming Paradigms

View more presentations from Directi Group.