Homework #3 (due

(1)

(due date: 4/14(목))

1. n개의 정수를 갖는 리스트를 입력으로 갖고, 리스트에서 연속적인 정수간의 차 중에서 가장 큰 값을 출력하는 알고리즘을 작성하시오.

2. 배정문만을 사용하여 세 개의 수 (x, y, z)를 (y, z, x)로 교체하는 알고리즘을 작성하시오. 이 작 업에 필요 한 배정문의 최소 개수는 얼마인가?

3. 버블정렬을 이용하여 6, 2, 3, 1, 5, 4를 정렬하시오. 각 단계에서 얻어지는 리스트를 보이시오.

4. 2^x + 17이 O(3^x)임을 보이시오.

5. x³이 O(x⁴)이지만 x⁴이 O(x³)이 아님을 증명하시오.

6. x = c 일 때, a x_n ⁿa x_n_₁ ⁿ^¹  a x a₁  ₀의 해를 구하는 전통적인 알고리즘은 다음과 같이 표현된다.

procedure polynomial(c a a, , , , , ₀ ₁  a_n_₁ a_n⁾ : 1;

power  : 0; y a for i := 1 to n begin

power:power c ; y:  y a power_i ;

end

n 1 n ¹ 1 0

n n

y a c a c_ ^   a c a

(참고: 마지막 y의 값은 x = c일 때의 다항식 계산 값을 갖게 된다.) (a) 알고리즘의 각 단계를 수행하면서 x = 2일 때 3x² x 1을 구하여라.

(b) x = c일 때 n차 다항식을 계산하기 위해 곱셈과 덧셈이 정확히 몇 번 이루어지는가?

(루프 변수를 증가시키는데 사용되는 덧셈은 제외하라.)