Basic Algorithm List

List of few algorithm that come handy. Not that they are super important for interview or anything, but the mainly for knowledge sake.

  1. Kadane Algorithm  – Largest Sum Contiguous Subarray Code Youtube
    The idea is simple. At each index of array we check if what’s the maximum subarray till now. The max subarray can be either the current-index-element alone or the sum previous subarray index + the current index.
    At each index we check what’s the maximum subarray that we have found instead of storing the sum in another array.
    import java.lang.*; -> to use the Math.max collection.
  2. Boyer–Moore majority vote algorithm Youtube  Code
    Application – Find Majority Element in an Array.
  3. Sieve of Eratosthenes – Wiki – Given a number n, print all primes smaller than or equal to n. The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes. Code.
    The problem with this algo is the space requirement.
    We initially create an array equal to the size of n. Initialize all array index with a false flag. Now start looping through the array starting from i = 2(1 is already prime). We process only i which are marker as false. For each i’s factor mark all the array index as false. This will be a nested loop. Keep doing it till i < =n;
    The index left as false are the prime number.
  4. Pigeonhole Principle – simple but very helpful in solving many problem. Read few here.
  5. Brian Kernighan’s Algorithm – Count set bits in an integer
  6. Birthday ParadoxBirthday Paradox
  7. The Lazy Caterer’s Problem – Given an integer n, denoting the number of cuts that can be made on a pancake, find the maximum number of pieces that can be formed by making n cuts(pieces can be of unequal size). Wiki
    Thus, the total number of pieces after n cuts is

    f(n)=n+f(n-1).\,
    This recurrence relation can be solved. If ƒ(n − 1) is expanded one term the relation becomes
    {\displaystyle f(n)=n+(n-1)+f(n-2).\,}f(n)=n+(n-1)+f(n-2).\,
    Expansion of the term ƒ(n − 2) can continue until the last term is reduced to ƒ(0), thus,
    f(n)=n+(n-1)+(n-2)+\cdots+1+f(0).\,
    Since {\displaystyle f(0)=1}f(0)=1, because there is one piece before any cuts are made, this can be rewritten as
    f(n)=1+(1+2+3+\cdots+n).\,
    This can be simplified, using the formula for the sum of an arithmetic progression:
    f(n)=1+\frac{n(n+1)}{2}=\frac{n^2+n+2}{2}.

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s