Computer Algorithm
프로그래밍을 중심으로
남수 진
다음커뮤니케이션
Part I
Bitmap Sorting
Programming Pearls Bitmap Sorting
The Problem
Input
A file containing at most n positive integers, each less than n, where n = 107. It is a fatal error if any integer occurs twice in the input. No other data is associated with the inter.Output
A sorted list in increasing order of the input integers.Constraints
At most (roughly) a megabye of storage is available in main memory; ample disk storage is available. The run time can be at most several minutes; a run time of ten seconds need not be decreased.Programming Pearls Bitmap Sorting
Implementation Sketch
Viewd in this light, the bitmap or bit vector representation of a set screams out to be used. We can represent a toy set of nonnegative integers less than 20 by a string of 20 bits. For instance, we can store the set {1, 2, 3, 5, 8, 13} in this string:
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
The bits representing numbers in the set are 1, and all other bits are 0.
/* phase 1: initialize set to empty */
for i = [0, n) bit[i] = 0
/* phase 2: insert present elements into the set */
for each i in the input file bit[i] = 1
Part II
Vector Rotation
Programming Pearls Vector rotation
The Problem
Rotate a one-dimensional vector of n elements left by d positions.
For instance, with n = 8 and d = 3,
the vector abcdefgh is rotated to defghabc.
Can you rotate the vector in time proportional to n using only a few dozen extra bytes of storage?
Programming Pearls Vector rotation
Pricey Solutions
One might try to solve the problem by copying the first d elements of x to a temporary array, moving the remaining n − d elements left d places, and then copying the first d from the temporary array back to the last positions in x.
One could define a function to rotate x left one position (in time proportional to n) and call it d times, but that would be too time-expensive.
Programming Pearls Vector rotation
The Juggling Algorithm
The Idea (n = 12, d = 3):
Programming Pearls Vector rotation
The Block-Swap Algorithm
The Idea:
Change ab to ba
If a is shorter, divide b into bl and br . Swap a and br to change ablbrinto brbla.
Recur on pieces of b.
Programming Pearls Vector rotation
The Reversal Algorithm
The Idea:
Reverse a to get arb.
Reverse b to get arbr.
Reverse all to get (arbr)r= ba.
Part III
Josephus Problem
Concrete Mathematics Josephus problem
An ancient problem named for Flavius Josephus
Legend has it that Josephus wouldn’t have lived to become famous without his mathematical talents. During the Jewish-Roman war, he was among a band of 41 the rebels trapped in a cave by the Romans.
Preferring sucide to capture, the rebels decided to form a circle and, proceeding around it, to kill every third remaining persion until no one was left.
Concrete Mathematics Josephus problem
Josephus problem
In our variation, we start with n people numbered 1 to n around a circle, and we eliminate every second remaining persion until only one survives.
2, 4, 6, 8, 10, 3, 7, 1, 9, so 5 survives.
The Problem: Determine the survivor’s number, J(n).
For example, J(10) = 5.
Concrete Mathematics Josephus problem
J(n) = n/2
We just saw that J(10) = 5. We might conjecture that J(n) = n/2 when n is even;
J(10) = 5 J(2) = 1 The conjecture fails for n = 4 and n = 6
n 1 2 3 4 5 6
J(n) 1 1 3 1 3 5
Concrete Mathematics Josephus problem
J(2n), When the number is even
If n itself is an even number, we arrive at a situation similar to what we begin with, except that there are only half as many people, and their numbers have changed.
So let’s suppose that we have 2n people originally.J(2n) = 2J(n) − 1, for n ≥ 1.
J(20) = 2J(10) − 1 = 2· 5 − 1 = 9
Concrete Mathematics Josephus problem
J(2n + 1), What about the odd case?
With 2n + 1 people, it turns out that person number 1 is wiped out just after person number 2n, and we’re left with
J(2n + 1) = 2J(n) + 1, for n ≥ 1.
Concrete Mathematics Josephus problem
Recurrence of the problem
Combining these equations with J(1) = 1 give us a recurrence that define J in all cases:
J(1) = 1;
J(2n) = 2J(n) − 1, for n ≥ 1;
J(2n + 1) = 2J(n) + 1, for n ≥ 1.
This recurrence is much more “efficient,” because it reduces n by a factor of 2 or more each time it’s applied. We could compute J(100000), say, with only 19 application above equation. But still, we seek a
closed
form,
because that will be even quicker and more informative. After all, this is a matter of life or death.Concrete Mathematics Josephus problem
Seek the closed form of our recurrence.
Our recurrence make it possible to build a table of small values very quickly.
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 J(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1
Volià! It seems we can group by power of 2; J(n) is always 1 at the beginning of a group and it increased by 2 within a group. So if we write n in the form n = 2m+ l, where 2m is the largest power of 2 not exceeding n and where l is what’s left, the solution to our recurrence seem to beJ(2 m + l) = 2l + 1, for m ≥ 0 and 0 ≤ l < 2 m .
Concrete Mathematics Josephus problem
Solve J(n) by computer program.
The solution to our recurrence
J(n) = J(2m+ l) = 2l + 1, for m ≥ 0 and 0 ≤ l < 2m. C program to solve J(n):
unsigned josephus(unsigned n) {
unsigned m;
for (m = 1; m <= n; m *= 2) ; return 2*(n-m/2) + 1;
}
Power of 2 played an important role in our finding solution. It’s natural to look at the radix 2 representation of n and J(n).
Concrete Mathematics Josephus problem
Seek the soft method.
Suppose n’s binary expression, n = 2m+ l (m ≥ 0, 0 ≤ l < 2m) n = bm2m+ bm−12m−1+ . . . + b12 + b0= (bm bm−1 . . . b1 b0)2, where each bi is either 0 or 1 and where the leading bit bm is 1.
n = (1 bm−1 bm−2 . . . b1 b0)2, l = (0 bm−1 bm−2 . . . b1 b0)2, 2l = (bm−1 bm−2 . . . b1 b0 0)2, 2l + 1 = (bm−1 bm−2 . . . b1 b0 1)2,
J(n) = (bm−1 bm−2 . . . b1 b0 bm)2.
Concrete Mathematics Josephus problem
Illustrate the magic.
√Let’s compute J(100). In this case we have 100 = 26+ 36, so J(100) = 2· 36 + 1 = 73.
n = 100 = (1100100)2 J(n) = J ((1100100)2)
= (1001001)2
= 26+ 23+ 1 = 64 + 8 + 1
= 73.
C program to solve J(n):
unsigned josephus(unsigned n) {
unsigned k, m;
for (m=n, k=0; m!=1; k++, m>>=1) ; return ((n & (1<<k)-1) << 1) | 1;
}
Concrete Mathematics Josephus problem
When J(n) = n/2 is true?
Let’s return briefly to our first guess, that J(n) = n/2 when n is even.
J(n) = n/2 2l + 1 = (2m+ l)/2
l = 1
3(2m− 2).
m l n = 2m+ l J(n) = 2l + 1 = n/2 n(binary)
1 0 2 1 10
3 2 10 5 1010
5 10 42 21 101010
7 42 170 85 10101010
Concrete Mathematics Josephus problem
Generalize the problem.
Does the generalized Josephus recurrence admit of such magic?
f(1) = α;
f(2n + j) = 2f(n) + βj, for j = 0, 1 and n ≥ 1.
And this recurrence unfolds, binary-wise:
f ((bm bm−1 . . . b1 b0)2)
= 2f ((bm bm−1 . . . b1)2) + βb0
= 4f ((bm bm−1 . . . b2)2) + 2βb1+ βb0 ...
= 2mf ((bm)2) + 2m−1βbm−1+· · · + 2βb1+ βb0
= 2mα + 2m−1βbm−1+· · · + 2βb1+ βb0.
f ((b m b m−1 . . . b 1 b 0 ) 2 ) = (α β b
m−1β b
m−2· · · β b
1β b
0) 2 .
Concrete Mathematics Josephus problem
Check the generalized solution.
Let’s check the following equation.
f ((b m b m−1 . . . b 1 b 0 ) 2 ) = (α β b
m−1β b
m−2· · · β b
1β b
0) 2 .
For example, when n = 100 = (1100100)2, our original Josephus values α = 1, β0= −1, and β1 = 1 yield.
n = (1 1 0 0 1 0 0)2 = 100
f(n) = (1 1 −1 −1 1 −1 −1)2
+64 +32 −16 −8 +4 −2 −1 = 73.
The cyclic-shift property follows because each block of binary digits (10· · · 00)2 in the representation of n is transformed into
Concrete Mathematics Josephus problem
Generalization of the Josephus problem
If we’re really uninhibited, we can now generalize even more. The recurrence
f(j) = αj, for 1 ≤ j < d;
f(dn + j) = cf(n) + βj, for 0 ≤ j < d and n ≥ 1.
is the same as the previous one except that we start with numbers in radix d and produce value in radix c. That is, it has the radix-changing solution
f ((b m b m−1 . . . b 1 b 0 ) d ) = (α b
mβ b
m−1β b
m−2· · · β b
1β b
0) c .
Concrete Mathematics Josephus problem
Example of the generalization
For example,
f(1) = 34, f(2) = 5,
f(3n) = 10f(n) + 76, for n ≥ 1, f(3n + 1) = 10f(n) − 2, for n ≥ 1, f(3n + 2) = 10f(n) + 8, for n ≥ 1,
and suppose we want to compute f(19). Here we have d = 3 and c = 10. Now 19 = (203)3, and the radix-changing solution tell us to perform a digit-by-digit replacement from radix 3 to radix 10. So the 2 becomes a 5, and the 0 and 1 become 76 and −1, giving
Concrete Mathematics Josephus problem
Josephus problem revisited
Let’s consider the more authentic Josephus problem in which every third person is eliminated, instead of every second. If we apply the methods that worked in previous slides to this more difficult problem, we wind up with a recurrence like
J3(n) = 3 2J3 2
3n
+ an
mod n + 1.
where we have an= −2, +1or −12 according as n mod 3 = 0, 1, or 2.
But this recurrence is too horrible to pursue.
Concrete Mathematics Josephus problem
Another approach to the problem
Whenever a person is passed over, we can assign a new number. Thus 1 and 2 become n + 1 and n + 2, then 3 is executed; 4 and 5 become n + 3 and n + 4, then 6 is executed; . . .; 3k + 1 and 3k + 2 become n + 2k + 1 and n + 2k + 2, then 3k + 3 is executed; . . . then 3n is executed (or left to survive). For example, when n = 10 the numbers are
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22
23 24 25
26 27
28
Concrete Mathematics Josephus problem
The survivor’s number J 3 (n)
If N > n, person number N must have had a previous number, and we can find it as fllow: We have N = n + 2k + 1 or N = n + 2k + 2, hence k =b(N − n − 1)/2c; the previous number was 3k + 1 or 3k + 2, respectively. That is, it was 3k(N − n − 2k) = k + N − n. Hence we can calculate the survivor’s number J3(n)as fllow:
N := 3n;
while N > n do N := N − n − 1 2
+ N − n;
J3(n) := N.
This is not a closed form for J3(n); it’s not even a recurrence. But at least it tell us how to calculate the answer reasonably fast, if n is large.
Concrete Mathematics Josephus problem
Simplify the algorithm
Fortunately there’s way to simplify this algorithm if we use the variable D = 3n + 1 − N in place of N. (This change in notation corresponds to assigning numbers from 3n down to 1, instead of from 1 up to 3n; it’s sort of like countdown.) Then the complicated
assignment to N becomes
D := 3n + 1 − (3n + 1 − D) − n − 1 2
+ (3n + 1 − D) − n
= n + D − 2n − D 2
= D − −D 2
= D + D 2
= 3 2D
, and we can rewrite the algorithm as follows:
D := 1;
Concrete Mathematics Josephus problem
J q (n) when every qth person is eliminated
We can show by the same reasoning that the survivor Jq(n) when every qth person is eliminated can be calculated as follows:
D := 1;
while D ≤ (q − 1)n do D :=
q q − 1D
; Jq(n) := qn + 1 − D.
In the case q = 2 that we know so well, this makes D grow to 2m+1 when n = 2m+ l; hence J2(n) = 2(2m+ l) + 1 − 2m+1= 2l + 1. Good.
Part IV
문학적 프로그래밍
Computer programs are fun to write Computer programs are fun to read.
컴퓨터 프로그램은 읽기 쉬워야 한다
소프트웨어 개발에 있어서,
프로그램
작성에 들어가는 노력은10%나머지
90%는 이미 작성된 코드의유지보수, 디버깅, 문서화작업
타인이 작성한 컴퓨터 프로그램은 읽기가 힘들다.
심지어 자신이
작성한 프로그램도 시간이 지나면 읽기 어려워진다.
우리는 다른 사람이 작성한 소스 코드를 보고 프로그래밍을 배운다.
프로그래밍 언어는 사람들 사이에사용되는 언어이기도 하다
컴퓨터 프로그램도 소설 처럼 읽고 즐길 수 있는 것이어야 한다.
Computer programs are fun to write Computer programs are fun to read.
Computer Programming as an Art
1974년 Donald Knuth의 ACM Turing Award 수상기념 강연 제목
좋은 프로그램은쉽게 읽고 이해할 수 있는 것어야 한다.
프로그램의효율성, 최적화만 강조하여 코드가 쓸데없이
복잡해진다면, 프로그램 읽기가 어렵게 되고, 디버그와
유지보수도 힘들어져서, 결국 그 소프트웨어의 효율은 전체적으로
낮아진다.
Premature optimization is the root of all evil (or at least most of
it) in programming.
Computer programs are fun to write Computer programs are fun to read.
문학적 프로그래밍(Literate Programming)
컴파일러가 쉽게 알아들을 수 있도록 프로그래밍 하기 보다는 사람이 쉽게 이해할 수 있도록 프로그래밍 하자. 이것이 결국은
프로그램의 효율을 높이는것이다!
컴퓨터 프로그래밍이란 컴퓨터가 해야 할 일들을 논리적이고 순차적으로 지시하는 것이 아니라, 컴퓨터가 해야할 일을 사람들에게 논리적이고 재미있게 설명하는 작업이다.
프로그래밍 언어의 문법과 규칙은 컴파일러에 적합한 것이어서 우리 사람들의 정서에는 맞지 않는다. 따라서 프로그램은 사람이
작성하고 읽기 편하도록 사람에게 적합한 구조로 재배열되어야
한다.
문학적 프로그래밍이란 사람들이 읽기 편하도록 프로그램을
재구성하여 자연스런 설명을 곁들인 프로그램 코드를 작성하는
것이다.
Computer programs are fun to write Computer programs are fun to read.
CWEB 시스템
C(C++, Java) 언어로 작성하는 문학적 프로그래밍언어, 시스템.
C 프로그램이란 CWEB의 섹션에서 C 코드 만을 뽑아내어서 컴파일러가 이해하기 쉬운 구조로 재배열한 프로그램이다.
CWEB 프로그램은 C 프로그램을 섹션으로 나눈 다음, 사람들이 이해하기 쉬운 구조로 설명을 곁들여 재배열한 프로그램이다.
CWEB 프로그램과 C 프로그램은 근본적으로 동일한 것이고, 단지
그 배열 순서만이 다르다.
Computer programs are fun to write Computer programs are fun to read.
CWEB 시스템 = CWEAVE + CTANGLE
문학적 프로그래밍이란 사람들이 읽기 편하도록 자연스런 설명과
프로그램 코드를 하나의 소스 파일에서 동시에작성하는 것이다.
CTANGLE: 웹파일의 각 섹션들에서 C 코드만 뽑아내어 C 파일을 만들어 낸다. 사람들의 기준에서 잘 정돈된(untangle) 코드를 뒤섞어서(tangle) 컴파일러가 이해 할 수 있는 코드를 생성한다.
CWEAVE: 웹파일로 부터 TEX 파일을 만들어 낸다. 소스 코드와 문서를 잘 조합하여 직물을 짜내듯이(weave) 보기 좋은 문서를 만든다.
Computer programs are fun to write Computer programs are fun to read.
CWEB 프로그래밍 시연
N개의 여왕 배치 문제
Part V
과제
과제 1
An n-digit number that is the sum of the nth powers of its digits is called an n-narcissistic number. It is also sometimes known as an Armstrong number, perfect digital invariant (Madachy 1979), or plus perfect number. For example,
153 = 13+ 53+ 33, 8208 = 84+ 24+ 04+ 84. Find all n-narcissistic number, for 3 ≤ n ≤ 39.
과제 2
과제 3
The number √ 1,√
2, . . . ,√
50are to be partitioned into two parts whos number is nearly equal; find the best such partition you can.
For example, it turns out to be possible to find the best partition of the smaller set of numbers √
1,√
2, . . . ,√ 30is
√ 2 +
√ 6 +
√ 9 +
√ 11 +
√ 12 +
√ 13 +
√ 14 +
√ 21 +
√ 23 +
√ 24 +
√ 25 +
√ 26 +
√ 27 +
√ 30
= 56.04142 25880 73351 85163 20826;
√ 1 +√
3 +√ 4 +√
5 +√ 7 +√
8 +√ 10 +√
15 +√ 16 +√
17 +√ 18 +√
19 +√ 20 +√
22 +√ 28 +√
29