Discrete Math

sahinapili

assignment2Fall2018.docx

Home >Computer Science homework help >Discrete Math

CS 191 (Tue-Thr), Fall 2018, HW # 2

DUE: Monday, November 12, 2018 by 10:55PM

Q1) Let a be the sequence defined by a = 2n + 3n - 1, where n ≥ 3

Give the following sum and product notations:

Q2)

a) Determine if the following are one-to-one, onto, bijective function or none, explain your answer:

i) ii) iii) iv)

b) what is domain, codomain and range of ii) in part a.

c) f(x) = 4x3 - 5, X = set of real numbers. Find the inverse function (f --1 (y))

Q3) Let f and g be function from the positive integers to the positive integers defined by equations

f(n) = 2n +1

g(n) = 3n – 1

find the composition functions (f o g) and (g o f)

Q4) using proof by cases: prove that if an integer n is not divisible by 3, then n2 – 1 is divisible by 3 for some integer k.

Q5) using proof by equivalence: prove that Z, n is odd if and only if n + 2 is odd.

Q6) Using mathematical induction prove the following:

1. 12 +22+ 32 + ... + n2 =

1. Prove 3+5+7+⋯+(2𝑛+1)= n(𝑛+2) ,𝑓𝑜𝑟 𝑛=1,2,3,…

Q7) Algorithms:

1. Write the insertion sort algorithm and trace the Insertion Sort Algorithm 4.2.3 for the input. 12 18 9 15 16 , show your work.

1. Write text search algorithm, and what will be the output of that algorithm if you are looking for word “amazing” in the text “Thisisanamazingassignment”.

1. Write an algorithm that returns the largest and second largest values in the sequence 𝑠1,𝑠2,…𝑠𝑛. Assume 𝑛>1. The numbers in the sequence are not necessarily unique.

Q8) Prove that:

1. n3 + 2n + 5 = Θ(n3)

1. 1k +2k+…………+ nk = Θ(nk+1) for all n ≥ 1

Q9) For each of the following functions, determine the appropriate 𝑂,Ω,Θ. Show your work.

a. 𝑓(𝑛)=12𝑛3 + 3𝑛⋅𝑙𝑔𝑛 + 4𝑛

b. 𝑓(𝑛)=15lg𝑛 + 4𝑛 + 6⋅𝑛⋅lg𝑛

c. 𝑓(𝑛)=13+23+33+43+⋯+𝑛3

Q10) Represent the number of times x = x + 1 is executed in the following algorithms in Big-O notations.

i=1

x = 0

while ( i <= n ) {

x = x + 1

i = i + 2

}

x = 0

for i = 1 to n

for j = 1 to n

x = x + 1

for k = 1 to n

x = x + 1

Q11) Represent the following integers as product of primes:

i) 145

ii) 625

Q12) using Prime factorization determine the GCD and LCM of the following

i) (65, 98)

ii) (789, 456)

Q13) convert the following decimal and hexadecimal to binary:

i) 75610

ii) AEF16

Q14) convert the following decimal and binaries to Hexadecimal:

i) 84310

ii) 1011010012

Q15) convert the following binaries and Hexadecimal to decimal:

i) AE4516

ii) 1101100102

Q16) Add the following binaries and hexadecimals:

i) 6CB816 + ACD416

ii) 1011010012 + 1101001012

iii) 3EA816 + B4FE16

iv) 1101001012 + 0110010102