Binary Multiplication Flashcards by Adam A

Q

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

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

what is the efficiency of the following:

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

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

Complete it and share the complexity

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

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

2715 * 6399

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Perform the naive algorithm multiplation for these base 2 numbers:

0110 * 1101

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

What is the general multiplication for two n-bit integers

a * b

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

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

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

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

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

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

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

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

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

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

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

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

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

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

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

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

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

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

A

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

What is the worst-case performance of QuickSort?

A

Q

What is the performance of best case quickSort?

A

Q

What are the different pivot choice implementations of QuickSort?

A

Q

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?

A

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²)