Computational Number Theory and Algebra - Week 0 Quiz Solutions

Question 1

Revise the concept of vector space (V,+,\cdot) over a field \mathbb{F}, where a set V is equipped with operation +: V \times V \rightarrow V called vector addition and \cdot : \mathbb{F} \times V \rightarrow V called scalar multiplication. Recall the axioms that (V,+,\cdot) needs to satisfy in order to be called a vector space. Which of the following is a vector space?

A.Set of n × n matrices over reals R with '+' as matrix addition and '.' defined as multiplying a scalar constant c with each entry of matrix

B.Set of complex numbers C over reals R with ‘+’ as complex addition and ‘.’ as multiplying scalar with both real and imaginary part of given complex number

C.Set of all univariate polynomials over a field \mathbb{F} with ‘+’ as polynomial addition and ‘.’ as multiplying a scalar c with each term of polynomial

D.All of these

Correct Answer: All of these

Question 2

A linear system of m equations in n unknowns can be modeled as Ax = b, where A is m \times n matrix, x is the n \times 1 vector of unknowns and b is a m \times 1 constant vector. If b is a zero vector, then the system is called homogeneous. The goal is to determine x. Which of the following is true?

A.If det(A) = 0, then the system has a unique solution

B.If the number of equations is less than the number of unknowns, then the system always has a solution

C.A system of homogeneous linear equations may or may not have a solution

D.All of these

Correct Answer: If the number of equations is less than the number of unknowns, then the system always has a solution

Question 3

Recall recurrence relations and asymptotic notation. Consider the recurrence T(n) = 8T(n/2) + O(n^2). (This is the recurrence for simple algorithm of multiplying two nXn matrices). Find the time complexity T(n)?

A.O(n)

B.O(n²)

C.O(n³)

D.O(n² \log n)

Correct Answer: O(n³)

Question 4

This course deals with algorithms for a lot of number theoretic problems. As a novice programmer it is likely that you may have written a program to test whether a number n is prime or not. You would like to know that in this course you will learn very fast algorithms for primality testing (google AKS primality testing for one such beautiful algorithm). Before that refresh your memory with the following warm-up question. The pseudo code below tests primality of a given positive integer n > 2. i = 2 WHILE i <= y IF i divides n RETURN "Not Prime" i = i + 1 RETURN "Prime" Which of the following options give minimum possible value of y for the above program to work correctly?

A.y = n

B.y = [n/2] .where [n/2] is the least integer greater than or equal to n/2

C.y = [\log n] where [\log n] is the least integer greater than or equal to \log n

D.y = [√(n)] .where [√(n)] is the least integer greater than or equal to √(n)

Correct Answer: y = [√(n)] .where [√(n)] is the least integer greater than or equal to √(n)

Question 5

You must have learned probability in your high school curriculum. You will see beautiful applications of probability in some algebraic and number-theoretic algorithms in this course called probabilistic or randomized algorithms. Let us see the power of probability with a toy number-theoretic problem. Suppose you are given a permutation of 2n `consecutive' integers in an array A where n>0.You know an integer is either even or odd. The objective is to find an even number from A. What is the least number of queries a deterministic algorithm makes to A in the worst case? Let us try a randomized algorithm with only one query, which is to pick a number x uniformly randomly from A. With what probability x is an even number?

A.At least 2n queries in worst case; x is even with probability 1/2

B.At least n queries in worst case; x is even with probability 1/2

C.At least n+1 queries in worst case; x is even with probability 1/2

D.At least n+1 queries in worst case; x is even with probability 1/3

Correct Answer: At least n+1 queries in worst case; x is even with probability 1/2

Question 6

You must have learned to find the roots of a quadratic polynomial with integer coefficients in high school. Have you ever wondered how to find the roots of a general cubic or a degree d polynomial? In this course you will learn fast algorithms for the task. Let us recall the high school method with the following refresher problem. You are given a quadratic polynomial p(x)=x^2+bx+c with integer coefficients b and c. Which of the following is sufficient for p(x) to have an integer root?

A.If b²-4c is a perfect square

B.If a²=b²-4c for some integer a and 2 divides b-a

C.If a=b²-4c and 2 divides b+a

D.If b²-4c>0

Correct Answer: If a²=b²-4c for some integer a and 2 divides b-a

Question 7

You have learned about how to multiply two matrices in high-school mathematics. Two n\times n matrices A=(a_{ik}) and B=(b_{kj}) can be multiplied to get another n\times n matrix C=(c_{ij}) where the ij-th entry of C is c_{ij} = \Sigma_{k=1}^{n} a_{ik}b_{kj}. Using this formula to multiply matrices takes significant time for large n. Be ready to learn exciting tricks to get faster algorithms in this course. Before going to them, try to recall a few properties of matrix multiplication. Which of the following is true?

A.Matrix multiplication is both commutative and associative

B.Matrix multiplication is commutative but not associative

C.Matrix multiplication is not commutative but associative

D.Matrix multiplication is neither commutative nor associative

Correct Answer: Matrix multiplication is not commutative but associative

Question 8

You can multiply two integers digit by digit from high school algebra. You will learn some nice tricks in this course to multiply them in a faster way. What is the time complexity of digit by digit multiplication for the two n digit integers?

A.O( n² )

B.O( n3/2 )

C.O( n )

D.O( √(n) )

Correct Answer: O( n² )

Practice: Week 0 :Assignment 0