MAT 243 Practice for Test 3

pdf

School

Arizona State University *

*We aren’t endorsed by this school

Course

243

Subject

Mathematics

Date

Feb 20, 2024

Type

pdf

Pages

36

Uploaded by ConstableEnergyWaterBuffalo22

Report
Practice for Test 3 Question 1 2.4/2.4pts If f(x) is O(x®) and g(x) is O(x*), then what is the best we can say about f(x)-g(x)? Find the "lowest" big-O estimate that is guaranteed by the given information. f(x)-g(x) is O(x%) f(x)-g(x) is O(x?) f(x)-g(x) is O(x"). f(x)-g(x) is O(x2). The example f(x) =x3 and g(x) = x* shows that we can't conclude that f(x)-g(x) = x is O(x®) or O(x*). We can conclude f(x)-g(x) is O(x) by the product rule. This means that f(x)-g(x) is also O(x'2), but the question asked for the "lowest" big-O estimate.
Question 2 2.4/2.4pts True or False? 5x2 is O(x?). True False If the limit of [f(x)I/Ig(x)| as x goes to infinity exists, then f(x) is 0(g(x)- In particular, if f(x)/g(x) is a constant, then f(x) is O(g(x)). Here, the quotient is a constant 5.
Question 3 2.4/2.4pts Find the lowest integer k so that 1+2°+3°+4° +5°+ . +n° is O(nk). Letuscall 1°+2°+3°+4° +5°+ ...+ n° = S(n). Since each base is at most n, we have the inequality S(n) £n°+n°+ ... +n° = n-n° = n®. Therefore, S(n) is O(n®). On the other hand, if n is even, then n/2 + 1 bases in the sum are at least n/2. For example, S(8) = 1°+2°+3°+4° +5°+ 6+ 7°+ 8°, which has 5 bases that are at least 4. Thus, for even n, S(n) > (n/2)° + (n/2)° + ... + (n/2)°, where we have more than n/2 terms (n/2)° on the right side. Therefore, S(n) > (n/2)° = n°/ 64. This means that S(n) cannot be O(n°). Another way to see that S(n) cannot be O(n°) is to use calculus. By making a Riemann sum diagram, you can see that S(n) is a left sum for the integral of f(x) = x° from x=1to x=n+1. Since f is decreasing, the left sum overestimates the integral. The value of the integral is 1/6 ((n+1)- 1), an order n® function.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 4 2.4/2.4pts Enter the smallest integer n so that the following function is O(x"). f(x)=x2(x® + 1)+x°log(x). The first term is order of x®, hence also big-O of x°. The second term is "between” x° and x® in order, hence big-O of x® but not x°. That makes the first term negligible, and the sum big-O of x® but not x°.
Question 5 2.4/2.4pts Check all functions f(x) that are Q(x?). f(x) = log(x?) (x) = x3/2 +x2 f(x) = [x+2] - [x] f(x)=2x"2 +2x719 (x) = (x*+2x+3)/(x2-2) (%) = (x+2x+3)/(x2-2) f(x) = %2 - log(x) f(x) = 2x+x2
Question 6 2.4/2.4pts If f(x) is O(x3) and g(x) is O(x*), then what is the best we can say about f(x)+g(x)? Find the "lowest" big-O estimate that is guaranteed by the given information. f(x)+g(x) is O() )+g(x) is O(x). F)+g(x) is O(x7). f(x)+g(x) is O(x™?) The example f(x) =x® and g(x) = x* shows that we can't conclude that f(x)+g(x) is 0(x3). We can conclude f(x)+g(x) is O(x*) by the sum rule. This means that f(x)+g(x) is also O(x”) and O(x"2), but the question asked for the "lowest" big-O estimate.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 7 2.4/24pts Check all functions f(x) that are O(x2). (x) = log(x¥) f(x) =x3/2 +x2 () = 1x+2] - [x] (0=2x19 +2x719 f(x) = (x*+2x+3)/(x>-2) f(x) = (x*+2x+3)/(x2-2) f(x) = x2 - log(x) f(x) = 2x +x2
Question 8 2.4/2.4pts True or False? x3 is 0(3%). True False Any polynomial function is big-O of any increasing (base > 1) exponential function. Question 9 2.4/2.4pts Select the smallest k so that f(x)=x-(INx)*+x2 is big-0 of O(x¥). Both terms are big-O of x?, hence their sum is too. Neither is big-O of x, hence their sum can't be big-O of x either.
Question 10 2.4/2.4pts Find the smallest integer k so that _ 4t Flm) = is order of nk. As n gets large, the +1 in the denominator becomes negligible. Thus, f is approximately n + n2 for large n, and therefore order of n2. To prove this exactly, we show that the limit of f(n)/n2is a positive number: The last part of the equation is true because of the horizontal asymptote rule for rational functions. Question 11 2.4/2.4pts True or False? There is a smallest real number a so that 3xx is O(a). True False
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 12 2.4/2.4pts Given an increasing big-O order of the functions. This means that f1 is 0(f2), f2 is O(f3), etc. f1 log(n) v f2 n v 3 n-log(n) v f4 n? v 5 n! - log(n) is O(n) because the ratio log(n)/n goes to zero. nis O(nlog(n)) because the ratio n/(nlog(n)) = 1/log(n) goes to zero. nlog(n) is O(n?) because the ratio nlog(n)/n? = log(n)/n goes to zero. n2is O(n!) because the ratio n?/n! goes to zero. You can see that the last statement is true as follows: n?/nt = n/(n-1)! = n/((n-1)(n-2)!) = n/(n-1) - 1/(n-2)! . The factor n/(n-1) goes to 1, the factor 1/(n-2)! goes to zero.
Question 13 2.4/2.4pts Check all functions f(x) that are ©(x2). f(x) = log(x?) f(x) =x3/2 +x2 f(x) = [x+2] - [x] f(x)=2x"9 +2x7° () = (x*+2x+3)/(x-2) f(x) = (*+2x+3)/(x*-2) f(x) = x2 - log(x) f(x) = 2x +x2 fis ©(x?) iff f is both O(x?) and Q(x?). We get the answers to this problem by combining the answers of the two previous ones.
Question 14 2.4/2.4pts True or False? There is a smallest real number k so that xlog(x) is O(xK). True False xlog(x) is not O(x) because xlog(x)/x = log(x) goes to infinity. On the other hand, xlog(x) is O(xK) for any k > 1. This is because xlog(x) / xk = log(x) / X7, which goes to zero as x goes to infinity. (Use L'Hospital's rule to justify this statement.) It's a calculus fact that any positive power of x goes faster to infinity than log(x), so the denominator in log(x) / Xk (x has a positive power) "wins".
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 15 2.4/2.4pts Find a big-O estimate of (x)=(3x2 + xlog(x?) + x2log(x2))-(Tx® + 2x + 4) + (x2 + x*log(x)) such that in your estimate f(x) is 0(g(x)) and g(x) is a simple function of the smallest order. g(x)=x°log(x) g(x)=x* None of these functions are big O estimates of f(x). The big-O estimate of a sum is the big-O extimate of the largest function. The big-0 estimate of a product is the product of the big-O estimates. Thus, 3x2 + xlog(x2) + x2log(x?) is O(x? log(x)) and mx® + 2x + 4is 0(x3). Hence, (3x2 + xlog(x?) + x2log(x2))-(x® + 2x + 4) is O(x® 1og(x)). We know that x2 + x*log(x) is O( x*log(x)). Using the sum rule, f(x)=(3x2 + xlog(x?) + x2log(x2))-(mx® + 2x +4) + (x2 + x4log(x)) is O(x° log(x)).
Question 16 2/2pts Evaluate ((-14 mod 4) + (76 div 5)) mod 3. -14mod 4 =2; 76 div 5=15; (2+15) mod 3=2. Question 17 2/2pts True or False? There are positive integers n and m so that om =3, True False 2m = 3n s impossible for positive integers n and m due to uniqueness of prime factorization.
Question 18 2/2pts True or False? All numbers being in duodecimal, A7B times 100 is A7B00. True False In base-b, multiplication by b? is accomplished by appending two zero digits to the multiplicand. The base-b representation of b2 is always 100. Question 19 2/2pts True or False? Binary multiplication requires only bit shifts and binary addition. True False The shift-and-add algorithm for doing this is described in the lecture powerpoint.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 20 2/2pts Convert (11011001): to octal. 331 Convert each 3 digit group to octal. Question 21 2/2pts Use the Euclidean algorithm to evaluate the gcd of 1002 and 999. 1002 = 1*999 + 3; 999 =3*333 + 0. The last non-zero remainder is the gcd, in this case, 3.
Question 22 2/2pts Evaluate (23'24° - 21°7°1") mod 11. 10 We have: 23mod 11=1; 21 mod 11=10; 10=-1mod 11. Thus 2324 mod 11 =1; 219" mod 11=10"*"" mod 11 = (-1)¥*""mod 11 = 10. Thus, (23'242-2157°1") mod 11=(23'2* mod 11)-(215*"* mod 11) =1-10=10. Question 23 2/2pts Evaluate 12'°2¢ mod 11. You can use fast modular exponentiation, but an easier way isto use 12 mod 11 = 1. Thus, 12°2* mod 11=1"°2 mod 11=1
Question 24 2/2pts True or False? If k is an integer greater than 1, k3 = (1000)z.. True False The statement is true by the definition of base k representation of an integer. Question 25 2/2pts What is the minimum number of left bit shifts required to carry out the binary multiplication 11011011 -1000101?
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 26 2/2pts The product of two numbers is 48 and their gcd is 2. What is their lcm? 24 If a and b are positive integers, then ab = gcd(a,b) - lcm(a,b). Question 27 2/2pts True or False? To compute 134°®* mod 7 efficiently, you evaluate the quantity 134°#¢ (by multiplying out the product of 4096 factors 13) and then apply the division algorithm to it to find the remainder with respect to division by 7. True False
Question 28 2/2pts True or False? There is a prime number greater than 10'%. True False There are infinitely many primes; thus, for any given integer n, there must be prime greater than n. Question 29 2/2pts If p and q are distinct primes, then the number of positive divisors of the integer n = p3q2is 12 The positive divisors of n are: 1, p, p2 p?, g, pq, p2q, p°q, 42 pg? p°a% p°g>
Question 30 2/2pts Knowing that 5851, 5857, 5861 and 5867 are prime, we can be certain that 5851 - 5867 # 5857 - 5861 without evaluating the two products. True False This is due to uniqueness of prime factorization. Question 31 2/2pts True or False? If pmod 11 = 5and g mod 11 = 7, then (p + q) mod 11=12. True False
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 32 2/2pts If a positive integer has 100 hexadecimal digits with leading digit A, how many binary digits does it have? 400 Each hex digit corresponds to 4 binary digits. This means that a number with 100 hex digits can be expressed with 400 binary digits, including up to 3 leading zeros. Since the first hex digit is A, the first 4 binary digits are 1010, so there are no leading zeros in our count of 400 binary digits. Question 33 2/2pts True or False? We can block-convert from octal (base 8) to hexadecimal (base 16) by grouping the octal digits into pairs of 2, and converting each 2-digit octal number into a hexadecimal number. True False Two octal digits represent a number from 0 to 63, which can be represented by one base 64 digit, but not by one base 16 digit.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 34 2/2pts Convert hexadecimal 5A to binary. Enter a string of only the characters 0 and 1. Do not enter leading zeros or whitespaces. Canvas will add commas to your input. 1,011,010 Each hex digit becomes 4 binary digits: 5is 0101 and Ais 1010. Thus, 5A is 01011010. Omitting the leading zero, we get 1011010. Question 35 2/2pts True or False? All numbers being in hexadecimal, when you divide FA3BC by 10, you get the quotient FA3B and the remainder C. True False Hexadecimal 10 is the number 16. Division by b in base-b is accomplished by taking the last digit as the remainder and the remaining digits as the quotient.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 36 2/2pts The 10 digit hex number 1111111111 equals 9 3 ko 16 10 Y i 16¢ 9 8 i 16° 10 ok k1 16 By definition of base 16 representation, TTT111117=1-16° +1-16%+1-167+1-16°+ 1-16%+ 1-164+71-165+1-162+1-16"+1- 16°.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 37 2/2pts Match each decimal number to its duodecimal (base 12) representation. 10 A v 12 10 v 14 12 v 1 N . In duodecimal, A represents 10 and B represents 11. B is the highest digit. Thus, duodecimal 10 represents 12, and duodecimal 12 represents 14.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 38 2/2pts True or False? Prime factorization is generally a computationally more efficient way of finding the gcd of two positive integers than using the Euclidean algorithm. True False Generally speaking, the Euclidean algorithm is vastly more computationally efficient than using prime factorization. Finding the prime factorization of two extremely large numbers could take a computer longer than the age of the universe, while the same computer can still find their gcd using the Euclidean algorithm within fractions of a second. Question 39 2/2pts Find an integer n such thatn mod 31 =9 and -31<n<0. -22
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 40 2/2pts How many digits does the number 32347 have in base 3? 82,348 In base 3, 3°2347 is a digit 1, followed by 82347 zeros. Question 41 2/2pts How many decimal digits does the number 1292 - 1 have? 106,697 A positive integer n has | log:on | + 1 decimal digits. Thus, n = 12%%8 has | 10g:0129%% | + 1 = | 98868 - l0g1012 | + 1=106697 digits.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 42 2/2pts Evaluate -45 mod 6. We find the answer by using the division algorithm: -45 = (-8)6+3. Question 43 2/2pts Determine the gcd of 52-7° and 3-5-7°. ged(a,b) can be obtained by taking the lowest power of each prime factor p in a and in b. If a prime factor p is not present in one of the two numbers, we consider it present in the form p°.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 44 2/2pts To verify that 139 is prime, we only need to show that 139 is not divisible by 2,3,5,7 and 11. True False If an integer n>1 has no factors greater than 1 and the square root of n, then it is prime. Since 139 < 144 = 122, the square root of 139 is less than 12. Thus, we only need to test whether 139 is divisible by the primes that are less than 12 Question 45 2/2pts Enter the decimal representation of the hexadecimal number FF. 255 FF in hex equals 15:16+15 = 1517 = 255.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 46 0.8/0.8 pts Assemble an inductive proof to show that the quantity 8- 1is a multiple of 7 for all non-negative integers n. Your proof must not contain redundant elements. Write your proof on scratch paper first. Base Case: The n=0 case is true, since 8°- 1 = 0 is a multiple of 7. Inductive Step: Inductive Hypothesis: Now we assume that we have proved that 8" - 1is a multiple of 7 for some arbitrary integer n z 0. Finishing the Inductive Step: We rewrite 8™ -1 as 8-(8"- 1) +7. By the inductive hypothesis, 8" - 1 is a multiple of 7. Thus, s0 is 8(8"- 1) plus any multiple of 7. This completes the inductive step. Answer 1: The n=0 case is true, since 8°- 1 = 0 is a multiple of 7. Answer 2: Now we assume that we have proved that 8- 1 is a multiple of 7 for some arbitrary integer n = 0. Answer 3: We rewrite 8™ - 1 as 8:(8"- 1) +7. Answer 4: By the inductive hypothesis, 8" - 1 is a multiple of 7. Thus, so is 8(8"- 1) plus any multiple of 7.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 47 0.8/0.8 pts On scratch paper write an inductive proof to show that for all integers n at least 1: S 2k =ontl g After that assemble the proof below: Base Case: a. The case n=1 is true, since Zizl 2! =2 = 2and 2 -2=2 b. The case n=1 is true, since the formula becomes 2=2. c. The case n=2 is true, since 2271 2F =2 122 —6and 28 —2=6. d. P(1) is true, since both sides of the formula are equal to 2. e. The case n=1 is true, since Z,lg:l 2k =2 = 2and 2 —2= f. The case k=1 is true, since Z,lg:l 2k =2 = 2and 2 -2=2 e.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Inductive Step: Inductive Hypothesis: a. Assume the statement 3| 2% = 27+ — 2 is true for all positive positive integer n at least 1. b. Assume the statement 3| 2% = 2"+ — 2 istrue foran arbitrary integer n at least 1. c. Assume the statement P(n) is true for an arbitrary positive integer n at least 1. d. Assume the statement 3| 2% = 21 — 2 istrue foran arbitrary positive integer n at least 2. 271 — 2is true for an e. Assume the statement 3| 2" arbitrary positive integer k at least 1. FHL _ 2is true for an f. Assume the statement 22:1 2k = arbitrary positive integer n=k at least 1. b. Finishing the Inductive Step: [Select ] v
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
First we break up the next sum into a sum we already, know plus the next term: a Yhtob 2’1:»1 ok | gk+l b Y2 gk = Y gk gni . Z:’:l zk ZVH»I 2k on dzfl+l2k Zk 12k+2fl01 [ Select] v Now we use the inductive hypothesis for the sum we already know and derive the statement for the next case: a. S 2k pontl = (vt _g) yontl = b. S gk g2 — (gntl _g) q gni2 — 9. gntl C. S gk g2 (942 _g) q gnt2 — 9. gni2 d Sk pon = (2 —2) 4 on =2.2mH —g=n2 g e. 22:1 ok 4 ok+l — (2k+1 —2)+ o+l 9. gk+l _ 9 _ ok+2 | [Select] v
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
This concludes the inductive step. Answer 1: Answer 2: Answer 3: We'll show that the statement is true for n+1 in the following two steps: Answer 4: Answer 5:
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 48 0.8/0.8 pts Suppose we are proving a statement P(n) for all positive integers n by induction. Check all true statements. P(n) is the quantity about which we are proving something We always find P(n+1) by adding n+1 to the statement P(n) The inductive hypothesis is that we have proved P(1) already. The inductive hypothesis is n = k. In the inductive step, we show that n implies n+1 After we assume the inductive hypothesis, we write the statement P(n+1) by substituting n+1 for n. This proves P(n+1) and completes the inductive step. The inductive hypothesis is that P(n) is true for all n In the base case, we verify that P(1) is true.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Question 49 0.8/0.8 pts A working knowledge of laws of exponentiation is required for the induction proof you will be expected to write on the test. Check all algebraic identities. 30 +3m = 3mm 3n- 3m = 3m 30 - 3m = 3mm (Sn)m = Snm Question 50 0.8/0.8 pts On a piece of scratch paper write a short inductive proof for the following statement. After you are done with this practice test, you will find a reference solution to this proof in the detailed response feedback. If you are not certain whether the proof you developed was correct, post it on Discussions. -1 , n o 2-38=3" -1 Answer True if you developed a solution on paper for this problem as instructed. True False Quiz Score: 100 out of 100
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help

Related Documents

Homework 11 Bus Stats.docx
Homework 8 Bus Stats.docx
math-269-group-project-very-useful.pdf
MATH 269 Project.pdf
Week 5 Test 2024-02-02 at 7.15.05 AM.png
Learning and cognition Module 2 Chapter 3 Tazjuana (1).docx
Math 114 15 vs 30 year mortage project.docx
Free Fall- Acceleration due to gravity.docx
Untitled document (8).pdf
Untitled document (6).pdf
math1401-sect09-test3-spring2023 Angie (1).docx
Caution Make sure that your printed Page #1 is OK before you close the Capstone. All the data.pdf