NotesAtHKU

Example 2: $n^2 \in O(2^n)$ ( $n^2 \leq 2^n$ order of growth. This is one of the many satisfying $g(n)$ . The useful $g(n)$ would be: $n^2 \in O(n^2)$ )

Example 3: $n\log n \in \Omega(e^{\log n})$ ( $n\log n \geq n$ )

Data Structures

Reverse a linked list psuedocode

Example implementation of reversing a linked list. Reference section

def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        next = current.next
        current.next = prev
        prev = current
        current = next
    return prev
 
def find_middle_node(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Find middle node of a linked list psuedocode

Example implementation of finding the middle node of a linked list. Reference section

def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        next = current.next
        current.next = prev
        prev = current
        current = next
    return prev
 
def find_middle_node(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

BFS psuedocode

Example implementation of BFS. Reference section

def bfs(mtx, start):
    q = Queue()
    
    q.enqueue(start) # queue start node
    qd = [start]
    
    while not q.isEmpty():
        cur = q.dequeue() # visit node
        print(cur)
        for x in mtx[cur]:
            if x not in qd:    # if not queued
                q.enqueue(x)  # put in queue
                qd.append(x)   # mark as queued

Unsuccessful search

Example of finding the average number of slots inspected for unsuccessful search of built hash table with resolution method double hashing. Reference section

$m = 5,\quad h(k) = k \mod 5$ with double hashing $f(i) = i \cdot h'(k),\quad h'(k) = 2 - (k \mod 2)$ .

Therefore the average is $\frac{(4+1+3+1+2)+(2+1+2+1+3)}{5\times 2} = 2$

Sorting

Selection sort psuedocode

Example of implementation of selection sort. Sort Summary

function selection_sort(array):
    for i in array:
        min_index = i
        for j in array after i:
            if current element < min element:
                min_index = j
        swap(A, i, min_index)
    return A

Bubble sort psuedocode

Example of implementation of bubble sort. Sort Summary

function bubble_sort(array, n): 
    for i in 0 to n - 1:
        swapped = False
        for j in 0 to before n - i - 1:
            if current element > next element:
                swap(current, next)
                swapped = True
        if not swapped break 
        # if no two elements were swapped, the array is sorted
    return A

Insertion sort psuedocode

Example of implementation of insertion sort. Sort Summary

function insertion_sort(array):
    for i in array after 0:
        for j in array before i reversed:
            if array[j] > array[i]:
                swap(array, i, j)
            else:
                break
    return array

Heap sort psuedocode

Example of implementation of heap sort. Sort Summary

function heap_sort(array):
    create_max_heap(array)
 
    for i from right in array:
        swap(array, 0, i)
        heapify(array from 0 to i - 1)
    
    return array

Merge sort psuedocode

Example of implementation of merge sort. Sort Summary

function merge_sort(array):
    function merge(A1, A2):
        result = []
        while A1 and A2:
            if A1[0] < A2[0]:
                result.append(A1.pop(0))
            else:
                result.append(A2.pop(0))
        return result + A1 + A2
    
    if len(array) < 2 return array
 
    mid = len(array) // 2
    left = merge_sort(array to mid)
    right = merge_sort(array after mid)
 
    return merge(left, right)

Quick sort psuedocode

Example of implementation of quick sort. Sort Summary

function quick_sort(array):
    function partition(array):
        pivot = random index from array
        swap = -1
 
        for j in array:
            if current element < pivot element:
                swap += 1
                swap(arr, swap, current)
        
        # move pivot element to its correct position
        pivot_index = swap + 1
        swap(arr, pivot_index, pivot) 
        return pivot_index
    
    if len(array) < 2 return array
 
    pivot = partition(array)
    quickSort(array before pivot)
    quickSort(array after pivot)

Count sort psuedocode

Example of implementation of count sort. Sort Summary

function counting_sort(array):
    k = max(array) # O(n)
    counter = Array(k)
    for i in array:
        counter[i] += 1
    
    for i in counter after 0:
        counter[i] += counter[i-1]
    
    result = Array(len(array))
    for i, x in array:
        result[counter[x]-1] = x
        counter[x] -= 1
    
    return result

Radix sort psuedocode

Example of implementation of radix sort. Sort Summary

function radix_sort(array, b=10):
    function countin_sort_exp(i):
        function get_key(n):
            return ith digit of n in base b (0 based)
            # (n // b**i) % b
 
        counter = Array(b)
        for i in array:
            key = get_key(i)
            counter[key] += 1
            
            for i in counter after 0:
                counter[i] += counter[i-1]
            
            result = Array(len(array))
            for x in array:
                key = get_key(x)
                result[counter[key]] = x
                counter[key] -= 1
            array = result
 
    d = len(max(array))
 
    for i from 0 to d - 1:
        counting_sort_exp(i)

Examples & questions bank

Recursion

Solve recurrence relation with substitution method

Proving with Mathematical Induction

Algorithm Analysis

Disproving Big O notation

Proving Little o notation

Proving Big Theta notation

Identifying asymptotic growths