2019 Spring SKKU Discrete Mathematics (이산수학)

        Record of your DM class

          (Flipped/PBL Action Learning)

       It was a good class because of you.  Thanks a lot ~~

Class: Discrete Mathemetics

              Prof : Sang-Gu LEE   sglee at skku.edu

           http://matrix.skku.ac.kr/2019-album/

Students: Mr 김찬호, 김두원, 박재형, 최세현, Dam 담딘바자르, Piran, Angel, Gam, Simen, Chae, 김진녕, Greek, Dulkoon, ...

(1) State more than 10 DM Definitions and concepts and Theorems what you learned from the Chapters.

1.   Mathematical Induction

   Mathematical induction is a technique for proving a statement -- a theorem, or a formula -- that is asserted about every natural number. The Mathematical Induction is a proof technique to prove a statement is true for every positive integer. There are 2 steps for it – Basis Step and Inductive Step.

2.   Sequences and Strings

   A sequence is an ordered list of elements, which can be infinite and finite. Usually, lists of elements are represented by indexed letters. A string of length n on an alphabet l of m characters is an arrangement of n not necessarily distinct symbols from l. There are such distinct strings.

3.   Relations

   Relations are relationships between 2 or more sets and their objects that related to each set. Sets of ordered pairs are called binary relations.

...

   Sorting

   Sorting Algorithms, a sorted array is an array that is in a particular order. For example, [a,b,c,d] is sorted alphabetically, [1,2,3,4,5] is a list of integers sorted in increasing order, and [5,4,3,2,1] is a list of integers sorted in decreasing order.

 ...

               http://matrix.skku.ac.kr/2019-Album/MH-PBL/index.htm

 (2) State 9 things that you know/can/find after you studied the first 9 Chapters.

Chapter 1

We grasped the fundamental concept of Discrete Mathematics along with Computer Science, especially the sets – which are always used in coding. The propositions were directly linked to the Boolean, which I learn in my Logic Circuits class, and with the knowledge, I was able to make more sense out of the class I had taken a year ago.

Chapter 2

The concepts were mainly about proofs – their application and difference between related proofs. Proofs have always been a huge part of both Mathematics and Computer Science, and we learnt it, mostly, in elementary school. Even in real life situations, proofs have always made significant impacts – declaring about true or false.

Chapter 3

As we learnt in middle school and have been learning in colleges, functions have always been a crucial part of mathematics due to their applications on calculation. However, functions in Discrete Mathematics are mainly used to solve problems, whereas in high school we usually apply it on precise calculation.

Chapter 4

We learn about the most crucial topic of both Discrete Mathematics and Computer Science – Algorithm. Algorithm has always been the topic in the IT industry because we engineers have to deal with problems every day. With its applications, we learn about sorting algorithms, which is a sorted array is an array that is in a particular order.

Chapter 5

We gained the very fundamental knowledge of Computer Science – Number Theory, In the chapter, different number systems and representations of integers were introduced, more specifically, finding the common divisor and number base converters such as decimal to binary. Furthermore, we learnt binary addition, which is, I think, easier than adding the decimals. From my experience, I made lots of number base converter using different programming languages and implementing it on Discrete Mathematics was almost the same as I did on Python.

Chapter 6

We mainly learnt about Counting Methods and Pigeonhole Principle. However, it was based on what we learnt in middle school – Probabilities and Statistics. We consider whether it should be duplicated to find the answer. The 2 interesting topics in the chapter were Catalan Number and Fibonacci Number.

Chapter 7

We were introduced Recurrence Relation and how to solve them. A recurrence relation defines a sequence by giving the n th value in terms of its predecessors. Then the value is given in terms of the immediately preceding value. In order for a recurrence relation to define a sequence, a “start-up” value or values must be given. These startup values are initial conditions. A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation.

Chapter 8

We learnt about Graphs and their different types and fundamental structures and definitions. Graphs are drawn with dots and lines. Dots are vertices. The lines connecting the vertices are edges. The edges are e1 e2 etc. Path is from V0 to Vn. Simple Graph A graph with neither loops nor parallel edges is a simple graph. Simple cycle is a loop cycle etc.

Chapter 9

The famous Tree, which is popular amongst the Computer Science students, was introduced. We learnt difference between a “Tree” and a “Rooted Tree”. On top of that, binary tree that can only have 2 children at most. Probably, the most interesting chapter to CS students.

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

Chapter1

1. Sets (집합)

◆ A collection of objects.

◆ The objects are elements or numbers.

◆ The order of objects is not taken into account.

◆ The set have distinct elements.

There are lot of set notation.

◆ Equal : If set X and Y have same elements, X and Y is equal.

◆ Empty set (공집합) : The set with no elements. It denoted by the symbol ∅.

◆ Subset (부분집합) : Every element of the subset is an element of the original set.

◆ Proper subset (진부분집합) : It is same as subset, but it does not include the set that is equal to the original set.

◆ Power Set (멱집합) : The set of all subsets(proper or not) of a set.

2. Cardinality (집합의 크기)

If X is a finite set, |X| = number of elements in X.

|X| is the cardinality of X.

For example, the cardinality of set {1, 2, 3, 4, 5} is 5.

3. Union, intersection, difference (합집합, 교집합, 차집합)

Given two sets X and Y.

Union(합집합) : X∪Y = { x | x ∈ X or x ∈ Y}

The union consists of all elements belonging to X, Y or both.

Intersection(교집합) : X∩Y = { x | x ∈ X and x ∈ Y}

The intersection consists of all elements belonging to both X and Y.

Difference : X－Y = { x | x ∈ X and x ∉ Y}

The difference consists of all elements which belongs to X but not to Y.

4. Universal set and complement (전집합, 여집합)

U is a universal set or universe.

Given a universal set U and X ⊆ U, the set U - X is the complement of X.

X^C is the complement of X.

U^C is the complement of ∅.

5. Venn diagram (벤 다이어그램)

In a Venn diagram, a rectangle depicts universal set.

Subsets of the universal set are drawn as circles.

The inside of a circle represents the numbers of that set.

By Venn diagram, we can easily find the relation between sets.

6. Disjoint and Partition (서로소, 집합의 분할)

Disjoint (서로소)

◆ X ∩ Y = ∅ means sets X and Y are disjoint.

◆ If X and Y are distinct sets in S, X and Y are disjoint.

◆ We can assume a collection of sets S is pairwise disjoint.

Partition (집합의 분할)

◆ A partition of a set X divides into non-overlapping subsets.

◆ If every element in X belongs to exactly one member of S, a collection S of non-empty subsets of X is a partition of the set X.

◆ If S is a partition of X, then S is pairwise disjoint.

7. Proposition (명제)

If a sentence is either true or false but not both is called a proposition. The propositions are the basic building blocks of any theory of logic.

For example, a sentence “this apple is red” is a proposition. However, “this apple is delicious” is not a proposition. That sentence can not be definite as true or false.

Let p and q be propositions.

◆ p∧q is conjunction of p and q. It can be read as the proposition of “p and q.”

◆ p∨q is disjunction of p and q. It can be read as the proposition of “p or q.”

◆ ￢p is negation of p. It can be read as “not p.”

◆ without parentheses, there is a precedence in these operators. ￢ > ∧ > ∨.

8. Conditional Propositions (조건 명제)

Let p and q be propositions.

◆ “if p then q” is a conditional proposition.

◆ conditional proposition is denoted as p → q.

◆ p is the hypothesis

◆ q is the conclusion.

◆ p → q is equivalent to ￢ p ∨ q

◆ if p is false, conditional proposition p → q is always true. (tautology)

9. Rules of Inference (추론 법칙)

Deductive reasoning (연역적 추론)

◆ The process of drawing a conclusion from a sequence of propositions.

◆ Deductive reasoning is the process of reasoning form hypothesis to reach a conclusion.

◆ The given propositions are the hypotheses.

◆ The proposition that follows from the hypotheses are the conclusion.

◆ A argument consist of hypotheses and a conclusion.

◆ Deductive argument can be formed as “If p₁ and p₂ and p₃ and p₄ then q.”

Rules of inference for propositions.

10. Quantifiers (한정사)

 is a statement involving the variable .  is a set.

For each ,   is a proposition.

 is a propositional function (명제 함수)

 is the domain of discourse (담론영역)  of .

for every 

is a universally quantified statement of .

The symbol  means “for every.”

The symbol  is a universal quantifier (범용 정량자, ).

there exists 

is an existential quantified statement.

The symbol  means “there exists.”

The symbol  is an existential quantifier of .

1) Venn diagram

 벤 다이어그램(Venn diagram)은 집합에 대한 도식적 관점을 제공한다. 즉, 집합의 관계를 그림으로 나타내어, 시각적으로 우수한 표현 방법이다.

 벤 다이어그램에서 사각형은 전체집합, 원은 전체집합의 부분집합, 원의 내부는 그 부분집합의 원소들을 나타낸다. 원이 겹치는 부분은 교집합, 겹치지 않는 부분은 그 집합에서 다른 집합을 뺀 원소 부분 등을 나타낸다.

2) Cartesian Product

 만약 와 가 집합이면, 는 이고 인 모든 순서쌍 의 집합을 나타낸다. 이 집합 를 와 의 데카르트 곱(Cartesian Product)이라 한다.

 만약 이고 라 하면 다음과 같다.

3) Truth table

 명제 파트에서는 논리곱과 논리곱을 배우는데, 이들을 이용한 명제의 진리값은 진리표(Truth table)로 설명할 수 있다. 개별 명제인 으로 이루어진 진리표 는 이 갖는 진리값의 모든 조합을 나열해서 만들어진다.

 T는 참을 의미하고, F는 거짓을 의미하며, 이들의 조합은 의 진리값이다. 우리는 논리합과 논리곱을 정형적으로 정의하기 위하여 진리표를 사용한다.

4) Deductive reasoning

 일련의 명제들로부터 결론을 유도하는 과정을 연역적 추론(Deductive reasoning)이라고 부른다. 가설 또는 전제를 바탕으로 결론을 이끌어낸다.

 수학 및 컴퓨터의 많은 증명들이 연역적 논법을 사용한다고 한다. 모든 논법은 다음과 같은 형식을 갖는다.

                   만약 그리고 그리고 그리고 이면 이다.

5) Disproving a universally quantified statement

 다음 식을 반증(disprove)하는 것은

를 거짓으로 만드는 논의 영역에 속한 하나의 원소 를 찾으면 간단히 이루어진다. 그러한 값을 반례(counter example)라고 부른다.

6) Mathematical Induction

 수학적 귀납법(Mathematical Induction)은 참인 문장 을 증명하기 위한 증명 방법으로 두 단계로 실시된다.

 제일 먼저 이 참임을 보인 다음, 모든 에 대하여 이 참이면 이 참임을 보여준다. 그렇게 되면, 이는 도미노처럼 부터 모든 에 대해서 연쇄적으로 참임이 증명된다.

7) Floor and Ceiling function

 의 바닥함수(floor function)는 로 표시하며, 이 함수가 뜻하는 것은 보다 작거나 같은 최대 정수이다.

 의 천장함수(ceiling function)는 로 표시하며, 이 함수가 뜻하는 것은 보다 크거나 같은 최소 정수이다.

           Floor Function

       Ceiling Function

8) One-to-one function

 일대일함수(one-to-one function), 또는 단사 함수(Injective function)은 정의역에 속한 각각의 다른 원소들을 공역에 속한 각각의 다른 원소로 대응시키는 함수이다. 이를 수식을 통해 나타내면 다음과 같다.

에서 로의 함수 가 모든 에 대해, 인 가 기껏해야 한 개 존재하면 이 함수를 일대일함수 또는 단사함수라고 한다.

9) Inverse function

 변수와 함숫값을 서로 뒤바꾸어 얻는 함수이다. 즉, 에서 로의 함수 가 전단사함수라고 가정한다면, 를 만족하는 함수 를 함수 의 역함수라고 한다.

The function is the inverse of the function

10) Sequences

 수열(Sequence)은 수들의 정렬된 나열이다. 수열의 정의역은 연속된 정수의 집합으로 구성된다. 수열에는 유한수열(Finite sequence)과 무한수열(Infinite sequence)이 있다. 유한수열은 수열의 정의역이 유한한 수열을 뜻하고, 무한수열은 수열의 정의역이 무한한 수열을 뜻한다. 유한수열과 무한수열의 표기는 다음과 같이 표기한다.

          유한수열 : (인덱스가 부터 인 유한수열 )

          무한수열 : (첫 번째 인덱스가 인 무한수열 )

11) Strings

 문자열(String)은 문자들의 유한한 나열이다. 의 문자열은 에 속하는 원소들의 유한 수열이다.

 널 문자열(null string)은 원소가 하나도 없는 문자열을 뜻하고 로 표기한다.

 문자열 의 부분 문자열(substring)은 의 일부 또는 연속된 모든 원소들을 선택함으로써 구해진다.

12) Algorithms

 알고리즘(Algorithm)이란 어떤 문제를 단계적으로 해결하는 방법을 말한다. 알고리즘은 몇몇 특성을 가지는데 다음과 같다.

입력값 : 알고리즘은 입력을 받는다.

출력값 : 알고리즘은 출력을 만든다.

명확성 : 단계들은 명확하게 진술되어야 한다.

결정성 : 각 단계가 실행된 후의 실행 결과는 입력과 바로 전 단계의 결과에 따라 유일하게 결정된다.

유한성 : 알고리즘은 종료한다. 즉 유한한 많은 명령이 실행된 후에는 반드시 끝난다.

정확성 : 알고리즘에 의해 생성된 출력은 정확하다. 즉 알고리즘은 문제를 정확하게  해결한다.

일반성 : 알고리즘은 입력의 집합에 적용된다.

13) Searching and Sorting

 탐색(Searching)은 주어진 데이터에서 특정 데이터를 찾는 것을 탐색이라고 하며, 컴퓨터의 시간 중 많은 양이 탐색에 할애된다고 한다.

 반면에 정렬(Sorting)은 어떠한 특정한 순서로 배열함을 의미한다. 즉, 주어진 데이터를 우리가 원하는 순서로 재배열을 시키는 것을 의미하는 것이다.

 탐색과 정렬 모두 여러 가지 방법이 존재하고, 방법에 따라 시간복잡도 역시 다르다. 따라서 우리가 원하는 방법을 적절하게 사용하는 법을 터득해야 한다.

14) Inclusion-Exclusion Principle

 조합론에서, 포함배제의 원리는 유한 집합들의 합집합의 원소를 세는 기법 중의 하나이다. X와 Y가 유한 집합이라고 가정할 때, 다음이 성립한다.

15) Permutations and number of Permutations

 순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 순열은 정의역과 공역이 같은 일대일 대응이다. n개의 원소의 순서를 뒤섞는 순열의 개수는 n의 계승 n!과 같다. 즉, n 이하의 양의 정수를 곱한 값이다.

16) Recurrence relation

 점화식 또는 재귀식이란 인접한 항들 사이의 관계식을 말한다. 즉, 수열 의 각 항 이 함수 를 이용해서 처럼 귀납적으로 정해져 있을 때, 함수 를 수열 의 점화식이라고 하며, 또한, 수열 는 점화식 로 정의된다고 한다.

 점화식을 푼다는 것은 귀납적으로 주어진 수열 의 일반항 을 의 명시적인 식으로 나타내는 것을 말한다.

17) Bipartite Graph

 이분 그래프는 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다. 이를 수식으로 나타내면 다음과 같다.

(2) State more than 9 things that you know/can/find after you studied the first Chapters.

1) Cartesian Product

 위에 1)에서 배운 내용이라 개념에 대한 추가설명은 하지 않겠다. 데카르트 곱을 통해 배운 것은 곱하는 순서에 따라 원소쌍이 달라진다는 것이다. 예를 들기 위해 위에서 사용한 예를 들고 오겠다. 만약 이고 라 하면 다음과 같다.

이다. 이렇듯 일반적으로 인 것을 보여준다. 따라서 데카르트 곱은 일반적인 곱셈과는 다르다는 것을 알 수 있었다.

 그리고 인 것 또한 알 수 있었다. 그 이유는 순서쌍의 첫 번째 요소로 의 원소를 고르는 방법은 3가지이고, 순서쌍의 두 번째 요소로 의 원소를 고르는 방법은 2가지이기 때문에 이다. 앞의 논법은 임의의 유한 집합 와 에 대하여 성립하므로 즉, 는 항상 참임을 알 수 있다.

2) Rule of Inference

 명제에 대한 추론 규칙은 가설에 따라 결론을 유도하기 위한 여러 방법들을 나타낸 것이다. 우리는 총 7개에 대한 규칙을 배웠고, 이것들을 각각 이해하기 위해서 예시를 통해 정리하였다. (Q&A 게시판에도 올렸음)

1) Modulus Poenens (긍정식 논법)

p→​q     // If it rains, we won't be able to play soccer.

p         // It's raining.

------

∴​ q      // We cannot play soccer.


2) Modulus Tollens (부정식 논법)
p→​q     // If she gets up late, she will miss the train.

~q       // She didn't miss the train.

------

∴​ ~p    // She didn't get up late. 

3) Addition (추가법)
p         // He studies very hard - Let this is true.

------

∴​ p∨q  // Either he studies very hard OR he is a smoker.

Whether 'q'is true or not, the proposition 'p∨q​' is always true!


4) Conjunction (논리곱)

p         // He studies very hard.

q         // He is genius.

------

∴​ p^q  // He studies very hard and he is genius. 

If 'p' and 'q' are two premises, we can use 'Conjunction' rule to derive 'p^q'.


5) Simplification (단순화)

If p^q is a premise, I'm sure this will be not so difficult to understand Simplification rule.

6) Hypothetical syllogism (가설적 삼단논법)
p→​q     // If it rains, we won't be able to play soccer.

q→​r      // If we won't be able to play soccer, we won't need to buy uniforms.

------

∴​ p→​r  // If it rains, we won't need to buy uniforms.

7) Disjunctive syllogism (논리합 삼단논법)
p​∨​q     // The ice cream is either vanilla flavored or chocolate flavored.

~p       // The ice cream is not vanilla flavored.

------

∴​ q     // The ice cream is chocolate flavored.

3) Mathematical Systems

 수학적 체계(mathematical system)는 공리(axiom), 정의(definition), 그리고 정의되지 않은 용어(undefined term)로 구성된다.

 공리는 참이라고 가정한다. 정의는 기존의 개념을 이용하여 새로운 정의를 만드는 데 사용된다. 일부 용어는 명확하게 정의되지 않아서 오히려 공리를 이용하여 정의된다. 수학적 체계 내에서 정리를 유도할 수 있다.

 정리(theorem)는 참이라고 증명된 명제이다. 특수한 유형의 정리로서 보조 정리와 따름정리가 있다. 보조 정리(lemma)는 자신이 참이라는 것 자체는 큰 관심사가 아니지만 다른 정리로부터 쉽게 얻어지는 정리이다. 따름 정리(corollary)는 다른 정리로부터 쉽게 얻어지는 정리이다.

 정리가 참임을 확립하는 논법은 증명(proof)이라고 부른다. 논리는 증명의 분석을 위한 도구이다.

4) More Methods of Proof

 모순에 의한 증명(proof by contradiction)은 가설 가 참이고 결론 가 거짓이라는 가정 아래 를 수립하며, 수학적 체계와 함께 와 를 이용하여 모순을 유도한다.

 대우에 의한 증명(proof by contrapositive)은 특별한 경우의 모순에 의한 증명으로부터 유도된 증명방법으로, 의 모순에 의한 증명이 를 추론하므로 이를 정리한 를 뜻한다.

 경우에 의한 증명(proof by case)은 본래의 가설이 여러 가지 경우로 자연스럽게 나누어질 수 있을 때 사용된다.

5) Strong Form of Mathematical Induction

 강한 형식의 수학적 귀납법(Strong Form of Mathematical Induction)은 참인 문장 을 증명하기 위한 증명 방법으로 두 단계로 실시된다. 이 때 일반적인 수학적 귀납법과의 차이점은, 증명해야 할 문장은 으로 표시한다는 점이다.

 제일 먼저 이 참임을 보인 다음, 모든 에 대하여 만약 인 모든 에 대하여 가 참이면 이 참임을 보여준다. 그렇게 되면, 이는 모든 에 대해서 연쇄적으로 참임이 증명된다.

6) Bijection function

 단사함수이고 동시에 전사함수인 함수를 전단사함수(bijection function)라고 한다. 이를 수식으로 나타내면 다음과 같다.

7) Equivalence relation

 를 집합 의 분할이라 하자. 를 내의 어떤 집합 에 대해서 와 모두 에 속하는 것으로 정의하면, 은 반사적, 대칭적, 추이적이다. 만약 이면 의 멤버들을 관계 의 관점에서 동등하다고 간주할 수 있고, 이러한 이유로 반사적이고, 대칭적이며 추이적인 관계를 동치관계라고 한다.

8) Equivalence class

 관계 을 집합 에서의 동치 관계라고 하자. 모든 에 대해 집합 를 관계 에 대한 에서의 동치 클래스(Equivalence class)라고 한다. 이 때 집합 는   로 정의된다.

9) Matrix of the relation

 행렬은 에서 로의 관계 을 나타내는 편리한 방식이라고 한다.

 의 원소를 (임의의 순서로) 행에, 의 원소들을 (임의의 순서로) 열에 배치하고, 이면 행 열을 1로, 그렇지 않으면 0으로 지정한다.

 이렇게 만들어진 행렬을 관계 R의 행렬이라고 한다.

             Example of the matrix of the relation (from textbook)

10) Big O, Omega, Theta notation

 빅 오, 오메가, 세타 표기법은 알고리즘의 실행 시간이나 실행 공간을 비교할 때 중요한 표기법이다. 이들을 표기할 때는 최고차항의 차수를 바탕으로 표기하며, 이들의 개념을 확실히 알아두어야 나중에 알고리즘에 대한 분석이 편해질 것으로 생각된다.

10) Combination

 조합론에서, 조합은 집합에서 일부 원소를 취해 부분집합을 만드는 방법을 말한다. 그 경우의 수는 이항계수이다. 위의 표와 같은 결과가 도출된다.

11) The Pigeonhole Principle

 비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰인다. 이 원리는 간단한 귀류법으로 증명할 수 있고, 이 증명은 대표적인 존재 증명이다.

12) Some basic infomations about Graph

 그래프는 점과 선으로 그려진다. 여기서 점은 꼭짓점, 선은 모서리를 의미한다. 꼭짓점 에서 시작하여 을 지나, 를 지나, 최종적으로 에 도착한다. 이 때의 경로는 부터 까지이다.

 보다 자세한 용어 설명은 다음과 같다.

1. Power Set

- Power set이란, X라는 집합의 모든 subsets들의 집합을 말한다. 여기서 subset이란 만약 P와 Q라는 집합이 있을 때, P의 모든 원소들이 Q의 원소에 포함될 때 P가 Q의 subset이라고 한다. 즉, Power set이란 X라는 집합에서 가능한 모든 subset들의 집합이란 것을 알게 되었다.

2.Venn diagram

- 벤 다이아그램이란, 시각적으로 집합들의 포함관계를 나타낼 수 있는 가장 직관적인 방법이라고 생각한다. 전체 범위인 사각형안에 집합을 나타내는 원들을 비교하면 쉽게 결과를 도출해낼 수 있기 때문이다. idempotent, associative, commutative, distributive와 DeMorgan’s laws등을 적용시키기에 무리가 없고, 쉽게 이해하게 하는 핵심적인 개념이라 생각한다.

3.Conjunction and disjunction of propositons.

- p와 q가 명제라고 할 때, p∧q에서 ∧는 conjunction of p and q이며, 이는 읽을 때, p and q라고 읽는다. 그리고 p∨q에서 ∨는 disjunction of p and q이며, 읽을 때 p or q라고 읽는다. 이로 인해 명제들의 접속사를 알게 되었고 이를 이용해서 truth table에서 값을 구할 수 있다는 것을 알았다.

4.Truth Table

- 명제의 진위를 판별할 때, 안정적으로 결과를 도출할 수 있게하는 표이다. 이 진리표는 논리 연산을 할 때, 모든 가능한 편성을 열거하고 각각의 조합에 대해 True나 False의 값을 대입한다. 이렇게 표시함으로써 해당되는 명제의 진위를 알기 쉽게 설명할 수 있고 반례를 찾을 때도 쉽다는 걸 알았다.

5.Conditional Proposition(조건 명제)

- 조건 명제는 만약 p와 q라는 명제가 있을 경우 p이면 q이다 라는 것이 조건 명제이다. 기호로는 p->q라고 표현한다. 이 조건 명제가 쓰이는 경우는 정말 많아서 중요한 개념이고, 여기서 명제 p는 hypothesis(가설), q는 conclusion(결론)이라고 정의한다. p->q는 조건연산자로 표현이 가능한데, -p∨q라고 나타낼 수 있다는 걸 알았다.

6.Mathematical Induction

- 수학적 귀납법이라고 불리는 이 개념은 주어진 명제 P(n)이 모든 자연수에 대하여 성립함을 보이기 위해 사용되는 증명법이다. 첫 번째 명제가 참임을 증명하고 P(n)이 참이라면 P(n+1)또한 참이라는걸 증명하면 P(n)은 모든 자연수에서 참이다. 이는 증명법에 있어서 중요한 부분중 하나이며 이로 많은 문제들을 귀납법으로 풀 수 있었다.

7.Rule of inference

- p->q and p are true면 q도 true가 타당하면 이를 Modulus poenens(긍정식 논법)이라고 한다. 이러한 논법도 여러 가지 종류가 있다. p->q,-q가 참이면 -p가 참인 Modulus tollens(부정식 논법)도 있으며, p->q,q->r이면 p->r인 Hypothetical syllogism(가설적 삼단논법)또한 있다. 이러한 Rule of inference는 명제들의 진위들을 판별할 때 상당히 도움이 될만한 정의임을 깨달았다.

8. Quantifiers

- 명제함수 P가 D라는 담화영역안에서 모든 x에 대해서 P(x)이라는 것을 기호로 표기하면 ∀x, P(x)이다. 이것은 universally quantified statement of P(x)이다. ∀x는 모든이라는 뜻이다. 또한, 어떤 x에 대해서 P(x)이라는 것을 기호로 표기하면 ∃x, P(x)이고 이는 existentially quantified statement이며 ∃x는 어떤이라는 뜻이다. 이를 이용해서 명제함수들의 참, 거짓을 판별할 수 있다는 것을 알 수 있었다.

9.gcd(greatest common divisor),lcm(least common multiple)

- 최대공약수와 최소공배수의 개념이다. 최대 공약수는 두수의 약수(divisor)중에서 제일 큰 약수이며, 최소 공배수는 두 수를 곱했을 때 그 값에서 제일 작은 약수를 찾는 것이다. 양수일 때, 최대공약수와 최소공배수를 곱했을 때 두 수의 곱이 나온다는 것을 새롭게 알게되었고, number theory에서 크게 중요한 부분이라는 것이라고 생각했다.

10.One to One function, Onto fuction(injective, surjective)

- 일대일 함수는 단사(injective)함수라고도 불리우는데 함수 f:X->Y에서∀a,∀b∈X에 대해서 f(a)=f(b)이면 a=b가 성립한다.또한 일대일 대응 함수라고 불리는 전사(surjective)함수는 Y의 모든 원소가 함수에 대응한다. 모든 원소 y는 모든 원소 x에서 f(x)=y라고 보면 된다. 함수는 관계를 파악하는데 있어서 중요한 개념중 하나라는 것을 알 수 있다.

◆ Ch. 1    Personal Reflection Note

(1) Do you understand the most of contents of this learning process?

Flipped class is a new way to improve not only participation in class, but also students’ self-understandings. Traditionally, we would listen to lectures in class so that we usually don’t have enough time for direct contact with professors. At first, it was perhaps weird to watch lectures and understand the contents, but I wouldn’t say it was hard because I was so used to the traditional lectures.

Moreover, I have never been in a single class that offers a very active feedback on i-campus, which I really like because of short-time feedbacks from both students and Professor 이상구. Being proactive in both class and i-campus encourages me to increase my performance.

Nevertheless, I would not say the flipped class is everything because Professor 이상구 made so much for the class – his genuine help and feedbacks towards the students were professional and genuine, which I sincerely respect. He has the ability to look through students and thus helping them figure out their weakness or improvement room to be better in every possible way.

(2) What did you learn through the learning activities of this course?

        Specifically, the implementations Professor 이상구 made in class encourage me to learn through the active base of students in both offline and online methods. Indeed, I learnt the Discrete Mathematics concepts thoroughly, but the course helped me gain new methods of studying such as improved self-studying, more direct conversations with Professor 이상구 on both offline and online sites, and significantly better approach to effective and efficient studying.

(3)  What have you learned from other colleagues?

As expected of Korean students, the competitiveness is high, but it doesn’t mean they don’t help each other. I liked the students’ feedback in a quick instant to lend a hand. Even though, we don’t know each personally, I felt their efforts in helping, which is astounding.

(4)  How do you apply newly learned information to real world problems?

Flipped class definitely helped me gain a new perspective to see the simple, but not-that-simple situations. For instance, when I work in a group, we usually tend do stuff in the only times we met. However, implementing this new learning process, our work and performance improved dramatically because we do and learn the stuff by ourselves, and thus each of us approaches the problem differently. Hence, when we meet up, it was marvelous to see such differences in teammates as new perspective, new solutions, and better combined solutions.

(5)  What kind of learning materials have you used to study?

Indeed, textbooks and lecture materials are always used; nevertheless, with the flipped class, I managed to use many sources of information such as recorded lectures. Traditionally, we would not have time to discuss with professors due to the fact that we have to concentrate on lectures and professors’ explanations during the class, so we could not ask questions or think the other way. Therefore, when I listen to lectures online before class, lots of questions or misunderstood concepts came up so that I would be able to make questions and clarify the stuff in class. It enhanced my ability to critically think.

(6)  Self-Evaluation for Q/A Activities.

I registered for the class after week 1, so at first it seemed as if I missed lots of class rules and principles. I missed the opportunity to summarize or review the lectures of first week; however, I thank professor 이상구 letting me make up for them. I was able to catch up with others due to his efforts towards students. I might not have made much efforts in the first 2 weeks, but I have been adjusting myself for the class. I was able to make lots comments with students and help them with my own clarifications that my classmates might have had.

However, I think my efforts are not enough for perfection or at least not up to Professor 이상구’s expectations because I could not make and solve problems in QnA. I would like to improve aspects that are lacking.

Furthermore, I quickly managed myself to adapt the Question and Answer, so I am happy with my recent drastic improvement.

My Score:     9/10.

◆ Ch. 2 Self-Evaluation [Your Opinions]

(1) Satisfaction according to the self-evaluation.

I am greatly grateful for class contents and performance of Professor 이상구. He helped me in various ways to let me improve not only my academic principles, but also self-performance. I was able to gain new perspective towards problems; additionally, I gained a self-discovery, which means I have got to see my what I might spike at.

More importantly, I really thank Professor Lee Sanggu for his excellent methods of teaching and students who are excellent in their own ways. Everyone in the class let me realize that there is always room for growth and improvement.

(2) Sorrow according to the self-evaluation.

Although I am contented with class methods and efforts of others, my performance might have lacked in problem solving due to inadequate number of solved problems. I would like to improve this weakness of mine over the course of class in short period of time. Indeed, I was sort of inactive in the first 2 weeks since I missed the week 1 due to registering for the class late – from week 2. I want to perform significantly better for better efforts for both class and classmates.

However, I don’t regret because even though I was sort of left behind in the first few weeks, now that I am caught up, I am doing pretty well with some amazing classmates I found in the class.

◆ Ch. 3 Colleague who helped your learning

   Name of your classmate: 김찬호, 최세현, 박재형

(1) Reasons to recommend them:

The reason why I am recommending them is not simply because they are my team members, more importantly, they let me strive learning more and made teamwork so much fun. They are the geniuses in the team. As upper-class students, they encouraged me to learn different subjects in other aspects and helped me various ways to get better. I’m extremely happy that I got to join the team and work with them. 김찬호 got the leadership and energy that fuel us to do more. 최세현 and 박재형 are the brains of the team, and they can solve any problem. They made me feel that I have got a lot learn from them, and I really grateful for it.

(2) Your suggestion for them to improve his contributions to others.

They are utterly great at solving and analyzing problems. They all are excellent at what they. I actually don’t know what to suggest them, since I am learning from them. They do everything up to the expectation. I can’t say they should do more than perfection, but they are great, I mean it. I am very grateful to be a team with them.

◆ Ch. 4 Flipped/PBL Action Learning Class Feedback

by Students

(1)  What is the merit/importance/Significance of this PBL class?

The crucial part of the PBL class is to be active in both class and i-campus, therefore, not only it encourages our communication, but does it also improve our teamwork when worked as a group. The individuals’ post, feedback, and replies make a great deal of importance on class activity and learning. Furthermore, compared to traditional lectures where students would listen to lectures in class only concentrating on a professor’s explanation and PPT, in PBL, learn the lectures in-home or before the lectures as a self-study. As a result, we have time to discuss with professors about problems we had on the concepts instead of spending hours listening to professors’ explanation of the lectures and not making useful discussions in class; therefore, there not adequate time of direct conversation between students and professors. Ultimately, PBL encourages students’ teamwork, communication, problem-solving skills and self-studying.

(2)   What do you want to improve this PBL system?

I would like to increase the number of discussions in class with many students because PBL requires lots of time to study on their own views; therefore, the professor should sharpen the students’ thoughts and understanding. Nevertheless, I think Professor 이상구 is abundant in that aspect because there is much time for discussion in the beginning of the class and during the class, which the students need the most in my opinion.

...

5-1. 본 수업을 통해 자신이 습득한 자기 주도적 학습 기술을 구체적으로 설명하시오.

        What skills that you learned while you studied in the process of mathematics (PBL-Active Learning),?

우선 이 수업을 들으며, 혼자 열심히 자료를 찾아서 공부하는 습관이 생겼다. 누군가의 질문에 답변을 하려면, 수업시간에 배운 지식이나 자료로는 답변하기 힘든 경우가 많다. 이럴경우 혼자 검색을 해서 여러 방대한 자료중 추출해서 나에게 필요한 내용만 습득하고, 공부하는 습관이 생겼다. 그리고 flipped class 이기 때문에 수업 전 preview 즉 예습이 매우 중요하다. 나는 이 수업을 들으면서 위 두 과정을 성실히 수행해서, 자기주도 학습 능력이 많이 상승되었다.

      온라인 lab 홈페이지를 통한 주도적인 예 복습, 모르는 부분이 있을 시 동료들에게 질문을 하고 답변 할 수 있는 QnA공간 활용, 끝까지 이해가 가지 않을 경우 icampus 강의를 다시 들으면서 복습.

먼저 학습할 내용을 예습하면서 어느 부분이 약한지 체크할 수 있었다. 약한 부분을 위주로 수업을 듣고 나서, 더 모르겠으면 Q&A 게시판을 이용하여 질문하고 답변을 얻었다. 이미 아는 내용은 타 학생들이 올려준 질문에 답변을 달아주면서 개념을 더 확실히 하였다. 관련 문제를 풀어보며 내용 습득 여부를 다시 확인해 볼 수 있었다.

 항상 강의를 보면서 교수님이 말씀해주신 내용에만 집중했지, 능동적으로 내가 강의 내용을 요약하고 설명하는 일은 해보지 않았다. 그러나 이 이산수학 강의에서는 능동적으로 내가 참여해서 요약하고 남의 의견을 수정해주는 일을 하는 등 주도적으로 학습에 참여할 수 있었다.

12-1. 본 수업과정에서 자신이 참여한 활발한 의사소통을 구체적으로 설명하시오.

제가 qna에 참여했던 부분중 가장 discussion 이 활발 했던 qna하나를 저는 가장 중요한 contriution이라고 생각합니다. 그 부분은 다음과 같습니다.

우선 이 질문은 최세현 학생이 질문 한 내용으로 같은 문제로 여러번의 질의 응답을 했습니다. 이게 첫 질문이고 최세현 학생과 discussion 하면서 최세현 학생의 추가 질문도 있었습니다. 이에 저는 모든 질문과 답변을 공유하며 최종적으로 finalize했습니다.

     학우들이 필요할만한 지식을 공유하였다. 또한, 문제를 풀고 공유를 하였고, 다른 학우의 질문에 응답해 주는 등, 활발한 활동을 하고자 노력하였다. 그리고 팀에서 맡은 역할을 제대로 수행하였고, 온라인/오프라인 가리지 않고 팀과 소통하고자 노력하였다

QnA를 통해서 모르는 문제를 질문했고, 남이 모르는 것들을 답변했으며, 요약한 내용중에 잘못된 내용을 수정하면서 의사소통을 했다.온라인 QnA를 통해 질문과 답변을 하고 다른 동료들의 궁금증이나 미비점을 파악하고 깊이있는 심화 학습을 할 수 있었다.

14-1. Flipped/PBL 방식의 수업에서 효과적이었다고 생각되는 부분을 구체적으로 설명하시오.

         State some part that helps you by the learning process of  PBL/Active Learning /Flipped learning.

우선 우리가 아는 일반 강의에 대해서, 항상 교수님의 강의와 문제풀이 그리고 과제 시험같은 동일한 과정을 거치는 강의는 수동적인 강의이고, 보다 미리 예습을 통해 배울 내용을 공부하고 qna를 통해 공유하고 같이 성장해나가고, 수업시간에 다같이 이야기를 많이 하며 공부하는 것이 훨씬 더 능동적인 강의입니다. 본인의 의지에 비례해서 실력 향상이 많이 되는 것 같습니다. 학생의 능동적인 학습 능력을 향상시켜 주고 또 교우들과의 협업이 강조되기 때문에 PBL class의 중요성을 역설하기엔 충분한 것 같습니다.

        이 Flipped방식의 수업은 정말로 내가 공부를 해야 강의가 진행되는 느낌을 제대로 받는 수업방식이다. 강의를 시작하기 전에 공부를 하게 되고, 이는 정말 학습 효과가 대단하다고 생각한다. 또한 PBL은 작성하면서 내가 지금까지 해왔던 것들을 복습하게하는 효과가 있다고 생각한다.   우선 내가 모르는 내용을 알고 갔기 때문에, 어느 부분에 더 가중치를 둬서 수업을 들어야하는지 알 수 있었다. 또한, 서로간의 질의응답을 통해 더 나은 결과를 도출할 수 있었던 것 같다. 이러한 점이 이 수업에서 효과적인 부분이라고 생각한다. 뿐만 아니라 Q&A 게시판을 활용한 자발적 참여 유도 역시 훌륭한 방식이었다고 생각한다. 신선하고 즐거운 수업이었다. 학생들에게 적극적으로 수업을 이끌어나갈 수 있도록 질문 답변의 장을 마련했다는 것은 굉장히 획기적이라고 생각합니다. 오프라인으로 만나면 어색한 사이인 학우분들과 온라인 상으로 만나 서로 어색한 부분없이 자신이 가진 생각을 올리고 다른 학우분들과 공유하여 이 수업을 듣는 모든 학우분들에게 시너지 효과를 불러 일으킨다.

19. What is the merit of PBL system?

우선 여러 교우들과 질문과 답변을 공유하며 그 부분으로 부터 실력 향상이 가장 원하는 부분입니다. 이건 다른 학생들도 다 같을 것입니다. 여기에 저는 또다른 장점을 설명 드리고 싶습니다. 이 수업은 물론 컴퓨터 공학 소프트웨어에 가장 필요한 과목일 수 있지만 여러 타 과 학우분들도 많은 것으로 알고, 또한 타국 학생도 많은 것으로 알고 있습니다. 이 학우들과 여러 의견공유를 통해 친분을 맺고, 앞으로 학교생활하면서 모르는 부분을 서로의 major에서 잘 답변하고, 이산수학 수업이 끝나고 그 후에도 항상 서로 서로 도움이 되는 infra를 만들고 싶습니다.

20. 이 수업에서 보완해야 할 점은 무엇이라고 생각합니까?

       What can you suggest to improve this system of learning?

        지금 껏 받아온 강의시스템과는 크게 다른 획기적인 시스템이기 때문에 학생들이 이에 맞춰 적응하고 잘 수강 할 수 있도록 처음에는 예시를 많이 주는 것이 좋다고 생각합니다. 예를 들어 Example내 문제들을 모든 학생들에게 겹치지 않게 준 다음 QnA에 올리도록 하면, 모든 학생들은 자신이 푼 한 문제 뿐 만 아니라 다른 학생들이 풀은 문제들의 해결방법도 알게 됩니다. 그저 학생들이 문제를 풀어 올리길 기대하기 보다는 이런 식으로 가이드라인을 잡아주는 것이 시작부터 활발한 QnA를 이끌지 않을까 합니다.

또한 팀 방식은 정말 좋은 아이디어라고 생각하는데, 강의 시작 초기부터 팀과 팀원들을 할당하는 편이 더 좋을 것 같습니다. 팀 단위로 자유로운 QnA토론 분위기가 형성되어 빠른 적응을 할 수 있을 것 같습니다.

flipped class 이기 때문에 수업에서 얻어가는 양도 굉장하지만, 미리 준비가 되어있어야 어느정도 수업에 따라갈 수 있습니다. 그 것이 유일한 flipped class의 단점이라고 생각하지만, 본 수업은 수업 전 교수님과의 소통과 학습의 문이 자유롭게 열려있기 때문에 문제없이 진행할 수 있었습니다.

 수업에서 보완할 점으로는 강의 시간에는 QnA 내용을 직접 보면서 하나하나씩 교수님이 설명해주시거나 학생들이 올린 QnA자료에 교수님의 의견을 다시 한번 말씀해주시면 더 의욕을 받고 열심히 하지 않을까 생각해본다. 물론 지금도 QnA를 정말 많이 확인해주시고 final된 부분을 강의 시간에 설명해주시고 계시므로 딱히 보완할 점은 아니라고 본다. 또한, 조끼리 모여서 자신들이 올린 QnA내용을 서로 확인해보면 어떨까 생각해본다.

Open Feedback : Please leave any general comments and suggestions that will help improve this class in the future, including what you liked and did not like about this class. [FREE RESPONSE BOX]

Briefly describe your contributions through Q&A for yourself and fellow students in our "DM" classes!

Quantity : 137

I strive making as many comments on problem as I can make to clarify the solution so that not only I, but also the other students will find it much easier to understand. I usually finalize problems so that the clarification I made in them should make the solutions simpler to grasp. I enjoy asking interesting questions so that the students would find the class more engaging, since Mathematics is not all about solving problems.

Ultimately, I believe the beauty of Mathematics is that there is only one determined answer to a question.

-    Check your participation numbers in QnA for each week (Saturday to Friday):

(​Total=137 Entries)                Q: 8     A: 129

■ Number of online attendances:        (    85     ) / (     85     )   (1-15week)

   Off-line attendance:             (      25    ) /  (     25    )     (1-15week)

   Absences:    0.

Online Lecture Participation (온라인 출석 회수):  (1-15th week)

Full attendance

Off-line Lecture Participation/ Absence (오프라인 출석  / 결석  회수) (1-15th week)

Full attendance (Excluding Week 1, midterm week, and public holidays in which I was not registered)

Part 2: Participation Part (New Form)

Fill in the below for your self-assessment and your project/term paper.  (20 points/100)

A. (Quantity 10pts) Briefly describe your contributions through Q&A for yourself and fellow students in our "DM" classes! 

...

(2) What you contributed through this course (Q & A and/or In-class):

이 수업을 들으며, 항상 다른 학우보다 더 많은 Qna 를 작성했고, 발표도 다른 학우 보다 더 많이 한 것 같다. 총 161개의 Qna 를 작성했다.

 (3) (5 pt) What is your most important contribution or founding that you shared with others in QnA.(Quality)

To my mind, my most important contribution that I shared with others was:

1)  우선 팀 프로젝트를 진행하며, 다른 팀원들의 활동을 앞장 서서 수정해 나갔고, 더 좋은 프로젝트 결과물을 만들어 내기 위해서 노력했습니다.

2)  만약 제가 Qna 답변을 달았지만 질문한 학우가 정확한 이해를 하지 못했다면, 최선을 다해서 계속 답변을 달아 주었습니다.

(4) Number of Final OK by SG Lee Problems (and/or Completed Discussion/Question) in Q&A that your name is included:   ( 101 )       

 B. (Quantity 10pts) Quality of Your Participation: 2

     (1) Write what you especially remember while you are doing A-1, 2, 3.

우선 저는 아무래도 첫번째 과제를 할 때가 가장 기억에 남습니다.  그 당시 어떻게 PBL report를 쓸지 , 교수님이 바라는 바가 무엇인지 정확히 알지 못하였고, 저도 많이 헤맸던 기억이 납니다. 지금은 이번 학기 열심히 수강해서 보다 정확한 PBL report를 작성할 수 있게 되었습니다. 감사합니다.

    (2) What did you learn or feel while learning DM (Action Learning/PBL) with your classmates?

우선 저희 이산수학 수업의 학생들 모두 Qna 에 열심히 참여했습니다. 그 과정을 통해 저도 많이 배우고, 많이 질문하고, 다른 학우들의 궁금점에 많이 답해 주었습니다. 참 보람찬 시간이었습니다.

    (4) Write names of YOUR PBL Team members and Team Leader.

Team Leader:  김찬호

Team Members:  최세현, 박재형, 담딘바자르

(B4) (Tentative) Project (Title/ 1^stDraft/Final)

 What is your project (and In-depth study) and your role in your Team (Leader, Idea, Solve, Prove, Coding, Typing, Presentation etc.) 저는 Team Leader이고, 저희 Team은 derangement에 대한 주제를 받았습니다.

Role:  저는 Presentation과 Idea, Prove를 맡고 있습니다.

2장. 참여 부분 (New Form)   - 중간고사 20점 부분

       자기 평가와 본인의 Project (Term paper) Proposal 에 대해 아래를 채우시오.

1.  (20점) 본인이 그간 Q&A,  동료학생, “DM"강좌 등에 기여한 내용을 간단히 서술하세요!

  (1)  QnA 참여 회수 <QnA에서 직접 확인하세요> : 각 주별 (토요일에서 금요일) 

● 1주차 : 총  2  회,  2주차: 총  4  회,  3주차: 총  4  회,  4주차: 총  9  회

● 5주차 : 총  2  회,  6주차: 총  7  회,  7주차: 총  13 회,  8주차: 총  9  회

● 9주차 : 총  10 회,  10주차: 총  14  회,  11주차: 총  13  회,  12주차: 총  9  회

● 13주차 : 총  2  회,  14주차: 총   0  회,  15주차: 총   5  회.

                            총   103   회  (질문:  10   회,  답변/수정:  60  회) 

● 온라인 출석 회수 :   85  회  /  85  회  

● 오프라인 출석 및 결석 회수 : 26 회  /  0  회 

                            총    83 회  (질문:    5  회,  답변/수정:  78 회) 

● 온라인 출석 회수 :   82 회   

● 오프라인 출석 및 결석 회수 :   26 회  /   0 회  

(2) 본인이 본 강좌를 통하여 기여한 내용

      1. Q&A에 올린 좋은 본 강좌 및 관련 또는 기타 유의미한 정보 개수 ( 14 개)

      2. 본인이 토론을 정리하여 마무리한 (누군가 제목에 Final 표시한) QnA 내용에 자신의 이름이 포함 된 것 (   55  개)

   1, 2 중에서  특히 기억나는 내용 : 학기 초반에 한 학우분이 소수인지 아닌지 판별할 때 왜 소수로만 나눠주냐고 물었다. 그래서 한글로 답변을 해주었는데 이해가 잘 된다고 고맙다는 답글을 달아주셨다. 하지만, 외국인 학생은 그 문제에 대해 답을 이해할 수 없다는 의견을 제시해주었다. 그래서 영어로 번역해서 답글을 달아주었고, 다른 학우 역시 내용을 추가해서 번역하여 답글을 달아주어 그 외국인 학생 역시 이해가 되었다고 고맙다고 댓글을 달아주었다. 이 문제를 통해 Q&A 게시판이 정말 활발하게 돌아간다는 것을 느꼈고, 신선한 경험이여서 특히 기억에 남는 것 같다. 다른 학생들의 요약들을 하나로 정리하여 요약문을 만들었는데, 다른 학생이 그 요약문을 다듬고 고쳐 훨씬 좋게 만들어 완성했다, 완성된 요약이 전체적으로 훨씬 발전되자 같이 협력하여 멋진 작품을 만드는 경험을 한 것 같아 기뻤다. 또한 다른 학생의 문제 풀이 솔루션을 직접 마무리하기도 해보았는데, 다른 학생들과 협력하여 솔루션을 발전시키고 다듬는 과정에서 자연스럽게 공부를 할 수 있어서 좋았다.

<1번>

1) 1번에서 HLT (Horizontal Line Test)의 글을 PIRAN CACI 학우가 다른 학우분들과 공유하기 위해 올렸었는데. 저는 HLT와 비슷한 원리를 이용한 VLT를 알고 있어서 다른 학우분들과 공유를 하기위해서 답변에 추가 하였습니다.

2) 1번에서 4단원 Algorithm 단원에서 배운 Bubble Sort의 개념과 Time-Complexity에 관한 글을 어떤 학우분이 올리셔서 제가 알고 있는 지식과 수업을 진행하며 배운 내용을 댓글로 작성하였고 그 글이 토론의 장이 되어 제가 알고 있는 것 보다 더욱더 많은 단원을 배울 수 있게 되었습니다.

3) 1번에서 4단원 Algorithm 단원에서 배운 Time-Complexity과 Recursive 함수와의 연동성을 묻는 학우분께 Recursive함수의 장단점에 대해서 올 적이 있었습니다. 소프트웨어를 전공하면서 재귀함수를 다루는 것은 능숙하다고 생각했지만, 학우분께 답변을 해드리기 위해 재귀함수에 대한 정보를 찾던중, 제가 몰랐던 정보들도 많이 알 수 있었습니다.

4) 1번에서 4단원 Algorithm 단원에서 배운 Sorting 단원에서 Bubble Sort에 관한 글을 올린 학우 분이 계시길래, Bubble Sort와 Quick Sort를 비교하는 댓글을 단 적 있습니다.

Bubble Sort는 정확하지만 빠르지 않는 것에 비해 Quick Sort의 Time-complexity는 Bubble Sort보다 작지만 안정화 되지 않은 Sorting 방법인지 그 때 알게 되었습니다.

5) 저희 Team 2중 학우 한분이 Recursive Function에 대한 C코드를 올렸는데, 그중 일부분이 C코드가 아닌 부분이 있는 것 같아 알려드렸습니다

6) 저희 Team 2의 연구 과제중 Recursive Algorithm 단원에 있는 Hanoi Tower에 대한 C코드를 올려 참고하여 공부가 되도록 하였습니다

7) Recursive Function 단원에서 수업 자료에 나와있는 하노이 타워외에 Binary Search 을 Recursive Algorithm 을 이용한 C코드를 올려 참고하여 공부가 되도록 하였습니다

8) Chapter 8 수업 자료에 나와있는 하이퍼 큐브에 관한 내용을 찾아보고 정리하여 Team 2 학우분들과 정보 공유를 했습니다.

<2번>

1) 제가 4단원에서 배운 Euclidean Algorithm 에 대하여 한진수 학우분이 올린글에제가 아는 정보를 추가하여 댓글을 단적이 있습니다. 제가 댓글을 달고나서 다른 학우분들이 댓글을 달아주셔서, 모든 댓글을 총합하여 제가 Finailze를 해서 글을 올렸습니다. 다른 분들의 정보를 모두 통합하여 Finalize 하는 과정을 하면서 제가 모르는 내용을 저의 지식으로 만들 수 있었습니다.

2) 소프트웨어를 전공하고 있는 저로서는 Algorithm에 대하여 깊게 다뤄보는 4단원에 대해 흥미가 많았습니다. 따라서 저는 4단원을 제가 다른분들 요약한 것을 모두 합하여 Finalize 해보고 싶었습니다. 따라서 제가 다른분의 4단원 요약본을 참고하여 Finalize 하였습니다. Finalize 하는 도중에 놓친 내용은 다른 학우분이 Refinalize 해주셔서 제가 무엇을 놓쳤는지 알 수 있었습니다.

3) 이승원 학우님과 김두원 학우님이 5.2 단원에 대해서 요약하는 글을 작성하셔서 제가 시스템 프로그래밍을 배우면서 알게 된 지식을 추가하여 Finalize 했던 경험이 생각납니다. Finalize 하면서 제가 여태 배웠던 내용을 다시 되집어 볼수 있었습니다.

4) 현재 Chapter 9를 향하고 있는 시점에서 양세중 학우님이 Chapter 1의 Exercise 문제를 Solved 해서 올리셨길래 다른 학우분들로 하여금 복습하는 차원에서 Comments를 달아 정리 하였습니다.

5) 김도훈 학우님 께서 Chapter 8 p 396 Question 21번 Graph 문제를 Solved해서 올리셨길래 Path, Simple path, Cycle, Simple Cycle 에 관한 Definition을 정리해서 Team 2 학우분들과 공유했습니다.

6) 주박우 학우님 께서 Chapter 8.2 p 398 Question 75번 문제를 Solved해서 올리셨길래, 주박우 학우님의 풀이 말고 수학적 귀납법으로도 접근할 수 있다는 점을 다른 학우분들과 공유하였습니다.

7) Team 2 학우들이 Chapter 5에 Division에 관한 문제를 Solved해서 올려주셨습니다. 문제를 푼 방법은 정확해서 문제 해결 방식에는 추가할 것이 없었지만, Division에 관한 내용을 정리하여 다른 학우들이 내용 정리에 도움이 될 수 있게 Comments를 달고 Summary를 하였습니다.

8) Team 2 학우들이 Sorting Algorithm중 몇 개의 중요한 Sorting방법을 알고리즘 설명과 C언어 코드를 같이 정리하여 올렸습니다. 저는 각자 따로 정리한 것을 한눈에 보기 편하기 위해 제가 작년에 자료구조 개론 수업을 들으면서 정리해 놓은 내용을 저희 팀 멤버분들이 정리해 놓은 것에다 추가를 하고 중요한 Sorting Alorithm을 한번에 모아 정리하여 Finalized 해서 QNA에 올려 다른 학우들과 공유 했습니다.

9) Team 2 학우들이 GCD & LCD 에 관한 문제를 Solved 해서 올렸습니다. 문제에 나와있는 숫자 들과 문제 풀이 방식은 정말 간단하고 정확하게 풀어주셔서 더 이상 풀이에는 손댈 것이 없지만, 다른 문제가 출제되었을 때, 또는 GCD 와 LCD의 관계가 나타나져 있는 식을 다시 상기 시켜드리기 위해서 문제 풀이와 저의 Comments를 추가하여 Finalized 과정을 거쳐 학우분들고 공유 하였습니다.

10) Team 2의 김은민 조장님 께서 Binary 숫자를 Decimal로 Decimal 숫자를 Binary숫자로 변환시키는 문제를 Solved해서 올려주셨습니다. Binary 숫자를 Decimal로 바꾸는 방법은 2가지가 있어서 김은민 조장님께서 사용하신 방법 이외의 방법을 저의 Comments로 추가하여 Finalized 하였습니다. 또한 Deciaml 숫자를 Binary 숫자로 바꾸는 것은 MSD LSD와 연관성이 있어 이러한 연관성과 계산하는 방법을 서술하여 Finalized 했습니다.

11) 위의 문제와 비슷하게 이번에는 Team 2 멤버중 한명이 16진법을 10진법으로 바꾸는 방법과 10진법을 16진법으로 바꾸는 문제를 Solved해서 올려주셨습니다. 저는 저의 Comments에 추가 설명과 그림을 추가하여 학우들에게 한눈에 쉽게 이해할 수 있게 Finalized를 하여 올렸습니다.

12) Prim Algorithm 과 MST의 관계에 대한 질문을 학우분께서 올려주셨고, 다른 학우분이 연관성에 관해 올려주셨습니다. 저는 그 답변에 추가로 Prim Algorithm 에 대한 설명과 MST의 정의에 입각하여 왜 MST 는 Prim Algorithm으로 구현이 가능한지 정의와C코드를 통해 Finalized 했습니다.

 (3) 동료와 같이 본 강좌를 (Action learning) 학습 하면서 배우거나 느낀 점은?

        수학적 정보를 공유하는 방향으로는 많이 참여하고 있지만 아직 토론에 참여하여 저의 의견을 올리는 것에는 아직 미흡하다고 다른 동료에 비해 미흡하다고 생각합니다. 하지만 제가 이해하지 못하는 부분이나 어려운 부분들을 다른 동료분들이 자신의 지식을 많이 공유를 해주셔서 많은 도움이 되었다고 생각하고 저도 앞으로 다른 동료분께 도움이 될수 있게 조금더 열심히 하려고 합니다!

  QnA에 꾸준히 참여하는 것이 지속적으로 압박되고 걱정이 많았는데 동료들과 문제에 대해서 토론하고 요약문을 올리며 공부를 서로 도와가면서 할 수 있게 되어 좋았다. 앞으로 이러한 Action learning 강좌에 대해서 긍정적이게 된 것 같다. 다들 열정적으로 수업에 임하는 모습을 보고 많은 것을 생각할 수 있었다. 예습과 복습이 중요하다는 사실을 다시 한 번 깨달을 수 있었고, 집단지성의 위대함을 느낄 수 있었다. 내가 생각하지 못하고, 내가 배우지 못한 부분을 다른 학우들이 채워주고, 또, 그들이 부족한 부분을 내가 채워줌으로서 전반적인 실력향상을 기대할 수 있었다. 남은 강좌도 열심히 해서 더 알찬 수업을 만들어나가면 좋겠다!

2.  Talk about your Team Final Project 1 (& Project2)

 우선 프로젝트 1은 chapter 5에 대해서 정리하고, 관련 문제를 푸는 것으로 이루어져 있다. 앞에서는 개념을 정리하고, 뒤에서는 5단원에서의 몇몇 문제를 풀어보았다. 여기서 여러 기법을 사용하며 문제를 풀기도 하였다.

 프로젝트 2는 최대공배수를 찾는데, 코드로 구현해보고자 했다. 이 때, 재귀를 쓸 때와 안 쓸 때의 차이를 알아보고자 했다. 파이썬을 사용하여 코드를 짜보았다. 두 개의 결과 값을 비교해보았고, time complexity도 비교해보았다. 결론적으로는 재귀적으로 짠 코드의 time complexity가 더 좋았다.

Ch 3.   Your PBL Participation (참여 부분) 

Part 1:   수업 내용 관련하여 답변을 얻은 일반 유의미한 질문들 [Part 1: Your meaningful questions in QnA which you had you got the Final answer.]

1. Question about prove.

Chapter 3. Summary

Original Post or Solved by: Thygeson(2019.3.25.)

Revised by: 담딘바자르(2019.03.25.)

Final by: 김찬호(2019.09.26.)  Final Ok by SGLee

Reference : Discrete Mathematics, Richard Johnsonbaugh, Seventh Edition

           http://matrix.skku.ac.kr/2018-DM/DM-Ch-3-Lab.html

​

 Sequences are ordered lists and can be described by a function like C(n) = 5(n-2). Sequences can either be infinite or finite, defined by the function's individual domain. Two important types of sequences are increasing and non-increasing. We can also use the terms decreasing and non-decreasing. Note that a function can be both decreasing and non-increasing, or both increasing and non-decreasing. For instance, the sequence:

{34, 23, 23, 15, 15, 4} is ​not ​decreasing, but rather non-increasing.

(23과 15가 같은 수가 연속으로 나와서 decreasing이라고 정의 할 수 없습니다.)

A subsequence is a sequence that can be created from another sequence by deleting some elements, but without changing the order. For example, {12, 14, 40, 67} and {12, 80} are subsequences of {10, 12, 14, 40, 67, 80}.

(subsequence란 순서를 바꾸지 않은채 원소를 삭져하면서 만들어지는 부분집합의 개념입니다.)

We also learnt the big sigma and big pi denotion of representing the sum or the product of a sequence, respectively.

sigma와 pi의 연산과정을 조금더 이해하기 쉽게 수업 자료를 보면,

​sigma 연산을 하게되면 sequence 한 a​n​에 대하여 일련의 덧셈연산을 진행하게 되고, pi 연산을 하게되면 일련의 곱 연산을 진행하게 됩니다.

 A string is an finite sequence of characters. A string can be created by using values from a finite set of characters. For instance we can define the set X = {a, b, d, t, i, g} => we can obtain the string "digit". A substring is a sequence of consecutive characters in a string. A substring of "digit" is "it".

(string이란 어떤 문자의 유한한 연속입니다)

If a = "aabbbcd", |a| = 7 denotes the length of a. a[2] = "b", as we use zero-indexing. If we in addition have b = "ffg", ab denotes the concatenation of a and b, ab = "aabbbcdffg"

The string with no elements is the null string. is null string.

Relations

Relations are relationships between 2 or more sets and their objects that related to each set.

If X = Y, we call R a (binary) relation on X. : A function from X ×X to X is a binary operator on X . A (binary) relation R from a set X to a set Y ⇒​ xRy.

Moreover, A digraph is represented by two letters. The informative ways to picture a relation on a set is to draw its digraph -- Directed Graph. The number of vertices in the graph is equal to the number of elements in the set from which the relation has been defined. For each ordered pair (x, y) in the relation R, there will be a directed edge from the vertex ‘x’ to vertex ‘y’. If there is an ordered pair (x, x), there will be self- loop on vertex ‘x’.​

relation 부분에서 중요하다고 생각되는 부분인

symmetric과 antisymmetric의 설명이 필요합니다. 이 부분 설명을 위해 제가 qna에 올린 이부분에 대한 설명을 인용하겠습니다.(asked by 최세현,reply by 김찬호)

symmetric이란 X의 원소 (x,y)에 대해서 (x,y)가 R에 포함될때 (y,x)역시 R에 포함 될때 정의되고,

antisymmetric이란 X의 원소 (x,y)에 대해서 (x,y)​가 R에 포함되고, (y,x)역시 R에 포함될때 x와 y가 같으면 antisymmetric이라고 정의합니다.

Comment by 김찬호:

Speaking of the concepts, they are becoming more and more related to Computer Science studies, as they are fundamental studies of CS. The relations are directly connected my other class, so I am keen to learn more of it.

****

4.1 Algorithms

​Principles of Algorithms:

Input : An algorithm has input values from a set.

Output : From each set of input an algorithm produces output from a set. The output values are the solution to the problem.

Definiteness : The steps of an algorithm must be defined precisely.

Effectiveness : It must be possible to perform each step of an algorithm exactly and in a finite amount of time.

Finiteness : An algorithm should produce the desired output after a finite number of steps for any input in the set.

Correctness : An algorithm should produce the correct output values for each set of input values.

Generality : The procedure should be applicable for all problems of the desired form, not just for a particular set of input values.

​Pseudocode: Pseudocode is an informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a normal programming language, but is intended for human reading rather than machine reading.​

​4.2 Examples of Algorithms

Linear Search:

​A linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.​

Binary Search:

 Binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.​

binary search algorithm에 대해 설명을 하겠습니다

처음에 어떤 배열이 주어졌을때 i=0, j=len(배열의길이)로 설정하겠습니다.

우리가 원하는것은 x라는 원소가 배열 몇번째에 위치해있는지 아는 것 입니다.

처음에 mid라는 변수 하나를 설정합니다. mid는 (i+j)/2입니다.

우리가 원하는 x라는 원소가 mid 보다 아래쪽에 있는지 위 쪽에 있는지 확인합니다.

만약에 밑에 있으면 j=mid로 설정하고 다시 mid값을 (i+j)/2로 합니다

        위에 있으면 i=mid+1로 설정하고 mid값을 (i+j)/2​ 로 설정합니다

이런식으로 계속 범위를 반씩 줄여 나가며 원하는 값의 위치를 찾는 알고리즘 입니다.

( quoted from

https://medium.com/@jsh901220/toy-problem-%ED%92%80%EA%B8%B0-binarysearch-f50ffb19573f)​

(quoted from my qna)​​

Searching algoritm's one is binary search.

● THE BINARY SEARCH We will now consider another searching algorithm.

This algorithm can be used when the list has terms occurring in order of increasing size

(for instance: if the terms are numbers, they are listed from smallest to largest; if they are words, they are listed in lexicographic, or alphabetic, order).

This second searching algorithm is called the binary search algorithm.

And one of algoritm's is sorting algoritm.

Sorting:​

A sorting algorithm is an algorithm that puts elements of a list in a certain order. The most frequently used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the efficiency of other algorithms which require input data to be in sorted lists.​

Sorting is putting these elements into a list in which the elements are in increasing order. For instance, sorting the list 7, 2, 1, 4, 5, 9 produces the list 1, 2, 4, 5, 7, 9. Sorting the list d, h, c, a, f (using alphabetical order) produces the list a, c, d, f, h. An amazingly large percentage of computing resources is devoted to sorting one thing or another. Hence, much effort has been devoted to the development of sorting algorithms.

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent pairs and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.​

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

● Sorting

 Sorting is putting these elements into a list in which the elements are in increasing order.

Sorting is putting these elements into a list in which the elements are in increasing order. For instance,

sorting the list 7, 2, 1, 4, 5, 9 produces the list 1, 2, 4, 5, 7, 9. Sorting the list d, h, c, a, f (using alphabetical order)

produces the list a, c, d, f, h. An amazingly large percentage of computing resources is devoted to sorting one thing or another.

Hence, much effort has been devoted to the development of sorting algorithms.

● The Bubble sort is one of the simplest sorting algorithms, but not one of the most efficient.

 Time and Space Complexity for Algorithms

While analyzing an algorithm, we mostly consider time complexity and space complexity. Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input.​

Finiteness

 An operating system never terminates

Determinism

 Algorithms for multiprocessor machine or distributed environment are rarely deterministic

Generality or Correctness

 Many practical problem are too difficult to be solved efficiently

​4.3 Analysis of Algorithms Problem

​Useless program for certain type of input even though derived from a correct algorithm

  the time needed to run the program is too big or

  the space needed to hold the data is too big.

For Example,

 a set of  elements some elements are labeled 'red', some labeled 'black'.

Find the number of subsets of  that contain at least one red item.

Since a set that has  elements has  subsets, the program would require at least  units of time to execute.

What if  is very big?

Summary of 최세현:

4.3에서 알고리즘을 측정하는 방법에 대해 배웠습니다.

n개의 데이터를 연산할때, 시간복잡도를 f(n), g(n)으로 표현하는 것을 알게되었고,

가장 최악의 상황, 최선의 상황, 평균적인 상황일때의 시간복잡도를 서로 다른 기호로 표기하는 방법을 배웠습니다.

보통, 알고리즘의 시간복잡도를 판단할 때 빅-오 표기법을 이용해 최악의 상황에서의 시간복잡도를 측정하고, 비교합니다.

Summary of 담딘바자르:

As Algorithms is one of the fundamental concepts of Computer Science, we, Software Engineer students or related fields students are fairly familiar with the concept. Algorithms we use in Discrete Mathematics is used the same way; however, it's usually used like Pseudocode. Sorting is the crucial part of algorithms due to its space and time complexity. As for as I know, quick sorting is the most efficient sorting in most cases, in case someone wonders. On the other hand, bubble sort is the worst in case of time complexity. I haven't taken the Algorithm course, but Algorithm concepts in Discrete Mathematics make me itching for its applications in both CS and DM.​​

Furthermore, it's recommend to review Big O notation, Omega notation, and Theta notation for thorough understanding of time complexity of Algorithms.

Summary of 김찬호:​

4.1, 4.2를 배우며 직접적으로 나의 전공인 컴퓨터 공학의 프로그래밍에 직접적인 연관이 있는 알고리즘에 대해 배우게 되었다. 우선 기본적인 linear search, binary search에 대해 복습 하게 되었고, 기본적인 sorting알고리즘에 대해 다시 한번 공부하게 되었다. 이부분에서 매우 흥미를 느끼고, 프로그래밍에 흥미가 많은 나로서는 이 단원에 대해 공부하는게 재밌었다.

binary search : 간단히 소개하자면 배열의 첫번째 index 와 마지막 index의 중간값을 검사를 진행하며 바꿔나가며 검사해야할 배열을 줄여나가 결국 target을 찾게되는 search방법이다.

bubble sort: 배열의 첫번째 값부터 마지막값까지 하나씩 계속 비교를 하면서 가장 큰 값을 혹은 가장 작은 값을 마지막 인덱스에 넣는다. 다시 검사를 진행하면서 결과적으로 모든 배열이 오름차순 혹은 내림차순으로 정렬이 된다.

또 프로그래밍의 중요한 부분인 time complexity를 구하는 방법을 배우게 되었고, 그 중에는 빅오 표기법, 오메가, 세타표기법이 있지만 흔히 우리는 일반적으로 worst case를 기준으로 time complexity를 적기 때문에 빅오 표기법을 가장 많이 사용하게 된다.

Chapter 3. Composition of relations

Original Post or Solved by: 최세현(2019.03.27)

Revised by: 감동윤(2019.03.27)

Revised by: 박재형(2019.03.27)

Final by: 김찬호(2019.03.27)

Final Ok by SGLee

Reference : Discrete Mathematics, Richard Johnsonbaugh, Seventh Edition

           http://matrix.skku.ac.kr/2018-DM/DM-Ch-3-Lab.html

Problem Solution Part

(Choose problem in each chapter)

Chapter 1. Set & Logics

(page 218. number4)

Solved by 김찬호(2019.4.12)

Ex 37,40)

Let P(x.y) be the propositional function x≥=y. The domain of discourse is Z​+xZ​+​.Tell whether each proposition in Exercises is true of false.

37.∀x∀y p(x,y)​

the statement is false. because when x = 2 y =3 , x<y, this proposition is not true.

there is such x,y in the domain that make proposition false. so∀x∀yp(x,y)​​​​ is false.

40.∃x∃y P(x,y)

The statement is true. because it is possible to find at least one real number x,y for which the proposition is true. when x=2,y=1. the P(x,y)is true so the statement is true.

42-59

Determine the truth value of each statement in Exercises 42-59.

the domain of discourse is RxR. Justify your answers.

42.∀x∀y (x​2​<y+1​)

This statement is false because if x=1 and y=2 , the conditional proposition∀x∀y x​2​<y+1​is false. The pair x=1 and y=2 is counterexample

45.∃x∃y(x​2​<y+1)

It is true statement.because it is possible to find at least one real number x,y for which the proposition is true. When x=1 y=1 x​2​<y+1 is true. there is such x,y that make proposition true. so the statement is true.

48.∀x∀y(x​2​+y​2​=9)

it is false statement.because if x=1 and y=1 , the conditional proposition∀x∀y(x​2​+y​2​=9)​​is false. The pair x=1 and y=1 is counterexample​.

51.∃x∃y x​2​+y​2​=9

It is true statement.

when x=1,y=2*2​(1/2)​ the statement is true.

there is such x,y that make true the statement.

54.∃x∀y (x​2​+y​2​≥=0​)

x is in domain R so x​2​≥=0

y is in domain R so y​2​≥=0

​sox​2​+y​2​≥=0 is true.

57.∀x∃y((x<y) ->(x​2​<y​2​))

for every positive real number x, there is x that take y=x.

but the x<y is false.

so the proposition is always true.

Chapter 2. proof

(page 83. Number7)

Solved by 감광적(2019.4.13)

Finalized by 김찬호(2019.4.13)

(Reference:Discrete Mathematics, Richard Johnsonbaugh, Seventh Edition)

page 83. example.

Chapter 2.1 Mathematical Systems, Direct Proofs, and Counterexamples

​7)

Prove that for all integers m and n, if m and n are even, then m+n is even.

Solution)

Since m is even, there exists an integer K such that

m=2K.

Also, there is also an integer K1 such that

n=2K1.

So the sum is of m+n is 2K+2K1=2(K+K1)=2K3

because K3 is absolutely another integer.

And the fact is that 2 times an arbitrary integer, the product will always be even.

Therefore, m+n is also even.

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

final comment add by 김찬호)

//우선 m,n 이 짝수인 정수라고 했으므로 m=2k, n=2l 을 각각 만족하는 정수 k,l이 존재합니다.

// m+n = 2(k+l)이므로 m+n역시 짝수입니다.

Chapter 2. proof

(page 83. Number13)

Solved by 감광적(2019.4.13)

Finalized by 김찬호(2019.4.13)

(Reference:Discrete Mathematics, Richard Johnsonbaugh, Seventh Edition)

page 83. example.

Chapter 2.1 Mathematical Systems, Direct Proofs, and Counterexamples

13)

13.Prove that for all rational numbers x and y, xy is rational.

Solution)

Let’s assume 4 non-zero integers which are a,b,c,d and we can derive that x=a/b, y=c/d.

So the product of xy is (a/b)(c/d)=ac/bd where ac is an integer and bd is a non-zero number.

Therefore, by the definition of rational number, xy is a rational number.

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

final comment add by 김찬호)

x,y가 각각 유리수라고 문제에서 주어졌으므로 x=a/b, y=c/d (b,d≠0)을 만족하는 각각 정수 a,b,c,d 가 존재합니다.

xy=ac/bd이고 b와d모두 0이 아니므로 bd는 0이 아닙니다.

따라서 xy도 유리수입니다.

Chapter 2. proof

(page 83. Number27)

Solved by 감광적(2019.4.13)

Finalized by 김찬호(2019.4.13)

(Reference:Discrete Mathematics, Richard Johnsonbaugh, Seventh Edition)

page 83. example.

Chapter 2.1 Mathematical Systems, Direct Proofs, and Counterexamples

​27)

Prove thatP(X∩Y)=P(X)∩P(Y)for all sets X and Y.

Solution)

Let’s assume A∈P(X∩Y),

→Ais in X∩Y

→A is in X and A is in Y

→A∈P(X)and A∈P(Y)

→A∈P(X)∩P(Y)

→P(X∩Y) is in P(X)∩P(Y)

And then we suppose that B∈P(X)∩P(Y),then

→B∈P(X)and B∈P(Y)

→B is in X and B is in Y

→B is in (X∩Y)

→B∈P(X∩Y)

→P(X)∩P(Y) is in P(X∩Y)

Therefore,P(X∩Y)=P(X)∩P(Y)     

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

final comment add by 김찬호)

​A∈P(X∩Y) 인 A가 있다고 가정합니다.

A는 X와 Y 모두에 포함되어야 합니다.

따라서 A는 P(X) , P(Y)에 모두 속한다고 할 수 있습니다.

그렇게 되면 P(X∩Y)​가​P(X)∩P(Y)에 속한다고 최종적으로 말할 수 있습니다.

B∈P(X)∩P(Y)​인 B가 있다고 가정합니다.

B는 P(X), P(Y)에 모두 속합니다.

따라서 B는P(X∩Y)​에 속한다고 할 수 있습니다

최종적으로 P(X)∩P(Y)​가P(X∩Y)​에 속한다고 말할 수 있습니다.​

두가지 결론을 통해P(X∩Y)=P(X)∩P(Y)​라고 말할 수 있습니다.​

Chapter 2. proof

(page 218. number4)

Solved by 김찬호(2019.4.12)

Finalized by 최세현(2019.4.12)

(Reference:Discrete Mathematics, Richard Johnsonbaugh, Seventh Edition)

page 83. example.

Ch.2, Page 110, Exercise 1

using induction, verify that each equation is true for positive integer n.

1+3+5+....+(2n-1)=n^​2​

Basic step)

if k=1.

1=1^​2

inductive step)

suppose this equation satisfy when k.

​

Let's check if the equation is true when we take k as k+1.

2(k+1) - 1 = 2k+1

So, we add 2k+1 to both side

​So, we could know that the equation is true for k+1.

Thus, this is true for all k.

****

comment by 최세현 :

I add more detail to 김찬호's solution,

While solving this exercise, I could clearly know how to use the mathematical induction

and make basic step, inductive steps to solve problems.

Chapter 2. Proof

(page 83)

Solved by 감광적(2019.4.13)

Finalized by 김찬호(2019.4.13)

(Reference:Discrete Mathematics, Richard Johnsonbaugh, Seventh Edition)

page 83. example.

Chapter 2.1 Mathematical Systems, Direct Proofs, and Counterexamples

​7)

Prove that for all integers m and n, if m and n are even, then m+n is even.

Solution)

Since m is even, there exists an integer K such that m=2K.

Also, there is also an integer K1 such that n=2K1.

So the sum is of m+n is 2K+2K1=2(K+K1)=2K3 because K3 is absolutely another integer.

And the fact is that 2 times an arbitrary integer, the product will always be even.

Therefore, m+n is also even.

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

add by 김찬호)

우선 m,n 이 짝수인 정수라고 했으므로 m=2k, n=2l 을 각각 만족하는 정수 k,l이 존재합니다.

m+n = 2(k+l)이므로 m+n역시 짝수입니다.

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

13)

13.Prove that for all rational numbers x and y, xy is rational.

Solution)

Let’s assume 4 non-zero integers which are a,b,c,d and we can derive that x=a/b, y=c/d.

So the product of xy is (a/b)(c/d)=ac/bd where ac is an integer and bd is a non-zero number.

Therefore, by the definition of rationalnumber, xy is a rational number.

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

add by 김찬호)

x,y가 각각 유리수라고 문제에서 주어졌으므로 x=a/b, y=c/d (b,d≠0)을 만족하는 각각 정수 a,b,c,d 가 존재합니다.

xy=ac/bd이고 b와d모두 0이 아니므로 bd는 0이 아닙니다.

따라서 xy도 유리수입니다.

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

​27)

Prove thatP(X∩Y)=P(X)∩P(Y)for all sets X and Y.

Solution)

Let’s assume A∈P(X∩Y), so we can say,

→Ais in X∩Y

→A is in X and A is in Y

→A∈P(X)and A∈P(Y)

→A∈P(X)∩P(Y)

→P(X∩Y) is in P(X)∩P(Y)

And then we suppose that B∈P(X)∩P(Y),then

→B∈P(X)and B∈P(Y)

→B is in X and B is in Y

→B is in (X∩Y)

→B∈P(X∩Y)

→P(X)∩P(Y) is in P(X∩Y)

Therefore,P(X∩Y)=P(X)∩P(Y)         

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

add by 김찬호)

​A∈P(X∩Y) 인 A가 있다고 가정합니다.

A는 X와 Y 모두에 포함되어야 합니다.

따라서 A는 P(X) , P(Y)에 모두 속한다고 할 수 있습니다.

그렇게 되면 P(X∩Y)​가​P(X)∩P(Y)에 속한다고 최종적으로 말할 수 있습니다.

B∈P(X)∩P(Y)​인 B가 있다고 가정합니다.

B는 P(X), P(Y)에 모두 속합니다.

따라서 B는P(X∩Y)​에 속한다고 할 수 있습니다

최종적으로 P(X)∩P(Y)​가P(X∩Y)​에 속한다고 말할 수 있습니다.​

​

두가지 결론을 통해P(X∩Y)=P(X)∩P(Y)​라고 말할 수 있습니다.​

Chapter 4. Algorithm

(page 218. number4)

Solved by 김찬호(2019.4.12)

trace algorithm for input 34 20 144 55

Input s,n

output s(sorted)

insertion_sort(s,n){

for i=2 to n{

​val=s_​i​//save s_​i​ so it can be inserted into correct place

 j=i-1

 //if val<s_​j​,move s_​j​ right to make room for s_​i​

 while(j≥1^val<s_​j​)

  s_​j+1​=s_​j​

  j=j-1

 }

s_​j+1​=val//insert val

}

}

Solution)

First 20 is inserted in

34

Since 20 < 34, 34 must move one position to the right

 x 34

Now 20 is inserted

20 34

Since 144 > 34, it is immediately inserted to 34’s right

20 34 144

Since 55 < 144, 144 must move one position to the right

20 34 x 144

Since 55 > 34, 55 is now inserted

20 34 55 144

The sequence is now sorted.

Chapter 5. proof

(page 294. Number15)

Solved by 감광적(2019.4.13)

Finalized by 김찬호(2019.4.13)

Reference: 1.Discrete Mathematics, Richard Johnsonbaugh, Seventh Edition

​Chapter 5.3 The Euclidean Algorithm

Page 294 Exercises

15.If a and b are positive integers, show that gcd(a,b)=gcd(a,a+b).

Solution)

Suppose that d=gcd(a,b) and e=gcd(a,a+b)

Because d|a, d|b, and d|a+b, d is a common divisor of a and a+b.

// because suppose d=gcd(a,b) then a+b=d(p+q) so a+b can divided by d.

so d can also divide a, a+b

Therefore, d<=e. 

​// I can't understand this statement.

Since e|a, e|a+b, and e|(a+b)

​//​there exist e that satisfy e=gcd(a,a+b) then ei=a,ej=a+b

and e can also divide a, b.

so we can conclude that d=e.

Chapter 5. Number Theory

(page 294. Number16)

Solved by 감광적(2019.4.13)

Finalized by 김찬호(2019.4.13.)

Reference: 1.Discrete Mathematics, Richard Johnsonbaugh, Seventh Edition

​Chapter 5.3 The Euclidean Algorithm

Page 294 Exercises

16.Show that if a>b>=0,thengcd(a,b)=gcd(a-b,b).

Solution)

First

Let’s assume that d=gcd(a,b) and d’=gcd(a-b,a)

And as we know, d|a, d|b, and d|a-b, so d is a common divisior of "a"and "a-b".

So, we can say, d <= d’.

// def Set D ={d| d=gcd(a,b)}

// def Set D'={d| d=gcd(a-b,a)}

//we can say D⊆D'

Second

Using the same method, we have that d’|a ,d’|a-b, and d’|b [d’|a-(a-b)]

So, d’ is a common divisor of "a" and "b".

Therefore, d’<=d

        ​

Conclusion

From the "First" and "Second", we can conclude that gcd(a,b)=gcd(a-b,b).

Chapter 5. Number Theory

(page 294. Number24)

Solved by 감광적(2019.4.13)

Finalized by 김찬호(2019.4.13)

Reference: 1.Discrete Mathematics, Richard Johnsonbaugh, Seventh Edition

24.Suppose that d>0 is a common divisor of nonnegative integers a and b, not both zero. Prove thatd|gcd(a,b).

Solution)

First

d divides a means that there exists an integer k which makes a =dk.

Also, d divides b means that there exists an integer l which makes b=dl

Second

Now we assume two integers x and y such that ax+by=gcd(a,b)

So, we can have the following two equations:

dkx+dly=gcd(a,b)

d(kx+ly)=gcd(a,b)

//we show that a=dk, b=dl.

so gcd(a,b)=C*d( C is constant)

so we can show d|gcd(a,b)

Therefore, we can prove that d|gcd(a,b)

Chapter 5. Number Theory

(page 233. Number32)

Solved by 최세현(2019.4.12)

Finalized by 김찬호(2019.4.12)

Reference: 1.Discrete Mathematics, Richard Johnsonbaugh, Seventh Edition

Ch.5, Page 233,

Exercise 32 : Suggest ways to make Algorithm 5.1.8 more efficient.

​

Solution)

Algorithm 5.1.8 :

Testing Whether an Integer is Prime

Input : n

Output : d

is_prime(n) {

 for d = 2 to [√n]

  if(n mod d == 0)

   return d

 return 0

}

This algorithm checks

if all the integers less than√n can divide the n or not.

​But this way is inefficient,

because duplicated values are also checked (which is composite numbers)

For example,if we checked 2 is not divisor of n,

after then, we don't have to check the multiple of 2. (2,4,6,8,10...)

Because of above reason, If we want to check the number is prime or not,

we just have to calculate with

prime numbers less than√n.​

(For example, we want to check 400 is prime number,

we just check with 2,3,5,7,11,13,17,19 (less then√400 = 20))

But, we don't know what are the prime numbers less than√n,

So it is best way to calculate with only "odd" numbers. (first check with 2)

Then, the algorithm will be like this:

Input : n

Output : d

is_prime(n) {

 if(n mod 2 == 0)

  return 2

 for d = 3 to [√n]

  if(n mod d == 0)

   return d

  d = d + 1

 return 0

}

Therefore, This algorithm will reduce the number of operation to half of original's.

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

add more about why we can check only prime number...

I quote qna about this question.

Question :

(quoted from :http://matrix.skku.ac.kr/2018-DM/DM-Ch-5-Lab.html)

In this example,

It checks 2017 is prime or not

But It seems like to check if the prime number less than 44 divides 2017..

why it only checks the prime number(2,3,5,7,11....43) divides 2017? not all the integer(2,3,4,5,6,7....44)??

​Answer :

For the number​n​to be a prime number,

The number​n​must not be divided by all the integers less than√n.

(Since all the number bigger than√n are the pairs of the number less than√n)

But, Since all the integers can be shown as the product(multiply) of the prime numbers,

(for example : 2, 3,2^​2​, 5,2*3, 7,2^​3​, 3^​2​, 2*5....)

We just check thatall the prime numbers less than√ninstead of all the integers​can divide the number n.

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

​so we can check only prime number.

​and except 2

all prime number is odd

so we can check odd number > 2

we also think about why we cant divide direct prime number

because there is no way that we can make prime number sequence before divide.

왜바로 소수가 아닌 홀수로 나누는지에 대해 의문을 가질수 있지만.

그러면 sqrt(n)보다 작은 소수를 미리 다 구해놔야 하지만.. 그런 코드는 구현을 해도 새로운 코드의 time complexity가 추가되므로 Odd number로 나누는 것이 효율적입니다.

n이 정말커진다면 이부분은 같이 한번 토론하고 비교해 볼 수 있을 것 같습니다

Chapter 6. Counting Method.

(page 338. Number29)

Solved by 감광적(2019.5.10)

Finalized by 김찬호(2019.5.11)

Reference: 1.Discrete Mathematics, Richard Johnsonbaugh, Seventh Edition

Exercise 29

Ch.6.3, Page 338, Exercise 29 solved by감광적

Problem)

Prove that the number of solutions is integers to

WhereX_​1​, X_​2​, and X_​3​are positive integers, is

Solution)

Firstly, because of the domains of x1, x2, and x3 are all positive integers, we leave the case of x1=x2=x3=0. Hence, we have n-3 choices of positive integers.

Secondly, we have three categories so the number of “|” is 2.

Finally, apply the C(k+t-1,t-1) to solve the problem. And the answer is

_n-3+2​C_​2​

//we can approach with k=2, t=3

Answer

By the proof above, the number of solutions is[(n-1)(n-2)]/2

Comment

It's a simple example solved by applying Theorem 3.5.

​//comment by 김찬호

This problem is good to use theorem 3.5

and the solution is simple and exact

thank you

Chapter 7. recurrence relation

(page 377. Number15)

Solved by 김찬호(2019.5.18)

Revised by 최세현(2019.5.18)

Finalized by 박재형(2019.5.18)

Reference: 1.Discrete Mathematics, Richard Johnsonbaugh, Seventh Edition

Question

Solve the given recurrence relation for the initial condition given:

a_{n= 6an-1- 8an-2}

a_{0= 1, a1= 0}

(Combined both최세현 and 박재형​'s revisions.​)

Solution with최세현​'s Revision:

Characteristic equation.

(using theorem 7.2.11)

Let)

Substitute the initial condition

Answer:

a_{n= 2}^{n+1- 4n}

Solution with박재형​​'s Revision:

Theorem 2.11

http://matrix.skku.ac.kr/2018-DM/DM-Ch-7-Lab.html​

We can use theorem 2.11 in chapter 7

Let

Answer:

Chapter 7. recurrence relation

(page 377. Number15)

Solved by 김찬호(2019.5.18)

Revised by 최세현(2019.5.18)

Finalized by 박재형(2019.5.18)

Reference: 1.Discrete Mathematics, Richard Johnsonbaugh, Seventh Edition

Problem

Solve the given recurrence relation for the initial conditions given:

2a_{n= 7an-1- 3an-2 a0= a1= 1.}

Solution

Characteristic equation

2t^{2- 7t +3 = 0}

t=3, 1/2

Let)

a_{n= A3}^{n+ B(1/2)n}

(Substitute Initial Condition)

a_​0​ = A + B =1

a_​1​ = A*3 +B *(1/2) = 1

∴ A = 1/5  , B = 4/5

 (Substitute Coefficient to recurrence relation)

∴a_​n​= 1/5*3^​n​ +​4/5 * (1/2)^​n​

a_​n = ( 2^​2-n​ + 3^​n​ ) /5

a_{n= (2}^{2-n+ 3n})/5   (n ≥ 0)   ■​

***

(using theorem 7.2.11)

In this case, using the coefficients of the a_n,n-1,n-2, we make the quadratic equation

2a_n,7an-1, -3a_{n-2==> 2t}^{2- 7t + 3 = 0}

and by using the solution "t" from above equation, (t = 3, 1/2)

we make the form like this :

a_{n= p3}^{n+ q(1/2)n}

Answer:

a_{n= (2}^{2-n+ 3n})/5    (n ≥ 0) ■​

Chapter 7. recurrence relation

(Ackerman’s function)

Solved by 김찬호(2019.5.18)

Revised by 최세현(2019.5.18)

Finalized by 박재형(2019.5.18)

Reference: 1.Discrete Mathematics, Richard Johnsonbaugh, Seventh Edition

Explanation

Ackerman's function is the function that represent the recurrence relation.

but the rate of growth is very rapid.

for example, If we find A(1.2), the result is 4, it is very small number we can easily find

But, If we find the result by using a little bigger number, 4or3 ==> A(4,3)

There will be a lot of calculation, and the result is very big number.)

we can get more information from here :

Reference

https://ko.wikipedia.org/wiki/아커만_함수

So if you put big number. it cannot work well. even in computer.

So to solve problem efficiently, make a general term in each case. and solve it.

However, Ackerman's function is often used to analyze the complexity of algorithms.

Chapter 7.1 Page 363 Problem 40 we compute A(2,2)

Reference 

http://icampus.ac.kr/front/study/QnaAction.do?method=view&lmsBdotSeq=2929466&lmsBlbdId=394928&isRply=Y

In this problem, we use general terms to solve this problem.

Comment by 김찬호

Exercise를 보다 보면 Ackerman’s function에 관한 문제가 많지만 이 부분을 잘 아는 학생은 드물거라 생각하여 같이 post하게 되었다. 재귀적인 관계로 이루어진 Ackerman’s function은 직접 숫자를 가지고 진행 하다 보면 익숙해 지기 쉽다.

Problem  of recursive function perpective of Programmer

​

Variables  that are created when you call yourself are newly created variables. Soon, it  can cause memory problems.

One  of the most common mistakes when using recursive function is initialization in  recursive functions

If  you do not initialize the system, the system turns around the recursive function  of the infinite loop, causing a memory error

​Initialization  in a recursive funtion provides a return point to end the recursive funcion.  Therefor, initialization in a recursive funtion is absolutely necessary, and if  you do not use it, you will not be able to find the ending point, so you will  end up in an infinite loop.

Recursive  calls are performed internally through stack memory. The function stores  relevant information in the activation record, which is stored in the stack  memory in order and then popped in turn. Because of limit size of stack memory  it can be forcefully terminated due to insufficient memory if the recursive call  is repeated too much

A  linear search scans one item at a time, without jumping to any item .

The  worst case complexity is  O(n), sometimes known an O(n) search 

2. Time  taken to search elements keep increasing as the number of elements are  increased.

A  binary search however, cut down your search to half as soon as you find middle  of a sorted list.

The  middle element is looked to check if it is greater than or less than the value  to be searched. 

2. Accordingly,  search is done to either half of the given list

Important  Differences

    Input  data needs to be sorted in Binary Search and not in Linear Search 

Linear  search does the sequential access whereas Binary search access data randomly. 

Time  complexity of linear search -O(n) , Binary search has time complexity O(log n). 

   Linear  search performs equality comparisons and Binary search performs ordering  comparisons

Linear  Search to find the element “J” in a given sorted list from A-X

Binary  Search to find the element “J” in a given sorted list from A-X

참조  : https://www.geeksforgeeks.org/linear-search-vs-binary-search/

Bubble  sorting is called bubble sorting, as it moves from the first element to the last  spot while continuing between adjacent elements. n memories are used for n  elements. Since data can be compared one by one, it can be compared precisely,  but the number of comparisons increases, which is not a good way of performance.  Repeat from the first element to the last element and align the largest element  to the last element after one step.

Time  complexity :  O(N²)

[69  10 30 2 16 8 31 22]

[10  30 2 16 8 31 22] 69

[10  2 16 8 30 22] 31 69

[2  10 8 16 22] 30 31 69

[2  8 10 16] 22 30 31 69

[2  8 10] 16 22 30 31 69

[2  8] 10 16 22 30 31 69

2  8 10 16 22 30 31 69

출처: https://tctt.tistory.com/47 [TcTT]

​Nevertheless time complexity of Big-O is  O(n^2)(longer than quick sort and other sorts), we use bubble sort often becuase  of precise data result. For example, between quick sort and bubble sort, quick  sort has quick time complexity than bubble sort(nlogn<n^2) but it has less  accuracy than bubble sort.

1.

// 원반을 from에서 to로 옮긴다.
void move(int from, int to){
    printf("\nMove from %d to %d", from, to);
}

// n개의 원반을 from 에서 by를 거쳐 to로 옮긴다.
void hanoi(int n, int from, int by, int to){
    if (n == 1)
        move(from, to);
    else{
        hanoi(n - 1, from, to, by);    // 1번  N-1개의 원반을 기둥3을 거쳐 2로 옮긴다.
        move(from, to);                // 2번 기둥 1에서 1개의 원반을 기둥 3으롱 롬긴다.
        hanoi(n - 1, by, from, to);    // 3번 기둥 2에서 N-1개의 원반을 기둥 3으로 옮긴다.
    }
}

--> Hanoi tower  code in C

2. Another  example in recursive function

int BSearchRecur(int ar[], int first, int last, int target){

    int mid = (first + last) / 2;

    if (first > last)

        return -1;

    else{

        if (ar[mid] == target)

            return mid;

        else{

            if (ar[mid] > target){

                last = mid - 1;

                BSearchRecur(ar, first, last, target);

            }

            else{

                first = mid + 1;

                BSearchRecur(ar, first, last, target);

            }

        }

    }

--> This is binary search code in C which we learn in Chaper 4 (Algorithm  chpater). Binary search algorithm also use recursive function

In computability  theory, the Ackermann function, named  after Wilhelm Ackermann, is  one of the simplest^[1] and  earliest-discovered examples of a total computable  function that is not primitive  recursive. All primitive recursive functions are total and computable, but  the Ackermann function illustrates that not all total computable functions are  primitive recursive.

After  Ackermann's publication^[2] of  his function (which had three nonnegative integer arguments), many authors  modified it to suit various purposes, so that today "the Ackermann function" may  refer to any of numerous variants of the original function. One common version,  the two-argument Ackermann–Péter function, is defined as  follows for nonnegative  integers m and n:

C code that  represent Ackermann-function 

int acker(int m, int n) {
if (m == 0)
  return n +  1;
else if (n == 0)
  return acker(m - 1, 1);
else
  return  acker(m - 1, acker(m, n - 1));
}

Every n-cube  of n > 0 is composed of elements, or n-cubes of a lower  dimension, on the (n−1)-dimensional surface on the parent hypercube. A  side is any element of (n−1)-dimension of the parent hypercube. A  hypercube of dimension n has  2n sides (a 1-dimensional line has 2 endpoints; a  2-dimensional square has 4 sides or edges; a 3-dimensional cube has 6  2-dimensional faces; a 4-dimensional tesseract has 8 cells). The number of  vertices (points) of a hypercube is (a  cube has vertices,  for instance).

The  number of m-dimensional hypercubes (just referred to  as m-cube from here on) on the boundary of  an n-cube is

,^[3]      where and n!  denotes the factorial of n.

For  example, the boundary of a 4-cube (n=4) contains 8 cubes (3-cubes), 24 squares  (2-cubes), 32 lines (1-cubes) and 16 vertices (0-cubes).

This  identity can be proved by combinatorial arguments; each of  the vertices  defines a vertex in a m-dimensional boundary. There  are ways  of choosing which lines ("sides") that defines the subspace that the boundary is  in. But, each side is counted times  since it has that many vertices, we need to divide by this number.

This  identity can also be used to generate the formula for  the n-dimensional cube surface area. The surface area of a  hypercube is:
These  numbers can also be generated by the linear recurrence relation

For  example, extending a square via its 4 vertices adds one extra line (edge) per  vertex, and also adds the final second square, to form a cube,  giving  =  12 lines in total.

<What is Euclidean Algorithm>

The Euclidean Algorithm. Recall that the Greatest Common Divisor (GCD) of two integers A and B is the largest integer that divides both A and B. The Euclidean Algorithm is a technique for quickly finding the GCD of two integer.

<Proof Euclidean Algorithm in Korean>

<Euclidean Algorithm code in python>

Understanding this important part of python code will be good.

 while b != 0:

        r = a % b

        a = b

        b = r​

Finalize by 김도훈.

Let's assume that n≥​m is not lost to generality. (n = max(n,m))

Then, m≥n%m is clear, considering the n characteristic of the remaining operations.

So get_gcd goes as shown below.

get_gcd(n,m) → get_gcd(n%m,m) → get_gcd(m%m,n%m)

So time complexity can be O(log(max(n,m))) and, it can be O(log(n+m)).

=====

Add)

I take the above mentioned expression

'get_gcd(n,m) → get_gcd(n%m,m) → get_gcd(m%m,n%m)',

I will give you a further explanation.

It is clear that the constant number of operations was required until 'get_gcd(m%(n%m), n%m) is called. And let this first sentence.

Next, the maximum value of 'm%(n%m)' or 'n%m' is 'n%m'. And let this second sentence.

In case of n≥​m, n​ > 2*(n%m) is formed. And let this third sentence.

Combining first and second sentence means that the maximum value of the two numbers was changed from 'n' to 'n%m' by counting the constant number, which means that the maximum value was less than half by third sentence.

This allows you to prove that the time-complexity of the above source is O(log(n,m)). This is because the maximum value was less than half due to the computation of the constant number. Also, if you change it to a simple marker, it becomes an O(log(n+m)).

Comment by 채상은:

S​ince I had a difficulty for understanding the proof of Euclidean Algorithm,

 I did search in Google for easy proof of this algorithm, then I can understand it easily.

Also because I’m major in software, I can understand intuitively by looking the python code.

Comments by 김도훈:

Comments : There are few more time-complexities of Euclidean Algorithm, because there are some different expressions that can express Euclidean Algorithm - such as using recursion or iteration etc. So I was impressed that there are many ways to express one algorithm!

A bit is  a binary digit..

The binary  Number System consists  of  symbols(bit).

The octal  Number System consists  of  symbols.

The decimal  Number System consists  of  symbols.

The hexadecimal  Number System consists  of  symbols.

The  system is based the base of  the number system.

      Decimal numbers

the  numbers we use in everyday life are decimal numbers, because they are based on  10 digits (0,1,2,3,4,5,6,7,8 and 9).

​Binary  Numbers use only the digits 0 and 1.

Examples:
•  0 in Binary equals 0 in the Decimal Number System,
• 1 in Binary equals 1 in  the Decimal Number System,
• 10 in Binary equals 2 in the Decimal Number  System,
• 11 in Binary equals 3 in the Decimal Number System,

•  100 in Binary equals 4 in the Decimal Number System,

Octal  Number System

Definition: The  number system whose base is 8 is known as the octal number system.  The base 8 means the system uses eight digits from 0 to 7. All the  eight digits from 0 to 8 have same physical meaning as that of decimal numbers.  The next digit in octal number is represented by 10, 11, 12, 13, 14, 15, 16, 17  which represents the decimal digits 8, 9, 10, 11, 12, 13, 14, 15. In this manner  the octal number 20 represents the decimal number 16 and subsequently 21, 22,  23….octal numbers will show the decimal digits 17, 18, 19…etc

https://circuitglobe.com/octal-number-system.html

Hexadecimal  number​

Hexadecimal  describes a base-16 number system. That is, it describes a numbering system  containing 16 sequential numbers as base units (including 0) before adding a new  position for the next number. (Note that we're using "16" here as a decimal  number to explain a number that would be "10" in hexadecimal.) The hexadecimal  numbers are 0-9 and then use the letters A-F.

https://whatis.techtarget.com/definition/hexadecimal​

에서 보듯이

집합 X 위의  관계 R이   아래의 3가지 조건을 모두 만족하므로 동치관계 라는 것을 보여주는 예이다.

  X는  다음  3 조건들을 만족한다.

(반사관계)  임의의 X 에  대하여, x=x

(대칭관계)  임의의 X 에  대하여, 만약 x =y라면,y=x 

  (추이관계)  임의의 X 에  대하여, 만약 x=y이고 y=z라면 x=z

그리고 동치관계이므로 동치류가 존재하고, 그 동치류를 집합으로, 그 안의 성분들을   X 라는 집합으로 보여준 것이다.

집합 X 위에  동치관계 R 이  주어졌을 때, 원소 x 의,  동치관계 y 에  대한 동치류(同値類, 영어: equivalence class) R 는  그 원소와 동치인 원소들의 집합이다

처음에  이해를 하지 못했던 부분은 symmetric 부분에서 왜 3이 x-y로 나누어지면 y-x도 3으로 나누어지는것이 symmetric일까 생각을  했지만, 조금만 더 symmetric의 정의에 대해서 생각해보면 당연한 얘기 입니다.

이  문제를 통하여 Equivalence class 에 관련된 내용을 조금더 확실히 이해할 수 있었습니다.

Solved by 김세진

Added by 김두원

Finalized by 김찬호

1.Solution of Ex.6.2.23

출처 : http://matrix.skku.ac.kr/2018-DM/DM-Ch-6-Lab.html 

//이 문제는 catalan number에 대한 문제입니다. 

교재 Ex.6.2.23 에서의 설명이 조금 부족한 것 같아 제가 이해한 대로 설명하고자 합니다.

문제에서와 같이 4 x 4 grid 와 3 x 5 grid 가 주어져 있습니다.

원래의 4 x 4 grid 에서 배드 루트가 되려면 그림에 표시한 지점 1~4 중에서 적어도 한 곳을 지나야 함은 자명합니다. 또한 3 x 5 grid 에서 왼쪽 아래에서 오른쪽 위 까지의 루트는 마찬가지로 표시한 1~4 지점 중 적어도 한 곳을 지나야 함을 알 수 있습니다.

 이제 각각의 루트들이 bijective 하게 나타내어질 수 있는지 확인해 보겠습니다.

 먼저 4 x 4 grid 에서 배드 루트가 지점 1 을 첫번째로 통과할 경우, 이를 스트링으로 나타내면 U □ □​ □​ □​ □ ​□​ □ 가 되고 빈 자리에는 남은 U 세개와 R 4개가 들어가야 될 것입니다.​ 따라서 지점 1을 첫번째로 통과하는 배드루트의 갯수는 C(7,3)= 7! / (4!*3!) 입니다.

한편 3 x 5 grid 에서 지점 1을 먼저 통과하는 루트를 스트링으로 나타내면

U □ □​ □​ □​ □ ​□​ □ 가 되고 빈 자리에는 남은 U 4개와 R 3개가 들어가야 됩니다.

따라서 지점 1을 첫번째로 통과하는 루트의 갯수는 C(7,4) = 7! / (3!*4!) 이며 

이는 위의 배드루트의 갯수와 같음을 알 수 있습니다. 따라서 각각의 루트는 서로 one-to-one 으로 매칭이 가능합니다.

4 x 4 grid에서 배드 루트가 지점 2를 첫번째로 통과하는 경우, 이를 스트링으로 나타내면 

R U U​ □​ □​ □ ​□​ □​ 이고 빈 자리에 R 3개와 U 2개가 들어가야 됩니다.

따라서 이 경우 배드루트의 갯수는 C(5,2)= 5! / (3!*2!)

3 x 5 grid 에서 지점 2를 첫번째로 통과하는 경우는 마찬가지로 R U U​ □​ □​ □ ​□​ □​ 이고​ 빈 자리에는 R 2개와 U 3개가 들어가므로 C(5,3) = C(5,2)

따라서 이 경우도 각각의 루트가 서로 one-to-one으로 매칭됨을 알 수 있습니다.

마찬가지 방법으로 지점3 과 4 를 첫번째로 통과하는 경우도 서로 one-to-one 임을 알 수 있습니다. 여러 지점을 동시에 첫번째로 통과할 수 없기 때문에, 위에서 살펴본 4 종류의 case는 서로 독립적입니다. 

또한 모든 루트는 위 4 지점 중 적어도 하나를 통과하여야 하기 때문에 4 cases 의 route set 들은 pairwise disjoint family 를 이룸을 알 수 있습니다. 따라서 Addition principle 에 따라 4 cases 를 전부 합하면 4 x 4 grid 에선 모든 배드루트들의 수가, 3 x 5 grid 에선 모든 루트들의 수가 구해집니다.

이 루트들이 서로 빠짐없이 one-to-one 으로 매칭되므로, 이 루트들은 onto function이기도 합니다. 따라서 두 루트들은 서로 bijective 함을 알 수 있습니다.

같은 원리로 이를 n x n matrix 로 generalization 이 가능합니다. 

이에 따라 B_n=C(2n, n-1) 임이 증명됩니다.

// general 하게 위에 있는 경우를 나타내어 보면

모든 bad route에 해당하는 점들이 y=x+1을 지나는 것을 알 수 있습니다.

따라서 제 qna에 올렸던 자료를 인용하겠습니다.

quoted from 

http://wiki.mathnt.net/index.php?title=%EC%B9%B4%ED%83%88%EB%9E%80_%EC%88%98_(Catalan_numbers)​

일단계

(0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수를 구해 보자.

이것은 매우 간단한 문제인데, 일대일대응을 통하여 문제를 풀어보자. 각 경로에서 x축으로 움직이는 것을 X로 표시하고 y축으로 움직이는 것을 Y로 표시하면, 각 경로는 X와Y를 n개 씩 쓴 문자열로 표현된다. 이것이 일대일 대응이다. 각각의 경로는 서로 다른 문자열로 표현될테고, 문자열은 또한 어떤 경로를 표현할테니까 말이다. 따라서 죽 늘어놓은 2n개 중에서 n개를 골라 X라고 써 놓으면 나머지 위치는 Y가 될 것이고 결정될 것이고, 그런 방법의 수는 (2nCn)이다. 즉, (0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수는 (2nCn)이다

이단계

이제 직선 y=x를 넘어서서 가는 경로의 수를 구하자. 경로는 반드시 y=x+1과 만나게 될 것이다.

이 때, 이 경로의 (0,0)에서부터 y=x+1과 처음으로 만나는 점까지를 잘라서, y=x에 대칭시키자.

그리고 나머지 경로를 평행이동시켜 대칭이동된 경로에 갖다붙이자.

그 결과는 (0,0)에서 출발하여 (n+1,n−1)에 도착하는 경로일 것이다.

위에서 한 작업은 서로 다른 두 경로의 집합 사이에 어떤 대응을 만들어 낸 것이다. 이 대응은 일대일 대응이다. 일대일대응임을 보이기 위해서는 두 가지를 생각해야 한다. 첫번째는, 서로 다른 것으로 대응되었는지를 살피고, 두번째는 공역의 모든 원소가 대응되었는지를 살피는 것이다.

comment 김두원:

해설의 이해를 돕기 위해서 문맥을 약간 수정했습니다. 이 문제를 이해하는데 애를 먹고 있었는데 훌륭한 설명 덕분에 쉽게 이해할 수 있었습니다. 감사합니다.

final comment 김찬호:

일반적인 예시로 설명을 잘 해주었습니다. 조금 더 general 한 설명을 인용해서 덧붙입니다.

Solution by 김두원

Solution added by 최세현

Final OK by 이상구 교수님

2.Three solutions to Ch.6.1 Example1.13

Solution 1 (Original)

Let  be the set of selection in which Alice is an officer.

Let  be the set of selection in which Dolph is an officer.

We first count the number of selection in which Alice is an officer.

Alice can be assigned an office in three ways. (3, chairperson, secretary and treasurer)

The highest remaining office can be filled in five ways.  (5)

The last office can be filled in four ways. (4)

There are three ways to assign Alice.

The number of selection in which Alice is an officer is , that is .

Dolph can be assigned an office in three ways.

The highest remaining office can be filled in five ways.

The last office can be filled in four ways.

There are three ways to assign Alice.

The number of selection in which Dolph is an officer is , that is .

[Both]  is the set of selection in which both Alice and Dolph are officers.

Alice can be assigned an office in three ways. (3)

The last office can be filled in four ways. (4)

The number of selection in which both Alice and Dolph are officer is , that is  and .

By the Inclusion-Exclusion Principle, there are

 = .      (Exs 92~97)

 Solution 2 (Solved by 김두원)

Above solution noted in "http://matrix.skku.ac.kr/2018-DM/DM-Ch-6-Lab.html" is a clean solution. But I found another simple solution to solve this problem effectively.

Selections are there in which either Alice or Dolph or both are offices is same as complementary selection of both Alice and Dolf is not an officer.​

Let U be the set of selection in which contains all of the possible cases.

Let X be the set of selection in which both Alice and Dolf is not an officer. 

The number of selection of all possible cases is 6*5*4 = 120. 

that is │U│=120

The number of selection in which both Alice and Dolf is not an officer.​ is 4*3*2 = 24, that is │X│​ = 24.

│U│​-│X│​=120-24=96. 

 ​Solution 3 (solved by 최세현)

We can easily solve this problem by multiplication principle with out using Sets or Diagram.

If both or one of Dolph and Alice is Officer, then the following is true.

1. One the other four person(Ben, Connie, Egbert and Francisco​) must be officer.

The number of this case is 4 * 3 (four person * three ways to officer)

2. and, we assign Alice or Dolph in to one of the remain two officer.

The number of this case is 2 (Alice or Dolph)

(We don't consider the number of ways. If we consider, the duplicate cases will be counted)

(So we determine the way of officer according to first process

If first process's officer is chairperson, now we assign Alice or Dolph in secretary. If first process's officer is secretary, now we assign Alice or Dolph in treasure. If first process's officer is treasure, now we assign Alice or Dolph in chairperson)

3. finally, we assign one of remain four persons at the one remain way of officer. The number of this case is 4 (four person)

(This process will assign remain Alice/Dolph or other three persons.

So this will satisfy the condition that both or one of Alice and Dolph is the officer)

the answer will be 4 * 3 * 2 * 4 = 96​

​

C​omment by 최세현: ​

(This process will assign remain Alice/Dolph or other three persons.

So this will satisfy the condition that both or one of Alice and Dolph is the officer)

So the answer will be 4 * 3 * 2 * 4 = 96

(한글로 추가 설명을 하자면,

2번과정에서 남은 2가지 Officer 과 2명(엘리스 혹은 돌프) 로 보고 4가지경우로 보지 않고 1번과정에 따라서 한가지 Officer을 정한 후 2명(엘리스 혹은 돌프) 로 보는 이유는, 3번과정에서 남은 한자리에 사람을 배정할 때에 중복된 경우가 생성되기 때문입니다.)

Solved By PIRAN CACI, Date: 2019.03.18.

Finalized by 김두원, Date: 2019.03.18

       Final OK by SGLee

Question

Let prove that the sum of two even integers is even.

Solution

We know that every integer multiplied by two will be an even integer. Let a = 2x and b = 2y, where x and y are integers.

This gives us: x + y = 2a + 2b = 2(a+b),

Because of that the sum of a and b must also be an even integer.

Solved By 강동윤, Date: 2019.03.18.

Finalized by 김두원, Date: 2019.03.18

       Final OK by SGLee

Question

In induction step, objective is to show that for all k, 4 < = k < n (n >= 6) k cents partage can be done

I understand basic​ step and objective of induction step.

But I can't understand next step.

Why is 4 < n-2 < k?

Solution

At the inductive step of the solution, we assumed that k cents postage can be done for all 4<=k<n for n>=6.

Because we supposed n>=6, we can say n-2>=4.

Also we already assumed the statement is true for all k when 4<=k<n

As a result there exists n-2 which fulfill the condition 4<=n-2<k.

Summurized by 최세현​

Added by 김찬호​

Added by 김두원​

Finalized by ​​박재형​

Re-Finalized by 담딘바자르​​

3.SKKU DM Chapter 6.3 Summary

(quoted from : http://matrix.skku.ac.kr/2018-DM/DM-Ch-6-Lab.html)​

6.3 Generalized Permutations and Combinations

This Theorem shows how to count the cases that there are same objects of distinct types.

We count the number of cases of n elements by using factorial ==> n!

But there are same objects, Duplicated cases exist.

So we have to divide it by the number of objects

Example of above Theorem :

There are 11 elements and one M, four i, four S, two P.

So, If we apply above theorem to this example,

the answer will be (11!)/ (4! 4! 2! 1!). 

This Theorem shows how to count the number of cases that Dividing same k elements to t groups.

It's same as Combination principle _​8​C_​2​ =  _​8​C_​6​

Example of it :

In this example, by using above theorem, we have to divide 6 same copies to 3 groups (computer science, physics, and history)

Then, the answer will be _​8​C_​2​.

The principle of it is, put two bar that divide 6 same copies to three groups.

If there are 6 copies,

(X X X X X X),

and we put two bars between them,

(XX|XXX|X)

We need 8 positions, and we choose 2 positions of the two bars.

The cases of it is _​8​C_​2​. 

.

In this, we can choose t(책의 종류) = 3  k(분류하는 선택지) = 6.

​

this is exciting theorem. and we can apply this at next example.

solution)

By Theorem 3.5, the number of ways of selecting eight balls is (공을 3개 상자에 8개 담는 방법) (=3, 8=)

.

We can also use Theorem 3.5 to solve part (b) if we first select one ball of each color. To complete the selection, we must choose five additional balls (5=). This can be done in

The following table summarizes the various formulas:

Comment by 김찬호:

최세현 군의 summary에서 중요한 theorem 과 example을 덧붙였습니다.

6.3장은 저희가 앞에서 배운 순열과 조합의 연장선이고 응용입니다. 내용이 어렵지만 공부하면 다루기 쉬운 부분이라고 생각합니다 

Comment by 김두원:

6.3장의 내용을 훌륭하게 정리한 요약이라고 생각합니다. 마지막에 문제마다 적용할 수 있는 공식을 쉽게 알 수 있는 테이블을 lab에서 참조하여 가져왔습니다. 이 공식들은 까다로운 문제를 쉽게 해결할 수 있는 공식이므로 꼭 숙지해야합니다. 

Comment by 박재형:

조합의 theorem에서 비슷한 이론을 덧붙였습니다. 그리고 예제에 이론이 어떻게 쓰였는지 붙였습니다.

6.3장의 내용은 생각보다 어렵지만 문제를 많이 풀다보면 식을 자유자재로 쓸 수 있을만큼 실력이 향상될 것을 믿습니다. 적용할 수 있는 공식을 이해하고 외운다면 문제를 쉽게 풀 수 있을 것임을 깨달았습니다. 

Comment by 담딘바자르​:

Chapter 6.3 has some background basics based off of middle school Mathematics concepts in my opinion, specifically statistics and probabilities. The crucial concept is on accountability of repeats.

Summary by 이승원

Add by 김두원

Finalized by 채상은

Re-Finalized by 에인젤피트리사리

 4. Summary of Chapter 5.2

(By 채상은​) 5.2 Representations of Integers and Integer Algorithms​

A bit is a binary digit. A bit has a 0  and a 1  .

The binary Number System consists of  2  symbols(bit).

The octal Number System consists of 8  symbols.

The decimal Number System consists of  10 symbols.

The hexadecimal Number System consists of 16  symbols. 

The system is based the base of the number system.

    Decimal numbers

the numbers we use in everyday life are decimal numbers, because they are based on 10 digits (0,1,2,3,4,5,6,7,8 and 9).

​Binary Numbers use only the digits 0 and 1. 
Examples: 
• 0 in Binary equals 0 in the Decimal Number System,
• 1 in Binary equals 1 in the Decimal Number System,
• 10 in Binary equals 2 in the Decimal Number System,
• 11 in Binary equals 3 in the Decimal Number System,

• 100 in Binary equals 4 in the Decimal Number System,

Octal Number System

Definition: The number system whose base is 8 is known as the octal number system. The base 8 means the system uses eight digits from 0 to 7. All the eight digits from 0 to 8 have same physical meaning as that of decimal numbers. The next digit in octal number is represented by 10, 11, 12, 13, 14, 15, 16, 17 which represents the decimal digits 8, 9, 10, 11, 12, 13, 14, 15. In this manner the octal number 20 represents the decimal number 16 and subsequently 21, 22, 23….octal numbers will show the decimal digits 17, 18, 19…etc 

https://circuitglobe.com/octal-number-system.html

Hexadecimal number​

Hexadecimal describes a base-16 number system. That is, it describes a numbering system containing 16 sequential numbers as base units (including 0) before adding a new position for the next number. (Note that we're using "16" here as a decimal number to explain a number that would be "10" in hexadecimal.) The hexadecimal numbers are 0-9 and then use the letters A-F.

https://whatis.techtarget.com/definition/hexadecimal​

Can also switch from decimal to hexadecimal:

We can covert a decimal inter into base b integer by the algorithm stated below.\

By using this algorithm, we can learn how the number system is consisted and understand the way to converting decimal to binary, octal and hexadecimal number. 

 (By 이승원​)  In today's class we learned about 5.2 which is about Representations of integers and integer algorithms.

We already know about decimal and binary number system, but we also learned other system such as octal and hexadecimal number system. In octal number system, we use only 0,1,2,3,4,5,6,7 to use any number. It is little bit same as decimal and binary system. For example, 33210 can be writen as 5148 because 332 is 5*8^2+1*8+4. We call the value on which the system is based such as 10 or 8 is the base of number system. In hexadecimal system, we have to use 16number from 0 to 15, but we can't use number bigger than 9 because we have to use one number in one symbol. So we use alphabet by using A B C D E F as 10 11 12 13 14 15. The other method is same as other system.

We can add two or more number in binary, not decimal in binary addition such as example below.

 Solution

We begin from the right, adding  and . This sum is .

We write  and carry . At this point the computation is

Next, we add  and  and . This sum is .

We write  and carry . At this point the computation is

                                                   00                     

Continuing in this way, we obtain

(By 김두원​) Similarly, we can add two hexadecimal number like below.

Solution

We begin from the right, adding  and . This sum is .

We write . At this point the computation is

Next, we add  and . This sum is .

We write  and carry . At this point the computation is

Continuing in this way, we obtain

Add on theorem (By 에인젤피트리사리): 

Theorem 2.17 Quoted by Chapter 5 Notes 

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

Comment by 에인젤피트리사리: ​

I feel that the Hexadecimal Addition is more complicated than the binary addition because in Hexidecimal Addition, it uses Hexadecimal numbers and the numbers 10-16 are represented with letters such as A,B,C,D,E,F. Whereas in Binary Addition it just uses 0 and 1, in which 1+1 = 0 and will carry another 1 that will be added with the next column. It is not that difficult to do the Hexadecimal Addition but it is sometimes confusing. However, I will make sure to keep on practicing to get better! 

Summary by 김두원

Add by 최세현

Finalized by 박재형

5.Summary of 4.3, 4.4

(quoted from http://matrix.skku.ac.kr/2018-DM/DM-Ch-4-Lab.html)​

4.3 Analysis of Algorithms Problem

* The program is useless If the time needed to run is too big or the space needed to run is too big.

​The time needed to execute an algorithm is a function of the input.

Instead of dealing directly with the input, we use parameters that characterize the size of the input.​

​

For example,

The input is a set containing  elements.      The size of the input is .

Best-case-time: We can ask for the minimum time needed to execute the algorithm among all inputs of size .  This time is the best-case-time for inputs of size .

 Omega

Worst-case-time: We can ask for the maximum time needed to execute the algorithm among all inputs of size .  This time is the worst-case-time for inputs of size .

 ​Big-Oh

Average-case time: Another important case is average-case time that the average time needed to execute  the algorithm over some finite set of inputs all of size .

 ​Theta

Here is example for it.

   (quoted from  http://matrix.skku.ac.kr/2018-DM/DM-Ch-4-Lab.html

There is three notation about complexity.

Big O notation is often described for complexity because it indicates worst case. 

To show whether the theta notation above is true, we have to show both of big-O notation and Omega notation are same.

Solution

Since

     for all ,

Taking  in Definition  to obtain

.

Since

       for all ,

Taking  in Definition  to obtain

.

Therefore,

 and   

.                  

​4.4 Recursive Algorithms 

​Recursive Algorithms means calling the function IN THE FUNCTION ITSELF. 

For example, If we want to find the n! (factorial of n)

​The recursive function will be like this : 

factorial(n) = n * factorial(n-1) (n >1)

If n = 1, factorial(n) = 1.

So, It will provide like this (for example of n = 5)

factorial(5) = 5 * factorial(4) = 5 * 4 * factorial(3) = ... = 5 * 4 * 3 * 2 * factorial(1) = 5*4*3*2*1.

This recursive algorithm is very efficient to repeat the similar operations.

Robot Walk Problem

We are going to find the number of ways the robot can walk, by using recursive algorithm.

Testing for the short distances (1,2,3,4),

If distance is 1, robot can walk through 1 way   (1)

If distance is 2, robot can walk through 2 ways (1,1)(2)

If distance is 3, robot can walk through 3 ways (1,1,1)(1,2)(2,1)

If distance is 4, robot can walk through 5 ways (1,1,1,1)(2,1,1)(1,2,1)(1,1,2)(2,2)

There are only 2 ways to go. 2 steps or 1 step.

According to above fact, If we make the function to find the number of ways the robot can walk n meters,

Then, the function will be like this :

Walk(n) = Walk(n-1) + Walk(n-2) (n >2)

if n = 2, Walk(n) = 2

if n = 1, Walk(n) = 1

=> Walk(n) = Walk(n-1) + Walk(n-2) = Walk(n-2) + Walk(n-3) + Walk(n-4) + Walk(n-3) = .....

This algorithm repeats to divide the last step to two cases that one meter step or two meter step.

So, it will provide the all cases that robot can walk. 

​Summary :​ 

In 4.3, We have learned about analysising the program (with time, space complexity) when the case is worst, best, and regular.

Also in 4.4, We learned to build recursive function to solve the problem like finding fibonachi, factorial.

Preview of 김찬호

Added by 김은민, 박재형, 최세현, 담딘바자르

Finalized by 김두원

6.Preview 6.1, 6.2

(quoted from : http://matrix.skku.ac.kr/2018-DM/DM-Ch-6-Lab.html)

6   Counting Methods and the Pigeonhole Principle

In chapter 6, we will learn about Counting Methods and Pigeonhole Principle.

6.1   Basic Principles

Example of counting:

Menu for Quick Lunch:

There are two appetizer, three main courses and four beverages and .

HT, HM, HC, HR, CT, CM, CC, CR, FT, FM, FC, FR ()

And

    NHT, NHM, NHC, NHR, NCT, NCM, NCC, NCR, NFT, NFM, NFC, NFR,

                    12 with Nachos   (N),   +

                                        12 with Salad     (S)  = 24.

    SHT, SHM, SHC, SHR, SCT, SCM, SCC, SCR, SFT, SFM, SFC, SFR 

We can solve this problem by using Multiplication Principle noted below.

Multiplication Principle  (Product Rule)

Using product rule to solve above problem :

The problem of counting the number of dinners consisting of one appetizer, one main course and one beverage,

  First step is “select the appetizer.”

  Second step is “select the main course.”

  Third step is “select the beverage.”

By the Multiplication Principle,

,  and , the total number of dinner is .

if any activity that consist of t times succesive steps,

step 1, n₁ ways

step 2, n₁ ways

..

step t, n_t ways

than we can represent the total different possible activity n₁*n₂*...n_t

Addition Principle

simmillary we can make addition principle.

we can pick the elements of each sets.

than the total union of sets's element is n₁+n₂+...+n_t

There is a theorem about Inclusion exclusion principle for two sets

 
6.2   Permutations and Combinations

permutation means the ordering of n elements

and r-permutation of n elements is an ordering of an r-element subset of

{x₁,x₂,,,x_n}

The number of this is P(n,r)

and we can calculate in this form

simillary we can define combination with

And this is detailed explanation about r- combination of a set of n distinct elements. The numbers of -combinations of a set of  distinct objects is

,     . 

***

Comment by 최세현 : We will learn about counting methods, permutation and combinations.

I think that it will be very useful to check the cases to solve problems or calculate the number of all the cases. 

Comment by 담딘바자르​:

In my opinion, counting methods are used to determine the complexity of algorithms ,and they can be used to solve other sorts of problems. I think counting is related to probabilities and statistics because it has some elements and techniques from the subjects such as finding all possible results to determine the best result. Moreover, these sections are even big part of our life, so they should be familiar with us. 

Comment by 김두원:

Multiplication Rules and Addition Rule are the most important basic principle to solve counting problem. By counting, we can calculate the complexity of an algorithm and statics kind problems.

summary by 웅요빈

add by 김진녕​/​김도훈​/한진수​/담딘바자르​/김은민​/김두원)​

Finalized by 박재형

​7. Summary 3.4,3.5

​​(quoted from http://matrix.skku.ac.kr/2018-DM/DM-Ch-3-Lab.html,

 summary of 웅요빈/김진녕​/​김도훈​/한진수​/담딘바자르​/김은민​/김두원)​​

3.4   Equivalence Relations​

The next theorem shows that some relation is always reflexive, symmetric and transitive. -> This is equivalence relation.

This proof displays how the 3 properties formed:

Proof 

Let .

By the definition of partition,  belongs to some numbers  of .

Thus  and  is reflexive.

   Suppose that .

Then both  and  belong to some set .

Since both  and  belong to ,  and  is symmetric.

    Finally suppose that  and .

Then both  and  belong to some set  and both  and  belong to some set .

Since  belong to exactly one member of , .

Therefore, both  and  belong to  and .

We have shown that  is transitive.                                          ■

By definition in order for us to consider a relation to be equivalence is to satisfy the following 3 conditions

1. Must be transitive

 and