SKKU Discrete Mathematics
(Ch. 5, Introduction to Number Theory)
Prof : Sang-Gu Lee at SKKU
http://matrix.skku.ac.kr/2018-DM/DM-Labs.htm Discrete Math Labs (실습실)
http://matrix.skku.ac.kr/2018-album/2018-Lectures-sglee.htm (강의실)
http://matrix.skku.ac.kr/2018-DM-QnA/ (질문과 답변)
http://matrix.skku.ac.kr/2018-DM-Sol/2018-DM-Sol.htm (문제풀이)
http://matrix.skku.ac.kr/2018-DM-PBL/ (PBL
report 보고서)
http://matrix.skku.ac.kr/2018-DM-PBL-Eng/ (PBL report
Eng, 영문 보고서)
Ch. 5, Introduction to Number Theory
Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-5/
DM-Ch-5-Lab http://matrix.skku.ac.kr/2018-DM/DM-Ch-5-Lab.html
DM Ch. 5, 동영상강의
5-1 Divisors https://youtu.be/NN46r0qlIW0
5-2 Repr of Integers and Integer Alg https://youtu.be/aF5MPAjkMcI
5-3 The Euclidean Algorithm https://youtu.be/sSuzv8J3MSA
Review (Ch 1-5) https://youtu.be/aeKA-MNkhCw
PBL 학생 발표 (Ch 1-5 Solutions) https://youtu.be/HuzLCXDD2AA
Midterm Exam Solutions : https://youtu.be/iAfQCycd6ac
(1) State more than 10 DM Definitions and concepts what you learned in Ch. 1, 2, 3, 4, 5 ,6,7,8,9
Sets and Logic |
Set, Logic, objects, cardinality, Empty set, Equal sets, subset , proper subset, power set, union, intersection , partition , Cartesian product , proposition, conjunction, disjunction, contrapositive , De Morgan’s Law… |
Proofs |
Definitions, Theorem, Lemma, Corollary, congruent, supplementary, direct proof, counterexample, Proof by contradiction, Proof by contrapositive, Proof by cases, Proofs of equivalence, existence Proofs … |
Functions, Sequences and Relations |
Functions, mappings, transformations, ordered-pair, floor, ceiling, The Quotient(Chinese)-Remainder Theorem, one-to-one (injunctive) function, Onto function, bijective function, Inverse Function, composition function, unary operator, sequence, string, digraph, reflexive, symmetric, transitive… |
Algorithms |
Algorithm, Sorting , Insertion Sort, Best-case-time, randomized algorithm , big oh, omega, theta … |
Introduction to Number Theory |
Divisor, factor, quotient, Fundamental Theorem of Arithmetic, prime number,LCM,GCD, bit, binary Number System, base, repeated squaring, Euclidean Algorithm, BÉZOUT’'S THEOREM,RSA cryptosystem… |
Counting Methods and The Pigeon Hole Principle |
Multiplication Principle, reflexive relations, Addition Principle, Inclusion-Exclusion Principle, Permutation, r-permutation, combinations, good route, Catalan numbers, Binomial Theorem, Pascal’s triangle, Pigeonhole Principle… |
Recurrence Relations |
recurrence relation, Ackerman’s Function, iteration, linear homogeneous recurrence relation with constant coefficient, nonlinear recurrence relations… |
Graph Theory |
Graphs, vertices, edges, Path, parallel edge, isolated vertex, simple graph, weight graph, similarity graph, bipartite , complete bipartite, connected graph, components, degree of a vertex, Hamilton’s puzzle, ring model, adjacency matrix, isomorphic, planer, planar graph… |
Trees |
rooted tree,level of a vertex, height, Huffman codes, Hierarchical Definition trees, internal vertex, terminal vertex , spanning tree , depth-first search, Minimal spanning tree, child, binary tree , Tree Traversals, isomorphic trees, nonisomorphic trees |
The level of a
vertex is the
length of the simple path from the root to
.
A recurrence relation defines a sequence
by giving the th value in terms of its
predecessors.
A cycle in a graph contains each vertex
in
exactly once, except for
the starting and ending vertex that appears twice, a Hamiltonian cycle.
The symbol is a universal
quantifier, which is interpreted as “for every”, “for any value of “
and etc.
The symbol is an existential
quantifier, which means “ there exists”, “there is at least one value
of” ant etc.
An algorithm is a sequence of operations that are executed in a certain step-by-step method.
binary number is a number written in the base-2numeral system or binary numeral system, which uses only 0 (zero) and 1 (one).
The octal numeral system is expressed in the base-8 number system, and uses the only 0 to 7.
(2) State more than 5 things that you know/can/find after you studied the first 5 Chapters.
Sets and Logic |
union, intersection , Cartesian product , proposition, conjunction, De Morgan’s Law… |
Proofs |
direct proof, counterexample, Proof by contradiction, Proof by contrapositive, Proof by cases, Proofs of equivalence, existence Proofs … |
Functions, Sequences and Relations |
floor, ceiling, The Quotient(Chinese)-Remainder Theorem, composition function, unary operator, sequence, digraph, reflexive, symmetric, transitive… |
Algorithms |
Algorithm, Sorting , Insertion Sort, Best-case-time, randomized algorithm , big oh, omega, theta ,Insertion Sort, Bubble Sort… |
Introduction to Number Theory |
Fundamental Theorem of Arithmetic, prime number,LCM,GCD, binary Number System, base, repeated squaring, Euclidean Algorithm, BÉZOUT’'S THEOREM,RSA cryptosystem… |
Counting Methods and The Pigeon Hole Principle |
Multiplication Principle, Addition Principle, Inclusion-Exclusion Principle, Permutation, r-permutation, combinations, good route, Catalan numbers, Binomial Theorem, Pascal’s triangle, Pigeonhole Principle… |
Recurrence Relations |
recurrence relation, Ackerman’s Function, iteration, linear homogeneous recurrence relation with constant coefficient, nonlinear recurrence relations… |
Graph Theory |
Graphs, Path, weight graph, Dijkstra’s Shortest-Path Algorithm, Hamilton’s puzzle, adjacency matrix… |
Trees |
rooted tree, Huffman codes, Hierarchical Definition trees, spanning tree , depth-first search, Minimal spanning tree, binary tree , Tree Traversals, inorder,preorder,postorder traversals |
The order of quantifiers is essential because changing the order changes the meaning.
A number is composite if it is divisible by any number in the range of [2; floor(sqrt(n))], otherwise it is a prime number.
The characteristics of algorithm is: input, output,definiteness, effectiveness, finiteness,correctness and generality but in some algorithms some characteristics my be absent.
To solve recurrence relation by iteration we need to keep substituting elements with the previous one until it reaches initial condition.
Ackerman’s function is the recurrence relations
(1.11) ,
(1.12) ,
.
The initial conditions
(1.13) ,
Ackerman’s function is rapid rate of growth.
gcd(a,b) can be found by taking the product of the prime numbers to the power of the minimum exponent between two numbers.
Then is
.
http://matrix.skku.ac.kr/2018-DM/DM-Ch-5-Lab.html
1. (5 pt) What is your most important contribution or founding that you shared with others in QnA.(Quality)
As it can be seen I was relatively active since I was participating on QnA a lot. I think my solutions were useful for some people to understand the concept of the class. Moreover, I solved a lot of computer exercises which can be useful to understand the concept and idea of the chapter 4, which is algorithm
A. No. of Final OK by SGLee Problems (and/or Completed Discussion/Question) in QnA that your name is included.
Final Ok Problems Number: 68 Problems (from chapter 1,2,3,4,5,6,7,8,9)
B.(Quantity 10pts) Quality of Your Participation : 2
(1) Write what you especially remember while you are doing A-1, 2, 3.
Page 124 (computer exercises) problem 2
Solved by 칭기즈,Date: 2018.09.25
Revised by 김정주,Date: 2018.09.30
Final OK by SGLee
I especially remember it since 김정주 made me conclude that any problem can be solved in different ways, however they are not equally efficient. After this I realized what does efficiency of the algorithm really mean. As a future student of software department, it is very important for me that is why I like the system of QnA.
(2) What did you learn or feel while learning DM (Action Learning/PBL) with your classmates?
During the classes of Discrete Mathematics, I developed my computational thinking skills due to chapter 4 and 3(Algorithms, Functions, Sequences and Relations ), critical thinking skills due to chapter 1 and 2(Sets and Logic, Proofs) and enlarged my knowledge of Number Theory due to chapter 5. I think these classes were useful for me as a student of software engineering department.
(4) Write names of YOUR PBL Team members and Team Leader.
Team Leader: 칭기즈
Team Members: 칭기즈, 유가이올렉산드르, 김승연, 권재연, 이상민,
(B4) (Tentative) Project (1st Draft)
What is your project (and In-depth study) and your role in your Team (Leader, Idea, Solve, Prove, Coding, Typing, Presentation etc). (Write what you have done on your Chapters!) or ******
The area of our project should be related to the chapter 4 which is Algorithms and chapter 5, Number theory, hence we decided to take Addition of Binary numbers for an in-depth study because it will show the relationship between those two chapters.
Role: Leader, coding,typing
3장. PBL 참여 부분
◆ Solve-Revise-Finalize (and Final OK)
Page : 64 Problem 21
Solved By : 칭기즈, Date: 2018.09.19
Finalized By: 유가이 올렉산드르, Date: 2018.09.21
Final OK by TA , Date: 2018.10.04
Problem 21
Let K (x, y) be the propositional function “x knows y”. The domain of discourse is the Cartesian product of the set of students taking discrete math with itself (i.e. both x and y take on values in the set of students taking discrete math). Represent the assertion “someone does not know anyone” symbolically.
Solution
Denote the statement “x does not know y” as ㄱK (x, y). Since both x and y are the Cartesian product of the set of students who have taking discrete mathematics (this is the set of students about which we are talking in the exercise [all students]), then we can assume than someone of the student x (∃x) doesn’t know anyone of the student y (∀y). Full symbolic expression (someone does not know anyone): ∃x ∀y ㄱK (x, y). ■
Note: This problem helped me to understand the meaning and the concept of symbols used in Discrete mathematics and apply them in
problem solving.
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 if is a conditional proposition.
Proposition Proposition |
\ (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:
1 |
1 |
0 |
1 |
0 |
1 |
|
|
|
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
44 |
64 |
77 |
15 |
3 |
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
44 |
64 |
77 |
15 |
3 |
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
44 |
64 |
77 |
15 |
3 |
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
44 |
64 |
77 |
77 |
3 |
j>=1 and val< s[2]= 64 is true
s[3] =s[2]=64 j=j-1 = 1
44 |
64 |
64 |
77 |
3 |
j>=1 and val< s[1]= 44 is true ,
s[2]=s[1]=44 j=j-1 = 0
44 |
44 |
64 |
77 |
3 |
j>=1 is false, skips the loop
s[j+1]=s[1]=val=15
15 |
44 |
64 |
77 |
3 |
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
15 |
44 |
64 |
77 |
77 |
j>=1 and val< s[3]= 64 is true ,
s[4] =s[3]=64 j=j-1 = 2
15 |
44 |
64 |
64 |
77 |
j>=1 and val< s[2]= 44 is true ,
s[3] =s[2]=44 j=j-1 =1
15 |
44 |
44 |
64 |
77 |
j>=1 and val< s[1]= 15 is true ,
s[2] =s[1]=15 j=j-1 = 0
15 |
15 |
44 |
64 |
77 |
j>=1 is false
15 |
15 |
44 |
64 |
77 |
s[1]=val=3
3 |
15 |
44 |
64 |
77 |
Output
3 |
15 |
44 |
64 |
77 |
is sorted. ■
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.
5 |
51 |
2 |
44 |
96 |
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
2 |
51 |
5 |
44 |
96 |
Step II) Next, i=2. If j=rand(2,5)=5,
after the swap we have
2 |
96 |
5 |
44 |
51 |
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:
2 |
96 |
5 |
51 |
44 |
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( max for if 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.
![]() |
*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.
Algoruthm1.8 |
Testing Whether an Integer Is Prime |
This algorithm determines whether the
integer If If To test whether Input: Output : |
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.
Algorithm 2.12 |
Adding Binary Numbers |
This algorithm add the binary
numbers Input: Output: binary_addition( carry for |
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 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.
![]() |
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.
|
Theorem:
|
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
|
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.
■
|
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:
Definition 2.15 |
|
Given a set (a) An (b) The number of |
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
|
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 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