ITA - Week 5

Question 1

Divide and Conquer

Answer 1

A problem is divided into several subproblems
The subproblems are solved (typically recursively)
The subproblems are combined

Question 2

Known divide and conquer algorithms

Answer 2

Binary search

Mergesort

Question 3

What is Mergesort

Answer 3

The problem is divided into 2, both halves are solved and later recombined

Question 4

Merge subroutine

Answer 4

Get 2 pointers, check the smaller number and add to final list while increasing pointer by 1.

Question 5

Divide and conquer x^8

Answer 5

x^8 = (((x^2)^2)^2)

Question 6

Divide and conquer x^2r

Answer 6

((x^2)^2) - r times

Question 7

Algorithm for exponention

Answer 7

If exponent (n) is odd multiply result by x and decrease n by 1
If exponent (n) is even square current value of x and divide n by 2
Repeat until n = 0