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-album/2018-Lectures-sglee.htm (강의실)
http://matrix.skku.ac.kr/2018-DM-QnA/ (질문과 답변)
http://matrix.skku.ac.kr/2018-DM-Sol/2018-DM-Sol.htm (문제풀이)
http://matrix.skku.ac.kr/2018-DM-PBL/ (PBL report 보고서)
http://matrix.skku.ac.kr/2018-DM-PBL-Eng/ (PBL report Eng, 영문
보고서)
PBL report of Mr. Muhammad Shakeel Zuhaib
Major: Software (2학년)
Ch 8, Graph Theory
Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-8/
DM-Ch-8-Lab http://matrix.skku.ac.kr/2018-DM/DM-Ch-8-Lab.html
Ch-8-Lab 2 http://matrix.skku.ac.kr/2014-Models/Graph-Project.html
http://discretetext.oscarlevin.com/dmoi/sec_gt-intro.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
[Team 4]
Leader 모하메드 with 김정주, 역충평, 장형준, 이윤성 (Ch 8)
Ch-8-PBL-Solution-모하메드 https://youtu.be/f7_WFw6AtAE
SKKU DM Ch 8, Graph
Theory (review part 2)
(Review
Lecture) https://youtu.be/do4UjVAplp0
◆ General Academic Knowledge (Ch.1 – Ch.9)
(1) State more than 10 DM Definitions and concepts what you learned in Ch. 1, 2, 3, 4, 5, 6, 7, 8, 9.
· Chapter 1: Power Set, Cardinality, Intersection, Relative component, Proposition, De Morgan’s law, Rules of Inference, Deductive Reasoning, Quantifiers and Domain of Discourse.
· Chapter 2: Axioms, Definitions, Proof by Contradiction, Proof by Contrapositive, Proof by Cases, Mathematical Induction and Well Ordering Property.
· Chapter 3: Functions, Pseudo Random Numbers, One to One Function (Injective), On to One Function (Bijective), String, Binary Relation, Symmetric/Anti-Symmetric relation, Equivalence Classes, Matrix of Relation, Relational Data Base.
· Chapter 4: Finiteness, Determinism, Insertion Sort, Big O notation, Theta Notation, Omega Notation and Recursive Function.
· Chapter 5: Prime Numbers, Composite numbers, Greatest Common Devisor, Prime Factorization, Least Common Multiple and The Euclidean Algorithm.
· Chapter 6: Multiplication Principle, Addition Principle, Inclusion-Exclusion Principle, Permutation, Combination, Binomial Theorem, Combinatorial Identity and The Pigeonhole Principle.
· Chapter 7: Recurrence Relation, Cobweb and Ackermann’s Function.
· Chapter 8: Graph, Bacon Numbers, Hypercube, Complete Graph, Bipartite Graph, Isomorphism, Hamiltonian Cycle and the Shortest Path Problem.
· Chapter 9: Free Tree, Huffman Code, Spanning Trees, Breadth-First Search, Depth-First Search, Prim’s Algorithm and In order Traversal.
(2) State more than 9 things that you know/can/find after you studied the 9 Chapters.
Since every chapter is a follow up for the chapter before it; it would be better to put a clear distinction between the academic and the mathematical things I have learnt from each part as following:
· Part 1: In chapter 1, I have filled and revised the knowledge I had back in school times about Sets and the functions related to them. Moving on we learnt new notations to describe any mathematical or real-life proposition by using Quantifiers.
· Part 2: in chapter 2, the most essential technique, that I have always been struggling with, which I have learnt is proving any mathematical statement using various methods from direct proofing to mathematical induction.
· Part 3: in chapter3, this chapter broadened my horizon with new terminology. In addition, I discovered different ways to resemble a relation. For instance, by using a matrix or a data base table.
· Part 4: in chapter4, this chapter I would say was the most interesting chapter for me since I relate to Software department. As far as for the things I have learnt and revised were around the area of analyzing any given algorithm using the three notations mentioned earlier.
· Part 5: in chapter 5, it became easier to identify basic quantities related to any given number like the Greatest Common Devisor and Least Common Multiple.
· Part 6: after studying chapter 6, the whole curriculum changed where I could actually relate the book topics to real world problems or my other courses directly. For instance, I can use Pigeonhole principle to analyze how statistics of a certain property work. E.g. “there are at least two students in SKKU who have the same grade”
· Part 7: in chapter 7, this chapter opened a new world of possibilities for me specifically in programming where I could use recursive functions or recurrence relations to simplify my code instead of depending on the iterative method.
· Part 8: in chapter 8, I learnt about applying Dijkstra’s Algorithm to solve the shortest path problem which a very famous problem in Computer Science. Moreover, through the different set of problems I discovered different types of graphs/subgraphs.
· Part 9: chapter 9 is a follow up chapter for the previous one where I connected my previous knowledge of graphs and Data structure with book’s material to learn more about tree representation and tree traversal methods.
* Personal Reflection Note
(1) Do you understand the most of contents of this learning process?
Yes, due to the fact that the professor already uploads the lectures beforehand and then revise it with us in an offline lecture makes the understanding ability higher. Moreover, in class discussion makes a significant difference on the overall learning and understanding process. In addition, after the midterm we started to have a weekly one-hour offline discussion where we can revise what we studied and clear any misconceptions we have regarding any topic.
(2) What did you learn through the learning activities of this course?
Other than the academic and mathematical knowledge that I mentioned above. The learning curriculum and environment made me more confident about my answers knowing the fact that I can always improvise and revise my own solutions. In addition, I got more familiar with the team work spirit shown by the other students which can be reflected in their quick replies that are intended to enhance the courses’ output for everyone. Moreover, I realized that online discussion could bring a whole new world of possibilities where everyone could use abundant resources to strengthen their point of views
(3) What have you learned from other colleagues?
I have leant how to stay organized and follow the rules instead of being extra quick and inefficient. At the same time, I learnt that working and learning in a group is far better than learning individually since there is always a chance to improvise by learning from others and sharing different ideas.
(4) How do you apply newly learned information to real world problems?
As a foreigner and a Software College student, applying the mathematical laws to a real-world problem is an important thing but what is more important is applying the skills that I am learning from this course onto real-life problems and issues. For instance, I am now always trying to put myself in different discussions rather than staying in the shadows even if it was discussions done by my Korean colleagues. Plus, I always tackle any given deadline by the time-management skills I have learnt from this courses’ curriculum. Moreover, my general programming skills got better through applying discrete mathematics techniques on computer science related problems.
(5) What kind of learning materials have you used to study?
I basically studied the Prof. Lee’s online/YouTube lectures and notes provided by the professor, followed by discussions on QnA where other students can clarify any doubts I might have. Next, the offline lectures made a drastic change where we can have a one to one discussion with the professor and the other students which is finally finished by practicing our knowledge through solving different exercise problems from the text book on the QnA section.
(6) Self-Evaluation for Q/A Activities.
My Score: Although it is hard to criticize myself I would give myself a score of */10. Which is higher than my last month’s evaluation because I believe I have grew to become a better DM student.
◆ Self-Evaluation [Your Opinions]
(1) Satisfaction according to the self-evaluation.
I would say I am satisfied with my overall performance which was very good since I tried my best to ask, solve, revise and finalize as many inquiries as possible. Moreover, I tried to share as much experience with the other as I can. In addition, I changed my approach of learning from questions to discussion which attracted more people and lent me more knowledge.
(2) Sorrow according to the self-evaluation.
The thing that I would definitely have an issue with and I would criticize myself for is the late replies, sometimes I can’t keep up with the number of posts. Which eventually makes my responses come out with a little bit of latency and this is why I deducted 0.5 in my self-evaluation score. Yet Am still improving and I have significantly got better than my last PBL report.
◆ Colleague who helped you learning [Your Opinions]
* Name of Your Class Mate: Chingis Oinar
(1) Reasons to recommend him
He has been extremely active through the QnA, which is very interesting to see it coming from a foreigner freshman from my major. Moreover, he has been always helpful in different discussions whether it was offline or online which encouraged me to be more active so that I could play a vital role in this experience.
(2) Your suggestions for him to improve his contributions to other
Although he has been doing an excellent job, the only thing I would recommend him is to try to have more explanation/comments for the people who don’t have any background about coding. Since his forte is coding and solving algorithms.
◆ 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.
(1) Satisfaction according to the evaluation
Judging from the online performance of my class mates, I would certainly say that everyone is quite satisfied with the system and the environment that the professor provided us with, as long as they are putting enough effort.
(2) Sorrow according to the self-evaluation
The only sorrow I noticed that others are having is that sometimes a good number of students are too late, so they start solving the questions that have already been solved which causes confusion and leads to an unorganized manner.
◆ PBL Feedback for Students
(1) What is the merit/importance/Significance of this PBL class?
The PBL-Flipped Class is playing a vital role in changing the learning experience as it shows the power of online discussions and following the online material. I want to really appreciate the professor to design such a fantastic course outline which is very different from traditional teaching styles. This kind of learning should be applied on other courses since it gives the chance for us as students to interact with each other way more than just sitting in a class and following the old-styled material.
(2) What do you want to improve this PBL system?
For me, the Professor, the TA and the Students are doing a great job in keeping an efficient environment that everyone can benefit from. On the other hand, I would really suggest focusing on the students that are lagging and not doing a great job by assigning them tasks rather than waiting for them to start a discussion. The reason I am saying that is the fact that some students have troubles in understanding the fast pace of others plus some students are too shy to post anything online. Although the team leaders tried to minimize this issue, but still it needs more work.
◆ Participation Part
Fill in the below for your self-assessment 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 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.
(B)Quality of Your Participation:
(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.
(B3) Write names of YOUR PBL Team members and Team Leader.
(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 )
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 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”
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/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
“
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 [Solve-Revise-Finalize and Final OK by SGLee/TA]
p.64, Problem 15 (Chapter1 Self-Test)
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 meeting-Final 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 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, 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 Self-Test)
Solved by 정호진 2018.09.17
Revised By : Muhammad/모하메, Finalized By : Muhammad/모하메드26/Sep/2018
Re-Finalized By : Muhammad/모하메드05/Oct/2018
[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 (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 Self-Test)
Solved by 정호진 2018.09.17 Revised by SGLee 2018.09.17
Finalized by Muhammad /모하메드 2018.9.26
Re-Finalized By : Muhammed/모하메드05/Oct/2018
[Offline] In person meeting-Final 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 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)
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 Self-Test)
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 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
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
Re-Finalized By : Muhammad/모하메드05/Oct/2018
[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. (!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 (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 Morgan’s Law )
≡ (¬pq∨ ¬r ) ^(¬pq∨ s) (Using equation 3.4 in chapter 2)
≡ (¬p ∨¬r )^(¬p ∨ s)^(q ∨¬r )^(q ∨ s)
(Using the 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 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 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 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 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 (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, 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
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)
Solved by Muhammad/모하드:2018.09.28
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 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 Self-Test)
Solved by Muhammad/모하드:2018.09.28
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 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 Self-Test)
Solved by Muhammad/모하드 Date:2018.09.28
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 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 Self-Test)
Solved by Muhammad/모하메드:2018.09.28
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 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 (n-m+1)
{
j = 1
// i is the index in t of the first character of the substring
// to compare with p, and j is the index in p
// the while loop compares ti · · · ti+m−1 and p1 · · · pm
while (ti+j−1 == pj )
{
j = j + 1
if ( j > m) //reaching the end of substring p
return i
}
}
return 0
}
"
*Solution:
Given:
t= "111011"
p= "110"
* Following the code and tracing the loop iterations we can find:
1) For-Loop's First Iteration / i=1:
a) j is set to 1
b) we execute the while-loop , and since t[1]==p[1], j is incremented to compare t[2] and p[2] and since t[2]==p[2], j is incremented once again to compare t[3] and p[3] and since t[3]!=p[3] , the while loop is broken and we move to the next for-loop iteration
2) For-Loop's Second Iteration / i=2:
a) j is set to 1
b) we execute the while-loop , and because i=2 we start
with t[2], since t[2]==p[1], j is incremented to compare t[3] and p[2]
and since t[3]==p[2], j is incremented once again to compare t[4] and p[3]
and since t[4]==p[3] j is incremented once again to become (j=4) which is
greater than (m) , so i=2 is returned.
--------------------------------------------------------
t = "111011" n=6
p = "110" m=3
Hint:
if ( j > m) //reaching the end of substring p
return i
The algorithm terminates when j>m, m=3 => j=4
Trace table:
|
i |
j |
t[i+j-1]==p[j] |
Output |
|
1 |
1 |
true |
- |
|
1 |
2 |
true |
- |
|
1 |
3 |
false |
- |
|
2 |
1 |
true |
- |
|
2 |
2 |
true |
- |
|
2 |
3 |
true |
- |
|
2 |
4 |
|
2 |
Output:
2
□
Comment by Muhammad: Always try to do a step by step plugging in- don’t rush.
p.247 problem 9 Chapter 4
Solved by Muhammad Date: 2018.10.03
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 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
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 I 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 유가이 올렉산드르
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 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
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) //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.
* 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 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 24 = 16.
Answer
24 = 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
Answer: 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 (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
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
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
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 10–13, 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
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
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 an, which 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 + a1 = 2 + 3
= 5
n = 3
-> a3 = 3 + a3-1 = 3 + a2 = 3 +
5 = 8
n = 4 -> a4 = 4 + a4-1 = 4 + a3 = 4 + 8
= 12
Answer:
(a) The first for terms of the sequence.
a1 = 3, a2 = 5, a3 = 8 , a4 = 12
(b) Initial condition for the sequence.
a1 = 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
Re-Finalized 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 a0 be the initial amount
invested
--> a0=4000
2. After 1
year, a1 will be
--> a1 = a0 + 0.17 a0 = 1.17 a0
3. After
2 years, a2 will be
--> a2 = a1 + 0.17 a1 = 1.17 a1 = (1.17)2 a0
4. Thus,
after n years, an will be
--> an = an-1 + 0.17 an-1 = (1.17) an-1 = ... = (1.17)n a0
Answer:
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). That’s why the relation/equation provided by the original answer (an = (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 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) Pk = ( n-2∑n=0 C(n-2,k) Pk )*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 a n-1 ways to cover the 2 x (n-1) board that remains.
If the first two dominoes are placed as shown,
there are a 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 = f3 ⇒ 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 , a0 = 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 = x2, an-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:
a0 = 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)
Answer:
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. an = 3an-1 + 10an-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 = x2, an-1 = x, an-2 =1) as following:
x2=3x+10
x2-3x-10=0
(x-5)(x+2)=0
X=5 x=-2
There are 2 roots so
an=a*(5n)+b*(-2n)
* Our next step is to find the coefficients(a,b) using:
a0=4
a1=13
*For n=0 : a0=a*(50)+b*(-20)=2 =a+b=4
*For n=1: a1=2*(51)+b*(-21)=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,
an=3*(5n)+1*(-2n)
Answer:
an=3*(5n)+1*(-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
[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
By the Addition Principle
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 ⇒ Cn-1
(b) An n-lengths 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, ⇒Cn-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 ⇒3n-1- Cn-1
Thus,
Cn= Cn-1+Cn-1+3n-1-Cn-1 = 3n-1+Cn-1
Initial condition : C1=2
Cn = 3n-1+Cn-1 = 31+32+33 + … + 3n-1+ C1 =2+(3n-3)/(3-1) =(3n+1)/2
Answer:
A recurrence relation and initial condition : Cn = 3n-1 + Cn-1
Initial condition : C1=2
Solution : Cn = (3n+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, v3, v4, 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,W4 make 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
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 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
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) 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 v−e+f = 2
2. Then, 2e≥ 4(e-v+2)&n