Chapter 1 Flashcards
Steps of system life cycle & short descriptions of them
- Requirement
: set of specifications that defines the purpose of the program - Analysis
: Breaking down the problem into manageable pieces. - Design
: language dependence - Refinement and Coding
: language dependence - Verification
: Correctness proof, testing with variety of input data
Criteria of an ‘algorithm’ must satisfy?
- Input : zero or more quantities externally supplied.
- Output : At least one quantity is produced.
- Definiteness : Each instruction is clear and unambiguous.
- Finiteness : Algorithm must terminate in a finite number of steps.
- Effectiveness: Every instruction must be basic enough to be carried out.
Explain general idea of ‘Selection Sort’.
정리 안된 배열에서.
0부터 끝 인덱스까지 보면서 최솟값 찾기.
최솟값과 [0] 자리 원소 바꾸기.
1부터 끝 인덱스까지 보면서 최솟값 찾기.
최솟값과 [1] 자리 원소 바꾸기.
…
n-2(끝 바로 전 인덱스)부터 … 끝까지 보면서 최솟값 찾기
최솟값과 [n-2]자리 원소 바꾸기.
Make an actual code of ‘selection sort’.
include <stdio.h></stdio.h>
void swap(int* x, int* y){
int t;
t = *x;
*x = *y;
*y = t;
}
void sort(int list[], int n){
int min; // 최솟값의 인덱스
for(int i = 0; i < n-1; i++){
min = i;
for(int j = i + 1; j < n; j++){
if(list[min] > list[j]) min = j;
}
swap(&list[i], &list[min]);
} }
int main() {
int arr[10] = {9, 6, 5, 3, 10, 2, 7, 1, 4, 8};
sort(arr, 10);
return 0; }
Binary search의 핵심 컨셉
정렬된(오름이던 내림이던) 리스트에서 원하는 수를 찾기.
가운데 인덱스를 잡고 그보다 값이 큰지 작은지를 보면서 탐색 범위를 절반씩 쪼개는 방법.
Code binary search.
1. Normal way
2. Recursive way
끝으로 가면 불가능한 경우 무조건 right < left가 된다. 즉, 탐색 반복 조건은 left<= right일 경우.
1.
int binarySearch(int list[], int size, int searchNum){
int left = 0;
int right = size - 1;
while(left <= right){
int mid = (left + right) / 2;
if(searchNum == list[mid]) return mid;
if(searchNum < list[mid]){
right = mid - 1;
}
if(searchNum > list[mid]){
left = mid + 1;
}
}
return -1; }
- int binarySearch(int list[], int size, int searchNum, int left, int right){
int middle = (left + right) / 2;
if(left > right) return -1;
if(searchNum == list[middle]) return middle;
if(searchNum < list[middle]) binarySearch(list, size, searchNum, left, middle-1);
if(searchNum > list[middle]) binarySearch(list, size, searchNum, middle+1, right);
}
Binomial coefficients in both normal ways and recursive ways.
(just state equation, and final moments of recursive ways.)
- equation :
(n, m) = n! / (m! * (n-m)!) - final condition of recursive:
n == m || m == 0
(둘다 1 반환)
Permutation in recursive way
void perm(char* list, int startIndex, int endIndex) {
if (startIndex == endIndex) {
for (int i = 0; i <= endIndex; i++) {
printf(“%c “, list[i]);
}
printf(“\n”);
}
else {
for (int i = startIndex; i <= endIndex; i++) {
swap(&list[i], &list[startIndex]);
perm(list, startIndex + 1, endIndex);
swap(&list[i], &list[startIndex]);
}
}
}
핵심 : perm은 단순히 list를 재배열하는 것 뿐이고, 끝에 가서야 전체 list를 쫙 출력해주는 형식으로 해야 한다.
그러니깐 startIndex == endIndex일 때 전체 출력,
나머지 경우에 대해서는 시작인덱스와 j 번째 교환 –> 시작인덱스+1과 끝인덱스에서 재귀 –> 교환 복구를 반복
What is a ‘data type’?
Collection of objects & set of operations that act on those objects.
‘Abstract’ Data Type. what is it?
specification of the objects&operations != representation of the objects&operations
Space requirement for the program P, S(P) = ?
S(P) = c + S_P(I)
c is a fixed space requirement.
S_P(I) is a space that is required for an instance I to be working in a program P
당연한 말임. 고정 공간(코드를 담거나..하는 당연한 공간)과 인풋(instance)에 의존하는 가변 공간S_P(I)가 필요하다는 뜻.
Simple arithmetic function에서의 space requirement?
예) float abc(float a, float b, float c):
return a+b+b*c+(a+b-c)/(a+b)
고정공간c는 일단 당연히 존재.
가변공간이 있나? 어떤 abc가 들어오던 동일한 크기의 공간이 할당된다.
즉, 이게 고정공간일 것이고, 가변공간
S_abc(I) = 0이다.
배열을 주고 iterative sum을 하는 함수의 공간복잡도?
sum(float list[n], int size):
for(int i….)
sum+= list[i]
얼핏 보면 가변공간이 필요하다고 생각 가능. 하지만 배열을 넘겨줄 때 단순히 주소를 넘겨줌. C에서는 당연.
즉, 필요한 공간은 고정적이다.
S_sum(I) = 0
만약 다른 언어에서 이렇게 배열의 주소를 넘기는게 아니라 배열 자체를 복사해서 넘겨준다면 S_sum(I) = n으로, 계속 달라지는 n만큼의 공간이 가변적으로 할당되어야 했을 것.
Recursive function에서의 필요한 공간
rsum(float list[], int n):
if(n) return rsum(list, n-1) + list[n-1]
return list[0];
rsum을 한번 호출 할 때 할당되는 공간이 매개변수 2개를 위한 공간과 return할 주소를 담는 공간 1개로 총 3개이다.
이들 공간은 재귀가 발동할 때마다 계속 생성되기 때문에 가변적이다.
세보면 배열의 사이즈를 n이라 하면 이등 공간의 사이즈*n 만큼의 공간이 필요.
Definition of a ‘program step’
Meaningful program segments.
Tabular method for counting steps?
s/e * frequency = Total steps.
sum(Total steps).
for문의 조건문의 경우 비교연산만 고려
float rsum(list[], n):
if(n)
return rsum(list, n-1)+list[n-1]
return 0;
의 step count를 tabular method로
아무튼 2n+2
for(int i = 0; i<rows; i++):
for(int j = 0; j<cols; j++):
c[i][j] = a[i][j]+b[i][j];
의 step count
(rows+1) + rows(cols+1) + rows*cols
Big-O notation의 사전적 정의 + 직관적 의미
f(n) = O(g(n))
은 다음과 동치임.
f(n) <= c*g(n) (c는 양수)이 항상 성립하는 임계점 n0>0이 있음.
직관적으로는 특정 포인트를 넘어가면서부터는 f(n)은 절대 g(n)을 넘을 수 없다는 뜻.
Most common time complexities and their difference in computing times
O(1) < O(log n) < O(n) < O(n*log n) < O(n^2) < O(n^3) < O(2^n)
Is this statement correct?
2n+3 = O(n^2)
By the definition of the big-O notation, it is indeed correct.
2n+3<=c.n^2(c>0) for such n>=n0>0.
But it implies nothing since we can just add up any function higher than n^2. We must set g(n) to a minimal function.
Direction of proof of for a polynomial a_m n^m + … + a_0 = f(n), f(n) is O(g(n^m)).
계수들에 절댓값 씌우면 일단 그건 기존 식 이상임.
거기서 n^m만 따로 빼서 앞으로 묶기.
그러면 시그마 안쪽 n^(i-m)부분은 어차피 1 이하라서 그거 버리면 기존 식 이상임.
바로 증명 끝이고, 이러면 이제 기존 polynomial의 계수들의 절댓값의 합이 적절한 c라는 것 역시 알 수 있음
Omega notation의 사전적 정의/직관적 의미
Big-O notation의 반대 느낌.
Big-O는 f(n)이 g(n)을 절대로 넘지 못하는 임계점이 있는 거면, Omega는 반대로 g(n)이 특정 순간부터는 무조건 f(n)보다 작은 것.
there exists c, and n>=n0>0 s.t. f(n) >= cg(n) for all n.
for a polynomial that has positive coefficient for a^m, f(n) is omega(n^m). Proof?
…
theta notation의 정의와 의미
f(n) = theta(g(n))은 다음과 equivalent.
c1g(n)<=f(n)<=c2g(n)임. 특정 포인트 이후로 계속. c1, c2>0이고 특정 포인트 역시 양수.
즉, big-O와 omega 를 합친 것. 이게 성립할 경우 당연히 정의 상 f(n) = O(g(n))이고 f(n) = omega(g(n)).
마방진의 coxeter’s rule
n is odd.
맨 윗줄 중앙에 1.
방금 놓은 주소 위, 왼쪽에 다음 숫자. 점용된 공간이면 방금 놓은 주소 아래에.
(위 혹은 왼쪽이 경계 바깥인 경우 …암튼 그렇게)
