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 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:
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(, , : 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.
*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 is prime. If is prime, the algorithm returns . If is composite, the algorithm returns a divisor satisfying . To test whether divides , the algorithm checks whether the remainder when is divided by , is zero. 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 and and stores the sum in . Input: , , Output: binary_addition(, , , ) carry for to
|
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.
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 -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.
■
|
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 containing (distinct) elements, (a) An -combination of is an unordered selection of -elements of (i.e. an -element subset of ). (b) The number of -combination of a set of distinct elements is or .
|
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 Cn-1 strings contain even numbers of 1's
3n-1- Cn-1 contain odd number of 1's
Thus,
Cn=Cn-1+Cn-1+3n-1-Cn-1= 3n-1+Cn-1
Hence initial condition
C1=2
Solving the recurrence relation by iteration:
Cn = 3n-1+Cn-1
= 3n-1+(3n-2+Cn-2)
= 3n-1+3n-2+3n-3 + Cn-3
Keeping solving in this way, once we
will get:
=31+32+33 +... + 3n-1+ C1
=2+(3n-3)/(3-1)=(3n+1)/2
Conclusion:
A recurrence relation and initial condition :
Cn = Cn-1+Cn-1+3n-1-Cn-1 = 3n-1 + Cn-1
with the initial condition
C1=2
Solution : Cn = (3n+1)/2 ■
Comment:
The idea of this questions is not simple . So I recommend you to go through the different theorems/principles mentioned through the solution before.
plus Definition of recurrence relation
[Final OK by SGLee] Ch 7, P424, P.9, by 칭기즈, 전종문
Ch 7, P424, P.9, by 칭기즈, 전종문
This algorithm evaluates the polynomial
at the point t.
Input: The sequence of coefficients C0,C1, ... ,Cn, the value t, and n
Output: p(t)
poly(c,n,t){
f(n==0) ⇒ line 1
return c0 ⇒ line 2
return t*poly(c,n-1,t)+cn ⇒ line 3
}
Find the recurrence relation and an initial condition for the sequence {bn}.
Solution
Let bn : the total number of multiplications at line 3 required to compute p(t).
Initial condition : b0 = 0 (The total number of multiplications = 0 when n=0 )
At line 1-2 the number of multiplications is 0.
At the line 3, there is 1 multiplication and
in this line the function is invoked by itself with the input of size n-1, hence there is bn-1 number of multiplications at this line.
∴ The total number of multiplications : bn = bn-1 + 1
Answer : The recurrence relation and an initial condition for the sequence {bn} is bn = bn-1 + 1 with b0=0 ■
[Final OK by SGLee] Ch 7, P424, P.10 solved by 칭기즈 Finalized by 김영철
Solution
0. In problem 9 we derived a recurrence relation and initial
condition as below :
bn=bn-1+1
b0=0
1. Thus,
For n=1 :
b1= b1-1+1=b0+1=0+1=1
For n=2 :
b2= b2-1+1=b1+1=1+1=2
For n=3:
b3= b3-1+1=b2+1=2+1=3
2. So
we can find out that
b1=1
b2=2
b3=3
Solution. b1=1 , b2=2 , b3=3 ■
Comment: The problem is very straightforward which requires put 1 , 2 and 3 into equation in order to compute the first, the second and the third element.
[Final OK by SGLee] Ch 7, P424, P.11 solved by 칭기즈 Finalized by 김영철
Problem
Solution
0. In Exercise problem 9, we derived a recurrence relation and
initial condition.
--> bn = bn-1 + 1
--> b0 = 0
1. [Solve] Thus,
Let's solve by iteration :
--> bn = bn-1 + 1
= bn-2 + 1 + 1
= bn-3 + 1 + 1 + 1
2. If
we keep substitute like that, we will get
--> bn = ... = b0 + 1 + 1 + 1 + ... + 1
= 0 + n*1
= n
So we get bn = n
Solution : bn = n ■
Comment : The problem is a very good example which helps to understand how to solve recurrence relation by iteration. The idea is to keep substituting elements with their previous elements until we get the base element.
Problem 11, Ch.8, P.459, Chapter-Self Test
Solved by 강병훈 Date.2018.11.17
Revised by 칭기즈 Date.2018.11.17
Finalized by Muhammad Date 2018.11.23
Problem 11
Note:
A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once .
Solution:
Since there are seven vertices, a Hamiltonian cycle must have seven edges. Suppose that we could eliminate edges from the graph, leaving just a Hamiltonian cycle:
We would have to eliminate three edges at vertex b and one edge at vertex f. This leaves 10−4=6 edges,
thus it is not enough for a Hamiltonian cycle.
Conclusion:
Therefore, the graph does not have a Hamiltonian cycle. ■
Comment: The problem is very easy the key point of it is that A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once .
Ch. 8, Page 495, Problem № 12 (Chapter Self-Test), solved by 강병훈, revised by 칭기즈, finalized by 유가이 올렉산드르
Page 495, problem № 12 (Chapter Self-Test)
Show that the cycle (a, b, c, d, e, f, g, h, i, j, a) provides a solution to the traveling salesperson problem for the graph shown.
Solution
In a minimum-weight Hamiltonian cycle, every vertex must have degree 2.
1) Edges (a, b), (a, j), (j, i), (i, h), (g, f),(f, e), and (e, d) must be included.
2) Cannot include edge (b, h) or we will complete
a cycle. This implies that we must include edges (h, g)and (b,
c).
3) Vertex g now has degree 2, we cannot include edge (c, g) or (g, d).
4) Therefore we must include (c, d).
Conclusion:
This is a Hamiltonian cycle and the argument shows that it is unique. So, it's minimal. ■
Comment: The problem is very easy to understand. The idea is that in a minimum-weight Hamiltonian cycle, every vertex must have degree 2.
[Final OK by TA] Chapter 8 Page 495 Problem22 solved by 전종문 finalized by 칭키즈Problem
In Exercises 21 and 22, determine whether the graphs G1 and G2 are isomorphic. Prove your answer.
22.
Definition:
Definition 6.1 |
|
|
Proof
The adjacency matrix of graph G1 relative to vertex ordering v1, v2, v3, v4, v5, v6
is equal to the adjacency matrix of graph G2 relative to the vertex ordering w1, w2, w3, w4, w5, w6
Conclusion:
∴G1 and G2 are isomorphic. ■
Comment:
This problem is quite straightforward but very useful to get better understanding of Chapter 8, especially isomorphic graphs. The idea of the problem is to check if orderings V1,V2,V3,V4,V5,V6 and W3,W6,W2,W5,W1,W4 make equal adjacency matrices.
[Final OK by TA] CH. 8, Page 496, Problem № 27 (Chapter Self-Test), solved by 전종문, revised by 김영철, finalized by 칭기즈, re-finalized by 유가이 올렉산드르
Page 496, problem № 27 (Chapter Self-Test)
Show that any simple, connected graph with 31 edges and 12 vertices is not plane.
Solution
Euler's formula is v - e + f = 2.
The sum of the degrees of the regions is equal to twice the number of edges, but each region must have degree ≥ 3.
So, we have
2e ≥ 3f.
Thus,
2e ≥ 3(2 - v + e)
Therefore,
e ≤ 3v - 6
31 ≤ 3(12) - 6 = 30 is false.
Sage Code:
g = graphs.CompleteBipartiteGraph(31,12)
g.show()
g.is_planar()
Practical Image:
Conclusion:
So, 31 edges and 12 vertices is not planar. ■
Comment: The problem is quite easy where the key point is that the sum of the degrees of the regions is equal to twice the number of edges, but each region must have degree ≥ 3.
[Final OK by TA] chapter 8 problem 29 by 강병훈 Finilized by 칭기즈
Problem
Scheme:
Here is an image of four cubes just for convinience:
Note:
Draw one vertex for each color and an edge between two vertices if those colors are opposite faces on the cube.
Solution
We will name the vertices as R, G, W and B. The edges will be named as 1, 2, 3 and 4 depending on which cube they come from.
Keeping these two points in mind, we will have the following:
1. Three edges labeled (1) can be drawn between vertices {B,G}, {G, R}, {G, B}. These edges come from the first cube.
2. Similarly three edges labeled (2) can be drawn between vertices {R, B}, {G, B}, {W, W}. These edges come from the second cube.
3. Similarly three edges labeled (3) can be drawn between vertices {R, W}, {B, R}, {W, G}. These edges come from the third cube.
4. Similarly three edges labeled (4) can be drawn between vertices {W, B}, {W, R}, {R, B}. These edges come from the fourth cube.
5. Below is the corresponding graph:
■
Comment:
This problem is very easy but useful to understand the concept of graph theory. The key idea is to represent cubes by graph by drawing edges between two vertices if those colors are opposite faces on the cube.
Solved By 오동찬, Date: 2018.11.17
Finilized by 칭기즈Date: 2018.11.17
re-finilized by 김정주 date:2018.11.22
Problem 31
Find all subgraphs of the graph of Exercise 29 satisfying properties (8,1) and (8,2).
*Graph of Exercise 29
Definition:
Definition 2.8 |
|
|
Property
■ Each vertex should have degree 2. (8.8.1)
■ Each cube should be represented by an edge exactly once in each graph. (8.8.2)
Solution
There are total six graphs.
I will denote as Gn (n= 1,2,3,4,5,6).
■
Comment:
This problem is a good exercise that helps to get better understanding of subgraphs where the idea is to from a subset of the vertices of the graph and all of the edges connecting pairs of vertices in that subset.
Solved by 전종문 Date:2018.11.19
Revised and Finilized by 칭기즈 Date:2018.11.20
Problem
2.Write a program that determines whether a graph contains an Euler cycle.
Theory:
Theorem 2.18 |
|
|
Code C:
#include
int graph[50][2], answer[50];
int main()
{
int i=0, count= 0;
printf("Input the graph (v1,v2): \n");
printf("When you are done entering graph, input -1 -1\n");
while (1) {
int v1, v2;
scanf("%d %d", &v1, &v2);
if (v1 == -1 && v2 == -1) { break; }
graph[i][0] = v1;
graph[i][1] = v2;
i++;
}
for (int n = 0; n < i; n++) {
answer[graph[n][0]]++;
answer[graph[n][1]]++;
}
for (int n = 0; n < i; n++) {
if (answer[n] % 2 == 0) { count++; }
}
if (count == i) { printf("Euler cycle"); }
else{ printf("No Euler cycle"); }
return 0;
}
Note:
To check if a graph has a Euler cycle we need to use function is_eulerian() which will return True or Flase.
Not eulerian_circuit() because it will make unnsecesary for this case computations.
This is sage code:
# Euler cycle
G = Graph([(1,2),(1,3),(1,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,6),(4,5),(4,6),(4,7),(5,7)])
G.show()
G.is_eulerian()
Practical image:
Comment: Euler cycle은 모든 점이 짝수개의 연결을 가진다는 점을 이용하여 코드를 짜 보았다.
Comment: The problem is very easy. The key idea is that we should check whether every vertex has an even degree.
Solved by 전종문 Date:2018.11.19
Finilized by 칭기즈 Date:2018.11.23
[Finilized] Chapter 8 Page 495 Computer Exercise 3 by 칭기즈
Problem
3.Write a program that finds an Euler cycle in a connected graph in which all vertices have even degree.
Code C:
#include
int graph[50][2], answer[50];
int main()
{
int i=0, count= 0;
printf("Input the Euler cycle graph (v1,v2): \n");
printf("When you are done entering graph, input -1 -1\n");
while (1) {
int v1, v2;
scanf("%d %d", &v1, &v2);
if (v1 == -1 && v2 == -1) { break; }
graph[i][0] = v1;
graph[i][1] = v2;
i++;
}
for (int n = 0; n < i; n++) {
answer[graph[n][0]]++;
answer[graph[n][1]]++;
}
for (int n = 0; n < i; n++) {
if (answer[n] % 2 == 0) { count++; }
}
if (count == i) { printf("All vertices have even degree"); }
else{ printf("Not all vertices have even degree"); }
return 0;
}
Result
Example:
This is sage code:
G = Graph([(1,2),(1,3),(1,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,6),(4,5),(4,6),(4,7),(5,7)])
G.show()
if G.is_eulerian()==True:
print "All vertices have even degree"
else:
print "Not all vertices have even degree"
Example:
Comment: 이 문제의 코드를 짜고 예시를 돌려보면서 Euler cycle는 모든 점이 짝수개의 연결을 가진다는 점을 알아보았다.
Comment(Chingis): This problem is useful to get better understanding of graph theory, which is chapter 8. The idea is that there is no Euler cycle in the graph providing the number of edges incident on a certain vertex is odd.
Solved by 김정주 2018.11.21
Finilized by 칭기즈 Date:22.11.2018
Problem
Theorem:
Definition 1.11 |
|
A graph is bipartite if there exist subsets and of , each edge in is incident on one vertex in and one vertex in . |
Solution
Python code:
import queue as Queue
q=Queue.Queue()
graph={0:[4,2,1],1:[5,3,0],2:[6,0],3:[1],4:[5,0],5:[4,1],6:[2]}
visit=[]
bi=[]
for i in range(0,len(graph)):
visit.append(0)
bi.append(0)
##initial insert 1. and as 1
q.put(0)
bi[0]=1
while q.qsize()>0:
now=q.get()
visit[now]=1
nex=graph[now]
for i in nex:
if bi[i]==0:
bi[i]=bi[now]*-1
elif bi[i]==bi[now]:
print("it is not bipartite")
exit()
if visit[i]==0:
q.put(i)
print("it is bipartite")
print("A : ",end='')
for i in range(0,len(graph)):
if bi[i]==1:
print(i,end=" ")
print('')
print("B : ",end='')
for i in range(0,len(graph)):
if bi[i]==-1:
print(i,end=" ")
result:
Sage code:
G=Graph({0:[4,2,1],1:[5,3,0],2:[6,0],3:[1],4:[5,0],5:[4,1],6:[2]})
print G.is_bipartite()
G.show()
E=Set([])
A=[]
B=[]
A.append(0)
if G.is_bipartite()==True:
for i in range(1,len(G)):
check=0
for j in range(len(A)):
if Set(G[i]).intersection(Set(G[A[j]]))==E:
check=check+1
if check!=len(A):
A.append(i)
print A
for i in range(len(G)):
check=0
for j in range(len(A)):
if i==A[j]:
check=1
if check==0:
B.append(i)
print B
Practical image:
comment:
queue is a appropriate data structure to search every vertex.
i made visited check array and checking bipartite array.
initially start point 0 is bipartite 1.
if some vertex near by 0, those bipartite are -1.
if near vertex has same bipartite, that graph is not bipartite.
finally print the vertex followed same bipartite
[Finalized] Ch 9, Exercise21 오동찬/전종문/김영철/칭기즈
Final OK by TA Date:2018.11.30
Problem
Encode the following words using the given Huffman code.
(Nod decoding, it is encoding) --> "PENNED
Solution
1. First we have to separate the string into independent words :
PENNED --> P / E / N / N / E / D
2. Next we have to determine the binary numbers to go through to get to each letter above .
As you can see in the picture above, the numbers to go through to get to each word are like below :
P = 0110
E = 00
N = 010
N = 010
E = 00
D = 01111
3. So to sum up, it is P - E - N - N - E - D = 0110 - 00 - 010 - 010 - 00 - 01111
= 0110000100100001111
Conclusion:
4. Therefore, the answer is 0110000100100001111. ■
Comment: The problem is very easy to understand. The idea is split the word into characters and follow the path in the picture provided in order to get encoded character.
Ch 9, Exercise 5 by 김승연 칭기즈
Problem
Use DFS with vertices order ’hfdbgeca’ to find spanning tree of graph G in Figure 9.3.1
Algorithm:
http://matrix.skku.ac.kr/2018-DM/DM-Ch-9-Lab.html
Solution
By given vertices string order ’hfdbgeca’, set a first vertex, h as root.
I) connected with h : f
II) connected with f : d ,e
As given problem's order, we connect f to d.
III) connected with d : c , b
Same reason above, connect d to b
IV) connected with b : a , g
In the same way, connect b to g
V) connected with g : e , a
Connect g to e
VI) connected with e : c , f
If we connect e to f , it will cause cycle.
So, we have to link e to c.
VII) connected with c : d , a
because link c with d cause cycle, connect c to a.
Now we can watch all vertices are connected.
∴ picture at 'VII' is spanning tree of graph G
Comment:
The problem is quite easy but very useful to get better understanding of spanning trees. The key idea of the problem is that we take h as a root and when we visit new vertex select the first one in the order.
Articles and Opinions I shared with my class
Midterm problem:
Integers s and t satisfying s*396+t*480= gcd(396,480) are s=17 and t= - 14
Prime factorizations:
480= 25 x 31 x 51
396=22 x 32 x 111
Definition:
.
Thus,
gcd(396,480)=22*31=12
Let's put -14 and 17 intot t and s respectively:
396*17+(-14*480)=6 732-6 720 = 12 = gcd(396,480) => True
Conclusion:
The statement is True
Comment: There was a minor mistake in one of the midterm problems so I shared my opinion concerning it. The idea is that gcd(a,b) can be found using the prime factorizations. Formula:
.
Subject: Catalan numbers
As a student of Software engineering department, I feel that Catalan numbers can be effictively applied in the programming as well.
To start with, I want to emphasize that Catalan numbers belong to enumerative combinatorics, which is an area of combinatorics that deals with the number of ways that certain patterns can be formed.
To give some simple examples :
We can use Catalan numbers to:
1. The number of binary search trees that can be formed using 'n' nodes is the nth Catalan number.
2.
The number of ways that a convex polygon of n+2 sides,
can be cut into 2 or more triangles by joining any 2 edges is the
nth Catalan number.
3. The closed solution to the number of possible parantheses matching given 'n' pairs is the nth Catalan number.
But I think that one of the most important applications of Catalan numbers in programming is determining expected running time of a certain program.
Let me just give you a simple example where we are going to count how many times you go through the inner loop
Consider the following code:
Python code:
count=0
for i in range(2):
for j in range(i,3):
for k in range(j,4):
for h in range(k,5):
count=count+1
print(count)
The output:
Notice that in this case n is 5
Thus, calculating Catalan number for n=5
Python code:
import functools
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))
Output:
So Ctalan number for n=5 is 42.
Hence it is possible to predict the running time of an algorithm.
Subject: Bernard Taschi theorem
Actually, I took a look at the theory again and noticed one interesting thing for me.
Consider this example:
Let X be a set of all prime numbers {2,3,5,7....}
Hence, the cardinality of the set X is an infinitely huge number because we can assaign all natural numbers to each prime number.
Let Y be a set of all composite numbers {4,6,8...}
Hence, the cardinality of the set Y is an infinitely huge number because we can assaign all natural numbers to each composite number.
Now look at this theorem too:
Theorem 1.12 |
Inclusion-Exclusion Principle for Two Sets |
If and are finite sets, then . |
The intersection of X and Y is obviously an empty set.
But the union is the set of all numbers startig from 2. Let's take it as U={2,3,4,5.....}
Hence, the cardinality of the set U is also an infinitely huge number because we can assaign all natural numbers to each number in the set U.
Thus ,
|U|= |X|
|U|= |Y|
X≠Y
and by theorem:
|U|=|X|+|Y|
Subject:Combinatorics
Suppose that there are piles of red, blue and green balls (=3) and that each pile contains at least eight (8=) balls.
(a) In how many ways can select eight balls?
Discussion:
So, let's imagine what kind of possible combination we can have
RRRRGGBB
RRGGGBBB
RRRGBBBB
BBBBBBBB
.....................
Obviously, the order does not matter in this case, we will list all of our selections in the same order: R then G then B( red,green,blue)
Let's imagine that we don't want them to be mixed, so we need to separate them:
RRRR|GG|BB
RR|GGG|BBB
RRR|G|BBBB
| |BBBBBBBB
Now substitute all the R G and B with "-", for example, because we don't need to label them if we know the order.
We get:
- - - - | - - | - -
- - | - - - | - - -
- - - | - | - - - -
| | - - - - - - - -
Now , we get 10 slots and the question becomes easier: in how many ways we can put 2 "|" signs.
As we know it is C(10,2)
...or equivalently C(10 , 8) ways to place ball selections.
Solution:
Hence
By Theorem 3.5, the number of ways of selecting eight balls is (공을 3개 상자에 8개 담는 방법) (=3, 8=)
.
Subject: De Morgan's law
De Morgan's law is introduced in middle school mathematics, and I think it is a familiar rule for all students. It is also not difficult for students who are new to logic / set theory because their contents are not difficult and they can be frequently accessed. In other words, it is practical enough to be frequently encountered, and it is often difficult to explain unless the de Morgan's law is used. Often we often take De Morgan's laws, but its practicality and convenience should always be kept in mind.
I just put it into Google translator so there may be some mistakes but the meaning is not distorted.
Actually De Morgan's laws are widely used in programming in order to reduce the time needed to execute the code, hence the efficiency is increased.
Let me show you a good example of it. Consider the following code:
Python code:
a=0
def my_function1():
return 1
def my_function():
global a
a=1
return 0
if (not(my_function1() and my_function())):
print("hello world!")
print(a)
The output:
Discussion:
In this example both my_function1() and my_function() are functions, a named section of a program that performs a specific task.
Meanwhile "a" is a global variable which is used in this example in order to see how computer uses De Morgan's law.
Now consider this statement:
if (not(my_function1() and my_function())):
So, just imagine that A is
A=my_function1()
and B is
B=my_function()
Hence, the statement theoretically becomes
if ¬(AB)
Now we need do find numerical values of A and B
A=my_function1() is result of what my_function1() returns, which is 1.
B=my_function() is result of what my_function() returns, which is 0.
Moreover, global variable changes in value from 0 to 1,
global a
a=1
which shows that the function was executed.
Now
A=1 B=0
AB=0
¬(AB)=1
Question:
So you may think now that computer in the condition
if (not(my_function1() and my_function())):
executes my_function1() to get the value as we did and then the same with my_function().
But in practice computer does not do so, that is why I said theoretically.
Proof:
Consider the following Python code:
a=0
def my_function1():
return 0
def my_function():
global a
a=1
return 0
if (not(my_function1() and my_function())):
print("hello world!")
print(a)
The output:
Now
A=my_function1() becomes 0
B=0
But as you may notice the value of the variable "a" did not change! Why??
Simply, because when the code is compiled, computer "translates" the statement
if (not(my_function1() and my_function())):
into something like
if (not(my_function1()) or not(my_function())):
using De Morgan's law
¬(AB)=¬A ∨¬B
Hence it computes initially only the value obtained from A=my_function1()
and if it satisfies the condition (if (¬A ∨¬B) =1)
computer just ignores the second one because the value of B does not affect on the result in this case if A=1.
That is why computer did not execute B= my_function() and the value of variable "a" did not change. Why?
Because it helps to save time of execution and increase ifficiency.■
Subject: Fibonacci numbers
Consider the following sequence of Fibonacci numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, ...
If we take any number from the list, for example 5, and compute the square of it:
5x5=25
Now take two adjacent numbers , that are to the left and to the right side of 5 in this case
So 3 and 8 and if we multply them
3x8 =24
we get 24
24+1=5x5
Now take a look at this pattern
The square of any number in The Fibonacci Sequence equals to the multiplication of adjacent numbers plus or minus 1.
Ex. 8*8= 13*5 -1
2*2=1*3+1
Interesting isn't it?
Now take a look at this:
Here is a square with the sides 8 and I divided it into different shapes with sides showed in the picture attached.
And rearrenged
to make a
rectangle with sides 13 and 5.
Now let's compute ares of the figures:
A(square)= 8*8=64
A(rectangle)=13*5=65
How is that possible?
Notice that 8 is the number from The Fibonacci Sequence
and 13 and 5 are numbers adjacent to 8!!
Does it mean that if we take any square with the sides value from The Fibonacci Sequence and rearrenge it so that the sides of rectangle are adjacent to the number of sequence we get larger of smaller area by 1?
Ex.
13*13= 21*8 +1
Area of square 13*13 is larger than the area of the rectangle 21*8 by 1.
Interesting, right?
However, the reality is a bit boring
The problem was
solved by noticing that points A B C D are not in the same straight line, hence they are vertexes of
a prallelogram, which has an area that equals to that "extra" 1.
Chapter 4. Algorithms |
|
Key term |
Input: algorithm has input values from a set Output: from each set of input an algorithm produces output from a set Sorting: putting elements into a list in which the elements are in specified order(increase or decreasing Best(or worst, average)-case-time: time needed to execute the algorithm among all inputs of size n(minimum or maximum) |
Definitions |
Algorithm: step-by-step method for performing a computation or for solving problem Big oh and Omega, Theta: Let f and g be functions with domain N {1,2,3,…}, Ǝ n ⋵Z+ f(n) =
O(g(n))
≡ f(n) is big oh of g(n) ≡ f(n) is of
order at most g(n) f(n) =
Ω(g(n)) ≡ f(n) is omega of g(n) ≡ f(n) is of
order at least g(n) f(n) =
Ω(g(n))
and
f(n) = O(g(n)). |
concepts |
binary search, bubble sort, insertion sort, randomized algorithm(rand function), matrix multiplication algorithm, Fibonacci sequence |
big-O notation
(definition)
Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). The notation is read, "f of n is big oh of g of n".
Formal Definition: f(n)
= O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤
cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and
must not depend on n.
Also known as O, asymptotic upper bound.
Ω
(definition)
Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = Ω (g(n)) means it is more than some constant multiple of g(n).
Formal Definition: f(n)
= Ω (g(n))
means there are positive constants c and k, such that 0 ≤ cg(n) ≤ f(n) for all
n ≥ k. The values of c and k must be fixed for the function f and must not
depend on n.
Also known as asymptotically tight bound, theta.
Θ
(definition)
Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = Θ (g(n)) means it is within a constant multiple of g(n). The equation is read, "f of n is theta g of n".
Formal Definition: f(n)
= Θ (g(n))
means there are positive constants c1, c2, and k, such
that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ k. The values
of c1, c2, and k must be fixed for the function f and
must not depend on n.
From,
https://xlinux.nist.gov/dads/HTML/theta.html
Here is the basic idea behind recursive algorithms:
To solve a problem, solve a subproblem that is a smaller instance of the same problem, and then use the solution to that smaller instance to solve the original problem.
When computing n!, we solved the problem of computing n! (the original problem) by solving the subproblem of computing the factorial of a smaller number, that is, computing (n−1)! (the smaller instance of the same problem), and then using the solution to the subproblem to compute the value of n!.
In order for a recursive algorithm to work, the smaller subproblems must eventually arrive at the base case. When computing n!, the subproblems get smaller and smaller until we compute 0!. You must make sure that eventually, you hit the base case.
For example, what if we tried to compute the factorial of a negative number using our recursive method? To compute (−1)!, you would first try to compute (−2)!, so that you could multiply the result by -1. But to compute (−2)!, you would first try to compute (−3)!, so that you could multiply the result by −2. And then you would try to compute (−3)!, and so on. Sure, the numbers are getting smaller, but they're also getting farther and farther away from the base case of computing 0!. You would never get an answer.
Even if you can guarantee that the value of n is not negative, you can still get into trouble if you don't make the subproblems progressively smaller. Here's an example. Let's take the formula n!=n⋅(n−1)! and divide both sides by n, giving n!/n=(n−1)!. Let's make a new variable, mm, and set it equal to n+1. Since our formula applies to any positive number, let's substitute m for n, giving m!/m=(m−1)!. Since m=n+1, we now have (n+1)!/(n+1)=(n+1−1)!. Switching sides and noting that n+1−1=n gives us n!=(n+1)!/(n+1). This formula leads us to believe that you can compute n! by first computing (n+1)! and then dividing the result by n+1. But to compute (n+1)!, you would have to compute (n+2)!, then (n+3)!, and so on. You would never get to the base case of 0. Why not? Because each recursive subproblem asks you to compute the value of a larger number, not a smaller number. If n is positive, you would never hit the base case of 0.
We can distill the idea of recursion into two simple rules:
· Let's go back to the Russian dolls. Although they don't figure into any algorithms, you can see that each doll encloses all the smaller dolls (analogous to the recursive case), until the smallest doll that does not enclose any others (like the base case).
Source: https://www.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/properties-of-recursive-algorithms
Chapter 5. Introduction to Number Theor |
|
Key term |
Composite: the integer n > 1, that not prime. Binary (or octal, hexadecimal) number System: consists of 2 (or 8, 16) symbols. The system is based the base of the number System. Carry: carry is a digit that is transferred from one column of digits to another column of more significant digits. In computing, carrying is an important function of adder circuits. Euclidean Algorithm: it is the algorithm for finding the greatest common divisor of two integers. Fibonacci sequence: explanation is in ‘Theorems VII)’ Inverse Modulo: For n, Φ ⋵ Z, n >0 and Φ> 1 such that gcd (n,Φ) = 1. Find s ⋵ Z, 0<s<Φ such that ns mod Φ =1. s is the inverse of n mod Φ. |
Definitions |
Divisor: if n, d ⋵ Z with d≠0. We say d divides n if ∃q ⋵Z, n = dq (d ∣ n) Then we say d is a divisor (or factor) of n, q is a quotient. Prime: An integer n > 1 is prime if is only positive divisors are itself and 1. An integer n > 1 is called composite if n is not prime. |
concepts |
Prime factorization: (ex ∣ 30 = 2 ∙ 3 ∙ 5) Transitivity of Divisibility: (for all integers a, b, c, if a ∣ b and b ∣ c then a ∣ c.) Max(a, b): it is defined mathematically max(a, b)=1/2(a + b +|a-b|) Converting an integer from Base n to Base m algorithm Adding binary numbers Binary representation of the exponent Recursive Euclidean Algorithm |
Theorems |
I) Let m, n and d are integers. a) If d ∣ m and d ∣ n ⇒ d ∣ (m + n). b) If d ∣ m and d ∣ n ⇒ d ∣ (m - n). c) If d ∣ m ⇒ d ∣ m n. II) A positive integer n > 1 is Composite ⇔ n has a Divisor d satisfying 2 ≤ D ≤ √(n). III) Fundamental Theorem of Arithmetic. Any integer greater than 1 can be written as a product if primes. Moreover, if the primes are written in non decreasing order, the factorization is unique. IV) There are infinitely many prime numbers. V) Let m and n be integers (m, n ≠0). A common divisor of m, n is an integer that divides both m and n. The greatest common divisor, written gcd(m, n), is the largest common divisor of m, n. VI) Let m, n are positive integers. A common multiple of m, n is an integer that is divisible by both m, n. lcm (m, n) is the least common multiple. lcm (m, n) is the smallest positive common multiple of m, n. VII) Suppose that the pair a, b, a>b, requires n ≥ 1 modulus operations when input to the Euclidean algorithm. Then a ≥ fn+2 and b ≥ fn+1, where {fn} denotes the Fibonacci sequence. VIII) Bézout's theorem If a and b ⋵ Z+ , then there exist integers s, z such that gcd (a, b) = sa + tb |
Converting between different number bases is actually fairly simple, but the thinking behind it can seem a bit confusing at first. And while the topic of different bases may seem somewhat pointless to you, the rise of computers and computer graphics has increased the need for knowledge of how to work with different (non-decimal) base systems, particularly binary systems (ones and zeroes) and hexadecimal systems (the numbers zero through nine, followed by the letters A through F).
In our customary base-ten system, we have digits for the numbers zero through nine. We do not have a single-digit numeral for "ten". (The Romans did, in their character "X".) Yes, we write "10", but this stands for "1 ten and 0ones". This is two digits; we have no single solitary digit that stands for "ten".
Instead, when we need to count to one more than nine, we zero out the ones column and add one to the tens column. When we get too big in the tens column -- when we need one more than nine tens and nine ones ("99"), we zero out the tens and ones columns, and add one to the ten-times-ten, or hundreds, column. The next column is the ten-times-ten-times-ten, or thousands, column. And so forth, with each bigger column being ten times larger than the one before. We place digits in each column, telling us how many copies of that power of ten we need.
The only reason base-ten math seems "natural" and the other bases don't is that you've been doing base-ten since you were a child. And (nearly) every civilization has used base-ten math probably for the simple reason that we have ten fingers. If instead we lived in a cartoon world, where we would have only four fingers on each hand (count them next time you're watching TV or reading the comics), then the "natural" base system would likely have been base-eight, or "octal".
Source: https://www.purplemath.com/modules/numbbase.htm
Let's look at base-two, or binary, numbers. How would you write, for instance, 1210 ("twelve, base ten") as a binary number? You would have to convert to base-two columns, the analogue of base-ten columns. In base ten, you have columns or "places" for 100 = 1, 101 = 10, 102 = 100, 103 = 1000, and so forth. Similarly in base two, you have columns or "places" for 20 = 1, 21 = 2, 22 = 4, 23 = 8, 24 = 16, and so forth.
The first column in base-two math is the units column. But only "0" or "1" can go in the units column. When you get to "two", you find that there is no single solitary digit that stands for "two" in base-two math. Instead, you put a "1" in the twos column and a "0" in the units column, indicating "1 two and 0 ones". The base-ten "two" (210) is written in binary as 102.
A "three" in base two is actually "1 two and 1 one", so it is written as 112. "Four" is actually two-times-two, so we zero out the twos column and the units column, and put a "1" in the fours column; 410 is written in binary form as 1002. Here is a listing of the first few numbers:
decimal |
binary |
|
0 |
0 |
0 ones |
1 |
1 |
1 one |
2 |
10 |
1 two and zero ones |
3 |
11 |
1 two and 1 one |
4 |
100 |
1 four, 0 twos, and 0 ones |
5 |
101 |
1 four, 0 twos, and 1 one |
6 |
110 |
1 four, 1 two, and 0 ones |
7 |
111 |
1 four, 1 two, and 1 one |
8 |
1000 |
1 eight, 0 fours, 0 twos, and 0 ones |
9 |
1001 |
1 eight, 0 fours, 0 twos, and 1 ones |
10 |
1010 |
1 eight, 0 fours, 1 two, and 0 ones |
11 |
1011 |
1 eight, 0 fours, 1 two, and 1 one |
12 |
1100 |
1 eight, 1 four, 0 twos, and 0 ones |
13 |
1101 |
1 eight, 1 four, 0 twos, and 1 one |
14 |
1110 |
1 eight, 1 four, 1 two, and 0 ones |
15 |
1111 |
1 eight, 1 four, 1 two, and 1 one |
16 |
10000 |
1 sixteen, 0 eights, 0 fours, 0 twos, and 0 ones |
Given three integers a,b,c, can you write c in the form
c=ax+by
for integers x and y? Can there be more than one solution? Can you find them all? Before answering this, let us answer a seemingly unrelated question:
How do you find the greatest common divisor (gcd) of two integers a,b?
We denote the greatest common divisor of aa and bb by gcd(a,b), or sometimes even just (a,b). If (a,b)=1 we say aa and bb are coprime.
The obvious answer is to list all the divisors aa and b, and look for the greatest one they have in common. However, this requires a and b to be factorized, and no one knows how to do this efficiently.
Amazingly, a few simple observations lead to a far superior method: Euclid’s algorithm, or the Euclidean algorithm. First, if d divides a and d divides b, then d divides their sum. Similarly, d must also divide their difference, a - b, where aa is the larger of the two. But this means we’ve shrunk the original problem: now we just need to find gcd(a,a−b). We can repeat until we reach a trivial case.
Hence we can find gcd(a,b) by doing something that most people learn in primary school: division and remainder. We give an example and leave the proof of the general case to the reader.
Suppose we wish to compute gcd(27,33). First, we divide the bigger one by the smaller one:
33=1×27+6
Thus gcd(33,27)=gcd(27,6). Repeating this trick:
27=4×6+3
and we see gcd(27,6)=gcd(6,3). Lastly,
6=2×3+0
So since 6 is a perfect multiple of 3,gcd(6,3)=3, and we have found that gcd(33,27)=3.
This algorithm does not require factorizing numbers, and is fast. We obtain a crude bound for the number of steps required by observing that if we divide aa by bb to get a=bq+r, and r>b/2, then in the next step we get a remainder r′≤b/2. Thus every two steps, the numbers shrink by at least one bit.
The above equations actually reveal more than the gcd of two numbers. We can use them to find integers m,nm,n such that
3=33m+27n
First rearrange all the equations so that the remainders are the subjects:
6=33−1×27
3=27−4×6
Then we start from the last equation, and substitute the next equation into it:
3=27−4×(33−1×27)=(−4)×33+5×27)
And we are done: m=−4,n=5.
If there were more equations, we would repeat until we have used them all to find m and n.
Thus in general, given integers a and b, let d=gcd(a,b). Then we can find integer mm and n such that
d=ma+nb
using the extended Euclidean algorithm.
Team Project
Team № 3
(칭기즈, 유가이 올렉산드르, 김승연, 권재연, 이상민)
Solution, revision and finalization in Chapter 5
Collected: 유가이 올렉산드르, 칭기즈
Typed: 유가이 올렉산드르, 김승연, 칭기즈
Comments: 김승연, 칭기즈
Involved in problem-solving: 유가이 올렉산드르, 권재연, 칭기즈
Chapter 5
[Final OK by SGLee] Ch. 5, Page 300, Problem № 2, solved by AYSU OZGUNEKIM, Revised by 김주형, Finalized by 유가이 올렉산드르, Re-Finalized by 모하메드
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.
Algoruthm1.8 |
Testing Whether an Integer Is Prime |
This algorithm determines whether the integer is prime. If is prime, the algorithm returns . If is composite, the algorithm returns a divisor satisfying . To test whether divides , the algorithm checks whether the remainder when is divided by , is zero. 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 and and stores the sum in . Input: , , Output: binary_addition(, , , ) carry for to
|
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 전종문
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 김희성
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 김희성
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 서명원, 정호진
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.
Team Project
Team № 3
(칭기즈, 유가이 올렉산드르, 김승영, 권재연, 이상민)
Typed: 유가이 올렉산드르, 칭기즈
Involved in problem-solving: 유가이 올렉산드르, 칭기즈
The reason to do this project
In mathematics and computer science, a binary number is a number expressed in the base-2 numeral system or binary numeral system, which used only two symbols: typically 0 and 1. The base-2 numeral system is a positional notation with a radix of 2. Each digit is referred to as a bit. Because of its straightforward implementation in digital electronic circuitry using logic gates, the binary system is used by almost all modern computers and computer-based devices. The expediency of using a binary system in digital electronics is explained by the fact that the basic element of any electronic circuit has two states that can be assigned values 0 and 1. Also, the binary system is used in digital devices because its simplicity and meets the require:
2. The less values exist in the system, the easier it’s to manufacture individual elements operating with these values. In particular, two digits of the binary numbers system can be easily represented by many physical phenomena: there is a current (current is greater than the threshold value) – there is no current (current is lower than the threshold value), magnetic induction is greater than the threshold value or not (magnetic induction is less than the threshold value) etc.
3. The smaller number of states of an element, the higher the noise immunity and the faster it can work. For example, to encode three states through voltage of current or magnetic field induction you need to enter two threshold values and two comparators.
There are three basic operation with binary numbers: addition, subtraction and multiplication.
However, as time has shown, the most frequently used operation with binary numbers in programming is addition. The addition of binary numbers is the initial and most important step in the study of operations with binary numbers. Therefore, in our team project we decided, using the example of problem solving, to show simple and most interesting methods of adding binary numbers. We also decided to show how recurrence relations can facilitate the process of adding binary numbers in programming.
Problem
Develop and analysis of various methods of addition of binary numbers. Also, create code on Python and Sage programming languages for addition of binary numbers. In addition, the analysis of the effect of the Recurrence Relation on Python and Sage codes. Example: First we take two arbitrary numbers, for example 11 and 27. Then we translate these two numbers into binary number system. To do this, lets use the table below:
24 |
23 |
22 |
21 |
20 |
16 |
8 |
4 |
2 |
1 |
In the case of the number 11:
24 |
23 |
22 |
21 |
20 |
16 |
8 |
4 |
2 |
1 |
0 |
1 |
0 |
1 |
1 |
So, the number 11 in binary looks like 01011
In the case of the number 27:
24 |
23 |
22 |
21 |
20 |
16 |
8 |
4 |
2 |
1 |
1 |
1 |
0 |
1 |
1 |
So, the number 27 in binary looks like 11011
Attacking the Problem
In developing an algorithm, a good way to start is to ask the question. “How would I solve this problem by my hand?” Now after we know how to translate ordinary numbers into binary numbers, we will learn how to add them. Binary adding is very similar to the usual decimal addition, except that it carries on a value of 2 instead of the value of 10. So, the same method that we use to add decimal numbers can be used to add binary numbers; however, we must replace the decimal addition table with the binary addition table
0 + 0 = 0 |
0 + 1 = 1 |
1 + 0 = 1 |
1 + 1 = 10 (which is 0 carry 1) |
For example, let’s add binary numbers 01011 and 11011
We write the problem as
As in decimal addition, we begin from the right, adding 1 and 1. This sum is 102; thus we write 0 and carry 1. At this point the computation is
Next, we add 1 and 1 and 1, which is 112. We write 1 and carry 1. At this point, the computation is
Continuing is this way, we obtain
Now let’s translate the binary number 100110 into decimal
So, the binary number 100110 in decimal looks like 38
The addition problem of previous example, in decimal, is
25 |
24 |
23 |
22 |
21 |
20 |
32 |
16 |
8 |
4 |
2 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
We turn the method of previous example into an algorithm. If the number to add are bnbn-1…., at the iteration i > 0 the algorithm adds , , and the carry bit from the previous iteration. When adding three bits, say B1, B2, and B3, we obtain a two-bit binary number, say cb. For example, if we compute 1 + 0 + 1, the result is 102; in our notation, c = 1 and b = 0. By checking the various cases, we can verify that we can compute the binary sum B1 + B2 + B3 by first computing the sum in decimal and then recovering c and b from the formulas
b = (B1 + B2 + B3) mod 2,
c = .
Finding a solution
We begin writing pseudocode for the algorithm that computes the sum of binary numbers:
Input: , ,
Output:
binary_addition(, , , )
carry
for to
Discussion:
Before we start to analyze the code let’s convert the provided pseudocode into an actual python code:
import math
b=[int(x) for x in input().split()]
b1=[int(x) for x in input().split()]
carry=0
s='' //the sum will be printed in the form of text(string)
list1 = list(s) //temporary converting string into the list for the convenience
for i in range(len(b)):
b2 = b[len(b)-i-1] //when we add binary numbers we start adding last digits
c1 = b1[len(b)-i-1]
list1.append( str((b2+c1+carry)%2))
carry=math.floor((b2+c1+carry)/2) //calculation of carry
list1.append(str(carry))
s = ''.join(list1)
print(s[::-1]) //reverse string
Example:
The loop allows as to read every digit of two given binary numbers because the idea is to read every digit starting from the last one and ending with the first one.
for i in range(len(b)):
Considering that we use only one loop, keep in mind that two binary numbers should have the same size.In order to read the binary number from the end we use:
b2 = b[len(b)-i-1]
This line means that we assign (len(b)-i-1)-nth element of the sequence b, which is a binary number, to a variable b2 and the same for the second binary number.
The computation relies on:
list1.append( str((b2+c1+carry)%2))
So add the result of the sum of two digits and carry into the list, but initially carry is obviously 0.
Now we compute the value for carry to add it to the next computation.
carry=math.floor((b2+c1+carry)/2)
Now, let’s print the result:
s = ''.join(list1)
We “convert” the list into the text again
print(s[::-1])
But note that we did addition starting from the last digit and added it into the list using the same order, so we need to get reverse s.
After developing an algorithm, take a close look to see where it can be improved. Look at the parts that perform key computations to gain insight into how to enhance the algorithm.
Notice that in the line
b2 = b[len(b)-i-1]
Due to the loop it looks like we always call the previous element of the sequence. Thus, there is a possibility to use recursive function instead of the loop. Hence, we also see how close chapter 4 and 5 are connected with chapter 7, which is Recurrence Relation.
Here is our new improved code:
import math
def binary(b,b1,n,list2,carry):
if n==0: //basic step
list2.append(str(math.floor((b[n]+b1[n]+carry)/2)))
s = ''.join(list2)
print(s[::-1])
return
list2.append( str((b[n-1]+b1[n-1]+carry)%2))
carry=math.floor((b[n-1]+b1[n-1]+carry)/2)
binary(b,b1,n-1,list2,carry) //calling previous elements
b=[int(x) for x in input().split()]
b1=[int(x) for x in input().split()]
list2=[]
binary(b,b1,len(b),list2,0) //calling the function
Practice: https://repl.it/@ChinghisOinar/Team3DiscreteMath
Example:
To provide a recap, we tried to show you steps needed to develop a good algorithm using the example of addition of binary numbers. Moreover, we demonstrated the connection not only between chapter 4(Algorithms) and 5(Introduction to Number Theory) but also Chapter 7(Recurrence Relation).
Summary of Problem-Solving Techniques:
1. In developing an algorithm, a good way to start is to ask the question. “How would I solve this problem by my hand?”
2. In developing algorithm, initially take a simple method.
3. After developing an algorithm, take a close look to see where it can be improved. Look at the parts that perform key computations to gain insight into how to enhance the algorithm.
References:
[1] Paul E. Black, "Θ", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 24 February 2016. (accessed TODAY) Available from:
<URL> https://www.nist.gov/dads/HTML/theta.html
[2] “Properties of Recursive Algorithms.” Khan Academy, Khan Academy, 2014,
[3] Stapel, Elizabeth. “Number Bases: Introduction & Binary Numbers.” Purplemath, 2018,
<URL> www.purplemath.com/modules/numbbase.htm
[4] “Binary Number.” Wikipedia, Wikimedia Foundation, 30 Nov. 2018,
<URL> en.wikipedia.org/wiki/Binary_number
[5] wikiHow. “How to Add Binary Numbers.” WikiHow, WikiHow, 17 Oct. 2018,
<URL> https://www.wikihow.com/Subtract-Binary-Numbers
[6] Johnsonbaugh, Richard. Discrete Mathematics, Pearson, 2014, page 277-238
n After 'DM' Fall Final PBL (보고서를 마치고) (5점)
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.
Due to chapter 6 (Counting methods and the Pigeonhole Princeple) I am now able to calculate possible combinations or arrangements. Also, I now can solve recurrence relations wich is very important for software engineering students, as well as graph theory and trees. I think these classes were useful for me as a student of software engineering department. Admittedly, talking about the information I learnt from chapters we covered, I gained very useful and important knowledge, especially related to algorithms, proofs and theory of numbers, which I will use regularly in the future not only on Discrete Mathematics classes, but equally outside the classes as a student of software engineering department.
To provide a recap, this is my first experience in studying under that kind of system, hence it was slightly difficult to adapt. However, I am happy that I have an opportunity to experience it, since this is the first class I have ever had where every single student is involved in the process of learning and activity of everyone is important for every student as well since we help each other to understand the concept of the class quicker by solving or revising and finalizing others’ solutions. I like QnA section because it became a kind of medium where students can have a discussion on any problem and just simply make any inquiry. This system of learning motivates me to use various materials, such as articles on the Internet, Youtube videos, books and QnA responses, in the process of learning and to study before the lecture to fully grasp the idea of the lecture.
(The End of Ch 5)
Copyright @ 2018 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee
*This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2017R1D1A1B03035865).