﻿

Discrete Mathematics

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

SKKU Math Lectures and Labs

DM Ch. 4, Algorithms

Lecture Note

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

Review (Ch 1-5)

PBL 학생 발표 (Ch 1-5 Solutions

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

Team 3

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

Solution, revision and finalization in chapter 4 and 5

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

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

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){ =12, b =3,=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

Comment: 여러 개의 parameter들 중에서 하나를 처음 지정한 후 다른 것들과 하나씩 비교하면서 큰 것으로 대체해 나가다가 비교할 것이 없어지면 남은 최종 parametervalue가 출력 되는 알고리즘이다.

Comment: This problem may be difficult to understand but if you follow the trace table and the code provided simultaneously it will be quite easier to get the idea.

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

Problem

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

Solution

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

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

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

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

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

Problem

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

Explanation

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

Text Search:

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

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

Input: p (indexed from 1 to m), mt (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+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

Sourcehttp://matrix.skku.ac.kr/2018-DM/DM-Ch-4-Lab.html

Solution

Suppose that the input is the following sequence

 44 64 77 15 3

Firstly, I=2,  j=I-1=1 ,val = s[2]=64

j>=1 and val< s[1]= 44 is false, so there is no change

Thus, s[j+1]=s[2]=val=64

 44 64 77 15 3

Now, I=3, j=2, val=s[3]=77

j>=1 and val< s[2]= 64 is false, so there is no change

Thus, s[j+1]=s[3]=val=77

 44 64 77 15 3

Now, I=4, j=3, val=s[4]=15

j>=1 and val< s[3]= 77 is true ,

s[4]=s[3]= 77               j=j-1 = 2

 44 64 77 77 3

j>=1 and val< s[2]= 64 is true

s[3] =s[2]=64                 j=j-1 = 1

 44 64 64 77 3

j>=1 and val< s[1]= 44 is true ,

s[2]=s[1]=44                 j=j-1 = 0

 44 44 64 77 3

j>=1 is false, skips the loop

s[j+1]=s[1]=val=15

 15 44 64 77 3

Now, I=5, j=4, val=s[5]=3

j>=1 and val< s[4]= 77 is true ,

s[5] =s[4]=77                 j=j-1 = 3

 15 44 64 77 77

j>=1 and val< s[3]= 64 is true

s[4] =s[3]=64                  j=j-1 = 2

 15 44 64 64 77

j>=1 and val< s[2]= 44 is true

s[3] =s[2]=44                 j=j-1 =1

 15 44 44 64 77

j>=1 and val< s[1]= 15 is true

s[2] =s[1]=15                  j=j-1 = 0

 15 15 44 64 77

j>=1 is false

 15 15 44 64 77

s[1]=val=3

 3 15 44 64 77

Output

 3 15 44 64 77

is sorted.​​

​​ Comment: 이 문제를 다시 해석하고 정리하였을 때에 알고리즘의 기준은 숫자의 대/소 관계에 의거해 정렬을 하였는데 약간의 실생활 경험만 있다면 컴퓨터의 파일들의 정렬의 기준은 이름, 크기, 항목의 유형, 수정한 날짜, 그 이외에 많은 기준들이 존재함을 떠올릴 수 있다. 지금이야 10개도 되지 않는 숫자들의 정렬이니 별로 대단치는 않을 것이라고 생각할 수는 있지만 수천 내지 수만 혹은 그것을 넘어서는 단위의 어떤 집단들을 기준을 따라 정렬하는 것은 컴퓨터와 알고리즘의 도움을 받지 않을 수 없을 것이며 새삼 컴퓨터와 그를 비롯한 수학이 가져다 준 문명의 혜택에 감탄할 뿐이다.

Comment: This problem is very good example to understand how swapping works in programming. The key idea of swapping is to store the some value in a temporary variable, which is m in this case.

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

Problem

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

Solution

According to the problem, the sequence  is this.

 5 51 2 44 96

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

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

after the swap we have

 2 51 5 44 96

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

after the swap we have

 2 96 5 44 51

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

the sequence does not change.

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

after the swap we have

Output:

 2 96 5 51 44

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

Comment: 이번 문제의 주제인 난수에 대해 이야기 하자면 사실 수업이나 교과과정이 코딩을 짠다거나 실제 컴퓨터의 'pseudo Random Number' 발생시키는 'Seed' 라던가 'XOR-shift'등의 발생 기법을 중점적으로 다루는 course 아니고 이러한 것이 있다 보여주는 수준이다. 난수는 실제 세상의 하고 많은 표본을 무작위적이고 고르게 뽑기 위한 학술, 통계적인 용도로 쓰일 수도 있고 요즘 이슈가 되고 있는 'Block chain' 기술 여러 암호 관련 기술/기법과 우리가 일상적으로 즐기는 비디오 게임에도 관여하는 중요한 요소이므로 앞으로 내가 흥미를 가지고 있는 soft 개발을 진지하게 기회가 있다면 다른 연관수업에 대해 찾아 나설 생각이다.

Comment: The key idea of a shuffle algorithm is to re arrange the given sequence by swapping a certain element with a random element generated by the function rand(n,m).