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
- 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
- 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:
- split doc. to words
- compute word frequencies
- dot product
2022/07/27 done.
Lecture 03: Insertion Sort, Merge Sort
- TODO