SKKU Discrete Mathematics

(Ch. 5, Introduction to Number Theory)

Prof : Sang-Gu Lee  at SKKU

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

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

Ch. 5, Introduction to Number Theory

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

DM-Ch-5-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-5-Lab.html
DM Ch. 5, 동영상강의

5-1 Divisors    https://youtu.be/NN46r0qlIW0

5-2  Repr of Integers and Integer Alg https://youtu.be/aF5MPAjkMcI

5-3  The Euclidean Algorithm   https://youtu.be/sSuzv8J3MSA

Review (Ch 1-5)  https://youtu.be/aeKA-MNkhCw

PBL 학생 발표 (Ch 1-5 Solutions)  https://youtu.be/HuzLCXDD2AA

Midterm Exam Solutions : https://youtu.be/iAfQCycd6ac

(1)  State more than 10 DM Definitions and concepts what you learned in Ch. 1, 2, 3, 4, 5 ,6,7,8,9

 Sets and Logic Set, Logic, objects, cardinality, Empty set, Equal sets, subset ,  proper subset, power set, union, intersection , partition , Cartesian product , proposition, conjunction, disjunction, contrapositive , De Morgan’s Law… Proofs Definitions, Theorem, Lemma, Corollary, congruent, supplementary, direct proof, counterexample, Proof by contradiction, Proof by contrapositive, Proof by cases, Proofs of equivalence, existence Proofs … Functions, Sequences and Relations Functions, mappings, transformations, ordered-pair, floor, ceiling, The Quotient(Chinese)-Remainder Theorem, one-to-one (injunctive)  function, Onto function, bijective function, Inverse Function, composition function, unary operator, sequence, string, digraph, reflexive, symmetric, transitive… Algorithms Algorithm, Sorting , Insertion Sort, Best-case-time, randomized algorithm , big oh, omega,  theta … Introduction to Number Theory Divisor, factor, quotient, Fundamental Theorem of Arithmetic, prime number,LCM,GCD, bit, binary Number System, base, repeated squaring, Euclidean Algorithm, BÉZOUT’'S THEOREM,RSA cryptosystem… Counting Methods and The Pigeon Hole Principle Multiplication Principle, reflexive relations, Addition Principle, Inclusion-Exclusion Principle, Permutation, r-permutation, combinations, good route, Catalan numbers, Binomial Theorem, Pascal’s triangle, Pigeonhole Principle… Recurrence Relations recurrence relation, Ackerman’s Function,  iteration, linear homogeneous recurrence relation with constant coefficient, nonlinear recurrence relations… Graph Theory Graphs, vertices, edges, Path, parallel edge, isolated vertex, simple graph, weight graph, similarity graph, bipartite , complete bipartite, connected graph, components, degree of a vertex, Hamilton’s puzzle,  ring model, adjacency matrix, isomorphic, planer, planar graph… Trees rooted tree,level of a vertex, height, Huffman codes, Hierarchical Definition trees, internal vertex, terminal vertex , spanning tree , depth-first search, Minimal spanning tree, child, binary tree , Tree Traversals, isomorphic trees, nonisomorphic trees

The level of a vertex  is the length of the simple path from the root to .

recurrence relation defines a sequence by giving the th value in terms of its predecessors.

A cycle in a graph  contains each vertex in  exactly once, except for the starting and ending vertex that appears twice, a Hamiltonian cycle.

The symbol   is a universal quantifier, which is interpreted as “for every”, “for any value of “ and etc.

The symbol is an existential quantifier, which means “ there exists”, “there is at least one value of” ant etc.

An algorithm is a sequence of operations that are executed in a certain step-by-step method.

binary number is a number written in the base-2numeral system or binary numeral system, which uses only 0 (zero) and 1 (one).

The octal numeral system is expressed in the base-8 number system, and uses the only 0 to 7.

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

 Sets and Logic union, intersection , Cartesian product , proposition, conjunction, De Morgan’s Law… Proofs direct proof, counterexample, Proof by contradiction, Proof by contrapositive, Proof by cases, Proofs of equivalence, existence Proofs … Functions, Sequences and Relations floor, ceiling, The Quotient(Chinese)-Remainder Theorem, composition function, unary operator, sequence, digraph, reflexive, symmetric, transitive… Algorithms Algorithm, Sorting , Insertion Sort, Best-case-time, randomized algorithm , big oh, omega,  theta ,Insertion Sort, Bubble Sort… Introduction to Number Theory Fundamental Theorem of Arithmetic, prime number,LCM,GCD, binary Number System, base, repeated squaring, Euclidean Algorithm, BÉZOUT’'S THEOREM,RSA cryptosystem… Counting Methods and The Pigeon Hole Principle Multiplication Principle, Addition Principle, Inclusion-Exclusion Principle, Permutation, r-permutation, combinations, good route, Catalan numbers, Binomial Theorem, Pascal’s triangle, Pigeonhole Principle… Recurrence Relations recurrence relation, Ackerman’s Function,  iteration, linear homogeneous recurrence relation with constant coefficient, nonlinear recurrence relations… Graph Theory Graphs, Path, weight graph, Dijkstra’s Shortest-Path Algorithm, Hamilton’s puzzle,   adjacency matrix… Trees rooted tree, Huffman codes, Hierarchical Definition trees, spanning tree , depth-first search, Minimal spanning tree, binary tree , Tree Traversals, inorder,preorder,postorder traversals

The order of quantifiers is essential because changing the order changes the meaning.

A number is composite if it is divisible by any number in the range of [2; floor(sqrt(n))], otherwise it is a prime number.

The characteristics of algorithm is: input, output,definiteness, effectiveness, finiteness,correctness and generality but in some algorithms some characteristics my be absent.

To solve recurrence relation by iteration we need to keep substituting elements with the previous one until it reaches initial condition.

Ackerman’s function is the recurrence relations

(1.11)               ,

(1.12)               ,

.

The initial conditions

(1.13)                    ,

Ackerman’s function is rapid rate of growth.

gcd(a,b) can be found by taking the product of the prime numbers to the power of the minimum exponent between two numbers.

Then  is

.

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

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

As it can be seen I was relatively active since I was participating on QnA a lot. I think my solutions were useful for some people to understand the concept of the class. Moreover, I solved a lot of computer exercises which can be useful to understand the concept and idea of the chapter 4, which is algorithm

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

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

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

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

Page 124 (computer exercises) problem 2

Solved by 칭기즈,Date: 2018.09.25

Revised by 김정주,Date: 2018.09.30

Final OK by SGLee

I especially remember it since 김정주 made me conclude that any problem can be solved in different ways, however they are not equally efficient. After this I realized what does efficiency of the algorithm really mean. As a future student of software department, it is very important for me that is why I like the system of QnA.

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

During the classes of Discrete Mathematics, I developed my computational thinking skills due to chapter 4 and 3(Algorithms, Functions, Sequences and Relations ), critical thinking skills due to chapter 1 and 2(Sets and Logic, Proofs) and enlarged my knowledge of Number Theory due to chapter 5. I think these classes were useful for me as a student of software engineering department.

Team Members: 칭기즈, 유가이올렉산드르, 김승연, 권재연, 이상민,

​(B4) (Tentative) Project (1st Draft)

What is your project (and In-depth study) and your role in your Team (Leader, Idea, Solve, Prove, Coding, Typing, Presentation etc). (Write what you have done on your Chapters!)  or ******

The area of our project should be related to the chapter 4 which is Algorithms and chapter 5, Number theory, hence we decided to take Addition of Binary numbers for an in-depth study because it will show the relationship between those two chapters.

3. PBL 참여 부분

Solve-Revise-Finalize (and Final OK)

Page : 64   Problem 21

Solved By : 칭기즈, Date: 2018.09.19

Finalized By: 유가이 올렉산드르, Date: 2018.09.21

Final OK by TA , Date: 2018.10.04

Problem 21

Let K (x, y) be the propositional function “x knows y”. The domain of discourse is the Cartesian product of the set of students taking discrete math with itself (i.e. both x and y take on values in the set of students taking discrete math). Represent the assertion “someone does not know anyone” symbolically.

Solution

Denote the statement “x does not know y” as K (x, y). Since both x and y are the Cartesian product of the set of students who have taking discrete mathematics (this is the set of students about which we are talking in the exercise [all students]), then we can assume than someone of the student x (x) doesn’t know anyone of the student y (y). Full symbolic expression (someone does not know anyone): K (x, y). ■

Note: This problem helped me to understand the meaning and the concept of  symbols   used in Discrete mathematics and apply them in

problem solving.

p.124, Problem 7 (Chapter Self-Test)​​

Solved by 칭기즈 Date: 2018.09.26

Finalized by 서명원 Date: 2018.09.27

Final Ok by TA  Date: 2018.09.27

Problem

7. Use proof by cases to prove that

min{min{a,b},c}= min{a,min{b,c}}

for all real numbers a,b and c

Solution:

Discussion: In order to proof  by cases we have to identify all possible cases and try each of them to identify whether the given statement is true of false. There are 6 possible cases, which are:

1.a >=b >=c

2.a>=c>=b

3.b>=a>=c

4.b >= c >= a

5.c>=a>=b

6.c>=b>=a

Solution:

we arrange these cases to two case: a≤b and ab.

In each of these two cases, we should consider the two cases: b≤c and bc.

First suppose that a≤b.

If b≤c, then

min{min{a,b},c}=min{a,c}=a=min{a,b}

=min{a,min{b,c}}.

if b>c, then

min{min{a,b},c}=min{a,c}=min{a,min{b,c}}.

In either case,

min{min[a,b},c}=min{a,min{b,c}}.

And,

Suppose that ab.

if b≤c, then

min{min{a,b},c}=min{b,c}=b=min{a,b}

=min{a,min{b,c}}.

if bc, then

min{min{a,b},c}=min{b,c}=c=min{a,c}

=min{a,min{b,c}}.

In either case,

min{a,min{b,c}}=min{a,min{b,c}}.

Conclusion:

Thearefore,

The statement is true because all cases are true.

Note: This problem helped me to understand the concept of proof by cases where I need to analyze the problem from multiple sides.

Final OK by SGLee, Page 124 problem 5 칭기즈 revised by 서명원

When we want to prove the conclusion  using the proof by contradiction, the negated conclusion is assumed in addition to the given condition. And we only need to find one contradiction among many.

Whereas in a direct proof, we have to use the given condition only  to prove the one given conclusion. (the negated conclusion is not assumed!!)

So, there are more conditions and more conclusions options for us in a proof by contradiction.

Note: This problem helped to get the difference between proof by contradiction and the direct proof.

Final OK by SGLee, Page 124 (computer exercises) problem 2 칭기즈 revised by 김정주

Page 124 (computer exercises) problem 2

2. Write a program that gives an Egyptian form of a fraction

Python code:

from fractions import Fraction

str1=""

str2=""

fraction=input("enter a fraction:")

for i in range(len(fraction)):

if fraction[i]=='/':

slash=i

for i in range(slash):

str2=str2+fraction[i]

for i in range(slash+1,len(fraction)):

str1=str1+fraction[i]

frac = Fraction(int(str2), int(str1))

index=1

egypt=""

while frac > 0:

if frac >= Fraction(1,index):

egypt=egypt+"1/"+str(index)+"+"

frac -= Fraction(1,index)

index += 1

for index in range(len(egypt)-1):

print(egypt[index],sep=' ', end='', flush=True)

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

in this code, our index will check every integers until it finish the job.

So, it will takes too much time.

Here is our new algorithm.

Start this algorithm with x is 1.

The following is my python code:

example:

Note: I liked this solution, I now understand the importance of the efficiency of the algorithm.

Final OK by SGLee, page 124 problem 1  김주형  finilized by 칭기즈

page 124 problem 1  김주형  finilized by 칭기즈

Axioms are statements that are assumed to be true.

Definitions are used to give a precise meaning and concept to a new term.

To look at examples of axioms and definitions in http://matrix.skku.ac.kr/2018-DM/DM-Ch-2-Lab.html  on Euclidean geometry in order to get more clear view:

Comment: This problem is very easy but very important to understand the difference between axioms and definitions in math.

Final OK by SGLee page 124 problem 13 백선민   finilized by 칭기즈

﻿

page 124 problem 13

Solved by 백선민

Finilized by 칭기즈

Final OK by SGLee

Q. Use mathematical induction to prove that the statements are true for every positive integer n.

Statement 13 : 2 + 4 + ... + 2n = n(n+1)

Discussion:

[Principle of Mathematical Induction]

Suppose that we have a propositional function  whose domain of discourse is the set of positive integers.

Suppose that

1. Basic Step                   is true.

2. Inductive Step             If  is true, then  is true, for all .

Then  is true for every positive integer . (Induction means Mathematical Induction.)

Proof)

(1) Basis step  (k = 1)

2 k = k (k+1)

=> LHS = 2= 2*1= 1(1+1) = 2 =RHS   when k = 1

(2) Inductive step:

Assume that equation is true for  k= n   n>=1,

that is, we assume that

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

is true.

[Let's prove that the equality is true for k = n+1.]

Thus, add 2(n+1) to LHS of (*)

LHS = 2 + 4 + ... + 2n + 2(n+1) =  n(n+1) + 2 (n+1)

=  (n+1) ( n+2)  = RHS

This means (*)   is true for k = n+1.

By [Principle of Mathematical Induction],  2 + 4 + ... + 2n = n(n+1) is true for every positive integer .     □

Note: This problem helped to understand the concept of Mathematical Induction.

Final OK by SGLee page124 Problem 11 칭기즈 Finalized by 김은율

page124, Problem 11 (Chapter Self-Test)

Solved by 칭기즈, Date: 2018.09.24

Finalized by 김은율, Date: 2018.09.26

Final OK by SGLee

11. Use resolution to prove

1. ¬p v q

2. ¬q v ¬r

3. p v ¬r

-------

​ ¬r

Solution:

[ Resolution rule: if pvq and ¬p v r are both true, then q v r is true.]

If

1. pq
2.
qr
3.
pr

=>

4. pr  ( From 1 and  2, we have this )

=>

5. r       ( From 3 and  4, we have this )

Given the hypotheses 1,2 and 3 , we have proved the conclusion     □

Note:This problem helped to understand how to use resolution rule. The idea is if pvq and ¬p v r are both true, then q v r is true.

Final OK by SGLee Page 124 Problem 9 solved by 칭기즈 finalized by 강병훈

P.124 Problem 9 (Chapter Self-Test)

9. Write an expression, which is the and of clauses , equivalent to (p v q)-> r.

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

Solution

 Definition  1.3.1 Conditional Proposition If  and  are proposition, the proposition if  then        is a conditional proposition.   () :   if  then .  Proposition  is hypothesis (or antecedent, 가설).  Proposition  is conclusion (or consequent, 결론).

\​                  (p v q)-> r  =     ¬(p v q) v r

De Morgan's Law :  ¬(p v q)¬Λ ¬​​q

¬Λ ¬​​q v r

Distributive Law: (r v ¬p) Λ ( r v ¬​​q)

\​                  (r v ¬p) Λ ( r v ¬​​q)​

Truth tables:

\   (r v ¬p) Λ ( r v ¬​​q)​    =      (p v q)-> r     .

Python Code :

expression=input("enter a logical expression")

print("p |","q |","r |",expression)

count=0

value=[0]*8

for q in range(2):

for p in range(2):

for r in range(2):

value[count]=eval(expression)

print(bool(p),"|",bool(q),"|",bool(r),"|"bool(value[count]))

count=count+1

Final OK by SGLee Page 198 (Com) problem 7 칭기즈 Finalized by 전종문

Page 198 (Computer exercises) problem 7 칭기즈 Finalized by 전종문

Page 198 (Computer exercises) problem 7

Problem

7.Write a program that tests whether A is decreasing.

Solution

Python code:

A=[int(x) for x in input("enter a sequence of numbers:\n").split()]

count=1

for i in range(len(A)-1):

if A[i]<=A[i+1]:

count=-1

if count==1:

print("decreasing")

print("not decreasing")

Running  Examples:

﻿

It works^^

Note: This problem helped me to understand the concept of nondecreasing order and to know how to implement it in an algorithm.

Page 198 (Computer exercises) problem 6

Solved by 칭기즈 Date:2018.09.30

Revised by 김정주 Date:2018.09.30

finalized by 김희성 Date:2018.09.30

Final OK by SGLee

Problem : Write a program that checks whether a sequence is in increasing otder

Discussion:

For  and  are in the domain of the sequence.

sequence  is increasing

Solution:

Python code:

A=[int(x) for x in input("enter a sequence of numbers:\n").split()]

count=1

count1=1

for i in range(len(A)-1):

count+=1

if A[i]<a[i+< span="">1]:</a[i+<>

count1+=1

if count==count1:

print("increasing")

else:

print("not increasing")

because second and third elements are 2

Our modified code is as following.

import sys

A=[int(x) for x in input("enter a sequence of numbers:\n").split()]

for i in range(len(A)-1):

if A[i]>=A[i+1]:

print("not increasing")

sys.exit(0)

print("increasing")

Comment: When we check whether the given sequence is increasing, we have to check  .

But  if  such that      is  not true, then we can tell it is not increasing.

So if we find    such that      is  not true, we quickly exit and print "not increasing".

If our program execute all  with all loops, and it doesn't find any exception, then  we will print " increasing".

Final OK by SGLee, Page 198( Comp. exercises) problem 9 전종문 Re-Finilized by 칭기즈

Page 198 (Comp. Exercises) problem 9

Problem

9. Write a program that tests whether A is nondecreasing

Discussion:

For  and  are in the domain of the sequence.

The sequence  is nondecreasing

increasing is replaced by nondecreasing : is replaced by )

Solution:

Python code for a nondecreasing sequence  A :

A=[int(x) for x in input("enter a sequence of numbers:\n").split()]

count=1

count1=1

for i in range(len(A)-1):

count+=1

if A[i]<=A[i+1]:

count1+=1

if count==count1:

print("nondecreasing")

else:

print("not nondecreasing")

The code works: (a Right Example)

Wrong example

2. C code:

#include <stdio.h>

int A[10000000], N, answer = 1;

int main()

{

printf("Enter the number of sequence: ");

scanf("%d", &N);

printf("Enter a sequence: ");

for (int i = 1; i < N; i++) { scanf("%d", &A[i]);}

for (int i = 1; i < N; i++) {

if (A[i - 1] > A[i]) { answer = -1; break; }

}

printf("nondecreasing\n");

}else { printf("not nondecreasing\n"); }

return 0;

}

Comment: The idea of the problem is to check whether at least one element is less than the previous element, hence the sequence is not nondecreasing.

Page 198, Problem 13   (Very Good 10/10)

Solved by 칭기즈 Date: 2018.09.27

Finalized by 전종문 Date:2018.09.27

Final OK by SGLee

Ch 3. Page 198, Problem 13

Is the relation

{(1,1),(1,2),(2,2),(4,4),(2,1),(3,3)}

an equivalence relation on {1,2,3,4}? Explain.

Solution

Let, R = {(1,1),(1,2),(2,2),(4,4),(2,1),(3,3)}= {1,2,3,4}.

1. X, (x,x) R     (1,1),(2,2),(3,3),(4,4)      R  is reflexive.

2. (x,y) R ,(y,x) R ​​​    (1,2),(2,1)/(1,1)/(2,2)/(3,3)/(4,4)   R  is symmetric.

3. (x,y) R ,(y,z) R  are (x,z) R   (1,2)(2,1) are (1,1)/ (1,2)(2,2) are (1,2)/ (1,1)(1,2) are (1,2)/ (2,2)(2,1) are (2,1)  R  is transitive.

R  is reflexive, symmetric, and transitive.

{(1,1),(1,2),(2,2),(4,4),(2,1),(3,3)} is an equivalence relation on {1,2,3,4}.

Note: This problem helped me to understand the concept of relations not only by words but also by digraph.

Final OK by SGLee Page 198 problem 18 solved by 칭기즈 Finalized by 엄자균

Page 198 problem 18

R_2 = {(x,a),(x,b),(y,a),(y,c)}

18. Find the matrix A_2  of the relation R_2  relative to the orderings

x,y; a,b,c

Solution:

Given relation R_2 = {(x,a), (x,b), (y,a), (y,c)}

ordering is  x,y; a,b,c

to find A_2

a11=1 because (x,a) R

a12=1 because (x,b) R

a13=0 because (x,c) R

a21=1 because (y,a) R

a22=0 because (y,b) R

a23=1 because (y,c) R

so A_2=    1 1 0

1 0 1

Comment: The problem is very straightforward. The idea is that 1 indicates that there is a relation in a particular point ,whereas 0 vice versa. Hence we get:

 1 1 0 1 0 1

Solved by 정호진 2018.09.30

Finilized by 칭기즈  2018.10.02

Final OK by TA  2018.10.02

Problem 11

Give an example of a relation on {1, 2, 3, 4} that is reflexive, not antisymmetric, and not transitive.

Solution

reflexive: (x,x)  R for every x  X

antisymmetric: for all x, y  X, if (x,y)  R and (y,x)  R, then x=y

transitive: for all x, y, z  X, if (x,y) and (y,z)  R, then (x,z)  R

So, (1,1), (2,2), (3,3), (4,4)  R (Reflexive)

(2,3), (3,2)  ​​(not antisymmetirc)

(1,2)  R (not transitive)

R = {(1,1), (2,2), (3,3), (4,4), (2,3), (3,2), (1,2)}

Digraph:

1. Every vertex has a loop so

R is reflexive

2. (2,3) (3,2)  ​​R:Directed line from 2 to 3 , Directed line from 3 to 2 but xy

R is not antisymmetric

3.(1,2),(2,3)  ​​R Directed line from 1 to 2, Directed line from 2 to 3 but There is no line from 1 to 3

R is not transitive

Final OK by SGLee Page 197 problem 10 김정주  칭기즈  Re-Finilized by 전종문

Page 197 Problem 10

Problem

In Exercises 9 and 10, determine whether the relation defined on the set of positive integers is reflexive, symmetric, antisymmetric, transitive, and/or a partial order.

9. (x,y)R if divides + y

Solution

*   (1,1) R   R  is not reflexive

*   If  3|+y  then  3|+x    is symmetric

*   R  is symmetric but  is not reflexive   R is not antisymmetric

*   (1,2)R , (2,1)R   (1,1) R   R  is not transitive

*   R is antisymmetrictransitive but R is not reflexive  R is not a partial order

R is symmetric, not reflexive, not antisymmetric, not transitive, not a partial order

Comment: The problem is very simple which helps to get better understanding of relations. The idea is that if a relation is a partial order, then it is reflexive, antisymmetric and transitive simultaneously.

Final OK by SGLee Page 197 problem 5 solved by 칭기즈 finalized by 신혜수

Page 197 problem 5   (Q)

For the sequence a defined by a_n = 2*n+2....

Find

a) a6

b)

c)

Discussion:

Solution :

a)  14

b ) 18

c)   192         □

Comment :  문제를 풀면서 고등학교 재학 시절 배웠던 수열, 수열의 합은 물론, 수열의 곱까지 다시 한번 정리하고 응용하는 시간을 가졌습니다. 또한 학우들과 같이 문제를 풀고 finalize 하면서 보람찬 시간을 가졌습니다

[Final OK by TA] Ch. 4, Page 247, Problem № 1 (Chapter Self-Test) , solved by 권재용, revised by 칭기즈, finalized by 전종문 and 김승영

Problem

Trace Algorithm 1.1 for the values a = 12, b = 3, c = 0.

Algorithm 1.1

This algorithm finds the largest of the numbers a, b, and c.

Input: a, b, c

Output: large (the largest of a, b, c)

1. Max3 (a, b, c){

2. large  =a

3. if(b>large)//if b is larger than large, update large

4. large = b

5. if(c>large)//if c is larger than large, update large

6. large = c

7. return large

8. }

Solution

1. max3 (a, b, c){ a =12, b =3,c =0

2. large =a                           large =12​

3. if(b>large)   //if b is larger than large, update large        ​b =3 > large ​=12 is false, then jump to 5

4. large = b

5. if(c>large)//if c is larger than large, update large        c =0 >large​ =12 is false, then jump to 7

6. large = c

7. return large                   ​ return large =12

8. }                                      End​ ■

Trace table:

 Line number a b c Large 2 12 3 0 12 3 12 3 0 12(a>b) 4 12 3 0 12 5 12 3 0 12(a>c) 6 12 3 0 12 7 12 3 0 12

Sage code:

@interact

def _(a=input_box(default=1, label='a'),b=input_box(default=2, label='b'),c=input_box(default=3, label='c')):

large = a

if b > large:

large = b

if c > large:

large = c

print "maximum number is  ", large

return

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

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

idea.

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

Problem

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

Solution

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

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

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

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

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

Problem

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

Explanation

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

Text Search:

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

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

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

Output: ​(​the index of first match occurrence)

Pseudo Code:

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

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

{

j = 1

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

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

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

while (ti+j1 == pj )

{

j = j + 1

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

return i

}

}

return 0

}

"

Solution

Given:

t= "111011"

p"110"

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

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

a) j is set to 1

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

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

a) j is set to 1

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

t = "111011" n=6

p = "110” m=3

Hint:

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

return i

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

Trace table:

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

The output is 2

Comment: 문자열 110을 추적하고  ‘110이 발견된 경우 왼쪽부터 시작해서 최초의 1이 발견된 자릿수를 결과값으로 내어 출력하는 알고리즘이다. 여기서 검사하는 방식은 ‘i’번째 항을 첫 번째로 ‘I’번째 항이 ‘1’ 인가 보고 일치하면 ‘i+1’번째 항도 ‘1’ 인가를 확인하고 ‘i+2’번째 항까지 ‘0’ 임이 맞는다면’ j’항 즉, n번째 검사임을 나타내는 factor‘n=4’가 되게 된다면 검사를 중단하고 현재 ‘I’ value를 출력하게 됩니다. 이것은 ‘110’ 이라는 찾고 싶은 문자열을 찾고 나서 그 찾은 위치를 출력하고 작동을 멈추는 전형적인 Text Search 알고리즘이고 이것을 응용하여 좀더 길거나 영어 및 다른 글자 기호의 조합도 찾아 낼 수 있을 것 입니다.

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

[Final OK by SGLee] Ch. 4, Page 247, Problem № 6 (Chapter Self-Test), solved by 칭기즈, finalized by 서명원and 김승영

Problem

Trace algorithm 2.3 for the input:

44 64 77 15 3

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

Solution

Suppose that the input is the following sequence

 44 64 77 15 3

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

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

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

 44 64 77 15 3

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

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

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

 44 64 77 15 3

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

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

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

 44 64 77 77 3

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

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

 44 64 64 77 3

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

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

 44 44 64 77 3

j>=1 is false, skips the loop

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

 15 44 64 77 3

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

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

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

 15 44 64 77 77

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

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

 15 44 64 64 77

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

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

 15 44 44 64 77

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

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

 15 15 44 64 77

j>=1 is false

 15 15 44 64 77

s[1]=val=3

 3 15 44 64 77

Output

 3 15 44 64 77

is sorted.​​

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

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

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

Problem

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

Solution

According to the problem, the sequence  is this.

 5 51 2 44 96

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

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

after the swap we have

 2 51 5 44 96

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

after the swap we have

 2 96 5 44 51

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

the sequence does not change.

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

after the swap we have

Output:

 2 96 5 51 44

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

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

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

[Final OK by TA and SGLee] Ch. 4, Page 248, Problem № 1 (Computer Exercises), solved by 칭기즈, finalized by 유가이 올렉산드르

Problem

Implement  Algorithm 1.2, finding the largest element in a sequence, as a program

 Algorithm 1.2 Finding the Maximum Value in a Finite Sequence procedure max(, ,  : integers)  max   for  to         if  then   return                   or

Solution

A) Python code

sequence=[int (x) for x in input("enter a sequence of numbers:").split()]

largest=sequence[0]

for i in range(len(sequence)):

if sequence[i]>largest:

largest=sequence[i]

print(largest)

Practical image

B) Sage Code

@interact
def _(s=input_box(default=[1,5,4,2,6,3], label='sequence')):

n = len(s)              # list 길이
maximum = s[
0]

for i in range(1,n):

if  s[i] > maximum:
maximum = s[i]​

print "maximum number is  ", maximum

print max(s)

return

Example:

Comment: 알고리즘의 돌아가는 방식은 시퀀스의 길이를 던져주고 코드를 자신이 원하는 출력이 나오도록 조절을 하고 그것을 반복하게 하는 식이다. 여기서는 '가장 ' '0' , Default 값을 쥐어준 시퀀스 1항과 비교, 1항이 크면 '가장 ' 쪽으로 대체하고 2 과도 비교하고 비교대상 쪽으로 대체해 나가는 것을 Coder 설정해둔 길이 까지 수행하고 마지막까지 진행해 나간 '가장 ' 출력하는 방식이다. 지금이야 코딩이 간단하여 또한 조금만 공부하고 연습하면 바로 제작할 있을 정도로 간단하지만 앞으로 천줄 되는 프로그램을 짜게 된다면 여기서의 숫자 하나가 오타가 난다거나 변수 알파벳을 혼동한다던가 하면 몹시 곤란하게 것이다.

Comment: This problem is very easy but very useful since it helps to understand relatively effective algorithm of finding the largest number. The key idea is to assume any element to be the largest and then compare the remaining elements with it.

[Final OK by SGLee] Ch. 4, Page 248, Problem № 4 (Computer Exercises), solved by 유가이 올렉산드르, finalized by 칭기즈 and 김승영

Page 248, problem 4 (Computer Exercises)

Implement Algorithm 2.4, shuffle, as a program.

Discussion shuffle

This algorithm shuffles the value in the sequence

a1, ... an

Input:  a, n

Ouptut:  a (shuffled)

shuffle(a, n){

for i = 1 to n - 1

swap(a[i],a[rand(i, n)])

}

Solution

A) Python code

import random

sequence=[1,2,3,4,5,6,7]

for i in range(len(sequence)):

r=random.randint(i,len(sequence)-1)

val= sequence[i]

sequence[i]=sequence[r]

sequence[r]= val

print(sequence)

Practical image:

B) Sage code

@interact

def _(s=input_box(default=[1,5,4,2,6,3], label='sequence')):

n = len(s)

for i in range(1,n):

r=int(RR.random_element(i,n-1))

val= s[i]

s[i]=s[r]

s[r]= val

print s

return​

Practical image:

Comment:

Due to this problem I learnt how to implement pseudocode of a shuffle algorithm as a program, using both Python and Sage coding, along with the concept of this algorithm. The idea of a shuffle algorithm is to order elements in a sequence depending on random indexes obtained by function rand(), hence the result may differ every time the code is executed.

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

Problem

Implement Algorithm 2.3, insertion sort , as a program.

Algorithm:

Discussion:

In an insertion sort, the first element in the array is considered as sorted, even if it is an unsorted array. In an insertion sort, each element in the array is checked with the previous elements, resulting in a growing sorted output list. With each iteration, the sorting algorithm removes one element at a time and finds the appropriate location within the sorted array and inserts it there. The iteration continues until the whole list is sorted.

Solution

Python code:

def insertionSort(alist):

for i in range(1,len(alist)):

val = alist[i]

j = i

while j>0 and alist[j-1]>val:

alist[j]=alist[j-1]

j = j-1

alist[j]=val

alist = [int(x) for x in input("Enter:").split()]

insertionSort(alist)

print(alist)

Example:

Comment: Due to this problem I learnt how to implement the algorithm of insertion sort as a program. I realized that the time complexity is O(n2) and the worst case occurs when the sequence is sorted in reverse order. Insertion sort is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.

[Final OK by SGLee] Ch. 4, Page 247, Problem № 15 (Chapter Self-Test), solved by 조영은, finalized by 강병훈, re-finalized by 김영철 and 칭기즈

Problem

Write a recursive algorithm to compute t[n] from the tribonacci sequence above, n ≥ 1.

Solution

Using the Python code we’ve already seen up there, by modifying it little bit, we can compute t[n] easily. But before we do that, let’s calculate by hand t[1] ~ t[10] below, to compare it with the output later to check if it gives the right results.

1.    t[1] = 1 (by definition)

2.    t[2] = 1 (by definition)

3.    t[3] = 1 (by definition)

4.    t[4] = t[1] + t[2] + t[3] = 3

5.    t[5] = t[2] + t[3] + t[4] = 5

6.    t[6] = t[3] + t[4] + t[5] = 9

7.    t[7] = t[4] + t[5] + t[6] = 17

8.    t[8] = t[5] + t[6] + t[7] = 31

9.    t[9] = t[6] + t[7] + t[8] = 57

10. t[10] = t[7] + t[8] + t[9] = 105

Python code:

def sequence(n):

if (n==0 or n==1 or n==2 or n==3):

return 1

else:

return (sequence(n-1)+sequence(n-2)+sequence(n-3))

def tribonacci(n):

for i in range(1,n+1):

print(sequence(i),"",end="")

n=10

tribonacci(n)

Output:

We can see the by-hand calculation and test result is identical.

Comment: This problem is quite easy but very useful because it helps to get better understanding of the concept of recursive algorithms, where the key idea is to invoke a simpler version of itself, as well as Tribonacci sequence.

[Final OK by SGLee] Ch. 4, Page 247, Problem № 12 (Chapter Self-Test), solved by 강병훈, finalized by 모하메드, re-finalized by 김영철 and 칭기즈

Problem

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, B (both n x n matrices), n

Output – True (if A = B), False (if A  B)

Pseudo Code >

Note: We have to compare each element in A and B, and as soon as different match is found, we return False. The worst case is when the two are actually same matrices, so that we end up comparing all the elements of A and B.

So the code is like below:

Python code:

N = 4

def areSame(A,B):

for i in range(N):

for j in range(N):

if (A[i][j] != B[i][j]):

return False

return True

A= [ [1, 1, 1, 1],

[2, 2, 2, 2],

[3, 3, 3, 3],

[4, 4, 4, 4]]

B= [ [1, 1, 1, 1],

[2, 2, 2, 2],

[3, 3, 3, 3],

[4, 4, 4, 4]]

print(areSame(A,B))

Output:

<Worst case>

As I mentioned above, the worst-case time occurs when the two are actually

same matrices​​, so that we end up comparing all the elements of A and B.

To compare all the elements of the two, as each of them have n * n = (n^2)

elements, it will take (n^2) times comparing them. So, the Theta notation

for the worst-case time here is Theta of (n^2)

Note: 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 O-notation since it gives the upper bound-worst case- for an algorithm. ■

[Final OK by SGLee] Ch. 4, Page 247, Problem № 4 (Chapter Self-Test), solved by 엄자균, finalized by 강병훈, re-finalized by 김은율 and 칭기즈

Problem

Which of the algorithm properties:

input, output, precision, determinism, finiteness, correctness, generality.

,if any, are lacking in the following? Explain.

Input:  S ( a set of intergers), m (an integer)

Output:  All finite subsets of S that sum to m

1. List all finite subsets of S and their sums.

2. Step through the subsets listed in 1 and output each whose sum is m.

Solution

1) If the set S is an i​nfinite set, the algorithm will not terminate, so it lacks the finiteness and output properties.

2) Line 1 is not precisely stated since how to list the subsets of S and their sums is not specified; thus the algorithm lacks the precision property.

3)The order of the subsets listed in line 1 depends on the method used to generate them, so the

algorithm lacks the determinism property

Since line 2 depends on the order of the subsets generated in line 1, the determinism property is lacking here as well.■

Comment: This is a very good example which helps to get the concept of chapter 4, especially what each property of an algorithm means. Due to this problem I am now able to distinguish each property an algorithm should have.

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

Problem

Write an algorithm that receives as input the distinct numbers a, b, and c and assigns the values a, b, and c to the variables x, y, and z so that

x < y < z.

Solution

We have to assign, compare and then swap if necessary, as below.

Hint:

How does the swap() actually work?

In programming it is wrong to write:

y=x

x=y

because when we assign x to y the original value stored in y is deleted, now it has the value of x. Therefore we need to store the original value of y in order to give it to x

Python code:

a=int(input())

b=int(input())

c=int(input())

x=a

y=b

z=c

if(y<x):

temp=y

y=x

x=temp

if(z<x):

temp=z

z=x

x=temp

if(z<y):

temp=z

z=y

y=temp

print(x,y,z)

Pactical image:

Now, it is sure that x < y < z.

Comment: This problem is very useful to understand how the function swap() really works, hence it may help to develop your computational thinking which is very important. The key idea is to store the original value of the variable in the temporary space to assign it to another variable.

[Final OK by SGLee] Ch. 4, Page 247, Problem № 8 (Chapter Self-Test), solved by 강병훈, finalized by 김은율, re-finalized by 김영철 and 칭기즈

Problem

Write an algorithm that receives as input the sequence

s[1], . . . , s[n]

sorted in non-decreasing order and prints all values that appear more than once. Example: If the sequence is

1  1  1  5  8  8  9  12,

the output is

1  8.

Solution

We have to run while loop and check if there are same numbers, and print them if exist, and skip to non-identical part. It is shown below.

Algorithm:

This way we can find repeated numbers and print them.

Python code:

i=0

s=[1 , 1 , 1 , 5 , 8 , 8 , 9 , 12]

n=len(s)

while(i<n-1):

if s[i]==s[i+1]:

print(s[i])

j=i

while(i<n and s[i]==s[j]):

i=i+1

Practical image:

Sage code:

i=0

s=[1 , 1 , 1 , 5 , 8 , 8 , 9 , 12]

n=len(s)

while(i<n-1):

if s[i]==s[i+1]:

print(s[i])

j=i

while(i<n and s[i]==s[j]):

i=i+1

Practical image:

Notice: Sage code and Python code are the same because SageMath uses a syntax resembling Python's, supporting proceduralfunctional and object-oriented constructs.        ■​

Comment: This problem is very straightforward because if a sequence is in nondecreasing order, the repeating numbers always stay next to each other and that is the key point to solve this problem. However, it helps to understand the concept of the sequence of numbers in nondecreasing order.

[Final OK by SGLee] Ch. 5, Page 300, Problem № 2, solved by AYSU OZGUNEKIM, Revised by 김주형, Finalized by 유가이 올렉산드르, Re-Finalized by 모하메드 and 칭기즈

Problem

Find the prime factorization of 539.

Discussion:

A) Key Terms

I) 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.

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

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

B) 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.

ex5*3 = 15. And Prime Factorization is finding which prime numbers multiply together to make the original number. ■
Comment (Muhammad): when you try to find Factorial tree, start checking the factors from smallest to biggest (1,2,3,4,...)

[Final OK by SGLee] Ch. 5, Page 300, Problem № 1 (Computer Exercise), solved by 칭기즈, Finalized by 유가이 올렉산드르

Problem

​​Implement Algorithm 1.8, testing whether a positive integer is prime, as a program.

 Algoruthm1.8 Testing Whether an Integer Is Prime This algorithm determines whether the integer  is prime. If  is prime, the algorithm returns . If  is composite, the algorithm returns a divisor  satisfying .  To test whether  divides , the algorithm checks whether the remainder when  is divided by ,   is zero.         Input:        Output :

Python code

import math

n=int(input("enter a number: "))

for i in range(2,math.floor(math.sqrt(n))+1)://check if it has a divisor in the range[2,floor(sqrt(n))]

if(n % i==0): //if there is no remainder, it means it has a divisor in this range

print(str(n)+" is not a prime number")

quit()

print(str(n)+" is a prime number") //if there is no divisor in the range, it is a prime

Practical image
Case A)

Case B)

Sage Code

# Testing Whether an Integer Is Prime

@interact
def _(n=input_box (default=43, label='Enter the number such that n>1 ')):
for i in range(2,floor (sqrt (n))+1):
if n % i == 0:
print n, "is composite"
return
print n, " is prime"
return
​​

Practical image

Comment: This problem is a good and very easy example to get the concept of chapter 5, especially the theory of identifying if the given number is prime or composite. The key idea is that a composite number has a divisor in the range 2 to √n⌋.

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

[Final OK by SG Lee] Ch. 5, Page 300, Problem № 3 (Computer Exercise), solved by 칭기즈and 김승영

Problem

Write a program that adds binary numbers.

 Algorithm  2.12 Adding Binary Numbers This algorithm add the binary numbers  and  and stores the sum in .       Input:  , ,      Output:       binary_addition(, , , )         carry         for  to

Python code

import math

b=[int(x) for x in input().split()]

b1=[int(x) for x in input().split()]

carry=0

s=''

list1 = list(s)

for i in range(len(b)):

b2 = b[len(b)-i-1]

c1 = b1[len(b)-i-1]

list1.append( str((b2+c1+carry)%2))

carry=math.floor((b2+c1+carry)/2)

list1.append(str(carry))

s = ''.join(list1)

print(s[::-1])

Practical image

Sage Code

@interact
def _(b=input_box(default=1101, label='binary number'),
c=input_box(default=1001, label='binary number')):
b = str(b)
c = str(c)
n = len(b)
carry = 0
s = ''
for i in range(n):
b1 = Integer(b[n-i-1])
c1 = Integer(c[n-i-1])
s = str((b1+c1+carry) % 2) + s
carry = (b1+c1+carry) // 2
s = str(carry) + s
print s
return

​ Practical image

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

Comment: 해당 코드는 binary numbers , 2진수의 덧셈을 논하고 있다.논리 회로 과목에서 배웠던  '4-bit Full adder' 구동방식의 공통점이 많아 언급 하지 않을 수가 없게 되었다.Discussion

Key Terms

I) LSB: Last Significant Bit, 가장 오른쪽자리의 Bit 뜻하며 여기선 20 자리이다.

II) MSB: Most Significant Bit, 전과 반대로 가장 왼쪽자리의 Bit 이고 여기선 23 자리다.

Similarity of operation

'4-bit Full adder' 그림 오른쪽의 '0' 알고리즘이 'carry' 라는 변수를 지정해 주고 값을 '0' 이라고 설정 해준 것과 대응 하며 A0 에서 A3 그리고 B0 에서 B3 각각의 변수 값이 뜻하는 바도 원래의 알고리즘이 표현하려던 목적과도 동일하다. 세부적으로는 알고리즘이 제시한 식은  이고 이는 i+1번째 자릿수의 결과 값은 3개의 변수의 연산으로부터 결정됨을 coding 것인데 logic gate 표현 식으로는’Ai Bi C(i-1) 배타적 논리합 연산으로 표현하고 다음 자릿수로 넘어갈 ‘Carry’    이라고 알고리즘이 제시하였으며 logic gate 표현 식으로는 ‘Ci= (Ai ^Bi) v (Bi ^C(i-1)) v (Ai ^C(i-1))’ 이고 이는 논리 곱과 논리 연산의 조합을 써서 3개의 parameter 2개가 1 이면 ‘carry’ 1 되는 연산이다. 이러한 연산을 하는 블록을 늘리면 많은 자릿수의 2진수 연산이 가능하게 것이고, 문제에서 제시된 알고리즘은 n 값을 원하는 길이만큼 조절하면 것이다.

Comment: The problem may seem to be difficult but it is important to keep in mind that in binary addition we need to start adding from the last digit. Therefore, we read array starting from the end and we need to consider carry digit because in binary system we have only 1 and 0.

[Final OK by SG Lee] Ch. 5, Page 300, Problem № 6 (Computer Exercise), solved by 칭기즈, finalized by 유가이 올렉산드르and 김승영

Problem

Implement Algorithm 2.16, exponentiation by repeated squaring, as a program.

 Algorithm  2.16 Exponentiation By Repeated Squaring This algorithm computes  using repeated squaring.       Input:  ,      Output:       exp_via_repeated_squaring(, )         result                 while ()           if( )             *            *                        return result

Solution

Python code

import math

a=int(input("Enter the number: "))

n=int(input("Enter the exponent: "))

result=1

x=a

while(n>0):

if(n%2==1):

result=result*x

x=x*x

n=math.floor(n/2)

print(result)


Practical image

Sage code:

@interact

def _(a=input_box(default=2, label='Enter the number:  '),n=input_box(default=2, label='Enter the exponent: ')):

result=1

while(n>0):

if(n % 2==1):

result=result*a

a=a*a

n=floor(n/2)

print result

return

Practical image`

Comment: The number of times that the while loop executes is determined by n. The variable n is repeatedly halved

and when n becomes 0, the loop terminates. Recall that it takes time O(lg n) to reduce n to 0 by repeated halving. This is a good and easy example not only to show how to implement repeated squaring but also how effectiveness of algorithm is important, the key idea is to compute the remainder after each multiplication thereby keeping the numbers relatively small.

[Final OK by SGLee] Ch. 5, Page 300, Problem № 9 (Chapter Self-Test), solved by 신혜수, finalized by 전종문 and 칭기즈

Problem

Use the Euclidean algorithm to find the greatest common divisor of the integers 396 and 480.

Theorem:

Euclidean Algorithm is algorithm for finding the greatest common divisor of two integers.

Ex) Let , where  and  are integers. Then .

Solution
The Euclidean algorithm gives

480 = 396 * 1 + 84.

b=396    r=84

Thus,

gcd(480, 396) = gcd(396, 84)​   (by the Euclidean algorithm, 480 = 396 * 1 + 84)

gcd(84, 60)    (by the Euclidean algorithm,  396 = 84*4 + 60)

= gcd(60, 24) = gcd(24, 12) = gcd(12,0) ​=12

Conclusion:

the greatest common divisor of the integers 396 and 480 = 12    ■

Comment: ​I think this Euclidean algorithm make me to find the greatest common divisor​ more easier in short time when integers are more bigger. Euclidean algorithm ​save more running time than prime factorization to find the greatest common divisor.

[Final OK by SGLee] Ch. 5, Page 300, Problem № 5 (Chapter Self-Test), solved by 정호진, finalized by 김희성 and 칭기즈

Problem

Write the binary number 10010110 in decimal.

Theory:

Solution

100101102=0*20+1*21+1*22+0*23+1*24+0*25+0*26+1*27 = 2+4+16+128

=15010

The binary number 10010110(2) is  equal to 150(10) in decimal.

Comment: This problem is good example which helps to get the algorithm used when converting any binary number into decimal and vice versa. The key idea is to multiply each binary digit by 2 two the power corresponding to the position of the digit.

[Final OK by SGLee] Ch. 5, Page 300, Problem № 7 (Chapter Self-Test), solved by 서명원, finalized by 전종문, re-finalized by 김희성 and 칭기즈

Problem

Trace Algorithm 2.16 for the value n = 30.

Algorithm

Solution

The algorithm begins by setting result to 1 and x to a.

Step 1) Since

n = 30 > 0,

the body of the while loop executes.

Step 2) Since

n mod 2 is not equal to 1,

result is not modified.

Step 3) x becomes a2, and n becomes 15.

Since

n = 15 > 0

the body of the while loop executes

Step 4) Since

n mod 2 is equal to 1,

result becomes

result * x = 1 * a2 = a2.

Step 5) x becomes a4, and n becomes 7.

Since

n = 7 > 0,

the body of the while loop executes

Step 6) Since

n mod 2 is equal to 1,

result becomes

result * x = a2​​ * a4 = a6.

Step 7) x becomes a8, and n becomes 3.

Since

n = 3 > 0,

the body of the while loop executes.

Step 8) Since

n mod 2 is equal to 1,

result becomes

result * x = a6 * a8 = a14.

Step 9) x becomes a16, and n becomes 1.

Since

n = 1 > 0,

the body of the while loop executes.

Step 10) Since

n mod 2 is equal to 1,

result becomes

result * x = a14 * a16 = a30.

x becomes a32, and n becomes 0.

Step 11) Since n = 0, the while loop terminates.

Conclusion:

Therefore, the algorithm returns the result which is equal to a​30   ■

I used the c language to code it.

The argument of multiplication is difficult to express and is expressed as addition of argument.

Comment: We can see the Output is always a​k when we input x=a and n=k.

Because this algorithm divide k into 2 and only multiply when n mod 2=1.

This is the same way of changing a decimal number to a binary number.

(Ex. =30 =11110​(2) ​=22​​ * 2​4​ *​ 2​8​ * 2​16 return result = a​2​​ * a​4​ *​ a​8​ * a​16 = ​ a​30

So, we can see that 11110​(2) ​=22​​ * 2​4​ *​ 2​8​ * 2​16​ and result = a​2​​ * a​4​ *​ a​8​ * a​16 = ​ a​30​ are same frame.)​

[Final OK by SGLee] Ch. 5, Page 300, Problem № 10 (Chapter Self-Test), solved by 정호진, finalized by 엄자균, re-finalized by 서명원, 정호진  and 칭기즈

Problem

Given that log 3/2 100=11.357747, provide an upper bound for the number of modulus operations required by the Euclidean algorithm for integers in the range 0 to 100,000,000.

Theorem:

Solution (Refer Theorem 5.3.6)

Given that

log3/2 100=11.357747

Discussion:

We have to provide an upper bound for the number of modulus operations required by the Euclidean algorithm for integers in the range 0 to 100,000,000.

If integers in the range of 0 to m, m  8, not both zero, are input to the  euclidean algorithm, then at most log3/2  (2m/3) modulus operations are required.

Since the given range 0 to 100,000,000,

So, in this problem, is 100,000,000. And we use this formula.

Solution:

log3/2 ((2(100,000,000))/3)

= log 3/2 (2/3)+ log 3/2 (100,000,000)

= log 3/2 (2/3) + log 3/2(100)4

= -1 + 4 log 3/2(100)

= -1 + 4 (11.357747)    //Since  log 3/2(100) = 11.357747

= -1 + 45.430988

= 44.430988

Conclusion:

Therefore, the upper bound we found is 44.  ■

Comment: Euclidean algorithm 대한 이해가 부족한 상태에서 문제에 접근하다보니 스스로 아쉬운 부분과 이해가 되지 않는 부분이 있었지만문제에 적용하고 수정하는 과정을 통해서 해당 알고리즘에 대해 완벽하진 않지만 어느 정도 보완할 있었다물론다른 문제에 적용해보면서 발전시켜 필요가 있다.(서명원)

처음 이 문제를 풀때는 위의 식이 어떤것을 의미하는지 정확히 몰랐었다. 그래서 문제를 완벽하게 풀이하지 못했다. 학우들이 처음 푼 풀이를 수정해주고 다시 문제를 풀어보니 처음 문제를 접했을 보다는 깔끔한 풀이가 완성된 느낌이다. 앞으로 문제를 풀때도 단순히 정답 도출에 목적을 두는게 아니라 어떻게 풀어야 하는지에 초점을 두고 공부해야겠다고 느낄 수 있는 문제였다. (정호진)

Comment: This problem is very easy if you know the rules used for logarithms.

[Final OK by SGLee] Ch. 5, Page 264, Problem № 6 (Chapter Self-Test), solved by 정호진, finalized by 엄자균, re-finalized by 서명원, 정호진, 칭기즈

Problem

Write the decimal number 430 in binary and hexadecimal.

Theory:

Binary Number System

In the Binary (base ) number system,

Any integer form is

based

where each  and each  is one of the binary digits

Any integer form is

based

where  and each  is one of the

hexadecimal digits ,, 10=,  11=, 15=.

Solution

I) 430 = 256+128+32+8+4+2

= 1×28 + 1×2+ 0×26 + 1×25 + 0×24 + 1×23 + 1×22 + 1×21 + 0×20​​ = 110101110(2)

II) 430 = 1×162 + 10×161 + 14×160 = 1AE(16)

Conclusion:

110101110(2)​​ , 1AE(16)​​

Comment: Binary is used at computer system because it is easy and fast to handle the data. In today's increasing use of computer, binary is very important and worth learning. Hexadecimal complemented the binary's weakness - too long - and it is well used at computer system, too.

[Final OK by SGLee] Ch. 5, Page 300, Problem № 13 (Chapter Self-Test), solved by 강병훈, finalized by 김주형, re-finalized by 전종문 , 칭기즈

Problem

In exercise 13-16, assume that we choose primes

=12          q =17      n =19 .

Compute z and φ.

Note:

=p×q

φ =(-1)(-1)

Solution

We need to find  =p×q and φ =(-1)(-1)

z =12×17 = 204

φ =(12-1)(17-1)=11×16=176

Conclusion:

z​​ =204, φ =176

Comment: I know about that φ() used at RSA(Type of Public-key cryptography) .

φ(n) is the number of coprime n and number which is less than n

[Final OK by TA] Ch. 5, Page 299, Problem № 4 (Chapter Self-Test), solved by AYSU OZGUNEKIM, finalized by 김정주, re-finalized by 서명원, 칭기즈

Problem

Find  lcm(2*52*72*134, 74*132*17)​

Theory:

Solution

Following the given theory about lcm(m,n), we gonna put the given data.

​                                    lcm(2*52*72*134, 74*132*17)​

= 2​max(1,0)​ * 5​max(2,0)​ * 7​max(2,4) * 13​max(4,2) * 17​max(0,1)

​                                    = 2 * 5​2​ * 7​4 * 13​4 * 17​

Conclusion:

lcm(2*52*72*134, 74*132*17)​​=     2 * 5​2​ * 7​4 * 13​4 * 17​

Comment: This problem is very straightforward which helps to understand the logic used when we need to compute the least common multiple of two given numbers. The key idea is to take the maximum power for the common prime factors and multiply them.

[Final OK by TA] Ch. 5, Page 300, Problem № 11 (Chapter Self-Test), solved by 엄자균, finalized by 정호진, 칭기즈

Problem

Use the Euclidean algorithm to find integers s and t satisfying

s·396+t·480= gcd(396,480)

Theory:

The Euclidean Algorithm:

Let , where  and  are integers.

Then .

BÉZOUT'S THEOREM:

If  and , then there  such that

.

Solution

Refer to the Euclidian Algorithm:

480= 396 × 1 + 84

396= 84  × 4 + 60

84 = 60 ×1 + 24

60 = 24 ×12 +12

24 = 12 × 2

Thus,

gcd(396,480) =gcd(396,84)=gcd(60,84)=gcd(60,24)=gcd(12,24)=12

Refer to Bezout’s theorem:

12 = 60 - 24 ×←⑤(inverse  )

12 = 60 - (84 - 60 × 1) × 2 (put in)

12 = 3 × 60 - 2× 84 ←⑥

12 =3 × (396-84×4)-2× 84 (putin)

12= 3 × 396 - 84× (12+2)

12=3× 396-14× 84   ←⑦

12=3× 396-14× (480-396×1) (putin)

12=17× 396-14× 480

396(17) + 480(-14)=12

Conclusion:

s=17, t= -14

Comment: This problem is a great example which helps to understand how to use the Euclidian Algorithm as well as Bezout’s theorem in a problem-solving. The key point is that the Euclidian algorithm makes it easier to use Bezout’s theorem, hence it is useful to keep in mind both of them in problem solving.

[Final OK by SGLee] Ch. 5, Page 299, Problem № 3 (Chapter Self-Test), solved by AYSU OZGUNEKIM, finalized by 전종문, 칭기즈

Problem

Find

gcd(52·72·134, 74·132·17).

Theory:

Solution

gcd(m,n) where m=52·72·134  and n=74·132·17

Let’s rewrite them in the form:

52·72·134​ = (72​·​13​2​) × (​5​2·13​2​​)

74·132·17 = (72​·​13​2​​) × (7​2·​17​)

5​2·13​2​​ and​ 7​2​·​17are coprime.

Note:

Two numbers are called relatively prime, or coprime, if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

Conclusion:

​   gcd(52·72·​134, 74·​132·​17) = ​72·13​2​.  ■

Comment: This problem is very simple to understand. The key idea here is to find the greatest common divisor by rewriting two given prime factorizations so that it becomes the multiplication of the sequence of common prime multiples having the least power and the remaining part of the given prime factorization.

[Final OK by SGLee][TA] Ch 6, P.37*, Com Exs. 2, 칭기즈,유가이,김은율

[TA] Ch 6, P.37*, Com Exs. 2, Problem № 2 (Com. Exs.)

Write a program that generates all permutations of the elements {1...n}

Theorem:

 Number of Permutations = n!  (factorial)

Solution

Python code:

import itertools

import math

array=[str (x) for x in input().split()]

print ("the number of permutations is "+str(math.factorial(len(array))))

print (list(itertools.permutations(array)))

EXAMPLE

Sage code:

#permutation

elements = ['A', 'B', 'C', 'D', 'F']

perms = Arrangements(elements,len(elements))

print perms

print perms.cardinality()

print perms.list()

Comment:  The problem is very easy but due to it I now understand how to implement the logic of solving in coding. The idea of finding permutations is based on a multiplication principle.

[TA] Ch 6, P.37*, Com Exs. 3, typed and solved by 칭기즈

ch 6, comp exercises, prob.3 solved by 칭기즈 finalized by 전종문

Problem

Write a program that generates all r-permutations of the elements {1...n}

Theorem:

 Theorem  2.10 The numbers of -permutation of a set of  distinct objects is ,     .

Solution:

Python code:

import itertools

import math

array=[str (x) for x in input().split()]

r=input("enter number of elements to be selected: ")

n=(math.factorial(len(array)))/(math.factorial(len(array)-int(r)))

print ("the number of permutations is "+str(int(n)))

print (list(itertools.permutations(array,int(r))))

EXAMPLE

This is sage code

# permutation

elements = ['A', 'B', 'C']

perms = Arrangements(elements, 3)

print perms

print perms.cardinality()

print perms.list()

Comment: The problem is very easy. The idea of arrangements(a,b) is to get the sequence and number of elements to be selected.

 Fina OK by SGLee [TA] Ch 6, P.37*, Com Exs. 1, 칭기즈,유가이, 김은율

Ch 6, P.37*, Com Exs. 1, Problem № 1 (Com. Exs.)

Write a program that generates all r-combinations of the elements {1...n}.

Theorem:

 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 .

Solution

Python code:

import itertools

import math

array=[str (x) for x in input().split()]

r=input("enter number of elements to be selected: ")

n=(math.factorial(len(array)))/(math.factorial(len(array)-int(r))*math.factorial(int(r)))

print ("the number of combinations is "+str(int(n)))

print (list(itertools.combinations(array,int(r))))

EXAMPLE

Sage code:

#Combination

sequence = ['A', 'B', 'C']

doubles = Combinations(sequence, 2)

print doubles

print doubles.cardinality()

print doubles.list()

[TA] Ch 6, P.37*, Com Exs. 8, typed and solved by 칭기즈

ch 6, comp exercises, prob.8 solved by 칭기즈 finalized by 전종문

ch 6, comp exercises, prob.8 solved by 칭기즈 finalized by 전종문 and re-finalized by 유가이 올렉산드르

Problem 8 (Com. Exs.)

Write a program that computes Catalan number

Theorem:

Catalan numbers are defined by the formula:

for  and .

Catalan numbers are

.
Solution

Python code:

import math

n=int(input())

c=int(math.factorial(2*n)/(math.factorial(n+1)*math.factorial(n)))

print ("Catalan number is " +str(c))

EXAMPLE

Sage code for Catalan number:

# Catalan number 생성(정의)

for i in range(10):

print binomial(2*i,i)/(i+1)

Also, to my mind, we can calculate the Catalan number in a simpler way, by using formulas of recurrence relations:

Alternate Python Code using recurrence relation formula:

import functools

@functools.lru_cache(maxsize=None)

def catalan(n):

if n == 0:

return 1

return catalan(n-1)*2*(2*n-1)//(n+1)

n=int(input("enter a number"))

print(catalan(n))

Alternate Sage Code by using reccurrence relation formula:

def _(n):

if n == 0:

return 1

return _(n-1)*2*(2*n-1)//(n+1)

print _(9)

Comment: As it can be seen there are many ways to calculate Catalan number in coding which makes this problem beautiful .

[Final OK by TA] Ch 6, P.37*, Com Exs. 9, typed and solved by 칭기즈 Revised-Finalized by Muhammad

Write a program that generates Pascal's triangle to level n

Theorem:

Pascals triangle

Binomial coefficients in a triangular form

Figure 6.7.1 Pascals triangle

Solution:

Python code:

n=int(input("Enter a triangle's level: "))

array=[]

for index in range(n):

array.append([])

array[index].append(1)

for j in range(1,index):

array[index].append(array[index-1][j-1]+array[index-1][j])

if(n!=0):

array[index].append(1)

for index in range(n):

print("   "*(n-index),end=" ",sep=" ")

for j in range(0,index+1):

print('{0:6}'.format(array[index][j]),end=" ",sep=" ")

print()

C-Code:

#include <stdio.h>

long factorial(int);

int main()

{

int i, n, c;

printf("Enter a triangle's level: ");

scanf("%d",&n);

for (= 0; i < n; i++)

{

for (= 0; c <= (- i - 2); c++)

printf(" ");

for (= 0 ; c <= i; c++)

printf("%ld ",factorial(i)/(factorial(c)*factorial(i-c)));

printf("\n");

}

return 0;

}

long factorial(int n)

{

int c;

long result = 1;

for (= 1; c <= n; c++)

result = result*c;

return result;

}

EXAMPLE

Comment: Pascal's Triangle also has significant ties to number theory. The most apparent connection is to the Fibonacci sequence. Adding the numbers of Pascal's triangle along a certain diagonal produces the numbers of the sequence. Sums along a certain diagonal of Pascal's triangle produce the Fibonacci sequence.

[Final OK by TA] p.371 problem 18 Solved by 정호진 finilized by 칭기즈

Problem

Two fair dice are rolled. What is the probability that the sum of the numbers on the dice is 8?

Solution

 Multiplication Principle (Product Rule)

All cases:

First dice have 6 different possible results ( from 1 to 6)

Second dice have 6 different possible results ( from 1 to 6)

Thus,

By the Multiplication Principle,

n1=6 and n2=6 => the total number of possible outcomes is

6*6=36

Cases that satisfies n1+n2=8:

(2,6), (3,5), (4,4), (5,3), (6,2)

which are 5 favourable outcomes in total.

Probability

Conclusion:

hence,  the probability is 5/36

Comment: The problem is very easy to understand since the idea is based on a multiplication principle which we learnt at high schools.

[Final OK by SGLee and TA] ch 6, p.371, prob.27  김승연, 오동찬, 칭기즈, TA

Problem 27​            section 7 p. 371

Use the Binomial Theorem to prove that

​

Binomial Theorem

 Theorem  7.1 Binomial Theorem If  and , then .

Solution:

Notice that:

in the given problem   a = 2 and b = -1.

Also:

.

Thus,

which can be written as

hence,

Because the LHS and RHS  is equal due to the Binomial  expansion when a = 2  andb = -1.    So the answer is 1 .                                                ■

Problem 32            section 8 p. 372

Solved by 서명원 Date: 2018.10.29

finilized by 칭기즈 Date: 2018.10.29

Re-Finalized & Final Thank you by 김은율, Date: 2018.10.31

Problem

Let P = {p1p2p3p4p5} be a set of five (distinct) points in the ordinary Euclidean plane each of which has integer coordinates. Show that some pair has a midpoint that has integer coordinates.

Solution

There are 5 different points having integer coordinates.but to find a midpoint we need to take different 2 points out of 5.Hence, we can take 4 points out of 5 to form 2 pairs.

 Pigeonhole Principle (1st Form) If  pigeons fly into  pigeonholes and , some pigeonhole contains at least two    pigeons.

pigeons or n = 5, total number of points in a set P

pigeonholes or k = 4 points ,which are 2 pairs.

Thus,

by the Pigeonhole Principle at least two points, P= ( x i, yi ) and Pj = ( x j, yj ) have

Both x i and x j even or both x i and x j odd

Both y i and y j even or both y i and y j odd​

Theorem:

The sum of even numbers a and b is always even

Proof: a=2k  b=2q

a+b=2k+2q=2(k+q)=2n

The sum of odd numbers a and b is always even

Proof: a=2k+1  b=2q+1

a+b=2k+2q+2=2(k+q+1)=2m

Thus,

( x+ xj )/ 2 and ( yi + yj) /2  are  integers.

Conclusion: Therefore, the midpoint of the pair pi and pj has integer coordinates.

Сomment: There are 5 different points having integer coordinates.but to find a midpoint we need to take different 2 points out of 5.Hence, we can take 4 points out of 5 to form 2 pairs hence it is based on pigeonhole principle. The idea is that there are at least two points having odd or even x and y coordinates.

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

Problem

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

1. The first term is 3.

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

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

(b) Find an initial condition for the sequence.

(c) Find a recurrence relation for the sequence.

Solution

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

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

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

4.     Hence to find another three elements:

n =
2     ->   a2 = 2 + a2-1 = 2 + 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

​​

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

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

(b) Find an initial condition for the sequence.

a​= 3​

(c) Find a recurrence relation for the sequence.

an​ = n + ​an-1

Comment/What We can learn from this question:

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

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

Problem

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

 Definition  1.1

Solution

1.    Let a0 be the initial amount invested

-->
a0=4000

2.    After 1 year, a1 will be

-->  a
1 = a+ 0.17 a= 1.17 a0

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

4.    Thus, after n years, an will be

-->  a
n = an-1 + 0.17 an-1 = (1.17) an-1 = ... = (1.17)a0

Initial state:

a
0=4000

Recurrence relation:

an = (1.17)an-1 ,where a0=4000

Comment

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

Is not a recurrence relation.

Final OK by SGLee] Ch 7, P424, P.5  칭기즈  finalized by 오동찬

Ch 7, p. 424  Problem 5

Is the recurrence relation

an=an-1+an-3

a linear homogeneous recurrence relation with constant coefficients?

Solution:

Definition:

 Definition  2.6

Thus,

The recurrence relation in the definition is linear because the right-hand side is a sum of previous terms of the sequence which are

an-1 and an-3​​

Notice that:

an​ = 1 *an-1​ + 1*an-3

Hence, 1   is a constant coefficient.​​

Conclusion:

The recurrence relation,

an=an-1+an-3

is linear homogeneous recurrence relation with constant coefficients

Comment:

We could find that the given recurrence relation is a linear homogeneous recurrence relation with constant coefficients, due to the definition.

Re-Finalized] Ch. 7 P.424 Problem 6  전솔람, 김희성, 칭기즈 by Muhammad

Chapter 7 Page 424 Problem 6      Problem

Ssolve the recurrence relation subject to the initial conditions.

6. a(n) = - 4 a(n-1) - 4 a(n-2), 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(n-1)= x ,  a(n-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

 Theorem  2.14

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

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

a= 2

a1 = 4

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

=a=2

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

=-4-2b=4

-2b=8

b=-4

Thus:

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

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

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

Problem

Solve the recurrence relation subject to the initial conditions.

7. a(n) = 3 a(n-1) + 10 a(n-2)

a(0) = 4  a(1) = 13​

Solution:

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

x​2​=3x+10

x​2​-3x-10=0

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

X=5   x=-2

There are 2 roots so​

 Theorem  2.11

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

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

a0=4

a1=13

*For n=0

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

=a+b=4

*For n=1:

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

=5a-2b=13

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

a+b=4 (1)

5a-2b=13 (2)

Let’s multiply equation (1) by 2:

2a+2b=8 (3)

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

7a=21

a=3

hence:

3+b=4

b=1

Thus:

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

Conclusion:

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

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,김희성

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.

Definition of recurrence relation

Solution:

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

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

1) 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, there are  C​n-1  strings of type (a).

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

Since any (n-1)-length​ string  containing even number of 1's​  can follow the initial 2, there are C​n-1   strings of type (b).​

For the type (c)

3) As n- length string  that begins with 1 should contain odd number of 1's to make even number overall.

By the formula of permutation with repetitions

RP(n,k)=nk

There are 3​n-1​ strings altogether of length  n-1​

and&nb