Algorithms

---

1. Algorithm

• input과 output을 가지는 well-defined computational procedure
• well-specified computational problem을 해결하기 위한 tool

2. Instance

• problem의 constraints를 만족하는 모든 input

3. Correct

• algorithm이 모든 instance에 대해 correct output을 갖는 경우
• correct algorithm일 때 computational problem을 solve

What kinds of problems are solved by algorithms?

1. Examples

• The Human Genome Project
• The Internet
• Electronic commerce
• Optimization
• Shortest route

2. Characteristics that are common to many interesting algorithmic problems

• 많은 수의 candidate solutions가 존재하지만 그중 거의 대부분이 problem을 해결하지 못 한다
• pratical applications 가능

Data structures

• access와 modifications를 더 쉽고 빠르게 하기 위해 data를 저장하고 구성하는 way

Technique

This book will..

• 나만의 algorithms를 개발하기 위한 algorithm design과 analysis의 techniques를 알려줄 것이다
• techniques가 correct answer를 주는 것을 보여줄 것이고 techniques의 efficiency를 이해시킬 것이다

Hard problems

NP-complete problem

• efficient solution이 존재하는지 안하는지 알려지지 않은 problems
• 만약 NP-complete problems들 중 어느 하나라도 efficient algorithm이 존재하면, 모든 NP-complete problems의 efficeint algorithms가 존재한다
• 몇몇 NP-complete problems는 이미 efficient algorithms가 알려진 problems와 매우 유사하다
• 종종 real applications에서도 NP-complete problems이 발생한다
• efficient algorithms의 대안으로 approximation algorithms가 존재한다

Parallelism

• processor의 clock speeds를 증가시키는 것에 physical limitations 존재
• computations per second의 양을 위해 여러 개의 processing cores 사용
• multicore computers는 parallelism을 고려한 algorithms 필요

Algorithms as a technology

---

Reason to study algorithms

• correct answer를 가지는 solution 설계
• computing time과 space는 bounded resource

Efficiency

Insertion sort vs Merge sort

• same problem을 해결하기 위한 different algorithms끼리 efficiency 차이가 심한 경우 자주 존재
  • insertion sort의 실행시간 : $c_1n^2$
  • merge sort의 실행시간 : $c_2n\log_{2}{(n)}$
• input size $n$이 일정 수준 이상 커지면 $c_1$이 $c_2$보다 아무리 작아도 $n$과 $\log_{2}{(n)}$의 차이로 merge sort가 더 빨라진다
• $n$이 커질수록 efficiency 차이가 매우 커진다

Algorithms and other technologies

• total system performance는 algorithms 뿐만 아니라 다양한 technologies에 의존
• contemporary technologies를 사용하는 some applications는 algorithmic content를 application level에서 요구하지 않지만 여전히 algorithm은 중요하다
• certain operations에 algorithms가 요구되고 대부분의 contemporary technologies는 결국 algorithms가 core
• capacities가 커진 contemporary computers를 전보다 큰 규모의 problems 해결을 위해 사용할 수 있는데, problem sizes가 커질수록 algorithms끼리의 efficiency 차이는 더 중요해진다
• algorithms를 잘 몰라도 contemporary technologies로 some tasks를 수행할 수 있지만, algorithms에 대한 background가 좋다면 훨씬 더 많은 것을 할 수 있을 것이다