p.124, Problem 7 (Chapter Self-Test)
Solved by 칭기즈 Date: 2018.09.26
Finalized by 서명원 Date: 2018.09.27
Final Ok by
TA Date: 2018.09.27
Problem
7.
Use proof by cases to prove that
min{min{a,b},c}=
min{a,min{b,c}}
for
all real numbers a,b and c
Solution:
Discussion:
In order to proof by cases we have to identify all possible cases and try
each of them to identify whether the given statement is true of false. There
are 6 possible cases, which are:
1.a >=b >=c
2.a>=c>=b
3.b>=a>=c
4.b >= c >= a
5.c>=a>=b
6.c>=b>=a
Solution:
we arrange these cases to two
case: a≤b and a＞b.
In
each of these two cases, we should consider the two cases: b≤c and b＞c.
First
suppose that a≤b.
If b≤c, then
min{min{a,b},c}=min{a,c}=a=min{a,b}
=min{a,min{b,c}}.
if b>c, then
min{min{a,b},c}=min{a,c}=min{a,min{b,c}}.
In
either case,
min{min[a,b},c}=min{a,min{b,c}}.
And,
Suppose
that a＞b.
if
b≤c, then
min{min{a,b},c}=min{b,c}=b=min{a,b}
=min{a,min{b,c}}.
if b＞c, then
min{min{a,b},c}=min{b,c}=c=min{a,c}
=min{a,min{b,c}}.
In
either case,
min{a,min{b,c}}=min{a,min{b,c}}.
Conclusion:
Thearefore,
The statement is true because all cases are
true.
Note: This
problem helped me to understand the concept of proof by cases where I need to
analyze the problem from multiple sides.
Final OK by SGLee, Page 124 problem 5 칭기즈 revised by 서명원
When we want to prove the conclusion using
the proof by contradiction, the negated
conclusion is assumed in addition to the given condition. And we only
need to find one contradiction among many.
Whereas in a direct proof, we have to use
the given condition only to prove the one given conclusion.
(the negated conclusion is not assumed!!)
So, there are more conditions
and more conclusions options for us in a proof by
contradiction.
Note: This problem helped to get the
difference between proof by contradiction and the direct proof.
Final OK by SGLee, Page 124 (computer exercises) problem 2 칭기즈 revised by 김정주
Page 124
(computer exercises) problem 2
2. Write a program that gives an Egyptian form of a fraction
https://en.wikipedia.org/wiki/Egyptian_fraction
Python code:
from
fractions import Fraction
str1=""
str2=""
fraction=input("enter
a fraction:")
for i in range(len(fraction)):
if
fraction[i]=='/':
slash=i
for i in range(slash):
str2=str2+fraction[i]
for i in range(slash+1,len(fraction)):
str1=str1+fraction[i]
frac =
Fraction(int(str2), int(str1))
index=1
egypt=""
while frac
> 0:
if frac
>= Fraction(1,index):
egypt=egypt+"1/"+str(index)+"+"
frac -= Fraction(1,index)
index += 1
for index in range(len(egypt)-1):
print(egypt[index],sep='
', end='', flush=True)
----------------------------------------------------
in this code, our index will check every integers until it finish the
job.
So, it will takes too much time.
Here is our new algorithm.
Start this
algorithm with x is 1.
The following is
my python code:
example:
□
Note: I liked this
solution, I now understand the importance of the efficiency of the algorithm.
Final OK by SGLee, page 124 problem 1 김주형
finilized by 칭기즈
page 124 problem 1 김주형
finilized by 칭기즈
Axioms are statements that are assumed to be true.
Definitions are used to give a precise meaning and
concept to a
new term.
To look at examples of axioms and definitions in http://matrix.skku.ac.kr/2018-DM/DM-Ch-2-Lab.html on Euclidean
geometry in
order to get more clear view:
Comment: This problem is very easy but very
important to understand the difference between axioms and definitions in math.
Final OK by SGLee page 124 problem 13 백선민
finilized by 칭기즈
page 124 problem 13
Solved by 백선민
Finilized by 칭기즈
Final OK by SGLee
Q. Use mathematical induction to prove
that the statements are true for every positive integer n.
Statement 13 : 2 + 4 + ... + 2n = n(n+1)
Discussion:
[Principle of Mathematical Induction]
Suppose that we have a propositional function 
whose domain of
discourse is the set of positive integers.
Suppose that
1. Basic Step 
is true.
2. Inductive Step
If is true, then 
is true, for all 
.
Then is true for every
positive integer 
. (Induction means Mathematical
Induction.)
Proof)
(1) Basis step (k = 1)
2 k = k (k+1)
=> LHS = 2= 2*1= 1(1+1) = 2 =RHS
when k = 1
(2) Inductive step:
Assume that
equation is true for k=
n n>=1,
that
is, we assume that
2 + 4 + ... + 2n = n ( n+1
)
(*)
is
true.
[Let's prove that the equality is true for k = n+1.]
Thus,
add 2(n+1) to LHS of (*)
LHS = 2 + 4 + ... + 2n + 2(n+1) = n(n+1) + 2 (n+1)
= (n+1) ( n+2) = RHS
This
means (*) is true for k = n+1.
By [Principle of Mathematical Induction], 2 + 4 + ... + 2n =
n(n+1) is true for every
positive integer n . □
Note: This problem helped to understand the
concept of Mathematical Induction.
Final OK by SGLee page124 Problem 11 칭기즈 Finalized by 김은율
page124, Problem 11
(Chapter Self-Test)
Solved by 칭기즈, Date:
2018.09.24
Finalized by 김은율, Date: 2018.09.26
Final OK by SGLee
11. Use resolution to prove
1. ¬p v q
2. ¬q v ¬r
3. p v ¬r
-------
¬r
Solution:
[ Resolution rule: if pvq and ¬p v r are both true, then q v r is
true.]
If
1. ￢p∨q
2. ￢q∨￢r
3. p∨￢r
=>
4. ￢p∨￢r ( From 1 and 2, we have this )
=>
5. ￢r ( From 3 and 4, we have
this )
Given the hypotheses 1,2 and 3
, we have proved the conclusion □
Note:This problem helped to understand how to
use resolution rule. The idea is if pvq and ¬p v r are both true, then q v r is true.
Final OK by SGLee Page 124 Problem 9 solved by 칭기즈 finalized by 강병훈
P.124 Problem 9 (Chapter
Self-Test)
9. Write an expression, which is the and of
clauses , equivalent to (p v q)-> r.
--------------------------------------------------------------------
Solution
|
Definition 1.3.1
|
Conditional Proposition
|
|
If  and  are proposition, the proposition
if then 
is a conditional proposition.
 ( ) : if then .
Proposition is hypothesis (or antecedent, 가설).
Proposition is conclusion (or consequent, 결론).
|
\ (p
v q)-> r = ¬(p v q) v r
De Morgan's Law
: ¬(p v q) = ¬p Λ ¬q
¬p Λ ¬q v r
Distributive Law: (r
v ¬p) Λ ( r v ¬q)
\
(r v ¬p) Λ ( r v ¬q)
Truth tables: 
\ (r v ¬p) Λ ( r v ¬q) = (p
v q)-> r
. □
Python Code :
expression=input("enter
a logical expression")
print("p
|","q |","r |",expression)
count=0
value=[0]*8
for q in range(2):
for p in range(2):
for r in range(2):
value[count]=eval(expression)
print(bool(p),"|",bool(q),"|",bool(r),"|", bool(value[count]))
count=count+1
Final OK by SGLee Page 198 (Com) problem 7 칭기즈 Finalized by 전종문
Page 198 (Computer exercises) problem 7 칭기즈 Finalized by 전종문
Page 198 (Computer
exercises) problem 7
Problem
7.Write a program that tests whether A is decreasing.
Solution
Python code:
A=[int(x) for x in input("enter a sequence of numbers:\n").split()]
count=1
for i in range(len(A)-1):
if A[i]<=A[i+1]:
count=-1
if count==1:
print("decreasing")
print("not decreasing")
Running Examples:
■
It works^^
Note: This problem
helped me to understand the concept of nondecreasing order and to know how to
implement it in an algorithm.
Page 198 (Computer exercises) problem 6
Solved by 칭기즈
Date:2018.09.30
Revised by 김정주
Date:2018.09.30
finalized by 김희성
Date:2018.09.30
Final OK by SGLee
Problem : Write a program that checks
whether a sequence is in increasing otder
Discussion:
For 
and 
are in the domain of
the sequence.
, 
sequence 
is increasing
Solution:
Python code:
A=[int(x) for x in input("enter a sequence of numbers:\n").split()]
count=1
count1=1
for i in range(len(A)-1):
count+=1
if A[i]<a[i+<
span="">1]:</a[i+<>
count1+=1
if count==count1:
print("increasing")
else:
print("not increasing")
because
second and third elements are 2
Our modified code is as following.
import sys
A=[int(x) for x in input("enter a sequence of
numbers:\n").split()]
for i in range(len(A)-1):
if A[i]>=A[i+1]:
print("not increasing")
sys.exit(0)
print("increasing")
Comment: When we check whether the given sequence is
increasing, we have to check .
But if ∃n such that is not
true, then we can tell it is not increasing.
So if we find ∃n such
that is not
true, we
quickly exit and print "not increasing".
If our program execute all n with all loops, and it
doesn't find any exception, then we will print "
increasing".
Final OK by SGLee, Page 198( Comp. exercises) problem 9 전종문 Re-Finilized
by 칭기즈
Page 198 (Comp.
Exercises) problem 9
Problem
9. Write a program that tests whether A is
nondecreasing
Discussion:
For and are in the
domain of the sequence.
, 
The sequence is nondecreasing
( increasing is replaced
by nondecreasing : “
” is replaced by “
”)
Solution:
Python code for a
nondecreasing sequence A :
A=[int(x) for x in input("enter a sequence
of numbers:\n").split()]
count=1
count1=1
for i in range(len(A)-1):
count+=1
if A[i]<=A[i+1]:
count1+=1
if count==count1:
print("nondecreasing")
else:
print("not
nondecreasing")
The code
works: (a Right Example)
Wrong example
2. C code:
#include <stdio.h>
int A[10000000], N, answer = 1;
int main()
{
printf("Enter
the number of sequence: ");
scanf("%d",
&N);
printf("Enter
a sequence: ");
for
(int i = 1; i < N; i++) { scanf("%d", &A[i]);}
for
(int i = 1; i < N; i++) {
if
(A[i - 1] > A[i]) { answer = -1; break; }
}
if
(answer == 1) {
printf("nondecreasing\n");
}else
{ printf("not nondecreasing\n"); }
return
0;
}
■
Comment: The idea of the problem is to check
whether at least one element is less than the previous element, hence the
sequence is not nondecreasing.
Page
198, Problem 13 (Very Good 10/10)
Solved by 칭기즈
Date: 2018.09.27
Finalized by 전종문
Date:2018.09.27
Final OK by SGLee
Ch 3. Page 198, Problem 13
Is the relation
{(1,1),(1,2),(2,2),(4,4),(2,1),(3,3)}
an equivalence relation
on {1,2,3,4}? Explain.
Solution
Let, R = {(1,1),(1,2),(2,2),(4,4),(2,1),(3,3)}, X = {1,2,3,4}.
1. ∀x ∈X, (x,x)∈ R ⇒
(1,1),(2,2),(3,3),(4,4) ⇒ R
is reflexive.
2. (x,y)∈ R ,(y,x)∈ R ⇒
(1,2),(2,1)/(1,1)/(2,2)/(3,3)/(4,4) ⇒ R
is symmetric.
3. (x,y)∈ R ,(y,z)∈ R
are (x,z)∈ R ⇒ (1,2)(2,1)
are (1,1)/ (1,2)(2,2) are (1,2)/ (1,1)(1,2)
are (1,2)/ (2,2)(2,1) are (2,1) ⇒ R
is transitive.
R
is reflexive, symmetric, and transitive.
∴
{(1,1),(1,2),(2,2),(4,4),(2,1),(3,3)} is an equivalence relation on
{1,2,3,4}.■
Note: This problem helped me to understand the concept of
relations not only by words but also by digraph.
Final OK by SGLee Page 198 problem 18 solved by 칭기즈
Finalized by 엄자균
Page 198 problem 18
R_2 =
{(x,a),(x,b),(y,a),(y,c)}
18. Find the matrix A_2
of the relation R_2 relative
to the orderings
x,y;
a,b,c
Solution:
Given relation R_2
= {(x,a), (x,b), (y,a), (y,c)}
ordering
is x,y; a,b,c
to find A_2
a11=1 because (x,a) ∈R
a12=1 because (x,b) ∈R
a13=0 because (x,c) ∉R
a21=1 because (y,a) ∈R
a22=0 because (y,b) ∉R
a23=1 because (y,c) ∈R
so， A_2= 1
1 0
1
0 1
Comment: The problem is
very straightforward. The idea is that 1 indicates that there is a relation in
a particular point ,whereas 0 vice versa. Hence we get:
Solved by 정호진 2018.09.30
Finilized by 칭기즈 2018.10.02
Final OK by
TA 2018.10.02
Problem 11
Give an example of a relation on {1, 2, 3,
4} that is reflexive, not antisymmetric, and not transitive.
Solution
reflexive: (x,x) ∈ R for every x ∈ X
antisymmetric: for all x, y ∈ X, if (x,y) ∈ R and (y,x) ∈ R, then x=y
transitive: for all x, y, z ∈ X, if (x,y) and (y,z) ∈ R, then (x,z) ∈ R
So, (1,1), (2,2), (3,3), (4,4) ∈ R (Reflexive)
(2,3), (3,2) ∈ R (not antisymmetirc)
(1,2) ∈ R (not transitive)
R = {(1,1), (2,2), (3,3), (4,4), (2,3), (3,2), (1,2)}
Digraph:
1. Every vertex has a loop so
R is
reflexive
2. (2,3) (3,2) ∈ R:Directed line from 2 to 3
, Directed line from 3 to 2 but x≠y
R is not
antisymmetric
3.(1,2),(2,3) ∈ R Directed line from 1
to 2, Directed line from 2 to 3 but There is no line from 1 to 3
R is not transitive
Final OK by SGLee Page 197 problem 10 김정주 칭기즈
Re-Finilized by 전종문
Page 197 Problem 10
Problem
In Exercises 9 and 10,
determine whether the relation defined on the set of positive integers is reflexive,
symmetric, antisymmetric, transitive, and/or a partial order.
9. (x,y)∈R if
divides x + y
Solution
*
(1,1)∉ R ⇒ R is not reflexive
* If 3|x +y
then 3|y +x ⇒ R is symmetric
* R
is symmetric but R is not reflexive ⇒ R is not antisymmetric
* (1,2)∈R , (2,1)∈R ⇒ (1,1)∉ R ⇒ R is not transitive
* R is antisymmetric, transitive but R is not reflexive ⇒ R is not a partial order
∴ R is symmetric,
not reflexive, not
antisymmetric, not transitive, not
a partial order
■
Comment:
The problem is very
simple which helps to get better understanding of relations. The idea is that
if a relation is a partial order, then it is reflexive, antisymmetric and
transitive simultaneously.
Final OK by SGLee Page 197 problem 5 solved by 칭기즈 finalized by 신혜수
Page 197 problem 5 (Q)
For the sequence a defined by a_n = 2*n+2....
Find
a) a6
b)
c)
Discussion:
Solution :
The answer:
a) 14
b ) 18
c)
192 □
Comment : 이 문제를 풀면서 고등학교 재학 시절 배웠던 수열, 수열의 합은 물론, 수열의 곱까지 다시 한번 정리하고 응용하는 시간을 가졌습니다. 또한 학우들과 같이 문제를 풀고 finalize 하면서 보람찬 시간을 가졌습니다.
[Final OK by TA]
Ch. 4, Page 247, Problem № 1 (Chapter Self-Test) , solved by 권재용, revised by 칭기즈, finalized by 전종문 and 김승영
Problem
Trace Algorithm 1.1 for the values a = 12, b = 3,
c = 0.
Algorithm 1.1
This algorithm finds the largest of the numbers a,
b, and c.
Input: a, b, c
Output: large (the largest of a, b, c)
1. Max3 (a, b, c){
2. large =a
3. if(b>large)//if b is larger than large,
update large
4. large = b
5. if(c>large)//if c is larger than large,
update large
6. large = c
7. return large
8. }
Solution
1. max3 (a, b, c){⇒ a =12, b =3,c =0
2. large =a
⇒ large =12
3. if(b>large) //if b is larger than large, update large
⇒ b =3 > large =12
is false, then jump to 5
4. large = b
5. if(c>large)//if c is larger than large,
update large ⇒ c =0 >large =12
is false, then jump to 7
6. large = c
7. return large
⇒ return large =12
8. }
⇒End ■
Trace table:
|
Line number
|
a
|
b
|
c
|
Large
|
|
2
|
12
|
3
|
0
|
12
|
|
3
|
12
|
3
|
0
|
12(a>b)
|
|
4
|
12
|
3
|
0
|
12
|
|
5
|
12
|
3
|
0
|
12(a>c)
|
|
6
|
12
|
3
|
0
|
12
|
|
7
|
12
|
3
|
0
|
12
|
Sage code:
@interact
def _(a=input_box(default=1,
label='a'),b=input_box(default=2, label='b'),c=input_box(default=3,
label='c')):
large = a
if b > large:
large = b
if c > large:
large = c
print "maximum
number is ", large
return
Source: http://matrix.skku.ac.kr/2018-DM/DM-Ch-4-Lab.html ■
Comment: 여러 개의 parameter들 중에서 하나를 처음 지정한 후 다른 것들과 하나씩 비교하면서 큰 것으로 대체해
나가다가 비교할 것이 없어지면 남은 최종 parameter의 value가 출력 되는 알고리즘이다.
Comment: This problem may be difficult to understand but if you
follow the trace table and the code provided simultaneously it will be quite
easier to get the
idea.
[Final OK by SGLee]
Ch. 4, Page 247, Problem № 3 (Chapter Self-Test), solved by 전종문, revised by 칭기즈, finalized by 김영철 and
김승영
Problem
Write an algorithm that
returns true if the values of a, b and c are distinct, and false otherwise.
Solution
If a, b and c are all distinct,
returned value will be ‘True’. Otherwise, returned value will be ‘False’.
Now, if all are distinct, we get ‘True’,
and if not, we get ‘False’. ■
Comment:
조건 문 if 절에서 3개의 condition (a가 b와 같다 와 b가 c와 같다.
그리고 c가 a와 같다.)
중 하나라도 충족될 때 거짓이고 그렇지 않을 때에만 참 이도록 하게 한 명령어이다. '==' 는 logical
equivalent 을 뜻하고 ‘‖’
는
logical or 을 뜻한다. 이로 인해 a, b, c 중 하나라도 다른 parameter와 같으면 거짓이 되도록 설정하였다.
Comment: This problem is quite
simple which needs some basic knowledge of programming. The idea is to check if
at least two of the numbers are equal using the logical operator “or”.
[Final OK by SGLee]
Ch. 4, Page 247, Problem № 5 (Chapter Self-Test), solved by 모하메드, finalized by 칭기즈 and
김승영
Problem
Trace Algorithm 4.2.1 for the input t
= “111011” and p
= “110”.
Explanation
The Algorithm stated in
section 4.2.1 is called Text Search and it is
defined as following:
Text Search:
This
algorithm searches for an occurrence of the pattern p in
text t . It returns the smallest
index i such
that p occurs in t starting at
index i. If p does not occur
in t, it returns 0.
Input: p (indexed
from 1 to m), m, t (indexed
from 1 to n), n
Output: i (the
index of first match occurrence)
Pseudo Code:
text search(
p, m, t, n) {
for (i =
1 to n − m +
1) //the starting point is 1, the ending point is (n-m+1)
{
j =
1
// i is the index in t of the first character of the substring
// to compare with p, and j is the index in p
// the while loop compares ti · · · ti+m−1 and p1 · · · pm
while
(ti+j−1 == pj )
{
j = j + 1
if
( j > m) //reaching the end of substring p
return
i
}
}
return 0
}
"
Solution
Given:
t= "111011"
p= "110"
* Following the code and
tracing the loop iterations we can find:
1) For-Loop's
First Iteration / i=1:
a) j is set to 1
b) we execute the
while-loop , and since t[1]==p[1], j is incremented to
compare t[2] and p[2] and since t[2]==p[2], j is
incremented once again to compare t[3] and
p[3] and since t[3]!=p[3] , the while loop is broken and we move to
the next for-loop iteration
2) For-Loop's
Second Iteration / i=2:
a) j is set
to 1
b) we execute
the while-loop , and because i=2 we start with t[2], since
t[2]==p[1], j is incremented to compare t[3] and
p[2] and since t[3]==p[2], j is incremented once again to compare t[4]
and p[3] and since t[4]==p[3] j is incremented once again to become
(j=4) which is greater than (m) , so i=2 is returned.
t = "111011" n=6
p = "110” m=3
Hint:
if ( j > m) //reaching the end of substring p
return i
The algorithm
terminates when j>m, m=3 => j=4
Trace table:
|
i
|
j
|
t[i+j-1]==p[j]
|
Output
|
|
1
|
1
|
true
|
-
|
|
1
|
2
|
true
|
-
|
|
1
|
3
|
false
|
-
|
|
2
|
1
|
true
|
-
|
|
2
|
2
|
true
|
-
|
|
2
|
3
|
true
|
-
|
|
2
|
4
|
|
2
|
∴ The output is 2 ■
Comment:
문자열 ‘110 ‘
을 추적하고 ‘110 ‘이 발견된 경우 왼쪽부터 시작해서 최초의
‘1 ‘ 이 발견된 자릿수를 결과값으로 내어 출력하는 알고리즘이다. 여기서 검사하는 방식은 ‘i’번째 항을 첫 번째로 ‘I’번째 항이 ‘1’ 인가 보고 일치하면 ‘i+1’번째 항도 ‘1’ 인가를 확인하고 ‘i+2’번째 항까지 ‘0’ 임이 맞는다면’ j’항 즉, n번째 검사임을 나타내는 factor가 ‘n=4’가 되게 된다면 검사를 중단하고 현재 ‘I’ 의 value를 출력하게 됩니다. 이것은 ‘110’ 이라는 찾고 싶은 문자열을 찾고 나서 그 찾은
위치를 출력하고 작동을 멈추는 전형적인 Text Search 알고리즘이고
이것을 응용하여 좀더 길거나 영어 및 다른 글자 기호의 조합도 찾아 낼 수 있을 것 입니다.
Comment: This problem may be difficult to understand but if you
follow the trace table and the code provided simultaneously it will be quite
easier to get the idea.
[Final OK by SGLee] Ch. 4, Page
247, Problem № 6 (Chapter
Self-Test), solved by 칭기즈, finalized by 서명원and 김승영
Problem
Trace algorithm 2.3 for the input:
44 64 77 15 3
Source: http://matrix.skku.ac.kr/2018-DM/DM-Ch-4-Lab.html
Solution
Suppose that the input is the following
sequence
Firstly,
I=2, j=I-1=1 ,val = s[2]=64
j>=1 and val<
s[1]= 44 is false,
so there is no change
Thus,
s[j+1]=s[2]=val=64
Now,
I=3, j=2, val=s[3]=77
j>=1 and val< s[2]= 64
is false, so there is no change
Thus,
s[j+1]=s[3]=val=77
Now,
I=4, j=3, val=s[4]=15
j>=1 and val< s[3]= 77 is true ,
s[4]=s[3]=
77
j=j-1 = 2
j>=1 and val< s[2]= 64 is true
s[3]
=s[2]=64 j=j-1
= 1
j>=1 and val< s[1]= 44
is true ,
s[2]=s[1]=44
j=j-1
= 0
j>=1 is false, skips the
loop
s[j+1]=s[1]=val=15
Now,
I=5, j=4, val=s[5]=3
j>=1 and val< s[4]= 77
is true ,
s[5]
=s[4]=77 j=j-1
= 3
j>=1 and val< s[3]= 64
is true ,
s[4]
=s[3]=64 j=j-1
= 2
j>=1 and val< s[2]= 44
is true ,
s[3]
=s[2]=44 j=j-1
=1
j>=1 and val< s[1]= 15 is
true ,
s[2]
=s[1]=15 j=j-1
= 0
j>=1 is false
s[1]=val=3
Output
Comment: 이 문제를 다시 해석하고 정리하였을 때에 알고리즘의 기준은 숫자의
대/소 관계에 의거해 정렬을 하였는데 약간의 실생활 경험만 있다면 컴퓨터의 파일들의 정렬의 기준은 이름, 크기, 항목의 유형, 수정한 날짜, 그
이외에 많은 기준들이 존재함을 떠올릴 수 있다. 지금이야 10개도 되지 않는 숫자들의 정렬이니 별로 대단치는 않을 것이라고 생각할 수는 있지만
수천 내지 수만 혹은 그것을 넘어서는 단위의 어떤 집단들을 기준을 따라 정렬하는 것은 컴퓨터와 알고리즘의 도움을 받지 않을 수 없을 것이며 새삼
컴퓨터와 그를 비롯한 수학이 가져다 준 문명의 혜택에 감탄할 뿐이다.
Comment: This problem is very good example to understand how
swapping works in programming. The key idea of swapping is to store the some
value in a temporary variable, which is m in this case.
[Final OK by SGLee]
Ch. 4, Page 247, Problem № 7 (Chapter Self-Test), solved by 칭기즈, finalized by 엄자균, re-finalized by 김영철 and
김승영
Problem
Trace Algorithm 4.2.4 for the
input 5, 51, 2, 44, 96. (See below to find
Algorithm 4.2.4)
Solution
According
to the problem, the sequence is this.
Step I) We first swap a[i] and a[j],
where i=1 and j=rand(1,5). If j=3,
after
the swap we have
Step II) Next, i=2. If j=rand(2,5)=5,
after
the swap we have
Step III)Next, i=3. If j= rand(3,5) =3,
the
sequence does not change.
Step IV)Finally, i
=4. If j = rand(4,5)=5 ,
after
the swap we have
Output:
Notice
that the output depends on the random choices,
so the result may vary all the time.
■
Comment: 이번 문제의 주제인 난수에 대해 이야기 하자면 사실 이 수업이나 교과과정이 코딩을 짠다거나 실제 컴퓨터의 'pseudo Random Number'를 발생시키는 'Seed' 라던가 'XOR-shift'등의 발생 기법을 중점적으로 다루는 course는 아니고 이러한 것이 있다 보여주는 수준이다. 이 난수는 실제 세상의 하고 많은 표본을 무작위적이고 고르게 뽑기 위한 학술, 통계적인 용도로 쓰일 수도 있고 요즘 이슈가 되고 있는 'Block chain' 기술 및 여러 암호 관련 기술/기법과 우리가 일상적으로 즐기는 비디오 게임에도 관여하는 중요한 요소이므로 앞으로 내가 흥미를 가지고 있는 soft 개발을 진지하게 할 기회가 있다면 다른 연관수업에 대해 찾아 나설 생각이다.
Comment: The key idea of a shuffle algorithm is to re arrange
the given sequence by swapping a certain element with a random element
generated by the function rand(n,m).
[Final OK by TA
and SGLee] Ch. 4, Page 248, Problem № 1 (Computer Exercises), solved by 칭기즈, finalized by 유가이 올렉산드르
Problem
Implement Algorithm 1.2, finding the largest element
in a sequence, as a program
|
Algorithm 1.2
|
Finding the Maximum
Value in a Finite Sequence
|
|
procedure max( ,  ,  :
integers)
max 
for  to 
if  then 
return 
or
|
|
|
|
|
Solution
A) Python code
sequence=[int (x) for x in input("enter
a sequence of numbers:").split()]
largest=sequence[0]
for i in range(len(sequence)):
if sequence[i]>largest:
largest=sequence[i]
print(largest)
Practical image
B) Sage Code
@interact
def
_(s=input_box(default=[1,5,4,2,6,3], label='sequence')):
n = len(s)
#
list의 길이
maximum = s[0]
for i in range(1,n):
if
s[i]
> maximum:
maximum = s[i]
print "maximum number is ",
maximum
print max(s)
return
Example:
Source: http://matrix.skku.ac.kr/2018-DM/DM-Ch-4-Lab.html ■
Comment: 알고리즘의 돌아가는
방식은 시퀀스의 길이를 던져주고 코드를 자신이 원하는 출력이 나오도록 조절을 하고 그것을 반복하게 하는 식이다. 여기서는 '가장 큰 수'를 '0' 즉, Default 값을 쥐어준 후 시퀀스 1항과 비교, 1항이 크면 '가장 큰 수'를 큰 쪽으로 대체하고 2항 과도 비교하고 비교대상 중 큰 쪽으로 대체해 나가는 것을 Coder가 설정해둔 길이 까지 수행하고 마지막까지 진행해 나간 '가장 큰 수'를 출력하는 방식이다. 지금이야 코딩이 간단하여 나 또한 조금만 공부하고 연습하면 바로 제작할 수 있을 정도로 간단하지만 앞으로 몇 백 몇 천줄 되는 프로그램을 짜게 된다면 여기서의 숫자 하나가 오타가 난다거나 변수 알파벳을 혼동한다던가 하면 몹시 곤란하게 될 것이다.
Comment: This
problem is very easy but very useful since it helps to understand relatively
effective algorithm of finding the largest number. The key idea is to assume
any element to be the largest and then compare the remaining elements with it.
[Final OK by SGLee]
Ch. 4, Page 248, Problem № 4 (Computer Exercises), solved by 유가이 올렉산드르,
finalized by 칭기즈 and 김승영
Page 248, problem 4
(Computer Exercises)
Implement Algorithm 2.4, shuffle, as a program.
Discussion
shuffle
This algorithm
shuffles the value in the sequence
a1,
... an
Input: a,
n
Ouptut: a (shuffled)
shuffle(a, n){
for i = 1 to n - 1
swap(a[i],a[rand(i,
n)])
}
Solution
A) Python code
import random
sequence=[1,2,3,4,5,6,7]
for i in range(len(sequence)):
r=random.randint(i,len(sequence)-1)
val= sequence[i]
sequence[i]=sequence[r]
sequence[r]= val
print(sequence)
Practical image:
B) Sage code
@interact
def
_(s=input_box(default=[1,5,4,2,6,3], label='sequence')):
n = len(s)
for i in range(1,n):
r=int(RR.random_element(i,n-1))
val= s[i]
s[i]=s[r]
s[r]= val
print s
return
Practical image:
Source: http://matrix.skku.ac.kr/2018-DM/DM-Ch-4-Lab.html ■
Comment:
Due to this problem I learnt how to implement pseudocode of a
shuffle algorithm as a program, using both Python and Sage coding, along with
the concept of this algorithm. The idea of a shuffle algorithm is to order
elements in a sequence depending on random indexes obtained by function rand(),
hence the result may differ every time the code is executed.
[Final OK by SGLee]
Ch. 4, Page 247, Problem № 3 (Chapter Self-Test), solved by 칭지즈, finalized by 전종문 and
김승영
Problem
Implement Algorithm 2.3,
insertion sort , as a program.
Algorithm:
Discussion:
In
an insertion sort, the first element in the array is considered as
sorted, even if it is an unsorted array. In an insertion sort, each
element in the array is checked with the previous elements, resulting in a
growing sorted output list. With each iteration, the sorting algorithm removes
one element at a time and finds the appropriate location within the sorted
array and inserts it there. The iteration continues until the whole list is
sorted.
Solution
Python code:
def insertionSort(alist):
for i in range(1,len(alist)):
val = alist[i]
j = i
while j>0 and alist[j-1]>val:
alist[j]=alist[j-1]
j = j-1
alist[j]=val
alist = [int(x) for x in input("Enter:").split()]
insertionSort(alist)
print(alist)
Example:
Comment: Due
to this problem I learnt how to implement the algorithm of insertion sort as a program.
I realized that the time complexity is O(n2) and the worst case
occurs when the sequence is sorted in reverse order. Insertion sort is used when number of elements is small. It can also be
useful when input array is almost sorted, only few elements are misplaced in
complete big array.
[Final OK by SGLee]
Ch. 4, Page 247, Problem № 15 (Chapter Self-Test), solved by 조영은, finalized by 강병훈, re-finalized by 김영철 and
칭기즈
Problem
Write a recursive algorithm
to compute t[n] from the tribonacci sequence above, n ≥ 1.
Solution
Using the Python code we’ve
already seen up there, by modifying it little bit, we can compute
t[n] easily. But before we do that, let’s calculate by hand t[1] ~
t[10] below, to compare it with the output later to check if it gives the
right results.
1. t[1] = 1 (by definition)
2. t[2] = 1 (by definition)
3. t[3] = 1 (by definition)
4. t[4] = t[1] + t[2] + t[3] = 3
5. t[5] = t[2] + t[3] + t[4] = 5
6. t[6] = t[3] + t[4] + t[5] = 9
7. t[7] = t[4] + t[5] + t[6] =
17
8. t[8] = t[5] + t[6] + t[7] =
31
9. t[9] = t[6] + t[7] + t[8] =
57
10. t[10] = t[7] + t[8] + t[9] = 105
Python code:
def
sequence(n):
if (n==0 or n==1 or n==2 or n==3):
return 1
else:
return (sequence(n-1)+sequence(n-2)+sequence(n-3))
def
tribonacci(n):
for i in range(1,n+1):
print(sequence(i),"",end="")
n=10
tribonacci(n)
Output:
We can see the by-hand
calculation and test result is identical. ■
Comment: This problem is quite easy but very useful
because it helps to get better understanding of the concept of recursive
algorithms, where the key idea is to invoke a simpler version of itself, as
well as Tribonacci sequence.
[Final OK by SGLee]
Ch. 4, Page 247, Problem № 12 (Chapter Self-Test), solved by 강병훈, finalized by 모하메드, re-finalized by 김영철 and
칭기즈
Problem
Write an algorithm that tests whether
two n × n matrices are equal and find a theta notation for its worst-case time.
Solution
Input – A, B (both n x n matrices), n
Output – True (if A = B), False (if A ≠ B)
< Pseudo Code >
Note: We have to compare
each element in A and B, and as soon as different match is found, we
return False. The worst case is when the
two are actually same matrices, so that we end up comparing all the
elements of A and B.
So the code is like below:
Python code:
N = 4
def
areSame(A,B):
for i in range(N):
for j in range(N):
if (A[i][j] != B[i][j]):
return False
return True
A= [ [1, 1, 1, 1],
[2, 2, 2, 2],
[3, 3, 3, 3],
[4, 4, 4, 4]]
B= [ [1, 1, 1, 1],
[2, 2, 2, 2],
[3, 3, 3, 3],
[4, 4, 4, 4]]
print(areSame(A,B))
Output:
<Worst case>
As I mentioned above, the worst-case time occurs when
the two are actually
same matrices, so that we end up comparing all
the elements of A and B.
To compare all the elements of the two, as each of
them have n * n = (n^2)
elements, it will take (n^2) times comparing
them. So, the Theta notation
for the worst-case time here is Theta of (n^2).
Note: Theta /O / Omega notations are read as "
O/theta/Omega of f(x)" -> where f(x) is a
function that counts the number of operations executed and generally the most used
notation is the O-notation since it gives the upper bound-worst case- for an algorithm. ■
[Final OK by SGLee]
Ch. 4, Page 247, Problem № 4 (Chapter Self-Test), solved by 엄자균, finalized by 강병훈, re-finalized by 김은율 and
칭기즈
Problem
Which of the algorithm
properties:
input,
output, precision, determinism, finiteness, correctness, generality.
,if any, are lacking in the
following? Explain.
Input: S (
a set of intergers), m (an integer)
Output: All finite subsets
of S that sum to m
1. List all finite
subsets of S and their sums.
2. Step through the
subsets listed in 1 and output each whose sum is m.
Solution
1) If the set S is an infinite set, the
algorithm will not terminate, so it lacks the finiteness and output
properties.
2) Line 1 is not precisely stated since how to list the subsets of S
and their sums is not specified; thus the algorithm lacks the precision
property.
3)The order of the subsets listed in line 1 depends on the method
used to generate them, so the
algorithm lacks the
determinism property.
Since line 2 depends on the
order of the subsets generated in line 1, the determinism property is
lacking here as well.■
Comment:
This is a
very good example which helps to get the concept of chapter 4, especially what
each property of an algorithm means. Due to this problem I am now able to
distinguish each property an algorithm should have.
[Final OK by SGLee]
Ch. 4, Page 247, Problem № 2 (Chapter Self-Test), solved by 강병훈, finalized by 엄자균, re-finalized by 김영철 and 칭기즈
Problem
Write an algorithm that
receives as input the distinct numbers a, b, and c and assigns the values a, b,
and c to the variables x, y, and z so that
x < y < z.
Solution
We have to assign, compare and then swap if necessary, as
below.
Hint:
How does the swap() actually work?
In programming it is wrong to write:
y=x
x=y
because when we assign x to y the original
value stored in y is deleted, now it has the value of x.
Therefore we need to store the original value of y in order to give it
to x
Python code:
a=int(input())
b=int(input())
c=int(input())
x=a
y=b
z=c
if(y<x):
temp=y
y=x
x=temp
if(z<x):
temp=z
z=x
x=temp
if(z<y):
temp=z
z=y
y=temp
print(x,y,z)
Pactical image:
Now, it is sure that x < y < z. ■
Comment: This problem is very useful to
understand how the function swap() really works, hence it may help to
develop your computational thinking which is very important. The key idea is to
store the original value of the variable in the temporary space to assign it to
another variable.
[Final OK by SGLee]
Ch. 4, Page 247, Problem № 8 (Chapter Self-Test), solved by 강병훈, finalized by 김은율, re-finalized by 김영철 and
칭기즈
Problem
Write an algorithm that receives as
input the sequence
s[1], . . . , s[n]
sorted in non-decreasing
order and prints all values that appear more than once. Example: If
the sequence is
1 1 1 5 8 8 9 12,
the output is
1 8.
Solution
We have to run while loop and check if there are same
numbers, and print them if exist, and
skip to non-identical part. It is shown below.
Algorithm:
This way we can find repeated numbers and print them.
Python code:
i=0
s=[1 , 1 , 1 , 5 , 8 , 8 , 9 , 12]
n=len(s)
while(i<n-1):
if s[i]==s[i+1]:
print(s[i])
j=i
while(i<n and
s[i]==s[j]):
i=i+1
Practical image:
Sage code:
i=0
s=[1 , 1 , 1 , 5 , 8 , 8 , 9 , 12]
n=len(s)
while(i<n-1):
if s[i]==s[i+1]:
print(s[i])
j=i
while(i<n and s[i]==s[j]):
i=i+1
Practical image:
Notice: Sage code and Python code are the same because SageMath
uses a syntax resembling Python's, supporting procedural, functional and object-oriented constructs. ■
Comment: This problem is very straightforward
because if a sequence is in nondecreasing order, the repeating numbers always
stay next to each other and that is the key point to solve this problem.
However, it helps to understand the concept of the sequence of numbers in
nondecreasing order.
[Final OK by
SGLee] Ch. 5, Page 300, Problem № 2, solved by AYSU OZGUNEKIM, Revised by 김주형, Finalized by 유가이 올렉산드르,
Re-Finalized by 모하메드 and 칭기즈
Problem
Find the prime factorization
of 539.
Discussion:
A) Key Terms
I) prime
number(N): natural number that is greater than 1
and that cannot be formed by multiplying two smaller natural numbers(x,y),
where x,y are also greater than 1.
II) prime
factor: A factor that is a prime number (Prime Numbers
that can be multiplied to form a composite number)
III) prime
factorization: the decomposition of a composite number into a
product of prime numbers
B) Algorithm/Pseudo Code for testing whether an integer(N)
is prime
Check_Prime(int N)
//N is the number to be
checked
{
for d=2 to N1/2
if (N mod d == 0)
//mod function returns the remainder
return
d
return 0
}
Solution
Using the algorithm mentioned
earlier, we can easily check whether an integer(N) is prime or
not, so we combine the same algorithm with division to solve this problem
as following.
Let's
solve this task by using a factorial
tree:
*The yellow marked numbers are prime.
So we get : 539=(7^2)*11
■
Comment: From
this problem, I realized that Factors are
the numbers you multiply together to get another number.
ex) 5*3 = 15.
And Prime Factorization is
finding which prime numbers multiply together to make the original number. ■
Comment (Muhammad): when you try
to find Factorial tree, start checking the factors from smallest
to biggest (1,2,3,4,...) ■
[Final OK by
SGLee] Ch. 5, Page 300, Problem № 1 (Computer Exercise), solved by 칭기즈, Finalized by 유가이 올렉산드르
Problem
Implement Algorithm 1.8, testing whether a positive
integer is prime, as a program.
Python code
import math
n=int(input("enter
a number: "))
for i in range(2,math.floor(math.sqrt(n))+1)://check
if it has a divisor in the range[2,floor(sqrt(n))]
if(n % i==0): //if
there is no remainder, it means it has a divisor in this range
print(str(n)+" is not a
prime number")
quit()
print(str(n)+"
is a prime number") //if there is no divisor in the
range, it is a prime
Practical image
Case A)
Case B)
Sage Code
# Testing Whether an Integer Is Prime
@interact
def _(n=input_box (default=43, label='Enter the number such that n>1 ')):
for i in range(2,floor (sqrt (n))+1):
if n % i == 0:
print
n, "is composite"
return
print n, " is prime"
return
Practical image
Source: http://matrix.skku.ac.kr/2018-DM/DM-Ch-5-Lab.html ■
Comment: This
problem is a good and very easy example to get the concept of chapter 5,
especially the theory of identifying if the given number is prime or composite.
The key idea is that a composite number has a divisor in the range 2 to ⌊√n⌋.
-------------------------------------------------------------------------------------------------------------------------
[Final OK by SG
Lee] Ch. 5, Page 300, Problem № 3 (Computer Exercise), solved by 칭기즈and 김승영
Problem
Write a program that adds binary numbers.
Python code
import math
b=[int(x) for x in input().split()]
b1=[int(x) for x in input().split()]
carry=0
s=''
list1 = list(s)
for i in range(len(b)):
b2
= b[len(b)-i-1]
c1
= b1[len(b)-i-1]
list1.append( str((b2+c1+carry)%2))
carry=math.floor((b2+c1+carry)/2)
list1.append(str(carry))
s = ''.join(list1)
print(s[::-1])
Practical image
Sage Code
# Adding Binary Numbers
@interact
def _(b=input_box(default=1101, label='binary number'),
c=input_box(default=1001, label='binary number')):
b = str(b)
c = str(c)
n = len(b)
carry = 0
s = ''
for i in range(n):
b1 = Integer(b[n-i-1])
c1 = Integer(c[n-i-1])
s = str((b1+c1+carry) % 2) + s
carry = (b1+c1+carry) // 2
s = str(carry) + s
print s
return
Practical image
Source: http://matrix.s`kku.ac.kr/2018-DM/DM-Ch-5-Lab.html ■
Comment: 해당 코드는 binary numbers 즉, 2진수의 덧셈을 논하고 있다.논리 회로 과목에서 배웠던 '4-bit Full adder'
와 구동방식의 공통점이 많아 언급 하지 않을 수가 없게 되었다.
Discussion
Key Terms
I) LSB: Last Significant Bit, 가장 오른쪽자리의
Bit를 뜻하며 여기선 20 자리이다.
II) MSB: Most Significant Bit, 전과 반대로 가장 왼쪽자리의
Bit 이고 여기선 23 자리다.
Similarity
of operation
'4-bit Full adder' 의 그림 맨 오른쪽의 '0' 은 알고리즘이 'carry' 라는 변수를 지정해 주고 그 값을 '0' 이라고 설정 해준 것과 대응 하며 A0 에서 A3 그리고 B0 에서 B3 의 각각의 변수 값이 뜻하는 바도 원래의 알고리즘이 표현하려던 목적과도 동일하다. 또 세부적으로는 알고리즘이 제시한 식은 
이고
이는 i+1번째
자릿수의 결과 값은 3개의 변수의 연산으로부터 결정됨을 coding한 것인데 logic gate의 표현 식으로는’Ai ⊕ Bi
⊕ C(i-1)‘ 인 배타적 논리합 연산으로 표현하고 다음 자릿수로 넘어갈 ‘Carry’ 는 
이라고 알고리즘이 제시하였으며 logic gate의 표현 식으로는 ‘Ci= (Ai ^Bi) v (Bi ^C(i-1)) v (Ai ^C(i-1))’ 이고 이는 논리 곱과 논리 합 연산의 조합을 써서 3개의 parameter중 2개가 1 이면 ‘carry’ 가 1이 되는 연산이다. 이러한 연산을 하는 블록을 늘리면 더 많은 자릿수의 2진수 연산이 가능하게 될 것이고, 문제에서 제시된 알고리즘은 n 값을 원하는 길이만큼 조절하면 될 것이다.
Comment: The problem may seem to
be difficult but it is important to keep in mind that in binary addition we
need to start adding from the last digit. Therefore, we read array starting
from the end and we need to consider carry digit because in binary system we
have only 1 and 0.
[Final OK by SG
Lee] Ch. 5, Page 300, Problem № 6 (Computer Exercise), solved by 칭기즈, finalized by 유가이 올렉산드르and 김승영
Problem
Implement Algorithm 2.16, exponentiation by repeated squaring, as a program.
|
Algorithm 2.16
|
Exponentiation By Repeated Squaring
|
|
This algorithm computes  using repeated
squaring.
Input:  , 
Output: 
exp_via_repeated_squaring(, ) 
result 
while ( )
if(  )
 *
 *
return result
|
|
|
|
|
Solution
Python code
import math
a=int(input("Enter
the number: "))
n=int(input("Enter
the exponent: "))
result=1
x=a
while(n>0):
if(n%2==1):
result=result*x
x=x*x
n=math.floor(n/2)
print(result)
Practical image
Sage code:
@interact
def _(a=input_box(default=2, label='Enter the
number: '),n=input_box(default=2, label='Enter the exponent: ')):
result=1
while(n>0):
if(n % 2==1):
result=result*a
a=a*a
n=floor(n/2)
print result
return
Practical image
Comment: The number of times that the while loop executes
is determined by n. The variable n is repeatedly halved
and when n becomes 0, the loop
terminates. Recall that it takes time O(lg n) to reduce n to 0 by
repeated halving. This is a good and easy example not only to show how to
implement repeated squaring but also how effectiveness of algorithm is
important, the key idea is to compute the remainder after each
multiplication thereby keeping the numbers relatively small.
[Final OK by
SGLee] Ch. 5, Page 300, Problem № 9 (Chapter Self-Test), solved by 신혜수, finalized by 전종문 and
칭기즈
Problem
Use the Euclidean algorithm to find the greatest
common divisor of the integers 396 and 480.
Theorem:
Euclidean
Algorithm is algorithm for
finding the greatest common divisor of two integers.
Ex)
Let 
, where 
, 
, 
and 
are integers. Then 
.
Solution
The Euclidean algorithm gives
480 = 396 * 1 + 84.
b=396 r=84
Thus,
gcd(480, 396) = gcd(396, 84) (by
the Euclidean algorithm, 480
= 396 * 1
+ 84)
= gcd(84, 60) (by the Euclidean algorithm, 396
= 84*4 + 60)
=
gcd(60, 24) = gcd(24, 12) = gcd(12,0) =12
Conclusion:
∴ the greatest common divisor of the integers
396 and 480 = 12 ■
Comment: I think this Euclidean
algorithm make me to find the greatest common divisor more easier in short time when integers are
more bigger. Euclidean algorithm save more running time than prime
factorization to find the greatest common divisor.
[Final OK by
SGLee] Ch. 5, Page 300, Problem № 5 (Chapter Self-Test), solved by 정호진, finalized by 김희성 and
칭기즈
Problem
Write the binary number
10010110 in decimal.
Theory:
Solution
100101102=0*20+1*21+1*22+0*23+1*24+0*25+0*26+1*27
= 2+4+16+128
=15010
Answer:
∴The binary number 10010110(2) is equal
to 150(10) in decimal. ■
Comment: This problem is good example which helps to get the algorithm used
when converting any binary number into decimal and vice versa. The key idea is
to multiply each binary digit by 2 two the power corresponding to the position
of the digit.
[Final OK by
SGLee] Ch. 5, Page 300, Problem № 7 (Chapter Self-Test), solved by 서명원, finalized by 전종문, re-finalized by 김희성 and
칭기즈
Problem
Trace Algorithm 2.16 for the value n =
30.
Algorithm
Solution
The
algorithm begins by setting result to 1 and x to a.
Step
1) Since
n = 30 > 0,
the body of the while loop executes.
Step
2) Since
n mod 2 is not equal to
1,
result is not modified.
Step
3) x becomes a2, and n becomes 15.
Since
n = 15 > 0
the body of the while loop executes
Step
4) Since
n mod 2 is equal to 1,
result becomes
result * x = 1 * a2 = a2.
Step
5) x becomes a4, and n becomes 7.
Since
n = 7 > 0,
the body of the while loop executes.
Step
6) Since
n mod 2 is equal to 1,
result becomes
result * x = a2 * a4 = a6.
Step
7) x becomes a8, and n becomes 3.
Since
n = 3 > 0,
the body of the while loop executes.
Step
8) Since
n mod 2 is equal to 1,
result becomes
result * x = a6 * a8 = a14.
Step
9) x becomes a16, and n becomes 1.
Since
n = 1 > 0,
the body of the while loop executes.
Step
10) Since
n mod 2 is equal to 1,
result becomes
result * x = a14 * a16 = a30.
x becomes a32, and n becomes 0.
Step
11) Since n = 0, the while loop terminates.
Conclusion:
Therefore, the algorithm returns the result which is equal to a30 ■
I used the c language to code it.
The argument of multiplication is difficult to express
and is expressed as addition of argument.
Comment: We can see the Output is
always ak when we input x=a and n=k.
Because this algorithm divide k into 2 and
only multiply when n mod 2=1.
This is the same way of changing a decimal number to a
binary number.
(Ex. n =30 =11110(2) =22 *
24 * 28 * 216 ⇒
return result = a2 * a4 * a8 * a16 = a30
So, we can see that 11110(2) =22 * 24 *
28 * 216 and result = a2 * a4 * a8 * a16 = a30 are same
frame.)
[Final OK by
SGLee] Ch. 5, Page 300, Problem № 10 (Chapter Self-Test), solved by 정호진, finalized by 엄자균, re-finalized by 서명원, 정호진
and 칭기즈
Problem
Given that log 3/2 100=11.357747,
provide an upper bound for the number of modulus operations required by
the Euclidean algorithm for integers in the range 0 to 100,000,000.
Solution (Refer
Theorem 5.3.6)
Given
that
log3/2 100=11.357747
Discussion:
We
have to provide an upper bound for the number of
modulus operations required by the Euclidean algorithm for integers in the
range 0 to 100,000,000.
If integers in
the range of 0 to m, m ≥ 8, not both zero, are input to the euclidean algorithm,
then at most log3/2 (2m/3) modulus operations are
required.
Since
the given range 0 to 100,000,000,
So,
in this problem, m is 100,000,000. And we use this formula.
Solution:
log3/2 ((2(100,000,000))/3)
= log 3/2 (2/3)+ log 3/2 (100,000,000)
= log 3/2 (2/3) + log 3/2(100)4
= -1 + 4 log 3/2(100)
= -1 + 4 (11.357747) //Since log 3/2(100) = 11.357747
= -1 + 45.430988
= 44.430988
Conclusion:
Therefore, the upper bound we
found is 44. ■
Comment: Euclidean algorithm에 대한 이해가 부족한 상태에서 문제에 접근하다보니 스스로 아쉬운 부분과 이해가 되지 않는 부분이 있었지만, 문제에 적용하고 수정하는 과정을 통해서 해당 알고리즘에 대해 완벽하진 않지만 어느 정도 보완할 수 있었다. 물론, 다른 문제에 적용해보면서 발전시켜 볼 필요가 있다.(서명원)
처음 이 문제를 풀때는 위의 식이
어떤것을 의미하는지 정확히 몰랐었다. 그래서
문제를 완벽하게 풀이하지 못했다. 학우들이
처음 푼 풀이를 수정해주고 다시 문제를 풀어보니 처음 문제를 접했을 보다는 깔끔한 풀이가 완성된 느낌이다. 앞으로 문제를 풀때도 단순히 정답 도출에 목적을 두는게 아니라 어떻게 풀어야 하는지에 초점을 두고 공부해야겠다고 느낄 수
있는 문제였다. (정호진)
Comment: This problem is very easy if you know the rules used for
logarithms.
[Final OK by SGLee] Ch. 5, Page 264, Problem № 6 (Chapter
Self-Test), solved by 정호진,
finalized by 엄자균, re-finalized by 서명원, 정호진, 칭기즈
Problem
Write the decimal number 430 in binary and
hexadecimal.
Theory:
Binary
Number System
In the Binary (base 
) number system,
Any integer form is
based
where each 
and each 
is one of the binary digits 
, 
.
Hexadecimal
number system
Hexadecimal notation is based 
.
Any integer form is
based
where and each 
is one of the
hexadecimal digits , ,, 
, 
, 
, 
, 
, 
, 
, 10=
, 11=
, 
, 
, 
, 15=
.
Solution
I) 430 = 256+128+32+8+4+2
=
1×28
+ 1×27 + 0×26 + 1×25
+ 0×24
+ 1×23
+ 1×22
+ 1×21
+ 0×20
= 110101110(2)
II) 430 = 1×162
+ 10×161
+ 14×160
= 1AE(16)
Conclusion:
∴110101110(2)
, 1AE(16)
■
Comment:
Binary is used at computer system because it is
easy and fast to handle the data. In today's increasing use of computer, binary
is very important and worth learning. Hexadecimal complemented the binary's
weakness - too long - and it is well used at computer system, too.
[Final OK by
SGLee] Ch. 5, Page 300, Problem № 13 (Chapter Self-Test), solved by 강병훈, finalized by 김주형, re-finalized by 전종문 , 칭기즈
Problem
In exercise 13-16, assume that we choose
primes
p =12
q =17 n =19 .
Compute z and φ.
Note:
z =p×q
φ =(p -1)(q -1)
Solution
We need to find z =p×q and φ =(p -1)(q -1)
z =12×17 = 204
φ =(12-1)(17-1)=11×16=176
Conclusion:
∴z =204, φ =176 ■
Comment: I know about that φ(n )
used at RSA(Type of Public-key cryptography) .
φ(n) is the number of coprime n and number which is less
than n
[Final OK by TA]
Ch. 5, Page 299, Problem № 4 (Chapter Self-Test), solved by AYSU OZGUNEKIM,
finalized by 김정주, re-finalized by 서명원, 칭기즈
Problem
Find lcm(2*52*72*134,
74*132*17)
Theory:
Solution
Following the given theory about lcm(m,n),
we gonna put the given data.
lcm(2*52*72*134, 74*132*17)
= 2max(1,0)
* 5max(2,0) * 7max(2,4) * 13max(4,2) *
17max(0,1)
=
2 * 52 * 74 * 134 * 17
Conclusion:
lcm(2*52*72*134, 74*132*17)= 2 * 52 * 74 *
134 * 17 □
Comment:
This problem is very straightforward which helps to understand the logic used
when we need to compute the least common multiple of two given numbers. The key
idea is to take the maximum power for the common prime factors and multiply
them.
[Final OK by TA]
Ch. 5, Page 300, Problem № 11 (Chapter Self-Test), solved by 엄자균, finalized by 정호진, 칭기즈
Problem
Use the
Euclidean algorithm to find integers s and t satisfying
s·396+t·480= gcd(396,480)
Theory:
The Euclidean Algorithm:
Let , where , , and are integers.
Then .
BÉZOUT’'S THEOREM:
If and 
, then there 
such that
.
Solution
Refer to the Euclidian Algorithm:
480= 396 × 1 + 84 ①
396= 84 × 4 + 60 ②
84 = 60 ×1 + 24 ③
60 = 24 ×12 +12 ④
24 = 12 × 2
Thus,
gcd(396,480)
=gcd(396,84)=gcd(60,84)=gcd(60,24)=gcd(12,24)=12
Refer
to Bezout’s theorem:
12 = 60 - 24 × 2 ←⑤(inverse④ )
12 = 60 - (84 - 60 × 1) × 2 (put③ in⑤)
12 = 3 × 60 - 2× 84 ←⑥
12 =3 × (396-84×4)-2× 84 (put②in⑥)
12= 3 × 396 - 84× (12+2)
12=3× 396-14× 84 ←⑦
12=3× 396-14× (480-396×1) (put①in⑦)
12=17× 396-14× 480
396(17) + 480(-14)=12
Conclusion:
s=17, t= -14
Comment: This problem is a great example which
helps to understand how to use the Euclidian Algorithm as well as Bezout’s
theorem in a problem-solving. The key point is that the Euclidian algorithm
makes it easier to use Bezout’s theorem, hence it is useful to keep in mind
both of them in problem solving.
[Final OK by
SGLee] Ch. 5, Page 299, Problem № 3 (Chapter Self-Test), solved by AYSU
OZGUNEKIM, finalized by 전종문, 칭기즈
Problem
Find
gcd(52·72·134, 74·132·17).
Theory:
Solution
gcd(m,n) where m=52·72·134 and n=74·132·17
Let’s rewrite them in the form:
52·72·134 = (72·132) × (52·132)
74·132·17 = (72·132) × (72·17)
52·132 and 72·17 are coprime.
Note:
Two numbers are called relatively
prime, or coprime, if their greatest common
divisor equals 1. For example, 9 and 28 are relatively prime.
Conclusion:
∴ gcd(52·72·134,
74·132·17) = 72·132.
■
Comment: This problem is very simple to
understand. The key idea here is to find the greatest common divisor by
rewriting two given prime factorizations so that it becomes the multiplication
of the sequence of common prime multiples having the least power and the remaining
part of the given prime factorization.
[Final
OK by SGLee][TA] Ch 6, P.37*, Com Exs. 2, 칭기즈,유가이,김은율
[TA] Ch 6, P.37*, Com Exs. 2, Problem № 2 (Com. Exs.)
Write a
program that generates all permutations of the elements {1...n}
Theorem:
|
Number of Permutations = n!
(factorial)
|
|
|
|
Solution
Python code:
import itertools
import math
array=[str (x) for x in input().split()]
print ("the
number of permutations is "+str(math.factorial(len(array))))
print (list(itertools.permutations(array)))
EXAMPLE
Sage code:
#permutation
elements =
['A', 'B', 'C', 'D', 'F']
perms =
Arrangements(elements,len(elements))
print perms
print
perms.cardinality()
print perms.list()
■
Comment: The problem is very easy but due to it I
now understand how to implement the logic of solving in coding. The idea of
finding permutations is based on a multiplication principle.
[TA] Ch 6, P.37*, Com Exs. 3, typed and solved
by 칭기즈
ch 6, comp exercises, prob.3 solved by 칭기즈 finalized by 전종문
Problem
Write a program that generates
all r-permutations of the elements {1...n}
Theorem:
|
Theorem 2.10
|
|
|
The numbers of  -permutation
of a set of distinct objects is
 ,  .
|
Solution:
Python code:
import itertools
import math
array=[str (x) for x in input().split()]
r=input("enter
number of elements to be selected: ")
n=(math.factorial(len(array)))/(math.factorial(len(array)-int(r)))
print ("the
number of permutations is "+str(int(n)))
print (list(itertools.permutations(array,int(r))))
EXAMPLE
This is sage code
# permutation
elements = ['A', 'B', 'C']
perms = Arrangements(elements, 3)
print perms
print perms.cardinality()
print perms.list()
Comment: The problem is very easy. The idea of
arrangements(a,b) is to get the sequence and number of elements to be selected.
■
|
Fina OK by SGLee
[TA] Ch 6, P.37*, Com Exs. 1, 칭기즈,유가이, 김은율
|
Ch 6, P.37*, Com Exs. 1, Problem № 1 (Com. Exs.)
Write a program that generates all r-combinations of the elements {1...n}.
Theorem:
Solution
Python code:
import itertools
import math
array=[str (x) for x in input().split()]
r=input("enter
number of elements to be selected: ")
n=(math.factorial(len(array)))/(math.factorial(len(array)-int(r))*math.factorial(int(r)))
print ("the
number of combinations is "+str(int(n)))
print (list(itertools.combinations(array,int(r))))
EXAMPLE
Sage code:
#Combination
sequence =
['A', 'B', 'C']
doubles =
Combinations(sequence, 2)
print doubles
print
doubles.cardinality()
print doubles.list()
■
[TA] Ch 6, P.37*, Com
Exs. 8, typed and solved by 칭기즈
ch 6, comp exercises,
prob.8 solved by 칭기즈 finalized by 전종문
ch 6, comp exercises,
prob.8 solved by 칭기즈 finalized by 전종문 and re-finalized by 유가이 올렉산드르
Problem №8 (Com. Exs.)
Write a
program that computes Catalan number
Theorem:
Catalan numbers are defined by the
formula:
for 
and 
.
Catalan numbers are
.
Solution
Python code:
import math
n=int(input())
c=int(math.factorial(2*n)/(math.factorial(n+1)*math.factorial(n)))
print ("Catalan
number is " +str(c))
EXAMPLE
Sage code for Catalan
number:
# Catalan number 생성(정의)
for i in range(10):
print binomial(2*i,i)/(i+1)
Also, to my mind, we can
calculate the Catalan number in a simpler way, by using formulas of recurrence
relations:
Alternate Python Code using recurrence
relation formula:
import functools
@functools.lru_cache(maxsize=None)
def catalan(n):
if n
== 0:
return 1
return catalan(n-1)*2*(2*n-1)//(n+1)
n=int(input("enter a
number"))
print(catalan(n))
Alternate Sage Code by
using reccurrence relation formula:
def _(n):
if n == 0:
return 1
return _(n-1)*2*(2*n-1)//(n+1)
print _(9)
Comment: As it can be seen there are many ways to
calculate Catalan number in coding which makes this problem beautiful .
[Final OK by TA] Ch 6,
P.37*, Com Exs. 9, typed and solved by 칭기즈
Revised-Finalized by Muhammad
Write a
program that generates Pascal's triangle to level n
Theorem:
Pascal’s triangle
Binomial
coefficients in a triangular form
Figure 6.7.1 Pascal’s triangle
Solution:
Python code:
n=int(input("Enter a triangle's
level: "))
array=[]
for index in range(n):
array.append([])
array[index].append(1)
for j in range(1,index):
array[index].append(array[index-1][j-1]+array[index-1][j])
if(n!=0):
array[index].append(1)
for index in range(n):
print(" "*(n-index),end="
",sep=" ")
for j in range(0,index+1):
print('{0:6}'.format(array[index][j]),end="
",sep=" ")
print()
C-Code:
#include
<stdio.h>
long factorial(int);
int main()
{
int i, n, c;
printf("Enter a triangle's
level: ");
scanf("%d",&n);
for (i = 0; i < n; i++)
{
for (c = 0; c <= (n - i - 2); c++)
printf(" ");
for (c = 0 ; c <= i; c++)
printf("%ld ",factorial(i)/(factorial(c)*factorial(i-c)));
printf("\n");
}
return 0;
}
long factorial(int n)
{
int c;
long result = 1;
for (c = 1; c <= n; c++)
result = result*c;
return result;
}
EXAMPLE
Comment: Pascal's Triangle also
has significant ties to number theory. The most apparent connection is to
the Fibonacci sequence. Adding the numbers of Pascal's triangle
along a certain diagonal produces the numbers of the sequence.
Sums along a certain diagonal of Pascal's triangle produce
the Fibonacci sequence.
[Final OK by TA] p.371
problem 18 Solved by 정호진 finilized by 칭기즈
Problem
Two fair dice are rolled.
What is the probability that the sum of the numbers on the dice is 8?
Solution
|
Multiplication Principle
|
(Product Rule)
|
|
|
All cases:
First dice have 6 different possible results ( from 1 to 6)
Second dice have 6 different possible results ( from 1 to 6)
Thus,
By the Multiplication Principle,
n1=6 and n2=6 => the total number of possible outcomes is
6*6=36
Cases that satisfies n1+n2=8:
(2,6), (3,5), (4,4), (5,3),
(6,2)
which are 5 favourable outcomes in total.
Probability= 
Conclusion:
hence, the probability is 5/36. ■
Comment: The problem is very easy to understand since the
idea is based on a multiplication principle which we learnt at high schools.
[Final OK by SGLee and TA] ch 6, p.371, prob.27 김승연, 오동찬, 칭기즈, TA
Problem 27 section 7 p. 371
Use the Binomial Theorem to
prove that
Binomial Theorem
|
Theorem 7.1
|
Binomial Theorem
|
|
If  and  , then
 .
|
Solution:
Notice that:
in the given problem a = 2 and b = -1.
Also:
.
Thus,
which can be written as
hence,
Because the LHS and RHS is equal
due to
the Binomial expansion when a = 2 andb = -1. So the answer is 1 .
■
Problem 32 section 8 p.
372
Solved by 서명원 Date:
2018.10.29
finilized
by 칭기즈 Date: 2018.10.29
Re-Finalized
& Final Thank you by 김은율, Date: 2018.10.31
Problem
Let P =
{p1, p2, p3, p4, p5}
be a set of five (distinct) points in the ordinary Euclidean plane each of
which has integer coordinates. Show that some pair has a midpoint that has
integer coordinates.
Solution
There are 5 different points having integer
coordinates.but to find a midpoint we need to take different 2 points out of 5.Hence, we can take 4 points
out of 5 to form 2 pairs.
|
Pigeonhole
Principle (1st Form)
|
|
|
If pigeons fly into  pigeonholes and  , some pigeonhole contains at least two pigeons.
|
pigeons or n = 5, total number of points in a set P
pigeonholes or k = 4 points ,which are 2 pairs.
Thus,
by the Pigeonhole Principle at least two points, Pi = ( x i, yi )
and Pj = ( x j, yj ) have
Both x i and x j even
or both x i and x j odd
Both y i and y j even
or both y i and y j odd
Theorem:
The sum of even numbers a and b is always even.
Proof: a=2k b=2q
a+b=2k+2q=2(k+q)=2n
The sum of odd numbers a and b is always even.
Proof: a=2k+1 b=2q+1
a+b=2k+2q+2=2(k+q+1)=2m
Thus,
( xi + xj )/
2 and ( yi + yj) /2 are integers.
Conclusion: Therefore, the midpoint of
the pair pi and pj has integer coordinates.■
Сomment: There are 5 different points having integer coordinates.but
to find a midpoint we need to take different 2 points out of 5.Hence, we can take 4 points
out of 5 to form 2 pairs hence it is based on pigeonhole principle. The idea is
that there are at least two points having odd or even x and y coordinates.
[Final OK by TA] Ch. 7 P.424 Problem 1 solved by 전솔람 Finalized by 칭키즈, 김영철 , Muhammad
Problem
Answer part (a)-(c) for the sequence defined by rules:
1. The first term is 3.
2. The n th term is n plus the previous term.
(a) Write the first four terms of the sequence.
(b) Find an initial condition for the sequence.
(c) Find a recurrence relation for the sequence.
Solution
1. Let n-th term of the sequence be an, which logically makes the previous term an-1.
2. Hence, the
formula of n-th term is
an = n + an-1
3. Let me
remind you that the first term is 3 ( a1=3 )
4. Hence to
find another three elements:
n = 2
-> a2 = 2 + a2-1 = 2 + a1 = 2 + 3 = 5
n = 3
-> a3 = 3 + a3-1 = 3 + a2 = 3 + 5 = 8
n = 4 -> a4 = 4 + a4-1 = 4 + a3 = 4 + 8 = 12
Answer:
(a) Write the first for
terms of the sequence.
a1 = 3, a2 = 5, a3 = 8 , a4 = 12
(b) Find an initial
condition for the sequence.
a1 = 3
(c) Find a recurrence
relation for the sequence.
an = n + an-1 ■
Comment/What
We can learn from this question:
Recurrence
relations are the same as recursive functions in Programming where we relate
some term in a sequence to a previous term. Secondly, a hint for solving this
problem can be using some values to plugin and check
[Final OK by
TA] Ch. 7 P.424 Problem 2 Solved by 전솔람 finilized by 칭기즈 , 김영철, Muhammad
Problem
Assume that a person invest 4000 dollars at
17 percent interest compounded annually. Let A(n) represent the amount at
the end of n years. Find a recurrence relation and an
initial condition for the sequence A(0), A(1), ......
|
Definition
1.1
|
|
|
|
Solution
1. Let a0 be the initial amount invested
--> a0=4000
2. After 1 year, a1 will
be
--> a1 = a0 + 0.17 a0 = 1.17 a0
3. After 2 years, a2 will be
--> a2 = a1 + 0.17 a1 = 1.17
a1 = (1.17)2 a0
4.
Thus, after n years, an will
be
--> an = an-1 + 0.17 an-1 = (1.17) an-1 = ... =
(1.17)n a0
Answer:
Initial
state:
a0=4000
Recurrence
relation:
an =
(1.17)an-1 ,where a0=4000 ■
Comment
Remember that recurrence relation should
in the form of an represented by
any predecessor term like (an-1). That’s why the
relation/equation provided by the original answer (an = (1.17)n * 4000 )
Is not a recurrence relation.
Final OK by SGLee] Ch 7, P424, P.5 칭기즈
finalized by 오동찬
Ch 7, p. 424 Problem 5
Is the recurrence relation
an=an-1+an-3
a linear homogeneous
recurrence relation with constant coefficients?
Solution:
Definition:
|
Definition 2.6
|
|
|
|
Thus,
The recurrence relation in the definition is
linear because the right-hand side is a sum of previous terms of
the sequence which are
an-1 and an-3
Notice that:
an = 1 *an-1 + 1*an-3
Hence,
1 is a constant
coefficient.
Conclusion:
The
recurrence relation,
an=an-1+an-3
is a linear homogeneous recurrence relation with
constant coefficients ■
Comment:
We could find that the given
recurrence relation is a linear homogeneous recurrence relation with constant coefficients, due to the definition.
Re-Finalized] Ch. 7 P.424 Problem 6 전솔람, 김희성, 칭기즈 by Muhammad
Chapter 7
Page 424 Problem 6 Problem
Ssolve the
recurrence relation subject to the initial conditions.
6. a(n) = - 4
a(n-1) - 4 a(n-2), a(0) = 2 a(1) = 4
Solution:
By using the
quadratic formula derived from theorem 2.14 we can see that we
can form a second power polynomial by replacing ( a(n)=
x^2 , a(n-1)= x , a(n-2)=1) as following
x2 = -4x-4
x2+4x+4 = 0
D = b2-4*a*c = 16-16
= 0
x1
and x2 =
-4/2 = -2 .
There is only one root 2
with multiplicity 2. So
|
Theorem 2.14
|
|
|
|
an=a*(-2n)+b*n(-2n)
* Our next step is to find the
coefficients (a,b) using:
a0 = 2
a1 = 4
1.For n=0 :
a0=a*(-20)+b*0(-20)=2
=a=2
2.For n=1 :
a1=2*(-21)+b*1(-21)=4
=-4-2b=4
-2b=8
b=-4
Thus:
an=2*(-2n)-4*n(-2n)
Conclusion: an=2(-2n) - 4n(-2n) ■
Comment:
After this question we can see that no
single information given in any mathematical problem is redundant, sooner or
later we can use it
[Final OK by TA] Ch. 7
P.424 Problem 7 solved by 전솔람 Finalized by 김희성, 칭키즈, Muhammad
Problem
Solve the
recurrence relation subject to the initial conditions.
7. a(n)
= 3 a(n-1) + 10 a(n-2)
a(0) =
4 a(1) = 13
Solution:
By using the
quadratic formula derived from theorem 2.14 we can see that we
can forma second power polynomial by replacing( a(n)= x^2 , a(n-1)=
x , a(n-2)=1) as following:
x2=3x+10
x2-3x-10=0
(x-5)(x+2)=0
X=5 x=-2
There are 2
roots so
|
Theorem 2.11
|
|
|
|
an=a*(5n)+b*(-2n)
* Our next step is to find the
coefficients(a,b) using:
a0=4
a1=13
*For n=0
a0=a*(50)+b*(-20)=2
=a+b=4
*For n=1:
a1=2*(51)+b*(-21)=13
=5a-2b=13
*Next: we will solve
these equations for (a,b):
a+b=4 (1)
5a-2b=13 (2)
Let’s multiply equation (1) by 2:
2a+2b=8 (3)
Let’s add equation (3) and (2):
7a=21
a=3
hence:
3+b=4
b=1
Thus:
an=3*(5n)+1*(-2n)
Conclusion:
an=3*(5n)+1*(-2n)■
Comment:
After this question we can see that no
single information given in any mathematical problem is redundant, sooner or
later we can use it
[ReFinalized] Ch.7, P.424, Problem7, 칭기즈, Muhammad,김희성
Problem
Let Cn denote the number of strings over {0,1,2} of length n that contain an even number of 1's.
Write a recurrence relation and initial condition that define the sequence C1,C2 ,
...
Solve the recurrence relation to obtain an explicit formula for Cn.
Definition of
recurrence relation
Solution:
By the Addition Principle
Cn=(a)+(b)+(c) , where a,b,c are string types formed by {0,1,2}
there are 3 ways to form a n-length string with even number of 1's:
1)
An n-length string begins with 0 and contain an even number of 1's.
Since
any (n-1)-length string containing even
number of 1's can follow the initial 0, there are Cn-1 strings of type (a).
2)
An n-lengths string begins with 2 and contain
an even number of 1's.
Since
any (n-1)-length string containing even
number of 1's can follow the initial 2, there are Cn-1 strings of type (b).
For the type (c)
3)
As n- length string that begins with 1
should contain odd number of 1's to make even number overall.
By the formula of permutation with repetitions
RP(n,k)=nk
There
are 3n-1 strings altogether of length
n-1
and&nb
is the
length of the simple path from the root to 
.
contains each vertex
in 
is a universal
quantifier, which is interpreted as “for every”, “for any value of “
and etc.
is an existential
quantifier, which means “ there exists”, “there is at least one value
of” ant etc.
, 
, 
.
, 
is
.
