Discrete Mathematics  (Ch 8, Graph Theory)

SKKU Math Lectures and Labs

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

http://matrix.skku.ac.kr/2018-DM/DM-Labs.htm  Discrete Math Labs (실습실)

http://matrix.skku.ac.kr/2018-DM-PBL/      (PBL report 보고서)
http://matrix.skku.ac.kr/2018-DM-PBL-Eng/  (PBL report Eng, 영문 보고서)

## Major: Software (2학년)

Ch 8, Graph Theory

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

(DM Sec 8.1 동영상강의) Graph Theory https://youtu.be/TSFIJBU2dX8

(DM Sec 8.2 동영상강의) Path and Cycle https://youtu.be/iqUTT5C1TOs

(DM Sec 8.3 동영상강의) Hamiltonian cycle https://youtu.be/at7Hx5wxnYk

(DM Sec 8.4 동영상강의) Shortest Path https://youtu.be/MHDJ3rALtEU

## ◆ Colleague who helped you learning [Your Opinions]

* Name of Your Class Mate: Chingis Oinar

## ◆ Colleagues who helped you learn [Your Opinions]

*Note: this part is more of a general response rather than picking a specific person as above mentioned.

## ◆ Participation Part

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

(A1) Quantity : **

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

My contribution as an individual was two-way contribution. In one way I learnt from others and I have been in part of different discussions throughout this course. The other way I have contributed is that I have put a lot of effort in helping others by revising and finalizing their solutions. Moreover, I tried my best to post as many general questions as possible regarding the course or assignments to make sure that not only me, but the others can benefit from my questions.

(A3) No. of Final OK by SGLee Problems (and/or Completed Discussion/Question) in QnA that your name is included.

Final Ok Problems Number: 72 Problems (from chapter 1,2,3,4,5,6,7,8,9)

Discussions that the Professor made a comment on/wrote a Final ok on: +15 posts.

(B1) What did you especially remember while you are doing A-1, 2, 3.﻿﻿

The most interesting thing that popped up in my head is how awkward I felt in the very beginning to post anything. However, thanks to the Professor and my classmates who always pushed me and appreciated the good work which made me feel way more comfortable day by day.

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

I am really happy to be part of this fabulous lecture where learning isn’t just about math and getting a good grade, but it has a broader meaning of sharing with others and participating in discussions to hold an effective place in the class and to be a productive individual.

​ (B4) What is your project (and In-depth study) and your role in your Team (Leader, Idea, Solve, Prove, Coding, Typing, Presentation etc.

As for our team work that is divided in two parts:

A)     QnA activity: In this part each we had to manage Chapter 8 (Graph Theory), where we took a different approach by embedding some discussion portals for the students to talk about. Moreover, we provided the students a chance to solve more exciting and core problem by removing the redundant ones.

B)     Actual Team Project: in this part Me and Mr.Kim Jung Ju participated in doing an in depth research for the shortest path problem under the name of “ Analysis of Shortest Path Algorithms from a Computer Science’s Perspective” where we discussed different approaches taken to solve such problem while keeping the time complexity into consideration.

(The QnA activity and The Team Project are attached at the end of this PBL Report)

As far as for my role I have been the leader who tried his best to organize and push the team specially the less active members by reminding them that how DM could affect them in a useful way. Moreover, I have been the concept founder and solver who provides the solutions for student’s questions plus finds new ideas and ways of making Chapter 8 way more joyful. Finally, I’ll be the main presenter and spokesperson for my Team.

## ◆ * PBL Participation Part

Number of your QnA participation up to the Due date. ( 192 total entries )

·       Note: The questions I have done are pretty general (yet still am attaching some of them – One question per one page)

Question Title: “Reply/Question on Homework”                             Date 13/09/2018

Question text:

Good Job :D , the professor didn't actually declare any rules for uploading the homework answers(yet) but I think you better insert pictures ( in the text itself) rather than an attachment, it'll be easier for everyone to follow up with you, rather than switching back and forth between downloaded files and icampus website.

by the way I have a question, The professor didn't mention any specific section, are you sure we have to solve just from 1.1?

“I see^^    I will check the page number of problem clear.

But if you solve and shared a couple of problems and Solution.

That will do it for you^^”

Original text by the TA:                                                Date 13/09/2018

방정식 P(x) = 0 이 실근을 갖지 않는다.

를 지금까지 배운 논리기호로 표시해 보세요 ( 실수 집합은 R로 표기합니다. )

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

The equation P (x) = 0 does not have a real root. (the real set is written as R).

Represent this proposition using logical symbol you have learned so far.

There is no x in real  such that   P (x) = 0.”

“There is no x in real  such that   P (x) = 0

given that P(x) means not having a real root

we can say

x in R , not P(x)=0

which means for all x in Real they can have a real root

Revised by SGLee:                                                    Date 17/09/2018

“There is no x in real  such that   P (x) = 0

<=>    !  x  R        P(x)=0

“

“Isn't it the same thing ? but the other way round

there is no x such that p(x)

all of x can't justify p(x)

I guess both are logically equivalent, do i have to stick with the exact same words?”

Final Answer by SGLee:                                                Date 17/09/2018

“Yes, you have to stick with the exact same words in symbol:

!  x  R        P(x)=0

(  for There is no x in real  such that   P (x) = 0 )

because it is the most clear statement to all (not only for you).”

Question Title: “Request for Chapter 2 notes-PDF”                          Date 23/09/2018

Question text:

“Hello there,

Can anyone tell me where can I find the PDF version of lecture notes for chapter2?

* if it's not uploaded it would be a great help if you can upload it Sir/TA.

Best Regards”

“Hello, Dear Muhammed!

..  PDF file of the Chapter 2 (Proofs) ...

I can give the file to you when you are ready. And  I will give it to you when you are ready.

NOW if you want, (as I said in the class) you can read copy and do work the second chapter on the link: http://matrix.skku.ac.kr/2018-DM/DM-Ch-2-Lab.html .

Professor uploaded all the materials of the second chapter on this link.

Happy Chuseok! “

Question Title: “About PBL Report(inquiry)”                          Date 27/09/2018

Question text:

Hello there,

Does anyone have any information about submitting the PBL report? I mean When ? hardcopy or softcopy?what should we include in it?

* I checked the related post on notice board. Alas, I didn't get much info.”

* I understood everything, but the part of "final ok" i didn't, How can I get the final ok if there are some questions which i solved/reviised/finalized without a final ok? Shall I tell you next class or remind you?

Thanks Sir

For the part of "final ok"

. We still have more than 10 days before we submit your pbl report.

So I will grade and You or your friend or the one you degignate or your team member can see me or TA to get final ok by sglee or TA ...    Once a week or before you submit.

You can get help from me in my OH or just after the next class.”

Part 2: Problems with your name in [Solve-Revise-Finalize and Final OK by SGLee/TA]

p.64, Problem 15 (Chapter1 Self-Test)

Solved by 전종문, 2018.09.14

Finalized by 전종문, 2018.09.20

[Offline] In person meeting-Final Ok By Professor, 2018.10.05

Problem:

Determine whether the following argument is valid.

r

∨￢q

q

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

q

Solution

By using Truth Table.

 Case p q r -q q ∨ r p →q ∨ r p ∨￢q r ∨ q q 1 T T T F T T T T T 2 T T F F T T T T T 3 T F T T T T T T F 4 T F F T F F T F F 5 F T T F T T F T T 6 F T F F T T F T T 7 F F T T T T T T F 8 F F F T F T T F F

For the conclusion to be true we have to consider the cases when all premises are true (cases marked in yellow), these cases are: 1 , 2 , 3 , 7.

Then we try to find a counter example -if any- in the conclusion for these cases. We can see that counter examples can be found in case 3 and case 7 where q is false.

Therefore, this argument is invalid.

Question by TA

Revised by SGLee and Final OK  Date 17/09/2018

방정식 P(x) = 0 이 실근을 갖지 않는다.

를 지금까지 배운 논리기호로 표시해 보세요 ( 실수 집합은 R로 표기합니다. )

The equation P (x) = 0 does not have a real root. (the real set is written as R).

Represent this proposition using logical symbol you have learned so far.

There is no x in real  such that   P (x) = 0.”

Solution:

“There is no x in real  such that   P (x) = 0

<=>    !  x  R        P(x)=0

“

p.64, Problem 14 (Chapter 1 Self-Test)​​

Solved by 김희성 Sep . 16th   Revised by 조영은 Sep, 21th

Finalized by 모하메드 Sep,26th   Re-Finalized by 모하메드 Oct,05th

[Offline] In person meeting-Final Ok By Professor, 2018.10.05

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

Problem 14:

Write the following argument symbolically and determine whether it is valid.

If the Skyscrapers win, I'll eat my hat.

If I eat my hat, I'll be quite full.

Therefore, if I'm quite full, the Skyscrapers won.

Solution:

First, lets give each statement(proposition) a symbol as following:

The Skyscrapers win  --->  proposition  p

Eat my hat  --->  proposition  q

quite full  --->  proposition  r

Secondly, changing the given argument into symbols we get:

p->q           (If the Skyscrapers win, I'll eat my hat)

q->r              (If I eat my hat, I'll be quite full)

ㅡㅡㅡ

r->p            (Therefore, if I'm quite full, the Skyscrapers won)

Finally, we check the validity:

For the argument to be valid, the conclusion and the premises should be true (no matter what the inputs are) but assuming that p is false, q is false and r is true we can get:

p->q           (Is true)

q->r              (Is true)

ㅡㅡㅡ

r->p            (but the conclusion is false)

Since the conclusion is False while the premises are true (counter example), we can say that the argument is invalid.

Note: This Invalidity is called the fallacy of affirming the conclusion

p.63, Problem 5 (Chapter 1 Self-Test)​​

Solved by 정호진 2018.09.17

[Offline] In person meeting-Final Ok By Professor, 2018.10.05

​​Problem 5:

If p, q and r are true, find the truth value of the proposition (pq)  ((p r) q))​​

Solution:

pq - true; p r - false;

(p r) q) - true; ((p r) q))​​​ - false;

(pq)  ((p r) q))​​ - false

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

Truth Table:

 p q r -p p∨q ￢p ∧ r (￢p ∧ r ) ∨ q ￢ ((￢p ∧ r ) ∨ q) ( p ∨ q) ∧￢((￢p ∧ r ) ∨ q). T T T F T F T F F

p.64, Problem 8 (Chapter1 Self-Test)​​

Solved by 정호진 2018.09.17  Revised by SGLee 2018.09.17

Re-Finalized By : Muhammed/모하메드05/Oct/2018

[Offline] In person meeting-Final Ok By Professor, 2018.10.05

​​Problem 8

Assume that a, band c are real numbers. Represent the statement

a<b or (b<c and  c)

symbolically, letting

p: a<b,          q: b<c,                r:   a<c.

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

Solution:

p(q∧ㄱr)

Page : 63 Problem 1  - Chapter 1

Solved By : Muhammed/모하메드, Date: 2018.09.17

Finalized By: 전종문, Date: 2018.09.20

Final OK by SGLee ​

Problem 1

1. If = {1, 3, 4, 5, 6, 7}= {is an even integer},

= {2, 3, 4, 5, 6}, find (∩ B C.

Solution

= {1, 3, 4, 5, 6, 7}

= {is an even integer}=2,4,6,8,10,...

= {2, 3, 4, 5, 6}

∩ B​= {4,6}​

Since, (∩ B​)  C

(∩ B C =​  { } ■   (empty set)

Page 64 Problem 12  Chapter 1

Solved by 전솔람 Date 2018.09.19

Revised and Finalized by Muhammad/모하메드 Date 2018.09.26

Final OK by TA  Date 2018.10.04

12. Represent the statement​

If ( a ≥ c or b < c ), then ( b ≥ c )

symbolically using the definitions of Exercise 8.( p : a < b,  q : b < c,  r : a < c )

Sol)

a ≥ c is equivalent to  the reverse of r ( a < c )​, so a ≥ c represents  r

And, b < c is equivalent to q ( b < c )

And, ≥ c is same to the reverse of ​q ( b < c )​, so ≥ c represents  q

As a result, " ( a ≥ c or b < c ), then ( b ≥ c ) ​" can be represented as " (  ​q ) → ​ q

Page 64 Problem 17-Ch. 1                             Solved by 전솔람 19th Sep.

Revised and Finalized by Muhammad/모하메드 26th Sep.

Final OK by SGLee,

17. Is the statement

" The team won the 2006 National Basketball Association championship "

a proposition? Explain.

Sol)

It is not proposition.

Because the statement cannot be determined to True or False.

Why? Because we don't know what "team" the statement is referring to.

Problem 13  p.124(Chapter2 Self-Test)

Solved by 전종문, Date : 2018.09.21

Revised by 유가이 올렉산드르: 2018.09.23

Re​​Finalized and Final OK by SGLee 2018.09.27

Problem

Use mathematical induction to prove that the statements in Exercises 13-16 are true for every positive integer n.

13.  2 + 4 + + 2n = n(n+1)       (*)

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

Proof

Basis Step: (*) is true for  n=1

2=1(1+1)=2 is true.

Inductive Step:

Assume (*) is true for n=k :

[that is:  If n=k, then 2 + 4 + + 2k = k(k+1)  --- (*)  is true.]

* We want to [show that it's true for n=k+1]

Add 2(k+1) at the left hand side of (*)

2 + 4 + + 2k + 2(k+1)

=  k(k+1) +   2(k+1)  (because of (*)  2 + 4 + + 2k = k(k+1) )

=  (k+1)(k+2)  (because k(k+1) +2(k+1) is equal to(k+1)(k+2) )

So, 2 + 4 + + 2k + 2(k+1)​​=(k+1)(k+2) is true.

By Principle of Mathematical Induction.

2 + 4 + + 2n = n(n+1) is true for every positive integer n.

p.124, Problem 1  Chapter 2

Solved by 유가이 올렉산드르, 2018.09.23

Final OK by SGLee

Problem №1

Distinguish between the terms axiom and definition.

Solution

By definition axioms (postulate) is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. (증명 없이 참으로 받아들이는 명제)(in simple words: things  that are assumed to be true)

In my opinion, the distinctive feature of the axioms is that, it is the mainstay of mathematics, which don't require proof (Because they can't be proved, they simply exist, as a universe).

Definitons are used to create new concepts in terms of existing ones. Some terms are not explicitly defined, but rather are implicitly defined by the axioms. ( : 수학용어나 기호에 대하여 그 의미를 규정한 것.)  ■

*** In math, 공리와 정의, 정리의  차이

http://blog.naver.com/PostView.nhn?blogId=young040511&logNo=220492536490&parentCategoryNo=&categoryNo=&viewDate=&isShowPopularPosts=false&from=postView

2) 공리

: 증명 없이 참으로 받아들이는 명제

예시 :

1. 임의의 점에서 임의의 점으로 직선을 그을 있다.

2. 유한인 직선( 애매함 선분이라고 생각하시는게좋음) 연장할 있다.

3. 임의의 중심과 거리를 가지고 원을 가지고 원을 그릴 있다.

4. 모든 직각은 서로 같다.

5. 직선 밖의 점을 지나 직선에 평행하는 직선은 오직 하나뿐이다.

위와 같은 유클리드기하의 5 공리가 예시이다.

1) 정의

: 수학용어나 기호에 대하여 의미를 규정한 .

예시 : 직각삼각형 : 내각의 크기가 직각인 삼각형을 직각삼각형이라 한다.

정삼각형 : 변의 길이가 같은 삼각형을 정삼각형이라 한다.

3) 정리

수학적으로 증명된 참인 명제

예시 :피타고라스의 정리 ( )

Page : 124 Problem 10 Chapter2

Finalized by 유가이 올렉산드르: 2018.09.26

[Offline] In person meeting-Final Ok By Professor, 2018.10.05

Question 10 :  Find an expression, which is the "and of clauses", equivalent to ( p ¬q)  ¬r s.

Discussion/Explanation:

Our Goal is to change the expression so that it becomes "and-clause",

* and-clause is a clause/statement of the form as following:

e.g.  a^b^c^d^e

e.g.2. (!ab)^(c)^(d!e)

*Remember that in DM or Logic Design we can omit the and Symbol.

e.g.  a^b   is equivalent to ab

* Preparation Before Solving:

Refer to the resolution proof (Chapter 2 Section 3) and equivalent statements mentioned throughout the section.

* Extra Info:
this question is essential in Digital Logic Design where we have to minimize a Boolean expression to  (and-clause) (also named maxterm).

* Solution:

*Note: rs = r^s

( p ¬q)   ¬rs    ¬( p ¬q) ¬rs (by using equivalent statements/Resolution Proof)

¬pq  ¬rs                         (using De Morgans Law )

(¬pq ¬r ) ^(¬pq s         (Using equation 3.4 in chapter 2)

## (Using  the equation 3.4 in chapter 2)

Page : 124 Problem 20     Chapter 2

Finalized by : 강병훈 27/sep/2018

Final OK by SGLee

20. Use the Well-Ordering Property to show that any nonempty set X of nonnegative integers that has an upper bound contains a largest element.

Hint: Consider the set of integer upper bounds for X.
----------------------------------------------------------------------------

Discussion/ Explanation:

We have to show that there exists an element in X (let’s call it x) which creates an upper bound for the set. In other words, the element x is greater than or equal to each element in the set X.

For example, 13934 is a lower bound for the set X= {5, 8, 42, 34, 13934}.

As far for the hint given, we can consider an arbitrary set that contains all values greater or equal to X.

For example, the set = {13934,13935,13936,...} is the set of integer upper bounds for X= {5, 8, 42, 34, 13934}.

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

Solution:

From the given question; we want to show that if there exists a nonempty set X of nonnegative integers that has an upper bound, then it contains a largest element.

Using the hint given, let’s assume there exists a set which is the set of integers upper bound for the set XBy this assumption, we can deduce that Y is a non-empty set of nonnegative integers following the properties of the Set X. Using the Well Ordering Property, the set Y has a least element (let’s call it y). By the previous deductions, we can say that yx for every x in the set X.

Now to ensure that the element y is in the set X , we can assume that y is not in X then there should be an element (y-1)  Y which is greater or equal to each element in X , but there isn’t since y is the lowest element in the set Y that makes an upper bound for X (contradiction).

Hence,
yx for every x ​ and y is the largest element in X.

An example would further clarify: X= {3} , Y={3,4,5}.

Page 198 Problem 20 Chapter 3

Solved by 오동찬 : 2018.09.27

Re-Finalized by 오동찬 2018.09.29

Final OK by SGLee

Exercises 17-20 refer to the relations

R= {(1,x), (2,x), (2,y), (3,y)},

R= {(x,a), (x,b), (y,a), (y,c)}.

Problem 20

Use the result of Exercise 19 to find the matrix of the relation R₂° R.

+) Result of Exercise 19 Solution Problem 21  p.198(Chapter3 Self-Test)

Finalized by 오동찬, Date: 2018.09.30

Re-Finalized By : Muhammed/모하메드:05/Oct/2018

[Offline] In person meeting-Final Ok By Professor, 2018.10.05

In Exercises 2124, write a sequence of operations to answer

the query. Also, provide an answer to the query. Use Tables 3.6.1

and 3.6.2.

21. Find all teams.

Discussion/Explanation:

Table 3.6.1:(Player Table)

 ID Number Name Position Age 22012 Johnsonbaugh c 22 93831 Glover of 24 58199 Battey p 18 84341 Cage c 30 01180 Homer 1b 37 26710 Score p 22 61049 Johnsonbaugh of 30 39826 Singleton 2b 31

Table 3.6.2: (Assignment Table)

 PID Team 39826 Blue Sox 26710 Mutts 58199 Jackalopes 01180 Mutts

*These tables represent  data base (collection of data)

*A query is a request for information from the database (Example: Find all the players with age of 22 years)

*To Solve/Answer a query we have to select certain data from the database using some operators:

-Selection Operator -> Row Selection

-Projection Operator -> Column Selection

-Join Operator -> merging all info for some related entries(in two tables)

*Key word "TEMP" is used to state an intermediate state (temporary)

Solution:

Operation :ASSIGNMENT [Team]

Blue Sox, Mutts and Jackalopes

Note:

These Tables are a very simple example where we use basic operations(mentioned earlier) to extract some specific data of our choice , it can be extended to any complexity of your desire

Problem 22  p.198(Chapter3 Self-Test)

Finalized by 오동찬, Date: 2018.09.30

Re-Finalized By : Muhammed/모하메드:05/Oct/2018

[Offline] In person meeting-Final Ok By Professor, 2018.10.05

In Exercises 2124, write a sequence of operations to answer

the query. Also, provide an answer to the query. Use Tables 3.6.1

and 3.6.2.

22. Find all players names and ages.

Discussion/Explanation:

Table 3.6.1:(Player Table)

 ID Number Name Position Age 22012 Johnsonbaugh c 22 93831 Glover of 24 58199 Battey p 18 84341 Cage c 30 01180 Homer 1b 37 26710 Score p 22 61049 Johnsonbaugh of 30 39826 Singleton 2b 31

Table 3.6.2: (Assignment Table)

 PID Team 39826 Blue Sox 26710 Mutts 58199 Jackalopes 01180 Mutts

*These tables represent  data base (collection of data)

*A query is a request for information from the database (Example: Find all the players with age of 22 years)

*To Solve/Answer a query we have to select certain data from the database using some operators:

-Selection Operator -> Row Selection

-Projection Operator -> Column Selection

-Join Operator -> merging all info for some related entries(in two tables)

*Key word "TEMP" is used to state an intermediate state (temporary)
Solution:

Operation: PLAYER [Name, Age]

Johnsonbaugh, 22;

Glover, 24;

Battey, 18;

Cage,30;

Homer, 37;

Score, 22;

Johnsonbaugh, 30;

Singleton, 31

Note:

These Tables are a very simple example where we use basic operations(mentioned earlier) to extract some specific data of our choice , it can be extended to any complexity of your desire

Problem 23  p.198(Chapter3 Self-Test)

Finalized by 전종문 Date: 2018.09.28

Re-Finalized By : Muhammed/모하메드:05/Oct/2018

[Offline] In person meeting-Final Ok By Professor, 2018.10.05

Problem

In Exercises 2124, write a sequence of operations to answer

the query. Also, provide an answer to the query. Use Tables 3.6.1 and 3.6.2.

23. Find the names of all teams that have a pitcher.

Discussion/Explanation:

Table 3.6.1:(Player Table)

 ID Number Name Position Age 22012 Johnsonbaugh c 22 93831 Glover of 24 58199 Battey p 18 84341 Cage c 30 01180 Homer 1b 37 26710 Score p 22 61049 Johnsonbaugh of 30 39826 Singleton 2b 31

Table 3.6.2:(Assignment Table)

 PID Team 39826 Blue Sox 26710 Mutts 58199 Jackalopes 01180 Mutts

*These tables represent  data base (collection of data)

*A query is a request for information from the database (Example: Find all the players with age of 22 years)

*To Solve/Answer a query we have to select certain data from the database using some operators:

-Selection Operator -> Row Selection

-Projection Operator -> Column Selection

-Join Operator -> merging all info for some related entries(in two tables)

*Key word "TEMP" is used to state an intermediate state (temporary)
Solution

Sequence of Operation:

TEMP1 := PLAYER [Position = p]  players who are pitchers

TEMP2 := TEMP1 [ID Number = PID] ASSIGNMENT  pitchers and playing in teams

TEMP2 [Team]  select the name of those teams having a picther

Mutts, Jackalopes

Note:

These Tables are a very simple example where we use basic operations(mentioned earlier) to extract some specific data of our choice , it can be extended to any complexity of your desire

Problem 24  p.198(Chapter3 Self-Test)

Finalized by 오동찬, Date: 2018.09.30

Re-Finalized By : Muhammed/모하메드:05/Oct/2018

[Offline] In person meeting-Final Ok By Professor, 2018.10.05

In Exercises 2124, write a sequence of operations to answer

the query. Also, provide an answer to the query. Use Tables 3.6.1 and 3.6.2.

24. Find the names of all teams that have players aged 30 years or older.

Discussion/Explanation:

Table 3.6.1:(Player Table)

 ID Number Name Position Age 22012 Johnsonbaugh c 22 93831 Glover of 24 58199 Battey p 18 84341 Cage c 30 01180 Homer 1b 37 26710 Score p 22 61049 Johnsonbaugh of 30 39826 Singleton 2b 31

Table 3.6.2:(Assignment Table)

 PID Team 39826 Blue Sox 26710 Mutts 58199 Jackalopes 01180 Mutts

*These tables represent  data base (collection of data)

*A query is a request for information from the database (Example: Find all the players with age of 22 years)

*To Solve/Answer a query we have to select certain data from the database using some operators:

-Selection Operator -> Row Selection

-Projection Operator -> Column Selection

-Join Operator -> merging all info for some related entries(in two tables)

*Key word "TEMP" is used to state an intermediate state (temporary)
Solution:

Sequence of Operations:

TEMP1 := PLAYER [Age 30] ->Players older than 30

TEMP2 := TEMP1 [ID Number = PID] ASSIGNMENT -> older than 30 and in teams

TEMP2 [Team] -> name of teams having players older than 30

Thus,

The teams Blue Sox and Mutts have players which ages are equal or older than 30.

Note:

These Tables are a very simple example where we use basic operations(mentioned earlier) to extract some specific data of our choice , it can be extended to any complexity of your desire

Page 247 Problem 5 (Chapter 4 Self Test)

Finilized by 칭기즈​​ : 2018.10.03

Final OK by SGLee,

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

5.Trace Algorithm 4.2.1 for the input t = 111011 and

p = 110.

*Explanation:

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

- Text Search:

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

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

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

Output: (the index of first match occurrence)

Pseudo Code:

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

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

{

j = 1

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

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

// the while loop compares ti · · · ti+m1 and p1 · · · pm

while (ti+j1 == pj )

{

j = j + 1

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

return i

}

}

return 0

}

"

*Solution:

Given:

t= "111011"

p= "110"

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

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

a) j is set to 1

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

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

a) j is set to 1

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

--------------------------------------------------------
= "111011" n=6

p = "110"   m=3

Hint:

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

return i

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

Trace table:

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

Output:

2

## Comment by Muhammad: Always try to do a step by step plugging in- don’t rush.

p.247 problem 9 Chapter 4

finalized by 엄자균 Date: 2018.10.04

Re-Finalized by 서명원 Date: 2018.10.05

​​Final OK by SGLee

Problem

Select a theta notation from among Θ (1), Θ (n), Θ (n2), Θ (n3),Θ (n4), Θ (2n), or Θ (n!)   for each of the expressions in Exercises 9 and 10.

9. 4n3 + 2n  5

Discussion

f(n)= O (g(n)) if f(n)  C_1 *g(n) for constant 'C_1 ' and  n0  n

f(n)= Ω (g(n))  if f(n) >= C_2 *g(n) for constant 'C_2' and  n0  n

f(n)= θ​ (g(n)) if f(n) is O(g(n)) and f(n) is  Ω (g(n)).

The problem 9     '4n3 + 2n − 5' is θ​(n3)

Sol.

Since 10n3 > 4n3 + 2n  5, c_1  = 10     where C_1 = 10  and   4n3 + 2n  5

> 1/10 n3  where    C_2  = 1/10      (n0=1)

=>        '4n3 + 2n  5'     is   Θ(n3)

Page 248 Problem 12 (Chapter 4 Self Test)

Solved by 강병훈 Date: 2018.10.3

Revised and finalized by Muhammad/모하메드 : 2018.10.03

Final Ok SGLEE

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

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

*Solution:

Input: A an(n × n matrices) and n

Output: true (if A = B ); false (if  B)

Code:

equal matrices(A, B, n)

{

for i = 1 to n
{

for j = 1 to n
{

if (Ai j != Bi j )
return false

}

}
return true

}

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

The worst-case time is theta of (n^2)  why? because we have a nested loop (2-step loop) where for each index in the i-loop the j-loop will be executed n times, and since i is also executed n times then n*n =n^2  (in worst case O(n^2) and best case Omega(n^2)->  hence Theta(n^2)).

Note by Muhammad: Theta /O / Omega notations are read as " O/theta/Omega of f(x)" -> where f(x) is a function that counts the number of operations executed and generally the most used notation is the Big O-notation since it gives the upper bound-worst case- for an algorithm. Since am from software department i thought this would be helpful.

Page 263 Problem № 2 (Chapter5 Self-Test)

Solved by AYSU OZGUNEKIM

Revized by 김주형

Finalized by 유가이 올렉산드르

Final OK by SGLee

Date: 05.10.2018

07.10.2018

08.10.2018

08.10.2018

Problem № 2 Page 263 (Chapter 5)

Find the prime factorization of 539.

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

*Discussion:

Important Terms :

-prime number(N) : natural number that is greater than 1 and that cannot be formed by multiplying two smaller natural numbers(x,y), where x,y are also greater than 1.

-prime factor : A factor that is a prime number (Prime Numbers that can be multiplied to form a composite number)

prime factorization : the decomposition of a composite number into a product of prime numbers

*Algorithm/Pseudo Code for testing whether an integer(N) is prime:\

Check_Prime(int N)        //N is the number to be checked

{

for d=2 to N1/2

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

return d

return 0

}

*Solution:

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

Let's solve this task by using a factorial tree: *The yellow marked numbers are prime.
So we get : 539=(7^2)*11

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

ex)  5*3 = 15. And Prime Factorization is finding which prime numbers multiply together to make the original number. ■

Another Comment by Muhammad: when you try to find Factorial tree , start checking the factors from smallest to biggest (1,2,3,4,...)

Page 263 Problem № 8 (Chapter5 Self-Test)

Solved by 김희성 2018.10.07​

Executed by 김영철 2018.10.08

* Problem:

Trace Algorithm 2.19 for the values a = 50, n =30, z =11.​​

* Discussion:

The algorithm is as following:Algorithm  2.19

(Exponentiation Mod By Repeated Squaring)

This algorithm computes  using repeated squaring.

Input:  a, n, z

Output:  exp_mod_via_repeated_squaring(a, n, z) result   while ( ) if(  ) *   *    return result * Solution (Step by Step plugging in):

result = 1

x=a mod z = 50 mod 11=6

-----------------------while Loop 1st iteration-------------

while(n>0)                               //While-loop executes since n=30>0

{

if(  )                           //If condition doesn't execute since 30 mod 2 !=1 *  x=6*6 mod 11 = 3

n=15

-----------------------while Loop 2nd iteration-------------

while(n>0)                               //While-loop executes since n=15>0

{

If (  )                   //If condition executes since 15 mod 2 ==1

result=1*3 mod 11=3

x=3*3 mod 11 = 9

n=7

-----------------------while Loop 3rd iteration-------------

while(n>0)                               //While-loop executes since n=7>0

{

If    (  )                 //If condition executes since 7 mod 2 ==1

result=3*9 mod 11=5

x=9*9 mod 11 = 4

n = 3

-----------------------while Loop 4th iteration-------------

while(n>0)                               //While-loop executes since n=3>0

{

If  (  )        //If condition executes since 3 mod 2 ==1  ​​

result = 5*4 mod 11 = 9

x=4*4 mod 11 = 5

n = 1

-----------------------while Loop 5th iteration-------------

while(n>0)                               //While-loop executes since n=1>0

{

If (  )           //If condition executes since 1 mod 2 ==1

result=9*5 mod 11 = 1

x=5*5 mod 11 = 3

n=0

}

Finally, Since n=0 is not greater than 0 the loop is broken and we get result = 1.

* Solution Checking :

by simply plugging in the original formula :

(a^n) mod z = (50^30) mod 11 = 1.​​​ hence our answer is right.

After Solving this problem I realized how important is it to write a pseudo code before actual programming.

Final OK by SGLee/CH.6 page 370 Problem 1

solved by 김승연, 모하메드, 김주형

Problem 1

How many eight-bit strings begin with 0 and end with 101?

Solution

Let's consider the final layout for the number as following:

0 □ □ □ □ 1 0 1

Step A) The 1st and the 5th-8th bit already have specific values.so there is no selection involved in these fixed bits.

Step B) The number of remaining bits are 4 bits. Moreover, there are two ways to select each bit (either 0 or 1).

Step C) By the Multiplication Principle, the total number of eight-bit encoding is 2= 16.

2= 16.

Comment

문제는 공간에 중복이 없는 가지 선택지가 있는 문제로 문제를 풀었다면 선택지가 개인 문제뿐만 아니라 간단한 선택 문제는 모두 있다.

This problem has two choices with no duplication of blank

If you solve this problem, you can solve not only the two choices but also the simple ones.

Final OK by SGLee/CH.6 page 371 Problem 5

solved by오동찬, 김영철, 모하메드, 엄자균, 강병훈, 김주형

Problem 5

How many 3-combinations are there of six objects?

Solution

C (6 ,3 ) = 6 ! ÷  (3 ! × 3 ! ) = 20

Note   Definition  2.15

Comment

콤비네이션 함수의 기본을 알고 있다면 다른 문제를 푸는데 문제가 없을 것이다.

If you know definition of combination function (definition 2.15), there won't be much trouble solving other related problems.

Final OK by SGLee/CH.6 page 371 Problem 7

solved by 오동찬, 김영철, 모하메드, 엄자균, 강병훈, 정호진

Problem 7

How many six-card hands chosen from an ordinary 52-card deck
contain three cards of one suit and three cards of another suit?

Solution

1.    C (133) = 286 (one suit)

2.    C (133) = 286 (another suit)

3.    C (4 , 2) = 6 (2 suits)

4.    286 x 286 x 6 = 490,776.

Comment

52 카드에 13개의 같은 문양이 있다는 것을 생각해서 콤비네이션 함수를 이용하면 쉽게 있는 문제이다.

Thinking that there are 13 identical shape on the 52 cards, it is a problem that can be easily solved by using the combination function.

Final OK by SGLee/CH.6 page 371 Problem 8

solved by 오동찬, 김영철, 모하메드, 엄자균, 강병훈, 정호진

Problem 8

A shipment of 100 compact discs contains five defective discs. In how many ways can we select a set of four compact discs that contains more defective than non defective discs?

Solution

1.     defective : 3, not defective : 1 C(5,3) × C(95,1).

2.     defective : 4 C(5,4)

C(5,3) × C(95,1)+ C(5,4) = 955

Comment

직접 답을 구하기 어려운 문제는 독립시행이라면 답을 더하거나 빼서 구할 있다.

The problem which is hard to finding the direct answer can be obtained by adding or subtracting the answer if it is independent trial.

Final OK by SGLee/CH.6 page 371 Problem 11

solved by 전종문, 김영철, 신혜수, 모하메드, 정호진, 강병훈

Problem 11

In how many ways can 12 distinct books be divided among four students if each student gets three books?

Solution

1st student: C(12,3)

2nd student: C(9,3)

3rd student:C(6,3)

4th student:C(3,3)

C(12,3) × C(9,3) × C(6,3)× C(3,3)  12!/(3!)4  ■

Note

Definition  2.15

Given a set containing (distinct) elements,

(a) An -combination of is an unordered selection of -elements of (i.e. an -element subset of ).

(b) The number of -combination of a set of distinct elements is or . Comment

선택 문제에서는 선택한 후에 선택지가 없어진다는 것을 알아두는 것이 중요하다.

It is important to know that, in a selective problem, the choice is lost after it is selected.

Final OK by SGLee/CH.6 page 371 Problem 12

solved by 신혜수, 전종문, 모하메드, 김주형, 강병훈, 정호진

Problem 12

How many integer solutions of

x1 + x2 + x3 + x4 = 17

Satisfy

x1 ≥ 0, x2 ≥ 1, x3 ≥ 2, x4 ≥ 3

Solution

x2 = x2'+ 1, x3 = x3'+ 2, x4 = x4' + 3

x1 + x2+ x3 + x4 = x1 + (x2'+1) + (x3'+2) + (x4'+3) = 17

x1 + x2' + x3' + x4' = 11

Satisfy

x1 ≥ 0, x2' ≥ 0, x3' ≥ 0, x4' ≥ 0

﻿ For combination for repetition,

nHr = n+r-1Cr = 11+4-1C4 = 14C4 = 14!/(4!×10!) = (14×13×12×11)/(4×3×2×1)=1001

Comment

문제는 단순히 생각하면 어렵겠지만 변수를 변경해주어 11 문제와 똑같이 만들어서 있는 문제이다.

This is a problem that can be solved simply by changing the variable and making it the same as Problem 11, even if it is difficult to think.

Final OK SGLee/CH.6 page 371  Problem 16

solved by 김정주, 모하메드, 이양휘, 강병훈

Problem 16

Find the permutation that will be generated by Algorithm 4.14 after 6427135.

Solution

Step1: Algorithm 4.14 generates the permutation that follows 6427135 by supposing that

s1 = 6, s2 = 4, s3 = 2, s4 = 7, s5 = 1, s6 = 3, s7 = 5

Step2:  At line 6, the largest index m satisfying sm < sm+1  is 6 (s6 = 3)

Step3:  At lines 1013, we find that the largest index k satisfying sk > sm  is 7 (s7 = 5).

Step4:  At line 14, swap sm and sk

s6 = 5 and s6 = 3

Step5:  Swap  6 and 7 : 6427153

Note

*what is lexicographic order?

it is an order that generalizes ordinary dictionary order.

*Algorithm 4.14 Generating Permutations

This algorithm lists all permutations of {1, 2, . . . , n} in an increasing lexicographic

order.

Input: n

Output: All permutations of {1, 2, . . . , n} in increasing lexicographic order

1. permutation(n) {

2. for i = 1 to n

3. si = i

4. println(s1, . . . , sn) // print the first permutation

5. for i = 2 to n! {

6. m = n 1

7. while (sm > sm+1)

8. // find the first decrease working from the right

9. m = m 1

10. k = n

11. while (sm > sk )

12. // find the rightmost element sk with sm < sk

13. k = k 1

14. swap(sm, sk )

15. p = m + 1

16. q = n

17. while ( p < q) {

18. // swap sm+1 and sn, swap sm+2 and sn1, and so on

19. swap(sp, sq )

20. p = p + 1

21. q = q 1

22. }

23. println(s1, . . . , sn) // print the ith permutation

24. }

25. }

Comment:
It may be a little bit difficult for people who do not know the code, but I think it is good for me to solve some problems in the future.

[Final OK by TA] Ch. 7 P.424 Problem 1 solved by 전솔람 Finalized by 칭키즈, 김영철 , Muhammad

Solved by 전솔람 date 2018. 11. 06.

Fina​lized b​y 칭기즈​ Date 2018.11.06

Re-Finalized by 김영철 Date 2018.11.07

Re-Finalized (fixed) by Muhammad Date 2018.11.10

Final OK by TA Date 2018.11.12​

Problem

Answer part (a)-(c) for the sequence defined by rules:

1. The first term is 3.

2. The n th term is n plus the previous term.

(a) Write the first four terms of the sequence.

(b) Find an initial condition for the sequence.

(c) Find a recurrence relation for the sequence.

Solution

1.    Let n-th term of the sequence be anwhich logically makes the previous term an-1.

2.     Hence, the formula of n-th term is  an = n + an-1​​

3.     Let me remind you that the first term is 3 ( a1=3 )

4.     Hence to find another three elements:

n =
2     ->   a2 = 2 + a2-1 = 2 + a= 2 + 3 = 5
n =
3     ->   a3 = 3 + a3-1 = 3 + a2 = 3 + 5 = 8
n =
4     ->   a4 = 4 + a4-1 = 4 + a= 4 + 8 = 12

(a) The first for terms of the sequence.

a1​ = 3,  a2​ = 5,  a3​ = 8 ,  a​= 12

(b) Initial condition for the sequence.

a​= 3​

(c) A recurrence relation for the sequence.

an​ = n + ​an-1

Comment:

Recurrence relations are the same as recursive functions in Programming where we relate some term in a sequence to a previous term. Secondly, a hint for solving this problem can be using some values to plugin and check

Comment:

일정한 규칙의 조건을 가지고 단계별로 점화식으로 표현하는 방법에 대해 배우게 되었다.

[Final OK by TA] Ch. 7 P.424 Problem 2 Solved by 전솔람 finilized by 칭기즈 , 김영철, Muhammad

Solved by 전솔람 date 2018.11.06

finilized by 칭기즈 Date 2018.11.06

Finalized by 김영철 Date 2018.11.07

Final OK by TA Date 2018.11.12​​​

Problem

Assume that a person invest 4000 dollars at 17 percent interest compounded annually. Let A(n) represent the amount at the end of n years. Find a recurrence relation and an initial condition for the sequence A(0), A(1), ......

Definition  1.1 Solution

1.    Let a0 be the initial amount invested
-->
a0=4000

2.    After 1 year, a1 will be
-->  a
1 = a+ 0.17 a= 1.17 a0

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

4.    Thus, after n years, an will be
-->  a
n = an-1 + 0.17 an-1 = (1.17) an-1 = ... = (1.17)a0

Initial state:  a0=4000
Recurrence relation:   an = (1.17)an-1 , where a0=4000

Comment:

복리계산에 대한 내용과 그것을 점화식으로 표현해 볼 수 있었다.

Comment:

Remember that recurrence relation should in the form of an represented by any predecessor term like (an-1). Thats why the relation/equation provided by the original answer (an = (1.17)* 4000 )Is not a recurrence relation.

[Final OK by TA] Ch. 7 P.424 Problem 3 solved by 서명원 Finalized by 김영철, Muhammad, 전종문

Solved by 서명원 date 2018. 11.09

Fina​lized b​y 김영철 Date 2018.11.10

RE- Finalized by 전종문 Date:2018.11.12

Final OK by TA Date:2018.11.12

Problem Solution

1.    Let X be an n-element set and choose x X and k be a fixed integer (0 ≤ k ≤ n - 1)

2.     We can select a k-element subset Y  from X - {x} in C(n-1, k) ways.

3.     Next, we can partition Y in Pk ways.

4.     This partition (from step 3) along with the set X - Y  -> partitions X.

5.      Since this works for every partition of X, the recurrence relationship is proven

Another Solution

To prove Pn satisfies the recurrence relation, we can find a relationship between Pn and Pn-1.

Pn   n-1​n=0​   C(n-1,k)  P​k = ( ​n-2​n=0​   C(n-2,k)  P​k )*n-1 +C(n-1,n-1)Pn-1 = (Pn-1) *n-1 + Pn-1​​= n*Pn-1​​​

Then we showed that Pn = n *Pn-1​​​​ satisfies the recurrence relation

Comment:

일정한 규칙이 반복되는 구조일 때, 점화식으로 표현할 수 있다는 것을 알 수 있었다.

Comment:

When a certain rule was a repetitive structure, it could be expressed as recursive relation.

[Final OK by TA]Ch 7, P424, P.4 Solved by 서명원, Finalized by Muhammad

solved by 서명원 Date : 2018.11.09

Revised and Finalized by Muhammad, Date: 2018.11.09

Final OK by TA Date: 2018.11.12

Problem Solution

If the first domino is placed as shown,

there are n-1 ways to cover the 2 x (n-1) board that remains. If the first two dominoes are placed as shown,

there are n-2 ways to cover the 2 x (n-2) board that remains. If follows that an = a n-1 + a n-2.

By inspection, a1 = 1 and a2 = 2.

Since (an} satisfies the same recurrence relation as the Fibonacci sequence

a1 = f2 and a2 = f an = f n+1 ,where { f n } is the Fibonacci sequence.

Comment:

그림을 통해 점화식의 규칙을 알 수 있었고 피보나치 수열의 점화식에 대해서도 알 수 있었다.

Comment:

This question is an extremely easy question as long as you can make a diagram /sketch to understand what's happening under different circumstances.

[Final OK by SGLee] Ch. 7 P.424 Problem 6 전솔람, 김희성, 칭기즈 by Muhammad

Solved by 전솔람 date 2018. 11. 06.

Finalized by 김희성 date 2018.11.07

Re-Finalized by 칭기즈​ and Muhammad date 2018.11.07/2018.11.10

Final OK by SGLee

Problem

Solve the recurrence relation subject to the initial conditions.

6. an = - 4 an-1 - 4 an-2 a= 2 , a1 = 4

Solution

By using the quadratic formula derived from theorem 2.14 we can see that we can form a second power polynomial by replacing (an = x2an-1 = x, an-2 =1) as following:

x2 = -4x-4

x2+4x+4 = 0

D = b2-4*a*c = 16-16 = 0

x1  and x2 = -4/2 = -2

There is only one root 2 with multiplicity 2.  So,

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

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

a= 2

a1 = 4

1. For n=0 : a0=a*(-20)+b*0(-20)=2

a =2

2. For n=1 : a1=2*(-21)+b*1(-21)=4 =-4-2b =4-2b =8

b=-4

Thus,   an=2*(-2n)-4*n(-2n)

an=2(-2n) - 4n(-2n)

Comment:

Second-order linear homogeneous recurrence relation with constant coefficients일 때 점화식을 푸는 방법에 대해 알 수 있었다.

Comment:

After this question we can see that no single information given in any mathematical problem is redundant, sooner or later we can use it

[Final OK by TA] Ch. 7 P.424 Problem 7 solved by 전솔람 Finalized by 김희성, 칭키즈, Muhammad

Solved by 전솔람 date 2018. 11. 06.

Finalized by 김희성 date 2018.11.07

Re-Finalized by 칭기즈​ and Muhammad date 2018.11.07/2018.11.10

Final OK by TA Date 2018.11.12

Problem

Solve the recurrence relation subject to the initial conditions.

7. a​n= 3a​n-1+ 10a​n-2​ ,  a(0) = 4  a(1) = 13​

Solution

By using the quadratic formula derived from theorem 2.14 we can see that we can forma second power polynomial by replacing(an = x2an-1 = x, an-2 =1) as following:

x​2​=3x+10

x​2​-3x-10=0

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

X=5   x=-2

There are 2 roots so​

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

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

a0=4

a1=13

*For n=0 : a​0​=a*(5​0​)+b*(-2​0​)=2 =a+b=4

*For n=1: a​1​=2*(5​1​)+b*(-2​1)=13 =5a-2b=13

*Next: we will solve these equations for (a,b):

a+b=4 (1)

5a-2b=13 (2)

Let’s multiply equation (1) by 2: 2a+2b=8 (3)

Let’s add equation (3) and (2): a=3

Hence, 3+b=4  b=1

Thus,

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

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

​​ Comment:

Second-order linear homogeneous recurrence relation with constant coefficients일 때 점화식을 푸는 방법에 대해 알 수 있었다.

Comment:

After this question we can see that no single information given in any mathematical problem is redundant, sooner or later we can use it

[ReFinalized] Ch.7, P.424, Problem7, 칭기즈, Muhammad,김희성

solved by 칭기즈 Date 2018.11.09

Revised and Finalized by Muhammad date 2018.11.10

Re-Finalized by 김희성 date 2018.11.14

Problem

Let Cn denote the number of strings over {0,1,2} of length n that contain an even number of 1's.Write a recurrence relation and initial condition that define the sequence C1,C2 , ...

Solve the recurrence relation to obtain an explicit formula for Cn. Solution

Cn=(a)+(b)+(c) , where a,b,c are string types formed by {0,1,2}

there are 3 ways to form a n-length string with even number of 1's:

(a) An n-length​ string begins with 0 and contain an even number of 1's​.

Since any (n-1)-length​ string containing even number of 1's​  can follow the initial 0 C​n-1

(b) An n-length​s string begins with 2 and contain an even number of 1's​.

Since any (n-1)-length​ string  containing even number of 1's​  can follow the initial 2, C​n-1

(c) As n- length string that begins with 1 and (n-1)-length string should contain odd number of 1's

(n-1)-length string should contain odd number of 1's 3​n-1​​C​n-1

Thus,

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

Initial condition : C​1​=2

C​n =​  3​n-1​​+Cn-1​​ = ​3​1​​​+​3​2​​+3​3  ​+ + 3​n-1​​+ C1 =2+(3​n​-3)/(3-1) =(3​n​+1)/2

A recurrence relation and initial condition : C​n = 3​n-1​​ + Cn-1

Initial condition : C​1=2

Solution :  C​n​ ​= (3​n​+1)/2

Comment:

​The idea of this questions is not simple . So I recommend you to go through the different theorems/principles mentioned through the solution before.

Comment:

점화식의 규칙이 보일 , 경우를 나누어서 생각하면 된다는 것을 있다.

Problem 22, Ch.8, P.496, Chapter-Self Test

Solved by 전종문 Date:2018.11.17​​

finilized by 칭기즈 Date:2018.11.17​​​

Final OK by TA Date:2018.11.18

Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28

Problem

In Exercises 21 and 22, determine whether the graphs G1 and G2 are isomorphic. Prove your answer.

22. Definition:

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

Definition  6.1 ---------------------------------------------------------------------

Proof

The adjacency matrix of graph G1​​ relative to vertex ordering v1, v2, v3v4, v5, v6 is equal to the adjacency matrix of graph G2 relative to the vertex ordering w1, w2​​, w3​​, w4, w5, w6​​ Conclusion:

G1 and G2 are isomorphic.

Comment:

This problem is quite straightforward but very useful to get better understanding of Chapter 8, especially isomorphic graphs. The idea of the problem is to check if orderings V1,V2,V3,V4,V5,V6 and W3,W6,W2,W5,W1,Wmake equal adjacency matrices.

Problem 23, Ch.8, P.496, Chapter-Self Test

Solved by 전종문 Date:2018.11.17

Finalized by 김영철 Date:2018.11.17

Final OK by TA Date:2018.11.18​​​​​​

Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28

Problem To have 2 edges and 5 vertices, we have to first think about drawing one edge.

There is only 1 way to draw a graph with 1 edge. However, you try, they are

all isomorphic. Let's call the edge we have drawn as e1 and the vertices that are incident to e1 as v1 and v2.

Now let's draw the second and the last edge and call it as e2. There are only 2 choices:

(1) e2  is incident to only one vertex among v1 and v2.
--> No matter to which vertex it is incident among v1 and v2, it counts as 1,
because the 2 cases are isomorphic.

(2) e2 is not incident to v1, nor v2.
--> Then we have e1 and e2, and v1, v2 and v3, v4 and it counts as 1.

(3) It is not possible that e2 is incident to both v1 and v2.

Considering all the conditions above, we can draw total of 2 graphs, like below. Comment:

This problem is quite straightforward but very useful to get better understanding of Chapter 8, especially isomorphic graphs.

Problem 24, Ch.8, P.496, Chapter-Self Test

Solved by 김승연 Date:2018.11.17​​​​​

Finalized by 김정주 Date:2018.11.26

Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28

Problem

Draw all non isomorphic, simple graphs having exactly five vertices, two components, and no cycles.

Solution

To have such graphs there should be a clear two set of groups of vertices and each group should have different degree of vertices and in this case we have three options:

1) 2-3 vertices groups (degree of 1 – degree 2)
2) 1-4 vertices (degree 3- degree 0)

3) 1-4 vertices (degree 2 – degree 0) Comment:

This problem is quite straightforward but very useful to get better understanding of Chapter 8, especially isomorphic graphs. The idea is we have to develop the thinking of considering all possible cases before sketching.

Problem 27, Ch.8, P.496, Chapter-Self Test

Solved by 전종문 Date:2018.11.17

Revised by 김영철 Date:2018.11.17

Finilized by 칭기즈 Date:2018.11.17

Final OK by TA Date:2018.11.20​​

Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28

Problem Proof

Euler’s formula is

v−e+f = 2

The sum of the degrees of the regions is equal to twice the number of edges.

But each region must have degree ≥ 3.

So we have

2e ≥ 3f

Thus,

2e ≥ 3(2-v+e)

Therefore,

e ≤ 3v − 6.

31≤ 3(12)-6 = 30 is false.

Sage code:

g = graphs.CompleteBipartiteGraph(31,12)

g.show()

g.is_planar()

Practical image: Conclusion:

So, 31 edges and 12 vertices is not planar.

Comment:

This problem is quite straightforward but very useful to get better understanding of Chapter 8, especially isomorphic graphs. The idea is we have to revise all the terminology then proceed to solving while keeping the graphs in mind.

Problem 28, Ch.8, P.496, Chapter-Self Test

Solved by 전종문 Date:2018.11.17

Revised by 김영철 Date:2018.11.17

Final OK by TA Date:2018.11.20​​

Final ok By Prof.Lee & Refinalized by Muhammad Date: 2018.11.28

Problem Proof

0. In a planar graph, each edges belongs to at most two bounding cycles. Therefore, 2e  4f .

1. Euler
s formula is ve+f = 2

2. Then, 2e 4(e-v+2)&n