! This is a note from MIT 6.006 Introduction to Algorithmic - YouTube

## Lecture 01: Algorithmic Thinking, Peek Finding

• find a peek in a Array

• find a peek in a 2D Array

2022/07/24 done.

## Lecture 02: Models of Computation, Document Distance

• algorithm term from “al-Khwarizmi”

• What’s a algorithm?

• computational procedure from solving a problem.
• `input` -> `alg` -> `output`
• Model of computation specifies

• what operation an algorithm is allowed
• cost (time, space …) of each operation
1. Random Access Machine (RAM)
• random access memory: modeled by big array
• an algorithm in O(1) time can (# O(1) : mean constant)
• load O(1) words (# word: w bits)
• do O(1) computations
• store O(1) words
• O(1) registers
1. Pointer Machine (modern language calls reference)
• dynamically allocated objects
• object has O(1) fields (# filed = word e.g. int or pointer)
• Python model:

• list = array
• object with O(1) attributes
• dict get value O(1)
• long long int
• heap
• Document distance problem:

• Q: d(D1, D2) (like google, wiki)
• document = sequence of words
• word = string of alphanumeric characters
• idea: shared words
• think of document as a vector, D[w] = number of occurrent of w in D
• inner product, D1.D2 / |D1||D2|
• Algorithm:
1. split doc. to words
2. compute word frequencies
3. dot product

2022/07/27 done.

## Lecture 03: Insertion Sort, Merge Sort

• why sorting?
• obverse: phone, book
• problem that become easy once items are sorted
• Finding a median
• array A [0:n] -> B[0:n]
• Binary search
• A[0:n] looking for specific item k
• compare B[0:n]
• Insertion sort
• For i = 1, 2, … n. Insert A[i] into sorted array A[0: i - 1]
• complexity: O(n^2)
• Binary Search Insertion Sort
• complexity: O(n * log(n))
• Merge sort (Divide & Conquer)
• split arrayA to arrayL and arrayR
• Merge: Two sorted arrays an input
• complexity: Theta(n * log(n)), Space: Theta(n)
• In-place merge sort (good to read paper but beyond of MIT6.006)
• Implement in others language:
• Merge sort in Python = 2.2 * n * log(n) ms
• Insertion sort in Python = 0.2 * n^2 ms
• Merge sort in C = 0.0.1 * n * log(n) ms
• so if n more than 4,000 then choose use Merge sort rather than Insertion sort

2022/08/28 done.

## Lecture 04: Heaps and Heap Sort

• Heap

• insert(S, x): in sort element x into set S

• max(S): return element of S with the largest key
• extract-max(S): return element of S with the largest key and remove it from S
• increase-key(S, x, k): increase the value of x’s key to new value k
• Heap is a Tree

• root of tree: first element (i = 1)
• parent(i) = i / 2
• left(i) = 2i
• right(i) = 2i + 1
• Max-Heap
The key of a node is >= the keys of its children

• Min-Heap
The key of a node is <= the keys of its children

• Heap operations

• build_max_heap: produce a max heap from an unordered array
• max_heapify: correct a single violation of the heap property is a subtree’s root
• Max Heapify

• Assume that the heap rooted at left(i) and right(j) are max heaps
• ex:
• MAX_HEAPIFY(A, 2), heap-size(A) = 10
• exchange A[2] with A[4]
• call MAX_HEAPIFY(A, 4)
• exchange A[4] with A[8]
• done
• Convert A[1 … n] into a max-heap

• Observe of Max_Heapify:
• Max_Heapify taken O(1) for nodes that are one level above the leaves and in general O(`l`) time for nodes that are `l` level above the leaves.
• n/4 nodes with level 1, n/8 with level 2, … i node log(n) level
• Total amt of work in the for loop
• n/4(1 c) + n/8(2 c) + n/16(3 c) + … + 1(log(n) c)
• Set n/4 = 2^k
• Heap sort (n log(n))

• Build_max_heap from unordered array
• Find max element A[i]
• Swap elements A[n] with A[i], now max element is at the end of array
• Discord node n from heap. decrementing heap size.
• New root may violate max-heap, but children are max heaps, max_heapify

2022/10/08 done.

## Lecture 05: Binary Search Tree, BST Sort

• Scheduling & Binary Search Trees
• Runway reservation system
• Def n
• How to solve with arrays/lists
• Binary Search Trees operations
• TODO