Question

9. (5 points) Please describe an algorithm that takes as input a list of n integers and finds the number of negative integers in the list. 10. (5 points) Please devise an algorithm that finds all modes. (Recall that a list of integers is nondecreasing if each term of the list is at least as large as the preceding term.) 11. (5 points) Please find the least integer n such that f() is 0(3") for each of these functions f() = 3r + (log :) (g(2)) for the function g(x). 12. (5 points) Please determine whether is 9(x) =+ 13. (5 points) Please give a big-O estimate for the number of addition used in this segment of an algorithm. for i:=1 to n {for i:=1 to n {t=t+ i + j}} 14. (5 points) Please find how much time does an algorithm take to solve a problem of size n if this algorithm uses 2n2 + 2 operations, each requiring 10-9 seconds, with n = 20 15. (5 points) Please determine what are the quotient and remainder when 1,234,567 is divided by 1001. 16. (5 points) Please decide whether the integer 66 is congruent to 3 modulo 7. 17. (5 points) Please convert the binary expansion of the integer (10 1011 0101)2 to a decimal expansion. 18. (5 points) Please find the Cantor expansion of 87. 19. (5 points) Please find the prime factorization of the integer 289. 20. (5 points) Please find the value of the Euler o-function. (25)

Answer 1

find the least least interes n integes n such such that to Olxha f(x) in for each of these functions. f(0) = 348 + C logwa Big-o notation: f wi o (900)) Us low is there exus C C and d such that If(x) < c locul whenever xod. vor f(x) = 3x3 + Clogr)" when aso, logasa . f(x) = 3x3 + (logx)" & 3x84x The largest power of x in the definition of f(x) is the smallest n for which f(x) lolxs Here n=5. when xol, we have property ? we choose d = 1 and thus ex>1 1f(x)) = 1 328 + log x)') £ 3x3 + x < 3x8 tas = 4 x3 =41851 Thus we need to choose c=4. Hence by the definition of Big-o notation, f(x) = Oca) with d=1, C =4.