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 equivalenceexistence 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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-9/PICFF.gif is the length of the simple path from the root to 설명: http://matrix.skku.ac.kr/2018-DM/Ch-9/PIC100.gif.

 

recurrence relation defines a sequence by giving the 설명: http://matrix.skku.ac.kr/2018-DM/Ch-7/PICED9F.gifth value in terms of its predecessors.

 

A cycle in a graph 설명: http://matrix.skku.ac.kr/2018-DM/Ch-8/PICB167.gif contains each vertex in 설명: http://matrix.skku.ac.kr/2018-DM/Ch-8/PICB168.gif exactly once, except for the starting and ending vertex that appears twice, a Hamiltonian cycle.

 

The symbol  설명: C:\Users\ww\AppData\Local\Microsoft\Windows\INetCache\Content.MSO\AC339814.tmp is a universal quantifier, which is interpreted as “for every”, “for any value of “ and etc.

 

The symbol 설명: C:\Users\ww\AppData\Local\Microsoft\Windows\INetCache\Content.MSO\492FFB42.tmpis 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 equivalenceexistence 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)               설명: http://matrix.skku.ac.kr/2018-DM/Ch-7/PICF28D.gif,                     설명: http://matrix.skku.ac.kr/2018-DM/Ch-7/PICF29E.gif

 (1.12)               설명: http://matrix.skku.ac.kr/2018-DM/Ch-7/PICF29F.gif,          설명: http://matrix.skku.ac.kr/2018-DM/Ch-7/PICF2B0.gif

                                                               설명: http://matrix.skku.ac.kr/2018-DM/Ch-7/PICF2B1.gif.

            The initial conditions

            (1.13)                    설명: http://matrix.skku.ac.kr/2018-DM/Ch-7/PICF2C1.gif,          설명: http://matrix.skku.ac.kr/2018-DM/Ch-7/PICF2E1.gif

            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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC9EE.gif is

설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC9EF.gif.

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): 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 ab.

 

 In each of these two cases, we should consider the two cases: b≤c and bc.

 

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 ab.

  if b≤c, then

    min{min{a,b},c}=min{b,c}=b=min{a,b}

                         =min{a,min{b,c}}.

  if bc, 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.

 

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jungju54/2018_09_30_151433.PNG
 

So, it will takes too much time.

 

Here is our new algorithm.

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jungju54/2018_09_30_151547.PNG

Start this algorithm with x is 1.

 

The following is my python code:

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jungju54/2018_09_30_151850.PNG
 

example:

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jungju54/2018_09_30_151943.PNG               

 

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:

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_30_213056.PNG

 

 

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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-2/PIC48E8.gif whose domain of discourse is the set of positive integers.

Suppose that

1. Basic Step                  설명: http://matrix.skku.ac.kr/2018-DM/Ch-2/PIC4918.gif is true.  

2. Inductive Step             If 설명: http://matrix.skku.ac.kr/2018-DM/Ch-2/PIC4958.gif is true, then 설명: http://matrix.skku.ac.kr/2018-DM/Ch-2/PIC4988.gif is true, for all 설명: http://matrix.skku.ac.kr/2018-DM/Ch-2/PIC49C7.gif.

 

Then 설명: http://matrix.skku.ac.kr/2018-DM/Ch-2/PIC49F7.gif is true for every positive integer 설명: http://matrix.skku.ac.kr/2018-DM/Ch-2/PIC4A27.gif. (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 .     □

 

 

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. pq
2. 
qr
3. 
pr

 

=> 

4. pr  ( 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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-1/PIC1FA8.gif and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-1/PIC1FA9.gif are proposition, the proposition

if 설명: http://matrix.skku.ac.kr/2018-DM/Ch-1/PIC1FBA.gif then 설명: http://matrix.skku.ac.kr/2018-DM/Ch-1/PIC1FBB.gif     설명: http://matrix.skku.ac.kr/2018-DM/Ch-1/PIC1FBC.gif

 is a conditional proposition.

설명: http://matrix.skku.ac.kr/2018-DM/Ch-1/PIC1FCD.gif  (설명: http://matrix.skku.ac.kr/2018-DM/Ch-1/PIC1FCE.gif) :   if 설명: http://matrix.skku.ac.kr/2018-DM/Ch-1/PIC1FDE.gif then 설명: http://matrix.skku.ac.kr/2018-DM/Ch-1/PIC1FDF.gif.

 Proposition 설명: http://matrix.skku.ac.kr/2018-DM/Ch-1/PIC1FF0.gif is hypothesis (or antecedent, 가설).

 Proposition 설명: http://matrix.skku.ac.kr/2018-DM/Ch-1/PIC1FF1.gif is conclusion (or consequent, 결론).

 

 

\​                  (p v q)-> r  =     ¬(p v q) v r

 

De Morgan's Law :  ¬(p v q)¬Λ ¬​​q

                                   ¬Λ ¬​​q v r

Distributive Law: (r v ¬p) Λ ( r v ¬​​q)

 

\​                  (r v ¬p) Λ ( r v ¬​​q)​  

 

 

Truth tables: 설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_24_113642.PNG


 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_24_115826.PNG 

 

\   (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:

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_30_184543.PNG

 


설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_30_184551.PNG

 

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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC10F7.gif and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1108.gif are in the domain of the sequence.

설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1109.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC110A.gif   설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC111A.gif   sequence 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC111B.gif 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")

 

 

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_30_184138.PNG
because second and third elements are 2

 

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_30_184205.PNG 

 

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")

 

 

 

 

 

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_30_184205.PNG

 

 

 

Comment: When we check whether the given sequence is increasing, we have to check  설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1109.gif.

 

But  if  such that    설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC110A.gif  is  not true, then we can tell it is not increasing.

 

So if we find    such that    설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC110A.gif  is  not true, we quickly exit and print "not increasing".

 

If our program execute all  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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC10F7.gif and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1108.gif are in the domain of the sequence.

설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC113F.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1140.gif   설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1151.gif   The sequence 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1152.gif is nondecreasing

 

increasing is replaced by nondecreasing : 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1176.gif is replaced by 설명: http://matrix.skku.ac.kr/2018-DM/Ch-3/PIC1177.gif)

 

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)

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_27_185222.PNG

Wrong example

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_27_185253.PNG 

 

 

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)}= {1,2,3,4}.

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_27_174829.PNG 

1. 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)  ​​(not antisymmetirc)

(1,2)  R (not transitive)

R = {(1,1), (2,2), (3,3), (4,4), (2,3), (3,2), (1,2)}

 

Digraph:

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_02_103545.PNG

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 xy

 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 + y

 

Solution

*   (1,1) R   R  is not reflexive

*   If  3|+y  then  3|+x    is symmetric

*   R  is symmetric but  is not reflexive   R is not antisymmetric

*   (1,2)R , (2,1)R   (1,1) R   R  is not transitive

*   R is antisymmetrictransitive 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)

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_27_201429.PNG
c)

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_27_201445.PNG

Discussion:

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_09_27_201550.PNG 

Solution :

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/gptntls/2018_09_29_135854.png

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

설명: 20181104_013540

Sourcehttp://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’.

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/kyc0816/2018_10_16_023425.jpg 

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), mt (indexed from 1 to n), n

Output: ​(​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+m1 and p1 · · · pm

while (ti+j1 == 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

 

설명: C:\Users\USER\AppData\Local\Microsoft\Windows\INetCache\Content.MSO\E7577520.tmp 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) 

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/kyc0816/2018_10_16_024506.jpg

 

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(설명: http://matrix.skku.ac.kr/2018-DM/Ch-4/PICD68E.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-4/PICD69F.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-4/PICD6A0.gif : integers)

 max 설명: http://matrix.skku.ac.kr/2018-DM/Ch-4/PICD6A1.gif

 for 설명: http://matrix.skku.ac.kr/2018-DM/Ch-4/PICD6B2.gif to 설명: http://matrix.skku.ac.kr/2018-DM/Ch-4/PICD6B3.gif

       if 설명: http://matrix.skku.ac.kr/2018-DM/Ch-4/PICD6C3.gif then 설명: http://matrix.skku.ac.kr/2018-DM/Ch-4/PICD6C4.gif

 return 설명: http://matrix.skku.ac.kr/2018-DM/Ch-4/PICD6D5.gif

                 or

설명: 그림입니다.
원본 그림의 이름: CLP000113980002.bmp
원본 그림의 크기: 가로 797pixel, 세로 365pixel

 

 

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

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_06_110113.PNG

 

 

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:

 설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_05_232341.PNG

 

 

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:

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_05_232534.PNG 

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:

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_03_170157.PNG

 

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:

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_03_170305.PNG

 

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:

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/kyc0816/2018_10_16_030507.jpg

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:

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/kyc0816/2018_10_16_025403.jpg

 

 

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 i​nfinite 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.

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/kyc0816/2018_10_16_023254.jpg

 

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:

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/kyc0816/2018_10_16_024728.jpg 

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 proceduralfunctional 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.

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/goldshakil/2018_10_08_141224.png

 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.

ex5*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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC789.gif is prime.

If 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC79A.gif is prime, the algorithm returns 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC79B.gif.

If 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC79C.gif is composite, the algorithm returns a divisor 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7AC.gif satisfying 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7AD.gif.

 To test whether 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7AE.gif divides 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7BF.gif, the algorithm checks whether the remainder when 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7C0.gif is divided by 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7C1.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7D2.gif 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7D3.gif is zero.

        Input: 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7D4.gif

      Output : 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7E4.gif

   설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7E5.gif

     설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7F6.gif

        설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7F7.gif

          설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7F8.gif

     설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC808.gif

     설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC809.gif

 

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)

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_12_002847.PNG

 

Case B)

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_12_002912.PNG

 

 

 

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

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/oleksandr/2018_10_13_175639.PNG 

 

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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3A2.gif and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3B3.gif and stores the sum in 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3B4.gif.

      Input:  설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3C4.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3C5.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3C6.gif

    Output:  설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3D7.gif

    binary_addition(설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3D8.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3D9.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3EA.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3EB.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3EC.gif

       carry 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3FC.gif

       for 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3FD.gif to 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3FE.gif 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD40F.gif

          설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD410.gif

          설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD421.gif

      설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD422.gif

       설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD432.gif

   설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD433.gif

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_12_011725.PNG

 

 

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

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/oleksandr/2018_10_13_184105.PNG

 

Source: http://matrix.s`kku.ac.kr/2018-DM/DM-Ch-5-Lab.html ■

 

 

Comment: 해당 코드는 binary numbers , 2진수의 덧셈을 논하고 있다.논리 회로 과목에서 배웠던  '4-bit Full adder' 구동방식의 공통점이 많아 언급 하지 않을 수가 없게 되었다.설명: 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 각각의 변수 값이 뜻하는 바도 원래의 알고리즘이 표현하려던 목적과도 동일하다. 세부적으로는 알고리즘이 제시한 식은 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD410.gif 이고 이는 i+1번째 자릿수의 결과 값은 3개의 변수의 연산으로부터 결정됨을 coding 것인데 logic gate 표현 식으로는’Ai Bi C(i-1) 배타적 논리합 연산으로 표현하고 다음 자릿수로 넘어갈 ‘Carry’   설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD421.gif 이라고 알고리즘이 제시하였으며 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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE39.gif using repeated squaring.

      Input:  설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE49.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE4A.gif

    Output:  설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE4B.gif

    exp_via_repeated_squaring(설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE5C.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE5D.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE5E.gif

       result 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE6F.gif

       설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE70.gif

       while (설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE71.gif)설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE81.gif

          if(설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE82.gif 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE83.gif)

            설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE94.gif*설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE95.gif

           설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE96.gif*설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAEA6.gif

          설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAEA7.gif

      설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAEB8.gif

     return result

   설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAEB9.gif

 

 

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)

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_12_013215.PNG
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

설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAEA7.gif

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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD647.gif, where 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD658.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD659.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD65A.gif and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD66A.gif are integers. Then 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD66B.gif.

 

                       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:

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/khsung0/2018_10_06_192854.PNG

 

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.

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jjm7jjm7/2018_10_07_164546.png

 Algorithm

 

 

Solution

The algorithm begins by setting result to 1 and x to a.

 Step 1) Since 

n = 30 > 0,

the body of the while loop executes.

 Step 2) Since 

n mod 2 is not equal to 1,

result is not modified.

 

 Step 3) x becomes a2, and n becomes 15.

Since 

n = 15 > 0

the body of the while loop executes 

 Step 4) Since 

n mod 2 is equal to 1,

result becomes 

result * x = 1 * a2 = a2.

 Step 5) x becomes a4, and n becomes 7.

 Since 

n = 7 > 0,

the body of the while loop executes

 

 Step 6) Since 

n mod 2 is equal to 1,

result becomes 

result * x = a2​​ * a4 = a6.

 Step 7) x becomes a8, and n becomes 3.

Since 

n = 3 > 0,

the body of the while loop executes.

 Step 8) Since 

n mod 2 is equal to 1,

 result becomes 

result * x = a6 * a8 = a14.

 

 

Step 9) x becomes a16, and n becomes 1.

Since 

n = 1 > 0,

the body of the while loop executes. 

 Step 10) Since 

n mod 2 is equal to 1,

result becomes 

result * x = a14 * a16 = a30.

x becomes a32, and n becomes 0.

 Step 11) Since n = 0, the while loop terminates.

 

 

Conclusion:

Therefore, the algorithm returns the result which is equal to a​30   ■

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/khsung0/2018_10_07_180210.PNG
 

 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 a​k 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. =30 =11110​(2) ​=22​​ * 2​4​ *​ 2​8​ * 2​16 return result = a​2​​ * a​4​ *​ a​8​ * a​16 = ​ a​30

So, we can see that 11110​(2) ​=22​​ * 2​4​ *​ 2​8​ * 2​16​ and result = a​2​​ * a​4​ *​ a​8​ * a​16 = ​ a​30​ 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. 

 

 

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/sglee/2018_10_11_143955.png

 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, 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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3C9.gif) number system,

Any integer form is

설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3D9.gif   설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3DA.gif   based 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3EB.gif

where each 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3EC.gif and each 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3ED.gif is one of the binary digits 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3FE.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3FF.gif

 

 Hexadecimal number system

Hexadecimal notation is based 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA803.gif.

Any integer form is

설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA813.gif   설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA824.gif   based 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA825.gif

where 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA836.gif and each 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA837.gif is one of the

hexadecimal digits 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA838.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA848.gif,설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA849.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA84A.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA85B.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA85C.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA85D.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA85E.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA86E.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA86F.gif, 10=설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA880.gif,  11=설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA881.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA882.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA893.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA894.gif, 15=설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA895.gif. 

 

Solution

 

 I) 430 = 256+128+32+8+4+2 

            = 1×28 + 1×2+ 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

=12          q =17      n =19 .

Compute z and φ.    

 

 

 

 

 Note:  

=p×q 

φ =(-1)(-1) 

 

 

Solution

 

We need to find  =p×q and φ =(-1)(-1)

 z =12×17 = 204

 φ =(12-1)(17-1)=11×16=176

 

 

Conclusion:

z​​ =204, φ =176    

 

 

Comment: I know about that φ() 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:

설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA223.png

 

 

Solution

 

Following the given theory about lcm(m,n), we gonna put the given data.

​                                    lcm(2*52*72*134, 74*132*17)​

= 2​max(1,0)​ * 5​max(2,0)​ * 7​max(2,4) * 13​max(4,2) * 17​max(0,1)

​                                    = 2 * 5​2​ * 7​4 * 13​4 * 17​   

Conclusion:

                 lcm(2*52*72*134, 74*132*17)​​=     2 * 5​2​ * 7​4 * 13​4 * 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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD647.gif, where 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD658.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD659.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD65A.gif and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD66A.gif are integers.

Then 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD66B.gif.

 BÉZOUT'S THEOREM:

If  and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD876.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD887.gif, then there 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD888.gif such that

설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD889.gif.

 

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 ×←⑤(inverse  )

12 = 60 - (84 - 60 × 1) × 2 (put in)

12 = 3 × 60 - 2× 84 ←⑥

12 =3 × (396-84×4)-2× 84 (putin)

12= 3 × 396 - 84× (12+2)

12=3× 396-14× 84   ←⑦

12=3× 396-14× (480-396×1) (putin)

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:

 

설명: 그림입니다.
원본 그림의 이름: CLP000113980015.bmp
원본 그림의 크기: 가로 804pixel, 세로 151pixel

 

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​·​13​2​) × (​5​2·13​2​​)

74·132·17 = (72​·​13​2​​) × (7​2·​17​)

5​2·13​2​​ and​ 7​2​·​17are 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·13​2​.  ■

 

 

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)

 

설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8053.png

 

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

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_28_231850.PNG

 

Sage code:

#permutation

elements = ['A', 'B', 'C', 'D', 'F']

perms = Arrangements(elements,len(elements))

print perms

print perms.cardinality()

print perms.list()

 

 

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/blueeye12/2018_10_31_110017.png

 

 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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC81CF.gif-permutation of a set of 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC81D0.gif distinct objects is

설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC81E0.gif,     설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC81F1.gif.

 


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 

 

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_28_234451.PNG 

 

This is sage code

# permutation

elements = ['A', 'B', 'C']

perms = Arrangements(elements, 3)

print perms

print perms.cardinality()

print perms.list()

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jjm7jjm7/2018_10_29_113755.png

Comment: The problem is very easy. The idea of arrangements(a,b) is to get the sequence and number of elements to be selected.

 

 


Fina OK by SGLee [TA] Ch 6, P.37*, Com Exs. 1, 
칭기즈,유가이김은율

  

Ch 6, P.37*, Com Exs. 1, Problem № 1 (Com. Exs.)

Write a program that generates all r-combinations of the elements {1...n}.

 

Theorem:

 

 Definition  2.15

 

 Given a set 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8300.gif containing 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8301.gif (distinct) elements,

 (a) An 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8312.gif-combination of 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8313.gif is an unordered selection of 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8314.gif-elements of 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8325.gif(i.e. an 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8326.gif         -element subset of 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8327.gif).

 (b) The number of 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8337.gif-combination of a set of 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8338.gif distinct elements is 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8339.gif or 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC834A.gif.

설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC834B.gif

 

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  

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_29_000018.PNG

 

 

Sage code:

#Combination

sequence = ['A', 'B', 'C']

doubles = Combinations(sequence, 2)

print doubles

print doubles.cardinality()

print doubles.list()
설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/blueeye12/2018_10_31_110440.png 

 

 

[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:

설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8624.gif  

for 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8625.gif and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8626.gif.

 

Catalan numbers are

설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC8637.gif.
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   

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_29_002223.PNG 

 

Sage code for Catalan number:

# Catalan number 생성(정의)

for i in range(10):

    print binomial(2*i,i)/(i+1)

 


설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/blueeye12/2018_10_31_111557.png

 

Also, to my mind, we can calculate the Catalan number in a simpler way, by using formulas of recurrence relations:

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/oleksandr/2018_10_30_003223.PNG

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)

 

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/blueeye12/2018_10_31_112058.png 

 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:

 

Pascals triangle

Binomial coefficients in a triangular form

설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC9503.png

Figure 6.7.1 Pascals 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 (= 0; i < n; i++)

   {

      for (= 0; c <= (- i - 2); c++)

         printf(" ");

 

      for (= 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 (= 1; c <= n; c++)

         result = result*c;

   return result;

}

EXAMPLE    

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_29_002923.PNG
 

 

 

 

  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)

설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC778F.png



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설명: https://www.shmoop.com/images/algebra/alg_probstat_prob_narr_latek_1.png

 

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 

 

​                              설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/5ehdcks/2018_10_29_172223.JPG

Binomial Theorem 

 

 Theorem  7.1

 Binomial Theorem

If 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC93E6.gif and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC93E7.gif, then

설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC93F7.gif.

 

Solution:

 

Notice that:

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_29_221106.PNG
 

in the given problem   a = 2 and b = -1.

 

Also: 

 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC93F7.gif.

 

Thus, 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_29_221130.PNG

which can be written as

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_29_221222.PNG

hence, 
설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_29_221339.PNG

 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 = {p1p2p3p4p5} 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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC9803.gif pigeons fly into 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC9804.gif pigeonholes and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC9815.gif, 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, P= ( 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,

 ( x+ 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 anwhich 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 ,  a​= 12

(b) Find an initial condition for the sequence.     

a​= 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

 

설명: 그림입니다.
원본 그림의 이름: CLP000022e80002.bmp
원본 그림의 크기: 가로 806pixel, 세로 107pixel


 

Solution

1.    Let a0 be the initial amount invested  

   -->  
a0=4000

2.    After 1 year, a1 will be  

    -->  a
1 = a+ 0.17 a= 1.17 a0

3.    After 2 years, a2 will be
    -->  a
2 = a+ 0.17 a​​1.17 a1 = (1.17)a0

4.    Thus, after n years, an will be   

    -->  a
n = an-1 + 0.17 an-1 = (1.17) an-1 = ... = (1.17)a0

Answer:

Initial state:                       

a
0=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). Thats why the relation/equation provided by the original answer (an = (1.17)* 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

 

 설명: 그림입니다.
원본 그림의 이름: CLP000022e8000b.bmp
원본 그림의 크기: 가로 804pixel, 세로 128pixel

 

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 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

 

설명: 그림입니다.
원본 그림의 이름: CLP000022e8000e.bmp
원본 그림의 크기: 가로 795pixel, 세로 358pixel

 

an=a*(-2n)+b*n(-2n)

 

* Our next step is to find the coefficients (a,b) using:

a= 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:

x​2​=3x+10

 

x​2​-3x-10=0

 

(x-5)(x+2)=0

 

X=5   x=-2

There are 2 roots so​

 

 Theorem  2.11

 

설명: 그림입니다.
원본 그림의 이름: CLP000022e8000d.bmp
원본 그림의 크기: 가로 797pixel, 세로 507pixel



a​n​=a*(5n​)+b*(-2​n​)

 

 

 

* Our next step is to find the coefficients(a,b) using:

a0=4

a1=13

 

*For n=0 

a​0​=a*(5​0​)+b*(-2​0​)=2

=a+b=4

*For n=1:

a​1​=2*(5​1​)+b*(-2​1)=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:

 

a​n​=3*(5n​)+1*(-2​n​)

  

Conclusion:

a​n​=3*(5n​)+1*(-2​n​)  

 

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

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/khsung0/2018_11_14_215640.PNG

 

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  C​n-1  strings of type (a).

 

2) An n-length​s 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 C​n-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 3​n-1​ strings altogether of length  n-1​

and C​n-1   strings contain even numbers of 1's

3​n-1​​C​n-1     contain odd number of 1's

 

Thus, 

C​n​=​Cn-1​​+Cn-1​​+3​n-1​​-Cn-1​= 3​n-1​​+Cn-1

 

Hence initial condition 

C​1​=2

 

 

 

 

 

Solving the recurrence relation by iteration:

C​n  =​  3​n-1​​+Cn-1​​

      = ​3​n-1​​​+(​3​n-2​​+Cn-2​)

      =​ 3​n-1​​​+​3​n-2​​+3​n-3  ​+ Cn-3

 

Keeping solving in this way, once we will get:

=​3​1​​​+​3​2​​+3​3  ​+... + 3​n-1​​+ C1

=2+(3​n​-3)/(3-1)=(3​n​+1)/2

Conclusion:

​A recurrence relation and initial condition :

C​n = Cn-1​​+Cn-1​​+3​n-1​​-Cn-1 =  3​n-1​​ + Cn-1

 

with the initial condition 

C​1=2

 

Solution :  C​n​ ​= (3​n​+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

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_11_09_160853.PNG
 


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 :   b= 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 김영철

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/kyc0816/2018_11_10_032816.jpg 

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 :

b
1= b1-1+1=b0+1=0+1=1

For n=2 :

b
2= 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

b
2=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

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/kyc0816/2018_11_10_031656.jpg

          

Solution

0.    In Exercise problem 9, we derived a recurrence relation and initial condition.

--> b
n = bn-1 + 1

--> b
= 0​​

1.  [Solve]   Thus, Let's solve by iteration :

--> b
n  = bn-1 + 1

= b
n-2 + 1 + 1

= b
n-3 + 1 + 1 + 1

2.     If we keep substitute like that, we will get

-->  
bn  ... = b+ 1 + 1 + 1 + ... + 1

            = 0 + n*1

           = n

So we get   b= n                                     

  Solution :                 b= 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

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/acusina/2018_11_17_141424.png 

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.

 

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/oleksandr/2018_11_26_164807.PNG

 

 

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.

 설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jjm7jjm7/2018_11_17_113257.png 

 

Definition:

 Definition  6.1

 

설명: 그림입니다.
원본 그림의 이름: CLP00000d6c000e.bmp
원본 그림의 크기: 가로 807pixel, 세로 139pixel

Proof

The adjacency matrix of graph G1​​ relative to vertex ordering v1, v2, v3v4, v5, v6 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jjm7jjm7/2018_11_17_114121.gif

is equal to the adjacency matrix of graph G2 relative to the vertex ordering w1, w2​​, w3​​, w4, w5, w6​​

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jjm7jjm7/2018_11_17_114121.gif

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,Wmake 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:

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_11_17_205144.PNG

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

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/acusina/2018_11_17_142930.png 

Scheme:

Here is an image of four cubes just for convinience: 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_11_17_192911.PNG

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:

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/acusina/2018_11_17_144054.png 

 

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

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/acusina/2018_11_17_144054.png​​

Definition:

 

 Definition 2.8

 

설명: 그림입니다.
원본 그림의 이름: CLP00001fd00001.bmp
원본 그림의 크기: 가로 801pixel, 세로 105pixel

 

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).

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/5ehdcks/2018_11_17_173112.JPG 

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

 

설명: 그림입니다.
원본 그림의 이름: CLP000021fc0001.bmp
원본 그림의 크기: 가로 798pixel, 세로 107pixel

 

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;

} 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jjm7jjm7/2018_11_19_113127.png
설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jjm7jjm7/2018_11_19_113212.png

 

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:

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_11_20_212629.PNG
 

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

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jjm7jjm7/2018_11_19_115511.png

 

 

Example:  설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jjm7jjm7/2018_11_19_115521.png

 

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:

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_11_22_235503.PNG

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

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jungju54/2018_11_21_183331.PNG
Theorem:

 Definition  1.11

 

 A graph 설명: http://matrix.skku.ac.kr/2018-DM/Ch-8/PICAB6C.gif is bipartite if there exist subsets 설명: http://matrix.skku.ac.kr/2018-DM/Ch-8/PICAB6D.gif and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-8/PICAB6E.gif of 설명: http://matrix.skku.ac.kr/2018-DM/Ch-8/PICAB7F.gif

 설명: http://matrix.skku.ac.kr/2018-DM/Ch-8/PICAB80.gif, 설명: http://matrix.skku.ac.kr/2018-DM/Ch-8/PICAB91.gif

 each edge in 설명: http://matrix.skku.ac.kr/2018-DM/Ch-8/PICAB92.gif is incident on one vertex in 설명: http://matrix.skku.ac.kr/2018-DM/Ch-8/PICABA2.gif and one vertex in 설명: http://matrix.skku.ac.kr/2018-DM/Ch-8/PICABA3.gif.

 

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:

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jungju54/2018_11_21_183415.PNG

 

 

 

 

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:

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_11_22_205907.PNG

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

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/kyc0816/2018_11_29_125442.JPG 

 

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 

 설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/ksy92zzang/2018_11_27_200650.png 

Algorithm:

설명: http://matrix.skku.ac.kr/2018-DM/Ch-9/PIC6A2.png

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. 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/ksy92zzang/2018_11_27_200704.png
I) connected with :
 f

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/ksy92zzang/2018_11_27_201242.png
II
) connected with f​​ : d ,e 

As given problem's order, we connect f​​ to d.

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/ksy92zzang/2018_11_27_201702.png
III
) connected with​​ d : c , b

Same reason above, connect d  to b

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/ksy92zzang/2018_11_27_202022.png
IV
) connected with ba , g

In the same way, connect b  to g​​

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/ksy92zzang/2018_11_27_202301.png
V) connected with g​​ e , a

Connect g​​ to​​ e

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/ksy92zzang/2018_11_27_202514.png
VI) connected with​​ e c , f

If we connect e to f , it will cause cycle.

So, we have to link e to c.

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/ksy92zzang/2018_11_27_202839.png
VII) connected with​​ c : d , a

because link c with d cause cycle, connect c to a.

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/ksy92zzang/2018_11_27_203137.png
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:

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_27_171952.PNG

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:

설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC9EF.gif.

 

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:

 

설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC9EF.gif.


 

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: 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_31_211157.PNG

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:

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_31_211910.PNG

 

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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC7EA9.gif and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC7EAA.gif are finite sets, then

설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC7EAB.gif.

 

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 (설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC911A.gif=3) and that each pile contains at least eight (8=설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC912A.gif) 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 담는 방법(설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC912B.gif=3, 8=설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC912C.gif)

설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC913D.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-6/PIC914E.gif.

 

 


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:

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_11_07_193049.PNG

​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:

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_11_07_195144.PNG
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)=B

Hence it computes initially only the value obtained from A=my_function1()

and if it satisfies the condition (if (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:

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_11_08_152826.PNG

 

Here is a square  with the sides 8 and I divided it into different shapes with sides showed in the picture attached.

 

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_11_08_153313.PNG



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 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_11_08_153947.PNG
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)
Ǝ C1 is positive constant such that f(n) C1g(n)

f(n) = Ω(g(n)) f(n) is omega of g(n) f(n) is of order at least g(n)
Ǝ C2 is positive constant such that f(n) C2g(n)
f(n) = Ɵ(g(n)) f(n) is theta of g(n) f(n) is of order g(n)

f(n) = Ω(g(n)) and f(n) = O(g(n)).
Factorial: the product of an integer and all the integers below it

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. 
설명: graph showing relation between a function, f, and the limit function, g

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. 
설명: graph showing relation between a function, f, and the limit function, g

 

 

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. 
설명: graph showing relation between a function, f, and the limit function, g

 

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 (n1)! (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(n1)! and divide both sides by n, giving  n!/n=(n1)!. 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=(m1)!. Since m=n+1, we now have (n+1)!/(n+1)=(n+11)!. Switching sides and noting that n+11=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, 0sΦ such that ns mod Φ =1.

s is the inverse of n mod Φ.

Definitions

Divisor: if n, d Z with d0.

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, ab, 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

 

Binary

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 = 1101 = 10102 = 100103 = 1000, and so forth. Similarly in base two, you have columns or "places" for 20 = 121 = 222 = 423 = 824 = 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
(base 
10)

binary
(base 
2)

 
    expansion

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

 

Euclid's Algorithm

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 differencea - 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,ab). 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.

Extended Euclidean Algorithm

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=331×27

3=274×6

Then we start from the last equation, and substitute the next equation into it:

3=274×(331×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.

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/goldshakil/2018_10_08_141224.png

 

 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.

ex5*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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC789.gif is prime.

If 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC79A.gif is prime, the algorithm returns 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC79B.gif.

If 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC79C.gif is composite, the algorithm returns a divisor 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7AC.gif satisfying 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7AD.gif.

 To test whether 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7AE.gif divides 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7BF.gif, the algorithm checks whether the remainder when 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7C0.gif is divided by 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7C1.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7D2.gif 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7D3.gif is zero.

        Input: 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7D4.gif

      Output : 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7E4.gif

   설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7E5.gif

     설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7F6.gif

        설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7F7.gif

          설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC7F8.gif

     설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC808.gif

     설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICC809.gif

 

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)

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_12_002847.PNG

 

Case B)

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_12_002912.PNG

 


 

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

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/oleksandr/2018_10_13_175639.PNG 

 

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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3A2.gif and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3B3.gif and stores the sum in 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3B4.gif.

      Input:  설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3C4.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3C5.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3C6.gif

    Output:  설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3D7.gif

    binary_addition(설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3D8.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3D9.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3EA.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3EB.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3EC.gif

       carry 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3FC.gif

       for 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3FD.gif to 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3FE.gif 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD40F.gif

          설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD410.gif

          설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD421.gif

      설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD422.gif

       설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD432.gif

   설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD433.gif

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_12_011725.PNG

 

 

 


 

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

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/oleksandr/2018_10_13_184105.PNG

 

Source: http://matrix.s`kku.ac.kr/2018-DM/DM-Ch-5-Lab.html ■

 

 

 

 

 

 

 


 

Comment: 해당 코드는 binary numbers , 2진수의 덧셈을 논하고 있다.논리 회로 과목에서 배웠던  '4-bit Full adder' 구동방식의 공통점이 많아 언급 하지 않을 수가 없게 되었다.설명: 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 각각의 변수 값이 뜻하는 바도 원래의 알고리즘이 표현하려던 목적과도 동일하다. 세부적으로는 알고리즘이 제시한 식은 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD410.gif 이고 이는 i+1번째 자릿수의 결과 값은 3개의 변수의 연산으로부터 결정됨을 coding 것인데 logic gate 표현 식으로는’Ai Bi C(i-1) 배타적 논리합 연산으로 표현하고 다음 자릿수로 넘어갈 ‘Carry’   설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD421.gif 이라고 알고리즘이 제시하였으며 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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE39.gif using repeated squaring.

      Input:  설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE49.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE4A.gif

    Output:  설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE4B.gif

    exp_via_repeated_squaring(설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE5C.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE5D.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE5E.gif

       result 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE6F.gif

       설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE70.gif

       while (설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE71.gif)설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE81.gif

          if(설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE82.gif 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE83.gif)

            설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE94.gif*설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE95.gif

           설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAE96.gif*설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAEA6.gif

          설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAEA7.gif

      설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAEB8.gif

     return result

   설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAEB9.gif

 

 

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)

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_12_013215.PNG
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

설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICAEA7.gif

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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD647.gif, where 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD658.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD659.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD65A.gif and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD66A.gif are integers. Then 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD66B.gif.

 

                       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:

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/khsung0/2018_10_06_192854.PNG

 

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.

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/jjm7jjm7/2018_10_07_164546.png

 Algorithm

 

 

Solution

The algorithm begins by setting result to 1 and x to a.

 Step 1) Since 

n = 30 > 0,

the body of the while loop executes.

 Step 2) Since 

n mod 2 is not equal to 1,

result is not modified.

 

 Step 3) x becomes a2, and n becomes 15.

Since 

n = 15 > 0

the body of the while loop executes 

 Step 4) Since 

n mod 2 is equal to 1,

result becomes 

result * x = 1 * a2 = a2.

 Step 5) x becomes a4, and n becomes 7.

 Since 

n = 7 > 0,

the body of the while loop executes

 

 Step 6) Since 

n mod 2 is equal to 1,

result becomes 

result * x = a2​​ * a4 = a6.

 Step 7) x becomes a8, and n becomes 3.

Since 

n = 3 > 0,

the body of the while loop executes.

 Step 8) Since 

n mod 2 is equal to 1,

 result becomes 

result * x = a6 * a8 = a14.


 

 Step 9) x becomes a16, and n becomes 1.

Since 

n = 1 > 0,

the body of the while loop executes. 

 Step 10) Since 

n mod 2 is equal to 1,

result becomes 

result * x = a14 * a16 = a30.

x becomes a32, and n becomes 0.

 Step 11) Since n = 0, the while loop terminates.

 

 

Conclusion:

Therefore, the algorithm returns the result which is equal to a​30   ■

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/khsung0/2018_10_07_180210.PNG
 

 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 a​k 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. =30 =11110​(2) ​=22​​ * 2​4​ *​ 2​8​ * 2​16 return result = a​2​​ * a​4​ *​ a​8​ * a​16 = ​ a​30

So, we can see that 11110​(2) ​=22​​ * 2​4​ *​ 2​8​ * 2​16​ and result = a​2​​ * a​4​ *​ a​8​ * a​16 = ​ a​30​ 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. 

 

 

설명: http://icampus.ac.kr/repository/attachfiles/operation/notice/sglee/2018_10_11_143955.png

 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, 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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3C9.gif) number system,

Any integer form is

설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3D9.gif   설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3DA.gif   based 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3EB.gif

where each 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3EC.gif and each 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3ED.gif is one of the binary digits 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3FE.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA3FF.gif

 

 Hexadecimal number system

Hexadecimal notation is based 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA803.gif.

Any integer form is

설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA813.gif   설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA824.gif   based 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA825.gif

where 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA836.gif and each 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA837.gif is one of the

hexadecimal digits 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA838.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA848.gif,설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA849.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA84A.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA85B.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA85C.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA85D.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA85E.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA86E.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA86F.gif, 10=설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA880.gif,  11=설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA881.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA882.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA893.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA894.gif, 15=설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA895.gif. 

 

Solution

 

 I) 430 = 256+128+32+8+4+2 

            = 1×28 + 1×2+ 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

=12          q =17      n =19 .

Compute z and φ.    

 

 

 

 

 Note:  

=p×q 

φ =(-1)(-1) 

 

 

Solution

 

We need to find  =p×q and φ =(-1)(-1)

 z =12×17 = 204

 φ =(12-1)(17-1)=11×16=176

 

 

Conclusion:

z​​ =204, φ =176    

 

 

Comment: I know about that φ() 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:

설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICA223.png

 

 

Solution

 

Following the given theory about lcm(m,n), we gonna put the given data.

​                                    lcm(2*52*72*134, 74*132*17)​

= 2​max(1,0)​ * 5​max(2,0)​ * 7​max(2,4) * 13​max(4,2) * 17​max(0,1)

​                                    = 2 * 5​2​ * 7​4 * 13​4 * 17​   

Conclusion:

                 lcm(2*52*72*134, 74*132*17)​​=     2 * 5​2​ * 7​4 * 13​4 * 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 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD647.gif, where 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD658.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD659.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD65A.gif and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD66A.gif are integers.

Then 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD66B.gif.

 BÉZOUT'S THEOREM:

If  and 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD876.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD887.gif, then there 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD888.gif such that

설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD889.gif.

 

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 ×←⑤(inverse  )

12 = 60 - (84 - 60 × 1) × 2 (put in)

12 = 3 × 60 - 2× 84 ←⑥

12 =3 × (396-84×4)-2× 84 (putin)

12= 3 × 396 - 84× (12+2)

12=3× 396-14× 84   ←⑦

12=3× 396-14× (480-396×1) (putin)

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:

 

설명: 그림입니다.
원본 그림의 이름: CLP000113980015.bmp
원본 그림의 크기: 가로 804pixel, 세로 151pixel

 

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​·​13​2​) × (​5​2·13​2​​)

74·132·17 = (72​·​13​2​​) × (7​2·​17​)

5​2·13​2​​ and​ 7​2​·​17are 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·13​2​.  ■

 

 

 

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:  설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3C4.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3C5.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3C6.gif

    Output:  설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3D7.gif

    binary_addition(설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3D8.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3D9.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3EA.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3EB.gif설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3EC.gif

       carry 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3FC.gif

       for 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3FD.gif to 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD3FE.gif 설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD40F.gif

          설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD410.gif

          설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD421.gif

      설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD422.gif

       설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD432.gif

설명: http://matrix.skku.ac.kr/2018-DM/Ch-5/PICD433.gif

 

 

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:

 

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_12_011725.PNG

 

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:

설명: http://www.icampus.ac.kr/repository/attachfiles/operation/notice/chingis/2018_10_12_011725.PNG

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,

     <URL> www.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/properties-of-recursive-algorithms

 

[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).