​     Discrete Mathematics

                        Prof : Sang-Gu LEE  (http://matrix.skku.ac.kr/sglee/ )

 

SKKU Math Lectures and Labs

DM Ch. 4, Algorithms

Lecture Note     http://matrix.skku.ac.kr/2018-DM/Ch-4/

DM-Ch-4-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-4-Lab.html 
DM Ch. 4, 동영상강의   https://youtu.be/Dtv-9ykjFFA 

 

DM 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

 

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, 영문 보고서)

 

SKKU DM, Ch 4 & 5,

Prob. and Solutions^ by Team 3

http://matrix.skku.ac.kr/2018-album/2018-Lectures-sglee.htm

 

Team № 3

(칭기즈, 유가이 올렉산드르, 김승연, 권재연, 이상민)

Solution, revision and finalization in chapter 4 and 5

Collected: 유가이 올렉산드르, 칭기즈

                         Typed: 유가이 올렉산드르, 김승연, 칭기즈

                         Comments: 김승연, 칭기즈

Involved in problem-solving: 유가이 올렉산드르, 권재연, 칭기즈

 

Chapter 4

 

[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

Final OK by SGLee] Ch. 4, Page 247, Problem № 3 (Chapter Self-Test), solved by 전종문, revised by 칭기즈, finalized by 김영철 and 김승연

 

Problem

Write an algorithm that returns true if the values of a, b and c are distinct, and false otherwise.

Solution

If a, b and c are all distinct, returned value will be ‘True’.  Otherwise, returned value will be ‘False’.

​  

Now, if all are distinct, we get ‘True’, and if not, we get ‘False’.      ■

 

 Comment: 조건 문 if 절에서 3개의 condition (a가 b와 같다 와 b가 c와 같다. 그리고 c가 a와 같다.) 중 하나라도 충족될 때 거짓이고 그렇지 않을 때에만 참 이도록 하게 한 명령어이다. '==' 는 logical equivalent 을 뜻하고 ‘‖’ 는 logical or 을 뜻한다. 이로 인해 a, b, c 중 하나라도 다른 parameter와 같으면 거짓이 되도록 설정하였다.

Comment: This problem is quite simple which needs some basic knowledge of programming. The idea is to check if at least two of the numbers are equal using the logical operator “or”.

 

 

[Final OK by SGLee] Ch. 4, Page 247, Problem № 5 (Chapter Self-Test), solved by 모하메드, finalized by 칭기즈 and 김승연

 

Problem  

Trace Algorithm 4.2.1 for the input t = “111011” and p = “110”.​ 

 

 

Explanation

The Algorithm stated in section 4.2.1 is called Text Search and it is defined as following:

 

Text Search:

This algorithm searches for an occurrence of the pattern p in text t . It returns the smallest

index i such that p occurs in t starting at index i. If p does not occur in t, it returns 0.

 

Input: p (indexed from 1 to m), m, t (indexed from 1 to n), n

Output: i ​(​the index of first match occurrence)

Pseudo Code: 

text search( p, m, t, n) {

for (i = 1 to n − m + 1)  //the starting point is 1, the ending point is (n-m+1)

{       

 j = 1                      

                           // i is the index in t of the first character of the substring

                           // to compare with p, and j is the index in p

                          // the while loop compares ti · · · ti+m−1 and p1 · · · pm

while (ti+j−1 == pj )

  {

       j = j + 1

if ( j > m)  //reaching the end of substring p

return i

  }

}

return 0

}​

"

 

 

 

 

Solution

Given:

t= "111011"

p= ​"110"

 

* Following the code and tracing the loop iterations we can find:

 

1) For-Loop's First Iteration / i=1:

 a) j is set to 1

 b) we execute the while-loop , and since t[1]==p[1], j is incremented to compare       t[2] and p[2] and since t[2]==p[2], j is incremented once again to compare         t[3] and p[3] and since t[3]!=p[3] , the while loop is broken and we move to the next for-loop iteration

 

2) For-Loop's Second Iteration / i=2:​

  a) j is set to 1

  b) we execute the while-loop , and because i=2 we start with t[2], since             t[2]==p[1], j is incremented to compare t[3] and p[2] and since t[3]==p[2], j is   incremented once again to compare t[4] and p[3] and since t[4]==p[3] j is   incremented once again to become (j=4) which is greater than (m) , so i=2 is   returned.

t = "111011" n=6

p = ​"110” m=3

Hint:

if ( j > m)  //reaching the end of substring p

return i

The algorithm terminates when j>m, m=3 => j=4

Trace table:

i	j	t[i+j-1]==p[j]	Output
1	1	true	-
1	2	true	-
1	3	false	-
2	1	true	-
2	2	true	-
2	3	true	-
2	4		2

∴ The output is 2         ■

 

 

Comment: 문자열 ‘110 ‘ 을 추적하고  ‘110 ‘이 발견된 경우 왼쪽부터 시작해서 최초의 ‘1 ‘ 이 발견된 자릿수를 결과값으로 내어 출력하는 알고리즘이다. 여기서 검사하는 방식은 ‘i’번째 항을 첫 번째로 ‘I’번째 항이 ‘1’ 인가 보고 일치하면 ‘i+1’번째 항도 ‘1’ 인가를 확인하고 ‘i+2’번째 항까지 ‘0’ 임이 맞는다면’ j’항 즉, n번째 검사임을 나타내는 factor가 ‘n=4’가 되게 된다면 검사를 중단하고 현재 ‘I’ 의 value를 출력하게 됩니다. 이것은 ‘110’ 이라는 찾고 싶은 문자열을 찾고 나서 그 찾은 위치를 출력하고 작동을 멈추는 전형적인 Text Search 알고리즘이고 이것을 응용하여 좀더 길거나 영어 및 다른 글자 기호의 조합도 찾아 낼 수 있을 것 입니다.

 

 

[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

 

 

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

 

  

 

 

 

 

[Final OK by SGLee] Ch. 4, Page 247, Problem № 7 (Chapter Self-Test), solved by 칭기즈, finalized by 엄자균, re-finalized by 김영철 and 김승연

 

Problem

Trace Algorithm 4.2.4 for the input 5, 51, 2, 44, 96.  (See below to find Algorithm 4.2.4) 

​

 

Solution

According to the problem, the sequence  is this.

5

51

2

44

96

Step I) We first swap a[i] and a[j],

where i=1 and j=rand(1,5). If j=3,

after the swap we have

2

51

5

44

96

Step II) Next,                          i=2. If j=rand(2,5)=5,

after the swap we have

2

96

5

44

51

Step III)Next,                          i=3. If j= rand(3,5) =3,

 the sequence does not change.

Step IV)Finally,                        i =4. If j = rand(4,5)=5 ,

after the swap we have

Output:

2

96

5

51

44

Notice that the output depends on the random choices, so the result may vary all the time. ■

 

 

 

 

[Final OK by TA and SGLee] Ch. 4, Page 248, Problem № 1 (Computer Exercises), solved by 칭기즈, finalized by 유가이 올렉산드르,

Problem

​Implement  Algorithm 1.2, finding the largest element in a sequence, as a program

 

 

Algorithm 1.2	Finding the Maximum Value in a Finite Sequence
procedure max( ,  ,   : integers)  max   for   to         if   then   return                   or

 

Solution

A) Python code

sequence=[int (x) for x in input("enter a sequence of numbers:").split()]

largest=sequence[0]

for i in range(len(sequence)):

  if sequence[i]>largest:

    largest=sequence[i]

print(largest) 

 

Practical image

 

 

B) Sage Code

@interact
def _(s=input_box(default=[1,5,4,2,6,3], label='sequence')):

      n = len(s)              # list의 길이
      maximum = s[0]

      for i in range(1,n):
            if  s[i] > maximum:
                  maximum = s[i]​

      print "maximum number is  ", maximum

      print max(s)

      return

 

Example:

Source: http://matrix.skku.ac.kr/2018-DM/DM-Ch-4-Lab.html  ■

 

 

Comment: 알고리즘의 돌아가는 방식은 시퀀스의 길이를 던져주고 코드를 자신이 원하는 출력이 나오도록 조절을 하고 그것을 반복하게 하는 식이다. 여기서는 '가장 큰 수'를 '0' 즉, Default 값을 쥐어준 후 시퀀스 1항과 비교, 1항이 크면 '가장 큰 수'를 큰 쪽으로 대체하고 2항 과도 비교하고 비교대상 중 큰 쪽으로 대체해 나가는 것을 Coder가 설정해둔 길이 까지 수행하고 마지막까지 진행해 나간 '가장 큰 수'를 출력하는 방식이다. 지금이야 코딩이 간단하여 나 또한 조금만 공부하고 연습하면 바로 제작할 수 있을 정도로 간단하지만 앞으로 몇 백 몇 천줄 되는 프로그램을 짜게 된다면 여기서의 숫자 하나가 오타가 난다거나 변수 알파벳을 혼동한다던가 하면 몹시 곤란하게 될 것이다.

 

 

 

[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

a₁, ... a_n

 

Input:  a, n

Ouptut:  a (shuffled)

shuffle(a, n){

for i = 1 to n - 1

                  swap(a[i],a[rand(i, n)])

}

 

 

Solution

 

A) Python code

import random

sequence=[1,2,3,4,5,6,7]

 

for i in range(len(sequence)):

  r=random.randint(i,len(sequence)-1)

  val= sequence[i]

  sequence[i]=sequence[r]

  sequence[r]= val

print(sequence)

 

 

Practical image:

 

 

 

B) Sage code

 

@interact

def _(s=input_box(default=[1,5,4,2,6,3], label='sequence')):

    n = len(s)  

    for i in range(1,n):

        r=int(RR.random_element(i,n-1))

        val= s[i]

        s[i]=s[r]

        s[r]= val  

    print s

    return​ 

 

Practical image:

 

 

Source: http://matrix.skku.ac.kr/2018-DM/DM-Ch-4-Lab.html  ■

 

 

[Final OK by SGLee] Ch. 4, Page 247, Problem № 3 (Chapter Self-Test), solved by 칭지즈, finalized by 전종문 and 김승연

 

Problem

 Implement Algorithm 2.3, insertion sort , as a program.

 

 

 

Algorithm:

 

Discussion:

In an insertion sort, the first element in the array is considered as sorted, even if it is an unsorted array. In an insertion sort, each element in the array is checked with the previous elements, resulting in a growing sorted output list. With each iteration, the sorting algorithm removes one element at a time and finds the appropriate location within the sorted array and inserts it there. The iteration continues until the whole list is sorted.

 

Solution

 

Python code:

def insertionSort(alist):

   for i in range(1,len(alist)):

     val = alist[i]

     j = i

     while j>0 and alist[j-1]>val:

         alist[j]=alist[j-1]

         j = j-1

     alist[j]=val

alist = [int(x) for x in input("Enter:").split()]

insertionSort(alist)

print(alist)

 

 

Example:

 

 

 

[Final OK by SGLee] Ch. 4, Page 247, Problem № 15 (Chapter Self-Test), solved by 조영은, finalized by 강병훈, re-finalized by 김영철

 

Problem

 Write a recursive algorithm to compute t[n] from the tribonacci sequence above, n ≥ 1.

 

 

Solution

Using the Python code we’ve already seen up there, by modifying it little bit, we can compute t[n] easily. But before we do that, let’s calculate by hand t[1] ~ t[10] below, to compare it with the output later to check if it gives the right results.

 

1.    t[1] = 1 (by definition)

2.    t[2] = 1 (by definition)

3.    t[3] = 1 (by definition)

4.    t[4] = t[1] + t[2] + t[3] = 3

5.    t[5] = t[2] + t[3] + t[4] = 5

6.    t[6] = t[3] + t[4] + t[5] = 9

7.    t[7] = t[4] + t[5] + t[6] = 17

8.    t[8] = t[5] + t[6] + t[7] = 31

9.    t[9] = t[6] + t[7] + t[8] = 57

10. t[10] = t[7] + t[8] + t[9] = 105

 

Python code:

def sequence(n):

    if (n==0 or n==1 or n==2 or n==3):

        return 1

    else:

        return (sequence(n-1)+sequence(n-2)+sequence(n-3))

 

def tribonacci(n):

    for i in range(1,n+1):

        print(sequence(i),"",end="")

       

n=10

tribonacci(n)

​

 

Output:

 

​

​

We can see the by-hand calculation and test result is identical.     ■

 

Comment: This problem is quite easy but very useful because it helps to get better understanding of the concept of recursive algorithms, where the key idea is to invoke a simpler version of itself, as well as Tribonacci sequence.

 

 

 

 

[Final OK by SGLee] Ch. 4, Page 247, Problem № 12 (Chapter Self-Test), solved by 강병훈, finalized by 모하메드, re-finalized by 김영철

 

Problem

 

Write an algorithm that tests whether two n × n matrices are equal and find a theta notation for its worst-case time.

 

Solution

Input – A, B (both n x n matrices), n 

Output – True (​if A = B), False (​if A ≠ B)

 

< Pseudo Code >

Note: We have to compare each element in A and B, and as soon as different match is found, we return False. The worst case is when the two are actually same matrices, so that we end up comparing all the elements of A and B.

 

So the code is like below:

 

 

 

 

 

 

 

 

Python code:

 

N = 4

def areSame(A,B):

    for i in range(N):

        for j in range(N):

            if (A[i][j] != B[i][j]):

                return False

    return True

A= [ [1, 1, 1, 1],

    [2, 2, 2, 2],

    [3, 3, 3, 3],

    [4, 4, 4, 4]]

B= [ [1, 1, 1, 1],

    [2, 2, 2, 2],

    [3, 3, 3, 3],

    [4, 4, 4, 4]]

print(areSame(A,B))

 

Output:

 

 

 

<Worst case>

 

As I mentioned above, the worst-case time occurs when the two are actually

same matrices​​, so that we end up comparing all the elements of A and B.

To compare all the elements of the two, as each of them have n * n = (n^2) 

elements, it will take (n^2) times comparing them. So, the Theta notation

for the worst-case time here is Theta of (n^2). 

Note: Theta /O / Omega notations are read as " O/theta/Omega of f(x)" -> where f(x) is a function that counts the number of operations executed and generally the most used notation is the O-notation since it gives the upper bound-worst case- for an algorithm. ■ ​

 

 

 

[Final OK by SGLee] Ch. 4, Page 247, Problem № 4 (Chapter Self-Test), solved by 엄자균, finalized by 강병훈, re-finalized by 김은율

​

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 김영철 

Problem

 Write an algorithm that receives as input the distinct numbers a, b, and c and assigns the values a, b, and c to the variables x, y, and z so that

x < y < z.

 

 

Solution

We have to assign, compare and then swap if necessary, as below.

​

 

Hint:

How does the swap() actually work?

In programming it is wrong to write:

y=x

x=y

because when we assign x to y the original value stored in y is deleted, now it has the value of x. Therefore we need to store the original value of y in order to give it to x

 

Python code:

a=int(input())

b=int(input())

c=int(input())

x=a

y=b

z=c

if(y<x):

  temp=y

  y=x

  x=temp

if(z<x):

  temp=z

  z=x

  x=temp

if(z<y):

  temp=z

  z=y

  y=temp

print(x,y,z)

Pactical image:

Now, it is sure that x < y < z.   ■

Comment: This problem is very useful to understand how the function swap() really works, hence it may help to develop your computational thinking which is very important. The key idea is to store the original value of the variable in the temporary space to assign it to another variable.

 

 

[Final OK by SGLee] Ch. 4, Page 247, Problem № 8 (Chapter Self-Test), solved by 강병훈, finalized by 김은율, re-finalized by 김영철

 

Problem

 

Write an algorithm that receives as input the sequence

s[1], . . . , s[n]

sorted in non-decreasing order and prints all values that appear more than once. Example: If the sequence is

1  1  1  5  8  8  9  12,

the output is

1  8.

 

 

Solution

We have to run while loop and check if there are same numbers, and print them if exist, and skip to non-identical part. It is shown below.

 

Algorithm:

​  

This way we can find repeated numbers and print them. 

 

Python code:

i=0

s=[1 , 1 , 1 , 5 , 8 , 8 , 9 , 12]

n=len(s)

while(i<n-1):

  if s[i]==s[i+1]:

    print(s[i])

  j=i

  while(i<n and s[i]==s[j]):

    i=i+1

 

Practical image:

 

 

 

Sage code:

i=0

s=[1 , 1 , 1 , 5 , 8 , 8 , 9 , 12]

n=len(s)

while(i<n-1):

  if s[i]==s[i+1]:

    print(s[i])

  j=i

  while(i<n and s[i]==s[j]):

    i=i+1

 

Practical image:

 

Notice: Sage code and Python code are the same because SageMath uses a syntax resembling Python's, supporting procedural, functional and object-oriented constructs.        ■​

 

Comment: This problem is very straightforward because if a sequence is in nondecreasing order, the repeating numbers always stay next to each other and that is the key point to solve this problem. However, it helps to understand the concept of the sequence of numbers in nondecreasing order.

 

 

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 N^1/2

  if (N mod d == 0)    //mod function returns the remainder

       return d

return 0

} 

 

 

Solution

 Using the algorithm mentioned earlier, we can easily check whether an integer(N) is prime or not, so we combine the same algorithm with division to solve this problem as following.

 

 
Let's solve this task by using a factorial tree:

 

 *The yellow marked numbers are prime.
So we get : 539=(7^2)*11                                       ■

 

Comment: From this problem, I realized that Factors are the numbers you multiply together to get another number.

ex) 5*3 = 15. And Prime Factorization is finding which prime numbers multiply together to make the original number. ■
Comment (Muhammad): when you try to find Factorial tree, start checking the factors from smallest to biggest (1,2,3,4,...) ■

 

 

 

[Final OK by SGLee] Ch. 5, Page 300, Problem № 1 (Computer Exercise), solved by 칭기즈, Finalized by 유가이 올렉산드르

 

Problem

​​Implement Algorithm 1.8, testing whether a positive integer is prime, as a program.

 

Algoruthm1.8	Testing Whether an Integer Is Prime
This algorithm determines whether the integer   is prime. If   is prime, the algorithm returns  . If   is composite, the algorithm returns a divisor   satisfying  .  To test whether   divides  , the algorithm checks whether the remainder when   is divided by  ,     is zero.         Input:        Output :

 

Python code

import math

n=int(input("enter a number: "))

for i in range(2,math.floor(math.sqrt(n))+1)://check if it has a divisor in the range[2,floor(sqrt(n))]

  if(n % i==0): //if there is no remainder, it means it has a divisor in this range

    print(str(n)+" is not a prime number")

    quit()

print(str(n)+" is a prime number") //if there is no divisor in the range, it is a prime

 

Practical image

Case A)

 

Case B)

 

Sage Code

​# Testing Whether an Integer Is Prime

@interact​
def _(n=input_box (default=43, label='Enter the number such that n>1 ')):
    for i in range(2,floor (sqrt (n))+1):
          if n % i == 0:
                print n, "is composite"
                return
    print n, " is prime"
    return​​

 

Practical image

 

 

​Source: http://matrix.skku.ac.kr/2018-DM/DM-Ch-5-Lab.html ■ 

 

Comment: This problem is a good and very easy example to get the concept of chapter 5, especially the theory of identifying if the given number is prime or composite. The key idea is that a composite number has a divisor in the range 2 to ⌊√n⌋.

 

 -------------------------------------------------------------------------------------------------------------------------

 

[Final OK by SG Lee] Ch. 5, Page 300, Problem № 3 (Computer Exercise), solved by 칭기즈and 김승연

Problem

Write a program that adds binary numbers.

Algorithm  2.12	Adding Binary Numbers
This algorithm add the binary numbers   and   and stores the sum in  .       Input:   ,  ,      Output:       binary_addition( ,  ,  ,  )         carry         for   to

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Python code

import math

b=[int(x) for x in input().split()]

b1=[int(x) for x in input().split()]

carry=0

s=''

list1 = list(s)

for i in range(len(b)):

  b2 = b[len(b)-i-1]

  c1 = b1[len(b)-i-1]

  list1.append( str((b2+c1+carry)%2))

  carry=math.floor((b2+c1+carry)/2)

list1.append(str(carry))

s = ''.join(list1)

print(s[::-1])

 

Practical image

 

 

 

Sage Code

# Adding Binary Numbers

@interact​
def _(b=input_box(default=1101, label='binary number'),
c=input_box(default=1001, label='binary number')):
    b = str(b)
    c = str(c)
    n = len(b)
    carry = 0
    s = ''
    for i in range(n):
        b1 = Integer(b[n-i-1])
        c1 = Integer(c[n-i-1])
        s = str((b1+c1+carry) % 2) + s
        carry = (b1+c1+carry) // 2
    s = str(carry) + s
    print s
    return

 

​ Practical image

 

 

[Final OK by SG Lee] Ch. 5, Page 300, Problem № 6 (Computer Exercise), solved by 칭기즈, finalized by 유가이 올렉산드르and 김승영

 

         Problem 

Implement Algorithm 2.16, exponentiation by repeated squaring, as a program.

  

Algorithm  2.16	Exponentiation By Repeated Squaring
This algorithm computes   using repeated squaring.       Input:   ,      Output:       exp_via_repeated_squaring( ,  )         result                 while ( )           if(   )             *            *                        return result

 

Solution

 

Python code

import math

a=int(input("Enter the number: "))

n=int(input("Enter the exponent: "))

result=1

x=a

while(n>0):

  if(n%2==1):

    result=result*x

  x=x*x

  n=math.floor(n/2)

print(result)

Practical image

 

Sage code:

@interact

def _(a=input_box(default=2, label='Enter the number:  '),n=input_box(default=2, label='Enter the exponent: ')):

    result=1

    while(n>0):

        if(n % 2==1):

            result=result*a

        a=a*a

        n=floor(n/2)

    print result   

    return

Practical image

 

 

[Final OK by SGLee] Ch. 5, Page 300, Problem № 9 (Chapter Self-Test), solved by 신혜수, finalized by 전종문

Problem

 Use the Euclidean algorithm to find the greatest common divisor of the integers 396 and 480.

 

Theorem:

 Euclidean Algorithm is algorithm for finding the greatest common divisor of two integers.

  Ex) Let  , where  ,  ,   and   are integers. Then  .

 

                       Solution
The Euclidean algorithm gives  

480 = 396 * 1 + 84. 

b=396    r=84

Thus,

 gcd(480, 396) = gcd(396, 84)​   (by the Euclidean algorithm, 480 = 396 * 1 + 84)

                    = gcd(84, 60)    (by the Euclidean algorithm,  396 = 84*4 + 60)

                    = gcd(60, 24) = gcd(24, 12) = gcd(12,0) ​=12

 

Conclusion:

     ∴ the greatest common divisor of the integers 396 and 480 = 12    ■

 

​

​Comment: ​I think this Euclidean algorithm make me to find the greatest common divisor​ more easier in short time when integers are more bigger. Euclidean algorithm ​save more running time than prime factorization to find the greatest common divisor.  

 

 

[Final OK by SGLee] Ch. 5, Page 300, Problem № 5 (Chapter Self-Test), solved by 정호진, finalized by 김희성

 

Problem 

 Write the binary number 10010110 in decimal.

 

Theory:

 

 

Solution

10010110​₂=0*2⁰+1*2¹+1*2²+0*2³+1*2⁴+0*2⁵+0*2⁶+1*2⁷ = 2+4+16+128

=150₁₀                                                 

 

 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.

 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 a^​2, 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 * a^​2​ = a^​2​.

 Step 5) x becomes a^​4, 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 = a^​2​​ * a^​4 = a^​6.

 Step 7) x becomes a^​8, 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 = a^​6 *​ a^​8​ = a^​14.

 Step 9) x becomes a^​16, 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 = a^​14 * a^​16 = a^​30.

x becomes a^​32, 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​   ■

 

 

 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. n =30 =11110_​(2) ​=2²​​ * 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) ​=2²​​ * 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. 

Theorem:

 

Solution (Refer Theorem 5.3.6)

 

Given that

log_3/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 log_3/2  (2m/3) modulus operations are required.

Since the given range 0 to 100,000,000, 

So, in this problem, m is 100,000,000. And we use this formula.

 

Solution:

 log_3/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)⁴

= -1 + 4 log _3/2(100)

= -1 + 4 (11.357747)    //Since  log _3/2(100) = 11.357747

= -1 + 45.430988

= 44.430988                                                 

 Conclusion:

Therefore, the upper bound we found is 44.  ■

 

 

 

Comment: Euclidean algorithm에 대한 이해가 부족한 상태에서 문제에 접근하다보니 스스로 아쉬운 부분과 이해가 되지 않는 부분이 있었지만, 문제에 적용하고 수정하는 과정을 통해서 해당 알고리즘에 대해 완벽하진 않지만 어느 정도 보완할 수 있었다. 물론, 다른 문제에 적용해보면서 발전시켜 볼 필요가 있다.(서명원) 

 

처음 이 문제를 풀때는 위의 식이 어떤것을 의미하는지 정확히 몰랐었다. 그래서 문제를 완벽하게 풀이하지 못했다. 학우들이 처음 푼 풀이를 수정해주고 다시 문제를 풀어보니 처음 문제를 접했을 보다는 깔끔한 풀이가 완성된 느낌이다. 앞으로 문제를 풀때도 단순히 정답 도출에 목적을 두는게 아니라 어떻게 풀어야 하는지에 초점을 두고 공부해야겠다고 느낄 수 있는 문제였다. (정호진)

Comment: This problem is very easy if you know the rules used for logarithms.

 

 

[Final OK by SGLee] Ch. 5, Page 264, Problem № 6 (Chapter Self-Test), solved by 정호진, finalized by 엄자균, re-finalized by 서명원, 정호진

 

Problem

Write the decimal number 430 in binary and hexadecimal.

 

 

Theory:

 Binary Number System

In the Binary (base  ) number system,

Any integer form is

       based 

where each   and each   is one of the binary digits  ,  . 

 

 Hexadecimal number system

Hexadecimal notation is based  .

Any integer form is

       based 

where   and each   is one of the

hexadecimal digits  ,  , ,  ,  ,  ,  ,  ,  ,  , 10= ,  11= ,  ,  ,  , 15= . 

 

Solution

 

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

            = 1×2^​8​ + 1×2^​7 ​+ 0×2^​6​ + 1×2^​5​ + 0×2^​4​ + 1×2^​3​ + 1×2^​2​ + 1×2^​1​ + 0×2^​0​​ = 110101110_​(2)​

 II) 430 = 1×​16^​2​ + 10×​16^​1​ + 14×​16^​0​ = 1AE_​(16)​

 

 Conclusion:

     ∴110101110_​(2)​​ , 1AE_​(16)​​  ■ 

 

 

 

 

 

[Final OK by SGLee] Ch. 5, Page 300, Problem № 13 (Chapter Self-Test), solved by 강병훈, finalized by 김주형, re-finalized by 전종문 

 

Problem

In exercise 13-16, assume that we choose primes

p =12          q =17      n =19 .

Compute z and φ.    

 

 

 

 

 Note:  

z =p×q 

φ​ =(p -1)(q -1) 

 

 

Solution

 

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

 z​ =12×​17 = 204

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

 

 

Conclusion:

∴z​​ =204, φ​ =176    ■

 

 

Comment: I know about that φ(n )​​ used at RSA(Type of Public-key cryptography​) .

 φ(n) is ​the number of coprime n and number which is less than n 

 

[Final OK by TA] Ch. 5, Page 299, Problem № 4 (Chapter Self-Test), solved by AYSU OZGUNEKIM, finalized by 김정주, re-finalized by 서명원

                              

Problem

 Find  lcm(2*5²*7²*13⁴, 7⁴*13²*17)​

 

 

 

Theory:

 

 

Solution

 

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

​                                              lcm(2*5²*7²*13⁴, 7⁴*13²*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*5²*7²*13⁴, 7⁴*13²*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  , where  ,  ,   and   are integers.

Then  .

 BÉZOUT’'S THEOREM:

If  and  , then there   such that

.

 

Solution

 

Refer to the Euclidian Algorithm:

480= 396 × 1 + 84 ①

396= 84  × 4 + 60 ②

84 = 60 ×1 + 24 ③

60 = 24 ×12 +12 ④           

24 = 12 × 2  

Thus,  

gcd(396,480) =gcd(396,84)=gcd(60,84)=gcd(60,24)=gcd(12,24)=12

 

Refer to Bezout’s theorem:

12 = 60 - 24 × 2  ←⑤(inverse④  )

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

12 = 3 × 60 - 2× 84 ←⑥

12 =3 × (396-84×4)-2× 84 (put②in⑥)

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

12=3× 396-14× 84   ←⑦

12=3× 396-14× (480-396×1) (put①in⑦)

12=17× 396-14× 480

396(17) + 480(-14)=12

 

 

 

Conclusion:

s=17, t= -14  

 

 

 

 

Comment: This problem is a great example which helps to understand how to use the Euclidian Algorithm as well as Bezout’s theorem in a problem-solving. The key point is that the Euclidian algorithm makes it easier to use Bezout’s theorem, hence it is useful to keep in mind both of them in problem solving.

 

 

[Final OK by SGLee] Ch. 5, Page 299, Problem № 3 (Chapter Self-Test), solved by AYSU OZGUNEKIM, finalized by 전종문

Problem                                

Find

gcd(5²​·7²​·​13⁴, 7⁴​·​13²​·​17).

 

 

Theory:

 

Solution

 

gcd(m,n) where m=5²​·7²​·​13⁴  and n=7⁴​·​13²​·​17

Let’s rewrite them in the form:

5²​·7²​·​13⁴​ = (7²​·​13^​2​) × (​5^​2​·13^​2​​)​

7⁴​·​13²​·​17 = (7²​·​13^​2​​) × (7^​2·​17​)

5^​2​·13^​2​​ and​ 7^​2​·​17​ are coprime.

Note:

Two numbers are called relatively prime, or coprime, if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

 

Conclusion:

    ∴​   gcd(5²​·7²​·​13⁴, 7⁴​·​13²​·​17) = ​7²​·​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.

 

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