Discrete Mathematics (Ch 8, Graph Theory)
SKKU Math Lectures and Labs
Prof : SangGu LEE (http://matrix.skku.ac.kr/sglee/ )
http://matrix.skku.ac.kr/2018DM/DMLabs.htm Discrete Math Labs (실습실)
http://matrix.skku.ac.kr/2018album/2018Lecturessglee.htm (강의실)
http://matrix.skku.ac.kr/2018DMQnA/ (질문과 답변)
http://matrix.skku.ac.kr/2018DMSol/2018DMSol.htm (문제풀이)
http://matrix.skku.ac.kr/2018DMPBL/ (PBL report 보고서)
http://matrix.skku.ac.kr/2018DMPBLEng/ (PBL report Eng, 영문
보고서)
Ch 8, Graph Theory
Lecture Note http://matrix.skku.ac.kr/2018DM/Ch8/
DMCh8Lab http://matrix.skku.ac.kr/2018DM/DMCh8Lab.html
Ch8Lab 2 http://matrix.skku.ac.kr/2014Models/GraphProject.html
http://discretetext.oscarlevin.com/dmoi/sec_gtintro.html
(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
* Name of Your Class Mate: Chingis Oinar
*Note: this part is more of a general response rather than picking a specific person as above mentioned.
Fill in the below for your selfassessment and your project/term paper.
(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 Inclass)?
My contribution as an individual was twoway 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.
(B)Quality of Your Participation:
(B1) What did you especially remember while you are doing A1, 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.
(B3) Write names of YOUR PBL Team members and Team Leader.
(B4) What is your project (and Indepth 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.
◆ Number of your QnA participation up to the Due date. ( 192 total entries )
Part 1: Your meaningful questions in QnA which you had you got the Final answer.
· 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?”
Professor Reply: Date
13/09/2018
“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^^”
Question by TA and follow up question by me (Muhammad)
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.”
Solved by Muhammad: Date 16/09/2018
“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
“
Follow up Question by Muhammad: Date 17/09/2018
“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 notesPDF” 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”
Professor Reply: Date 26/09/2018
“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/2018DM/DMCh2Lab.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
“
Professor
Reply: Date 29/09/2018
“
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 [SolveReviseFinalize and Final OK by SGLee/TA]
p.64, Problem 15 (Chapter1 SelfTest)
Solved by 전종문, 2018.09.14
Revised by Muhammad/모하메드, 2018.09.17
Finalized by 전종문, 2018.09.20
Refinalized by Muhammad/모하메드. 2018.10.05
[Offline] In person meetingFinal Ok By Professor, 2018.10.05
Problem:
Determine whether the following argument is valid.
p →q ∨ r
p ∨￢q
r ∨ 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
Solved by Muhammad Date 16/09/2018
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 SelfTest)
Solved by 김희성 Sep . 16^{th} Revised by 조영은 Sep, 21th
Finalized by 모하메드 Sep,26th ReFinalized by 모하메드 Oct,05^{th}
[Offline] In person meetingFinal 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, let’s 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 SelfTest)
Solved by 정호진 2018.09.17
Revised By : Muhammad/모하메, Finalized By : Muhammad/모하메드26/Sep/2018
ReFinalized By : Muhammad/모하메드05/Oct/2018
[Offline] In person meetingFinal Ok By Professor, 2018.10.05
Problem 5:
If p, q and r are true, find the truth value of the proposition (p∨q) ∧ ㄱ((ㄱp∧ r) ∨q))
Solution:
p∨q  true; ㄱp∧ r  false;
(ㄱp∧ r) ∨q)  true; ㄱ((ㄱp∧ r) ∨q))  false;
(p∨q) ∧ ㄱ((ㄱ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 SelfTest)
Solved by 정호진 2018.09.17 Revised by SGLee 2018.09.17
Finalized by Muhammad /모하메드 2018.9.26
ReFinalized By : Muhammed/모하메드05/Oct/2018
[Offline] In person meetingFinal Ok By Professor, 2018.10.05
Problem 8
Assume that a, b, and c are real numbers. Represent the statement
a<b or (b<c and a ≥ 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 A = {1, 3, 4, 5, 6, 7}, B = {x  x is an even integer},
C = {2, 3, 4, 5, 6}, find (A ∩ B) − C.
Solution
A = {1, 3, 4, 5, 6, 7}
B = {x  x is an even integer}=｛2,4,6,8,10,...｝
C = {2, 3, 4, 5, 6}
A ∩ B= {4,6}
Since, (A ∩ B) ⊆ C
(A ∩ 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, b ≥ c is same to the reverse of q ( b < c ), so b ≥ c represents ￢ q
As a result, " ( a ≥ c or b < c ), then ( b ≥ c ) " can be represented as " ( ￢ r ∨ q ) → ￢ q
Page 64 Problem 17Ch. 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)
Answer No!
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 SelfTest)
Solved by 전종문, Date : 2018.09.21
Revised by 유가이 올렉산드르: 2018.09.23
Finalized by Muhammad/모하메드:2018.09.26
ReFinalized and Final OK by SGLee 2018.09.27
Problem
Use mathematical induction to prove that the statements in Exercises 1316 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
Finalized by Muhammad/모하메드 2018.09.26
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, 공리와 정의, 정리의 차이
2) 공리
뜻 : 증명 없이 참으로 받아들이는 명제
예시 :
1. 임의의 점에서 임의의 점으로 직선을 그을 수 있다.
2. 유한인 직선(좀 애매함 선분이라고 생각하시는게좋음)은 연장할 수 있다.
3. 임의의 중심과 거리를 가지고 원을 가지고 원을 그릴 수 있다.
4. 모든 직각은 서로 같다.
5. 직선 밖의 한 점을 지나 이 직선에 평행하는 직선은 오직 하나뿐이다.
위와 같은 유클리드기하의 5대 공리가 예시이다.
1) 정의
뜻 : 수학용어나 기호에 대하여 그 의미를 규정한 것.
예시 : 직각삼각형 : 한 내각의 크기가 직각인 삼각형을 직각삼각형이라 한다.
정삼각형 : 세 변의 길이가 같은 삼각형을 정삼각형이라 한다.
3) 정리
수학적으로 증명된 참인 명제
예시 :피타고라스의 정리 ( )
Page : 124 Problem 10 Chapter2
Solved By : Muhammad/모하메드: 2018.09.24
Finalized by 유가이 올렉산드르: 2018.09.26
ReFinalized By : Muhammad/모하메드05/Oct/2018
[Offline] In person meetingFinal 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 "andclause",
* andclause is a clause/statement of the form as following:
e.g. a^b^c^d^e
e.g.2. (!a∨b)^(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 (andclause) (also named maxterm).
* Solution:
*Note: rs = r^s
( p ∨¬q) → ¬rs ≡ ¬( p ∨¬q) ∨¬rs (by using equivalent statements/Resolution Proof)
≡ ¬pq ∨ ¬rs (using De Morgan’s Law )
≡ (¬pq∨ ¬r ) ^(¬pq∨ s) (Using equation 3.4 in chapter 2)
Page : 124 Problem 20 Chapter 2
Solved By : Muhammad/모하메드 25/sep/2018
Finalized by : 강병훈 27/sep/2018
Final OK by SGLee
20. Use the WellOrdering 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 Y = {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 Y which is the set of integers upper bound for the set X. By this assumption, we can deduce that Y is a nonempty 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 y≧x 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 (y1) ∈ 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, y≧x for
every x ∈ 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
Finalized by Muhammad/모하메드 2018.09.28
ReFinalized by 오동찬 2018.09.29
Final OK by SGLee
Exercises 1720 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 SelfTest)
Solved by Muhammad/모하드:2018.09.28
Finalized by 오동찬, Date: 2018.09.30
ReFinalized By : Muhammed/모하메드:05/Oct/2018
[Offline] In person meetingFinal Ok By Professor, 2018.10.05
In Exercises 21–24, 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 SelfTest)
Solved by Muhammad/모하드:2018.09.28
Finalized by 오동찬, Date: 2018.09.30
ReFinalized By : Muhammed/모하메드:05/Oct/2018
[Offline] In person meetingFinal Ok By Professor, 2018.10.05
In Exercises 21–24, 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 SelfTest)
Solved by Muhammad/모하드 Date:2018.09.28
Finalized by 전종문 Date: 2018.09.28
ReFinalized By : Muhammed/모하메드:05/Oct/2018
[Offline] In person meetingFinal Ok By Professor, 2018.10.05
Problem
In Exercises 21–24, 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 SelfTest)
Solved by Muhammad/모하메드:2018.09.28
Finalized by 오동찬, Date: 2018.09.30
ReFinalized By : Muhammed/모하메드:05/Oct/2018
[Offline] In person meetingFinal Ok By Professor, 2018.10.05
In Exercises 21–24, 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)
Solved by Muhammad/모하메드 : 2018.10.03
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), m, t (indexed from 1 to n), n
Output: i (the index of first match occurrence)
Pseudo Code:
text search( p, m, t, n) {
for (i = 1 to n − m + 1) //the starting point is 1, the ending point is (nm+1)
{
j = 1
// i is the index in t of the first character of the substring
// to compare with p, and j is the index in p
// the while loop compares ti · · · ti+m−1 and p1 · · · pm
while (ti+j−1 == pj )
{
j = j + 1
if ( j > m) //reaching the end of substring p
return i
}
}
return 0
}
"
*Solution:
Given:
t= "111011"
p= "110"
* Following the code and tracing the loop iterations we can find:
1) ForLoop's First Iteration / i=1:
a) j is set to 1
b) we execute the whileloop , and since t[1]==p[1], j is incremented to compare t[2] and p[2] and since t[2]==p[2], j is incremented once again to compare t[3] and p[3] and since t[3]!=p[3] , the while loop is broken and we move to the next forloop iteration
2) ForLoop's Second Iteration / i=2:
a) j is set to 1
b) we execute the whileloop , and because i=2 we start
with t[2], since t[2]==p[1], j is incremented to compare t[3] and p[2]
and since t[3]==p[2], j is incremented once again to compare t[4] and p[3]
and since t[4]==p[3] j is incremented once again to become (j=4) which is
greater than (m) , so i=2 is returned.

t = "111011" n=6
p = "110" m=3
Hint:
if ( j > m) //reaching the end of substring p
return i
The algorithm terminates when j>m, m=3 => j=4
Trace table:
i 
j 
t[i+j1]==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
□
p.247 problem 9 Chapter 4
Solved by Muhammad Date: 2018.10.03
finalized by 엄자균 Date: 2018.10.04
ReFinalized by 서명원 Date: 2018.10.05
Final OK by SGLee
Problem
Select a theta notation from among Θ (1), Θ (n), Θ (n^{2}), Θ (n^{3}),Θ (n^{4}), Θ (2^{n}), or Θ (n!) for each of the expressions in Exercises 9 and 10.
9. 4n^{3} + 2n − 5
Discussion
f(n)= O (g(n)) if f(n) ≤ C_1 *g(n) for constant 'C_1 ' and n_{0} ≤ n
f(n)= Ω (g(n)) if f(n) >= C_2 *g(n) for constant 'C_2' and n_{0} ≤ n
f(n)= θ (g(n)) if f(n) is O(g(n)) and f(n) is Ω (g(n)).
The problem 9 '4n^{3} + 2n − 5' is θ(n^{3})
Sol.
Since 10n^{3} > 4n^{3} + 2n − 5, c_1 = 10 where C_1 = 10 and 4n^{3} + 2n − 5
> 1/10 n^{3} where C_2 = 1/10 (n_{0}=1)
=> '4n^{3} + 2n − 5' is Θ(n^{3}) □
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 worstcase time.
*Solution:
Input: A and B (n × n matrices) and n
Output: true (if A =
B ); false (if A ≠ 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
worstcase time is theta of (n^2) why? because we have a
nested loop (2step loop) where for each index in the iloop the jloop 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
Onotation since it gives the upper boundworst case for an algorithm.
Since I am
from software department i thought this would be helpful.
Page 263 Problem № 2 (Chapter5 SelfTest)
Solved by AYSU OZGUNEKIM
Revized by 김주형
Finalized by 유가이 올렉산드르
Refinalized by Muhammad/모하메드
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 N^{1/2}
if (N mod d == 0) //mod function returns the remainder
return d
return 0
}
*Solution:
Using the algorithm mentioned earlier, we can easily check whether an integer(N) is prime or not, so we combine the same algorithm with division to solve this problem as following.
Let's solve this task by using a factorial tree:
*The yellow marked numbers are prime.
So we get : 539=(7^2)*11
■
Comment: From this problem, I realized that Factors are the numbers you multiply together to get another number.
ex)
5*3 = 15. And Prime Factorization is finding which prime
numbers multiply together to make the original number. ■
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 SelfTest)
Solved by 김희성 2018.10.07
Executed by 김영철 2018.10.08
Revised and Finalized Muhammad/모하메드 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) //Whileloop 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) //Whileloop 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) //Whileloop 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) //Whileloop 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) //Whileloop 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.
* Comment by Muhammad:
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 eightbit 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 5th8th 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 eightbit encoding is 2^{4 }= 16.
Answer
2^{4 }= 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 3combinations are there of six objects?
Solution
C (6 ,3 ) = 6 ! ÷ (3 ! × 3 ! ) = 20
Answer: 2^{}0 ■
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
sixcard hands chosen from an ordinary 52card deck
contain three cards of one suit and three cards of another suit?
Solution
1. C (13, 3) = 286 (one suit)
2. C (13, 3) = 286 (another suit)
3. C (4 , 2) = 6 (2 suits)
4. 286 x 286 x 6 = 490,776.
Answer: 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
Answer: 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)
Answer
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
x_{}_{1 }+ x_{}_{2} + x_{}_{3 }+ x_{}_{4} = 17
Satisfy
x_{}_{1 }≥ 0, x_{}_{2 }≥ 1, x_{}_{3 }≥ 2, x_{}_{4 }≥ 3
Solution
x_{}_{2 }= x_{}_{2}'+ 1, x_{}_{3} = x_{}_{3}'+ 2, x_{}_{4 }= x_{}_{4}' + 3
x_{}_{1 }+ x_{}_{2}+ x_{}_{3 }+ x_{}_{4} = x_{}_{1 }+ (x_{}_{2}'+1) + (x_{}_{3}'+2) + (x_{}_{4}'+3) = 17
x_{}_{1 }+ x_{}_{2}' + x_{}_{3}' + x_{}_{4}' = 11
Satisfy
x_{}_{1 }≥ 0, x_{}_{2}'_{ }≥ 0, x_{}_{3}'_{ }≥ 0, x_{}_{4}'_{ }≥ 0
For combination for repetition,
_{}_{n}H_{}_{r} = _{}_{n+r1}C_{}_{r} = _{}_{11+41}C_{}_{4} = _{}_{14}C_{}_{4} = 14!/(4!×10!) = (14×13×12×11)/(4×3×2×1)=1001
Answer = 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
s_{1} = 6, s_{2} = 4, s_{3} = 2, s_{4} = 7, s_{5} = 1, s_{6} = 3, s_{7} = 5
Step2: At line 6, the largest index m satisfying s_{m} < s_{m+1 } is 6 (s_{6} = 3)
Step3: At lines 10–13, we find that the largest index k satisfying s_{k} > s_{m} is 7 (s_{7} = 5).
Step4: At line 14, swap s_{m} and s_{k}
s_{6} = 5 and s_{6} = 3
Step5: Swap 6 and 7 : 6427153
Answer : 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 sn−1, 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.
Finalized by 칭기즈 Date 2018.11.06
ReFinalized by 김영철 Date 2018.11.07
ReFinalized (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 nth term of the sequence be a_{}_{n}_{, }which logically makes the previous term a_{}_{n1}.
2. Hence, the formula of nth term is a_{}_{n} = n + a_{}_{n1}
3. Let me remind you that the first term is 3 ( a_{}_{1}=3 )
4. Hence to
find another three elements:
n = 2
> a_{}_{2} = 2 + a_{}_{21 }= 2 + a_{}_{1 }= 2 + 3
= 5
n = 3
> a_{}_{3} = 3 + a_{}_{31 }= 3 + a_{}_{2} = 3 +
5 = 8
n = 4 > a_{}_{4}_{ }= 4 + a_{}_{41 }= 4 + a_{}_{3 }= 4 + 8
= 12
Answer:
(a) The first for terms of the sequence.
a_{}_{1} = 3, a_{}_{2} = 5, a_{}_{3} = 8 , a_{}_{4 }= 12
(b) Initial condition for the sequence.
a_{}_{1 }= 3
(c) A recurrence relation for the sequence.
a_{}_{n} = n + a_{}_{n1}_{ }_{ }■
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
ReFinalized by Muhammad Date 2018.11.10
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 a_{}_{0}_{ }be the initial amount
invested
> a_{}_{0}=4000
2. After 1
year, a_{}_{1}_{ }will be
> a_{}_{1} = a_{}_{0 }+ 0.17 a_{}_{0 }= 1.17 a_{}_{0}
3. After
2 years, a_{}_{2}_{ }will be
> a_{}_{2} = a_{}_{1 }+ 0.17 a_{}_{1 }= 1.17 a_{}_{1}_{ }= (1.17)^{}^{2 }a_{}_{0}_{}
_{}4. Thus,
after n years, a_{}_{n} will be
> a_{}_{n} = a_{}_{n1 }+ 0.17 a_{}_{n1} = (1.17)^{ }a_{}_{n1} = ... = (1.17)^{}^{n }a_{}_{0}
Answer:
Initial
state: a_{}_{0}=4000
Recurrence
relation: a_{}_{n} = (1.17)a_{n1}^{ },
where a_{0}=4000 ■
Comment:
복리계산에 대한 내용과 그것을 점화식으로 표현해 볼 수 있었다.
Comment:
Remember that recurrence relation should in the form of a_{n}_{ }represented by any predecessor term like (a_{n1}). That’s why the relation/equation provided by the original answer (a_{}_{n} = (1.17)^{}^{n }* 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
Finalized by 김영철 Date 2018.11.10
Refinalized by Muhammad 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 nelement set and choose x ∈ X and k be a fixed integer (0 ≤ k ≤ n  1)
2. We can select a kelement subset Y from X  {x} in C(n1, k) ways.
3. Next, we can partition Y in P_{k} 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 P_{}_{n} satisfies the recurrence relation, we can find a relationship between P_{}_{n} and P_{}_{n1}.
P_{}_{n} = ^{}^{n1}∑^{}_{n=0} C(n1,k) P_{k} = ( ^{n2}∑^{}_{n=0} C(n2,k) P_{k} )*n1 +C(n1,n1)P_{}_{n1} = (P_{}_{n1}) *n1 + P_{}_{n1}= n*P_{}_{n1}
Then we showed that P_{}_{n} = n *P_{}_{n1} 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 a _{n1} ways to cover the 2 x (n1) board that remains.
If the first two dominoes are placed as shown,
there are a _{n2} ways to cover the 2 x (n2) board that remains.
If follows that a_{n} = a _{n1} + a_{ n2}.
By inspection, a_{1} = 1 and a_{2} = 2.
Since (a_{n}} satisfies the same recurrence relation as the Fibonacci sequence
a_{1} = f_{2} and a_{2} = f_{3 } ⇒ a_{n} = 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
ReFinalized 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. a_{}_{n} =  4 a_{}_{n1}  4 a_{}_{n2} , a_{}_{0 }= 2 , a_{}_{1} = 4
Solution
By using
the quadratic formula derived from theorem 2.14 we can see
that we can form a second power polynomial by replacing (a_{}_{n} = x^{}^{2}, a_{}_{n1} = x,
a_{}_{n2} =1) as following:
x^{}^{2} = 4x4
x^{}^{2}+4x+4 = 0
D = b^{}^{2}4*a*c = 1616 = 0
x_{}_{1} and x_{}_{2} = 4/2 = 2
There is only one root 2 with multiplicity 2. So,
a_{}_{n}=a*(2^{}^{n})+b*n(2^{}^{n})
* Our next step is to find the coefficients (a, b) using:
a_{}_{0 }= 2
a_{}_{1} = 4
1. For n=0 : a_{}_{0}=a*(2^{}^{0})+b*0(2^{}^{0})=2
a =2
2. For n=1 : a_{}_{1}=2*(2^{}^{1})+b*1(2^{}^{1})=4 =42b =42b =8
b=4
Thus, a_{}_{n}=2*(2^{}^{n})4*n(2^{}^{n})
Answer:
a_{}_{n}=2(2^{}^{n})  4n(2^{}^{n}) ■
Comment:
Secondorder 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
ReFinalized 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_{n1} + 10a_{n2} , a(0) = 4 a(1) = 13
Solution
By using the quadratic formula derived from theorem 2.14 we can see that we can forma second power polynomial by replacing(a_{}_{n} = x^{}^{2}, a_{}_{n1} = x, a_{}_{n2} =1) as following:
x^{2}=3x+10
x^{2}3x10=0
(x5)(x+2)=0
X=5 x=2
There are 2 roots so
a_{n}=a*(5^{n})+b*(2^{n})
* Our next step is to find the coefficients(a,b) using:
a_{}_{0}=4
a_{}_{1}=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 =5a2b=13
*Next: we will solve these equations for (a,b):
a+b=4 (1)
5a2b=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*(5^{n})+1*(2^{n})
Answer:
a_{n}=3*(5^{n})+1*(2^{n}) ■
Comment:
Secondorder 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
ReFinalized by 김희성 date 2018.11.14
Problem
Let C_{}_{n} 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 C_{}_{1,}C_{}_{2} , ...
Solve the recurrence relation to obtain an explicit formula for C_{}_{n}.
Solution
By the Addition Principle
C_{}_{n}=(a)+(b)+(c) , where a,b,c are string types formed by {0,1,2}
there are 3 ways to form a nlength string with even number of 1's:
(a) An nlength string begins with 0 and contain an even number of 1's.
Since any (n1)length string containing even number of 1's can follow the initial 0 ⇒ C_{n1 }_{ }
(b) An nlengths string begins with 2 and contain an even number of 1's.
Since any (n1)length string containing even number of 1's can follow the initial 2, ⇒C_{n1 }_{ }_{ }
(c) As n length string that begins with 1 and (n1)length string should contain odd number of 1's
(n1)length string should contain odd number of 1's ⇒3^{n1} C_{n1 }_{ }
Thus,
C_{n}= C_{n1}+C_{n1}+3^{n1}C_{n1} = 3^{n1}+C_{n1}
Initial condition : C_{1}=2
C_{n} = 3^{n1}+C_{n1} = 3^{1}+3^{2}+3^{3 }+ … + 3^{n1}+ C1 =2+(3^{n}3)/(31) =(3^{n}+1)/2
Answer:
A recurrence relation and initial condition : C_{n} = 3^{n1} + C_{n1}
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, ChapterSelf 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 G_{}_{1} and G_{}_{2} are isomorphic. Prove your answer.
22.
Definition:

Definition 6.1

Proof
The adjacency matrix of graph G_{}_{1} relative to vertex ordering v_{}_{1}, v_{}_{2}, v_{}_{3}, _{}v_{}_{4}, v_{}_{5}, v_{}_{6}
is equal to the adjacency matrix of graph G_{}_{2} relative to the vertex ordering w_{}_{1}, w_{}_{2}, w_{}_{3}, w_{}_{4}, w_{}_{5}, w_{}_{6}
Conclusion:
∴G_{}_{1} and G_{}_{2} 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 V_{}_{1,}V_{}_{2,}V_{}_{3,}V_{}_{4}_{}_{,}V_{}_{5,}V_{}_{6}_{ }and W_{}_{3,}W_{}_{6,}W_{}_{2,}W_{}_{5,}W_{}_{1,}W_{}_{4 }make equal adjacency matrices.
Problem 23, Ch.8, P.496, ChapterSelf 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
Answer:
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 e_{1} and the vertices that are incident to e_{1} as v_{1} and v_{2}.
Now let's draw the second and the last edge and call it as e_{2}. There are only 2 choices:
(1) e_{2}
is incident to only one vertex among v_{1} and v_{2}.
> No matter to which vertex it is incident
among v_{1} and v_{2}, it counts as 1,
because the 2
cases are isomorphic.
(2) e_{2} is not incident to v_{1}, nor v_{2}.
> Then we have e_{1} and e_{2},
and v_{1}, v_{2} and v_{3}, v_{4} and it counts
as 1.
(3) It is not possible that e_{2} is incident to both v_{1} and
v_{2}.
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, ChapterSelf Test
Solved by 김승연 Date:2018.11.17
Finalized by 김정주 Date:2018.11.26
Refinalized by Muhammad. Date: 2018.11.27
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) 23
vertices groups (degree of 1 – degree 2)
2) 14 vertices (degree 3 degree 0)
3) 14 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, ChapterSelf 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(2v+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, ChapterSelf 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 v−e+f = 2
2. Then, 2e≥ 4(ev+2)&n