"No one is harder on a talented person than the person themselves" - Linda Wilkinson ; "Trust your guts and don't follow the herd" ; "Validate direction not destination" ;

December 21, 2009

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;
          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

No comments: