# 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.   ## 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.

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

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

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

for i = 1 to n-1

if (max < values[i])

then max = values[i]

next i

# Sorting Algorithms 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