MIT 6.006 Introduction to Algorithmic 01

! 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
• 2. 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

  build_max_heap(A):
    for i = n/2 down to 1
      do max_heapify

  • 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

Ref

• MIT 6.006 Introduction to Algorithmic - YouTube