Binary Multiplication

Question 1

Up to what size number n can two integers be summed in a single CPU operation (O(1))?

Answer 1

Question 2

what is the efficiency of the following:

Answer 2

Question 3

What is the algorithm for binary multiplation using the grade school method.

Complete it and share the complexity

Answer 3

Question 4

What is the naive algorithm for this base 10 number multiplication?

2715 * 6399

Answer 4

Question 5

Perform the naive algorithm multiplation for these base 2 numbers:

0110 * 1101

Answer 5

Question 6

What is the general multiplication for two n-bit integers

a * b

Answer 6

Question 7

What is the Divide-and-conquer for general case of n-bit integers

Answer 7

Question 8

How efficient is the following? What is the recursive formula?

Answer 8

Question 9

Using master theorem, what is the speed of this algo:

Answer 9

Question 10

What is the observation that leads to Karatsuba’s Multiplication algo?

Answer 10

Question 11

What is the Divide, Conquer and Combine for Karatsuba’s mult algo?

Answer 11

Question 12

What is the recursive formula for Karatsuba’s mult algo and what is it’s speed?

Answer 12

Question 13

What are the algorithms that divide the size n into subproblems of approximately equal size?

Answer 13

Question 14

What are the divide and conquer algos that divide the problem into subproblems of uneven sizes?

Answer 14

Question 15

What is the divide,conquer and combine for quick sort?

Answer 15

Question 16

What is the worst-case performance of QuickSort?

Answer 16

Question 17

What is the performance of best case quickSort?

Answer 17

Question 18

What are the different pivot choice implementations of QuickSort?

Answer 18

Question 19

What is the complexity of:

Summing/Multiplying two numbers, where n <= the number of bits in a word of memory?

Summing/Multiplying two numbers where n is > the number of bits in a word of memory?

Answer 19

If n <= the number of bits in a word of memory:

• Both operations take one CPU cycle, O(1)

If n is > the number of bits in a word of memory:

• Summing:
  
  • Theta of (n), where n is the num of columns
• Multiplying:
  
  • Theta of (n²)