This is my daily life log.

2022-03-06

Understand Algorithm Evaluation and Fundamental Algorithms

Algorithm Evaluation

The main indicator to evaluate algorithms is the speed to process data. The major way to evaluate the speed of the algorithm is Big O notation.

Big O notation

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.(wikipedia: Big O notation)

In other word, Big O(Order) notation is the calculation ability of the functions according to how these run time or space requirements grow as the input size grows. The letter O is used because the growth rate of a function is also referred to as the order of the function.

There are the two key words to understand Big O notation like the below:Time complexity: time to finish the function executionSpace complexity: memory to use for the function execution

Time complexity is the same as space complexity but the usage is different.

Representations of Big O notation:O(1) > O(log n) > O(n) >O(n log n)> O(n2) > O(n3) > O(nn)

Reload again, if you are not able to see images.

This image is created by Jesse Tetsuya.

Coding example

# O(1)
def func1(nums):
    return nums[0]
# O(log(n))
def func2(nums):
    for num in nums:    
        if num < 1:
            return num 
        else:
            print(num)
# O(n)
def func3(nums):
    for num in nums:
        print(num)
# O(n*log(n))
def func4(nums):
    for i in nums:
        for j in i:
            if j > 15:
                print(j)
# O(n**2)
def func5(nums):
    for i in nums:
        for j in i:
            print(j)

References of time complexity:

Algorithm approach

There are two kinds of approaches and three algorithms to process data.

This image is created by Jesse Tetsuya.

Bottom up approach:

small number -> big number

for i in range(5):
    print(i)
-> 0,1,2,3,4

Top down approach:

big number -> small number

def recursion(N):
    if N < 2:
        return N
    print(N)
    return recursion(N-1)
recursion(5)
-> 5, 4, 3, 2, 1

Brute force

= for loop

Divide and Conquer

A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.

In short word, divide a problem into a few subproblems or more.=recursion

Dynamic algorithm

A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. On the top of that, store the result and re-use it.

In short word, divide a problem into a few subproblems or more and re-use the results of them.- recursion or for loop- memoization

CASE STUDY with Fibonacci Sequence:

# brute force with in-place
def fib(N: int) -> int:
    if N < 2:
        return N
    
    first, second = 0,1 
    for i in range(2, N+1):
        first, second = second, first + second
    return second
    
# brute force with list
def fib(N: int) -> int:
    if N < 2:
        return N
    fib_seq = [0,1]
    for i in range(2, N):
        fib_seq.append(fib_seq[i -1] + fib_seq[i -2])
    return fib_seq[-1] + fib_seq[-2]
    
# brute force with memoization and dict
def fib_memoize(N: int) -> int:
    if N < 2:
        return N
    cache = {0:0, 1:1}
    for i in range(2, N+1):
        cache[i] = cache[i-1] + cache[i-2]
    print(cache)
    return cache[N]
    
# brute force with memoization and list
def fib(n):
    A = [None] * (n+1)
    A[0] = 0
    A[1] = 1
    for i in range(2, n+1):
        print(A)
        A[i] = A[i-1] + A[i-2]
    return A[n]
    
# divide and conquer with recursion
def fib(N:int) -> int:
    if N < 2:
        return N
    
    # divide a problem into subproblem a
    a = fib(N-1)
    # divide a problem into subproblem b
    b = fib(N-2)
    # conquer
    c = a+b
    print(f"a: {a}, b:{b}, c:{c}, n:{n}")
    return c

# ===print output of divide and conquer with recursion
# $ python fib.py
# a: 1, b:0, c:1, n:2
# a: 1, b:1, c:2, n:3
# a: 1, b:0, c:1, n:2
# a: 2, b:1, c:3, n:4
# a: 1, b:0, c:1, n:2
# a: 1, b:1, c:2, n:3
# a: 3, b:2, c:5, n:5
# 5
# ===

# recursion with memoization to store the overlapped sub-problems
def fib_memo(n):
    # initialize memo 
    memo = {}
    def fib_m(n, memo):
        if n == 0 or n == 1:
            return n
        if n not in memo:
            res = fib_m(n-1, memo) + fib_m(n-2, memo) # 1, 0 -> {2: 1}...
            memo[n] = res
            return res
        print(memo)
        return memo[n]
    return fib_m(n, memo)

# ===print output of recursion with memoization
# {2: 1, 3: 2}
# {2: 1, 3: 2, 4: 3}
# 5
# ===

# dynamic algorithm with memoization
def fib_dynamic(n):
    fib = {}
    for k in range(1, n+1):
        if k <= 2:
            f = 1
        else:
            # re-use
            f = fib[k-1] + fib[k-2]
        # memoize
        fib[k] = f
    return fib[n]

References of Algorithm:

19. Dynamic Programming I: Fibonacci, Shortest Paths

Recursion

Three steps to implement Recursion:

Base case — Think of the simplest possible input for this function
Find the relation — Think how the larger problem can be solved with the help of the solution of the smaller problem
Generalize —Make a generalized function that solves the problem. Put this all together into a Mathematical function or a Tree.

Six Recursive Patterns:

Iteration — ex) Linked List in reverse order, Factorial, For loop
Breaking Into Subproblems — ex) Towers of Hanoi, Fibonacci
Selection — ex) Knapsack, Word break…etc.
Ording — ex) Permutationse…etc.
Divide and Conquer — ex) Mergesort, Generate all BSTs for a set of items
Depth First Search — ex) Search in a tree…etc.

Tree representation of Fibonacci Sequence:

You should understand the below picture following the code of divide and conquer approach by recursion and the code of recursion with memoization.

Fundamental Algorithms

Sort algorithms

Learning sort algorithms can be a good stepping stone to learn the core principle of the algorithms.

This is the basic sort algorithms and the speed ability of each here.

This image is created by Jesse Tetsuya.

Bubble sort: a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.

import random
nums = [random.randint(0,1000) for _ in range(10)]
len_nums = len(nums)
for i in range(1, len_nums):
    for j in range(len_nums):
        if nums[j] > nums[i]:
            nums[j], nums[i] = nums[i], nums[j]

Selection sort: the selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.

import random
nums = [random.randint(0,1000) for _ in range(10)]
len_nums = len(nums)
for i in range(len_nums):
    min_index = i
    for j in range(len_nums):
        if nums[j] > nums[min_index]:
            nums[j], nums[min_index] = nums[min_index], nums[j]

Insertion sort: the array elements are compared with each other sequentially and then arranged simultaneously in some particular order.

import random
nums = [random.randint(0,1000) for _ in range(10)]
len_nums = len(nums)
for i in range(1, len_nums):
    for j in range(i):
        if nums[j] > nums[i]:
            nums[j], nums[i] = nums[i], nums[j]

Quick sort: a type of Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot

nums = [random.randint(0,1000) for _ in range(10)]
def sort(nums):
    if len(nums) < 2:
        return nums
    
    pivot = nums[0]
    x, y = divide(pivot, nums[1:])
    return sort(x) + [pivot] +sort(y)

def divide(pivot, nums):
    if len(nums) < 1:
        return ([], [])
    
    x, y = divide(pivot, nums[1:])
    num = nums[0]
    if num < pivot:
        return [num] + x, y
    else:
        return x, [num]+y

Merge sort: a type of Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The point is that the numbers are sorted just when the numbers are merged.

def sort(nums):
    if len(nums) < 2:
        return nums
    center = len(nums) // 2
    left = sort(nums[:center])
    right = sort(nums[center:])
    return merge(left, right)

def merge(left, right):
    if len(left)<1:
        return right
    if len(right)<1:
        return left
    
    if left[0] > right[0]:
        return [right[0]] + merge(left, right[1:])
    else:
        return [left[0]] + merge(left[1:], right)

Search, Stack, and Queue

Search: the algorithm to find the number which you want. There are three kinds of basic search algorithms such as linear search, binary search, and binary search with recursion. The input data of the below code is sorted in order.

# linear search
import random
target = 217
nums = [1, 103, 196, 217, 262, 420, 577, 630, 649, 908]
def linear_search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
          
# binary search
def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        center = (left + right) // 2 
        if nums[center] == target:
            return center
        elif nums[center] < target:
            left = center +1
        else:
            right = center -1
            
# binary search with recursion
def binary_search(nums, target):
    def _binary_search(nums, target, left, right):
        if left > right:
            return -1
        center = (left + right) //2
        if nums[center] == target:
            return center
        elif nums[center] < target:
            return _binary_search(nums, target, center+1, right)
        else:
            return _binary_search(nums, target, 0, center-1)
    return _binary_search(nums, target, 0, len(nums)-1)

Stack: a stack is an abstract data type that serves as a collection of elements, with two main principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed.

format1 = {"key1": "value1", "key2": [1,2,3], "key3":(1,2,3)}
format2 = "[]"
format3 = "[][[{}]]{"

# validate pair format
def validate_format(char):
    lookup = {"{":"}", "[":"]", "(":")"}
stack = []
    for c in char:
        if c in lookup.keys():
            stack.append(lookup[c])
        if c in lookup.values():
            if not stack:
                return False
            if c != stack.pop():
                return False
    if stack:
        return False
    return True
  
# reverse string
from collections import deque
sentence = 'gnirtS esreveR'
def reverse_str(sentence):
    stack = deque(sentence)
return ''.join(stack.pop() for _ in range(len(sentence)))

reverse_str(sentence)
-> 'Reverse String'

Queue: a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue).

from collections import deque
def reverse(queue):
    new_queue = deque()
    while queue:
        new_queue.append(queue.pop())
    return new_queue
  
q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)
print(q)
q = reverse(q)
print(q)
-> deque([1, 2, 3, 4])
-> deque([4, 3, 2, 1])

＊ deque allows us to add and remove from both sides of queue. While List needs O(n) to add and remove by using insert() and pop(), deque has append(), appendleft(), pop(), and popleft() which are O(1).

Articles about Applied Algorithms

‌

‌‌‌

‌

‌‌‌

‌

‌‌‌