Benben 的小宇宙

喜歡寫程式,也喜歡寫文字。

0%

MIT 6.006 Introduction to Algorithmic 01

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

  • TODO

Ref