170613(화) - Stanford Engineering's Algorithms (Introduction)

Stanford Engineering's Algorithms (Introduction)

What is an algorithm

- basically, set of well defined rules.

- recipe in effect for solving some computational problem.

Why Study Algorithms

1. basic of algorithms and the related field of data structures is essential for computer science.

2. modern technology에서 핵심적인 역할

3. computer science 이외의 영역에서도 많이 사용되고 있다.

Good algorithm designer is to refuse to be content!

Can we do better?

Integer Multiplications

2n : multiply, second number의 합

Karatsuba Multiplication

About the course

1. Vocabulary for reasoning about algorithm performance.

2. the divide and conquer algorithm design paradigm

3. Randomization and algorithm design

4. Primitives for reasoning about graphs

5. Use and implementation of basic data structures.

Vocabulary for reasoning about algorithm performance.

- Big-Oh notation

- algorithms 에 대한 high level reasoning을 위한 sweet spot

Divide and conquer algorithms design paradigm

- ex) integer multiplication, sorting, matrix multiplication, closet pair

- General analysis methods ("master Method / Theorem")

Randomization in algorithm design paradigm

- ex) QuickSort, primality testing, graph partitioning, hashing

Primitives for reasoning about graphs

 - ex) connectivity information, shortest paths, structure of information and social network.

Use and implementation of data structures

- ex) Heaps, balanced binary search trees, hashing and some variants (bloom filters)

Merge Sort: Motivation and Example

Why Study Merge Sort?

- Good introduction to devide and conquer

Selection, insertion, bubble sort 보다 향상

- Calibrate your preparation

- Motivates guiding principles for algorithm analysis. (worst-case and asymptotic analysis)

- Analysis generalizes to "master method"

     

- Merge Sort: Pseudocode

Merge and sort: Analysis

Claim : input n, Merge sort output most  operations

Guiding principles analysis of algorithms

- Worst case analysis

- our running rime bound holds for every input of length n.

- particularly appropriate for "general purpose" routines

- As opposed to 

average case analysis

benchmarks

▶Both requires domain knowledge!

Bonus : worst case usually easier to analyze.

- Won't pay much attention to constant factors, lower order terms

Justifications

1. way easier

2. constants depend on architecture / compiler / programmer anyways

3. lose very little predictive power (as we'll see)

- Asymptotic Analysis : focus on running time for large input sizes n.

justification : only big problems are interesting.

- larger n, merge sort is better then insertion sort!

- What is a Fast algorithm?

- adopt these three biases as guiding principles

fast algorithms   worst case running time grows slowly with input size

- usually : want as close to linear (O(n)) as possible.