Algorithms

An algorithm should have three key features:

  1. Accurate: should produce correct results
  2. Understandable: should be implementable
  3. Efficient: should require reasonable resources and time to complete

Complexity Theory

Complexity theory is the study of “Efficiency” of algorithms.

Types of Complexity:

  1. Time: how much time does the algorithm take to complete
  2. Space: how much memory or disk space is required. There going to be trade offs.
  3. Other Resources like Network, Graphics, Hardware, etc.

 

Algorithm circumstances:

  1. Every Case
  2. Best Case
  3. Average Case
  4. Worst Case
  5. Expected Case

 

Big O Notation

Big O Notation is used to measure the upper bound performance of an algorithm.

Worst Case

Asymptotic Behavior: When the data grows very large

Big O Rules

  1. If an algorithm performs f(N) steps, then it is O(f(N)): If an algorithm loops through 1 to N to find the largest number, the algorithm has O(N) performance
  2. If an algorithm perform f(N) steps followed by g(N) steps, then it is O(f(N) + g(N)): If an algorithm loops through 1 to N to find the largest number, then loops through 1 to N to find the smallest number, the algorithm has O(N + N) = O(2N) performance
  3. If f(N) > g(N) for large N, then O(f(N) + g(N)) = O(f(N)): If an algorithm perform O(N^2) steps followed by O(N) steps, you can say that the algorithm has O(N^2) performance. Similarly, O(C + f(N)) = O(f(N)) where C is a constant
  4. If an algorithm performs g(N) steps for each of f(N) steps, then it is O(f(N) x g(N)): If in an algorithm a loop loops through 1 to N and a nested loop also loops through 1 to N, the algorithm has O(N x N) = O(N^2) performance
  5. Ignore constant multiples: O(C x f(N)) = O(f(N)) and O(f(C x N)) = O(f(N)) Big O Notation might not be very accurate about N steps and 3 x N steps as 3 x N steps theoretically should take 3 times longer. But you can still use Big O notation to compare two different algorithms

 

Some algorithms take a constant amount of time to complete. For example, setting a value of a variable. You can set value of one variable of a thousand variables, it will still take only one step. These algorithms are order one O(1) behavior. Constants get ignored when calculating Big O value of an algorithm runtime. As long as number of steps remain constant as N increases, the algorithm will have constant runtime.

O(1): int a = <value>; int b = <value>; …

O(N): for i = 1 to N

O(N^2): for i = 1 to N (for j = 1 to N)

O(log N): Algorithm that divides a search space in to 2 pieces at each step

O(log log N)

O(2^N): Selections of items. Dividing N items into two groups

O(N!): Arrangements of items.

ComparingFunctions1

ComparingFunctions2

ComparingFunctions3

Polynomial Time (P) and Non-deterministic Polynomial Time (NP)

Polynomial (P) algorithms are deterministic. There is no guessing of solution in these algorithms. You just follow the steps and you will get the result in polynomial time. For Example, to find the largest value in a list you just step through each value in the list and keep track of the largest value.

Non-deterministic Polynomial (NP) makes an inspired guess and verifies that the guess is correct. For Example, guess a password.

Subset Sum problem is an NP.

Does P = NP? Nobody has been able to prove that NP is not equal to P.

We know P is a subset of NP.

 

Random Numbers

True randomness is rare. Computers can do many complex things but they are still following definite instructions. The numbers generated can’t be really random if the are following definite instructions.

PRNG – Pseudo Random Number Generator: An algorithm with steps to generate random numbers. The numbers generated can be predicted if you know the algorithm. The numbers repeat even if its after a long period. They are the fastest.

CRNG – Cryptographic Random Number Generator: Hard to predict even if you know the algorithm. Tend to be slower than PRNG but more random.

TRNG – True Random Number Generator: Uses non-deterministic process to generate random numbers. For example – random fluctuations in radio signals, dice rolls, etc. They are complicated and relatively slow. Can use www.random.org to generate true random numbers.

 

Linked Lists

public class Cell

{

public int Value;

public Cell Next;

}

Iterate through a List

current = top

While (current <> null)

‘ Do something with the current cell

‘ Move to the next cell

current = current.Next

Loop

Insert at top

new_cell.Next = top

top = new_cell

Insert in Middle

Find the cell before

new_cell.Next = before.Next

before.Next = new_cell

Insert at End

before = top

While (before.Next <> null)

before = before.Next

 

new_cell.Next = before.Next

before.Next = new_cell

Remove from Beginning

top = top.Next

Remove from Middle

Find the cell before

before.Next = target_cell.Next

Sentinel is traversal node usually used at the beginning or the end of the list.

Adding a new item to a sorted list

before = sentinel

While ((before.Next <> null) and (before.Next.Value < new_cell.Value))

before = before.Next

Loop

new_cell.Next = before.Next

before.Next = new_cell

Adding a new item to a double linked list

AddAfter(new_cell)

new_cell.Next = this.Next

new_cell.Previous = this

this.Next = new_cell

new_cell.Next.Previous = new_cell

Removing an item from a double linked list

target.Next.Previous = target.Previous

target.Previos.Next = target.Next

 

Arrays

Finding the maximum ( O(N) )

max = values[0]

for i = 1 to n-1

if (max < values[i])

then max = values[i]

next i

 

Sorting Algorithms

SortingAlgorithmsComplexity

Which one should I use?

  • For very small list, use:
    • Selection Sort
    • Insertion sort
    • Bubble Sort
  • If the list is mostly sorted, use bubble sort
  • If the list contains integers, using counting sort
  • If the items don’t contain too many duplicates, use quick sort
  • If all else fails, use heap sort

 

Search Algorithms

Binary Search – O(log N)

min = 0

max = N – 1

while (min < max)

mid = (min + max) / 2

if (target = values[mid]) return mid

else if (target < values[mid] max = mid -1

else min = mid + 1

loop

 

Recursion

Fibonacci Series – O(Fibonacci(n))

Fibonacci(n)

if (n = 0) return 1

if (n = 1) return 1

return Fibonacci(n – 1) + Fibonacci(n – 2)

Improved Fibonacci Series –

F[] = {1, 1, 0, 0, 0, 0, …., 0}

Fibonacci(n)

if (F[n] = 0) then

F[n] = Fibonacci(n – 1) + Fibonacci(n – 2)

end if

return F(n)

Bottom-Up Approach

Fibonacci(n)

if (n <=1) then return 1

fn_minus_1 = 1

fn_minus_2 = 2

fn = fn_minus_1 + fn_minus_2

for i = 2 to n – 1

fn_minus_2 = fn_minus_1

fn_minus_1 = fn

fn = fn_minus_1 + fn_minus_2

next i

return fn