Recursion

Question 1

Many useful algorithms are r_____________ in structure.

Answer 1

recursive

Question 2

What is Recursion?

Recursion is when a method in the algorithm which calls itself from within itself.
See John’s video on YouTube.

Merge Sort uses r_______________ to sort the smaller subarrays.

Answer 2

recursion

Question 3

Divide and Conquer

A divide-and-conquer approach: breaks the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively and then combine these solutions to create a solution to the original problem.

1) D_____________ the problem into subproblems
2) C_____________ the subproblems recursively, or simply.
3) C____________ the solutions to the subproblems into
the solution for the original problem.

Answer 3

Divide
Conquer
Combine

Question 4

Time Complexity -NB

Our merge sort takes theata(n) , but in reality it takes longer.
I think we are working on a simplified version at the moment.

Question 5

Loop Invariants

A loop invariant is a tool used to prove the c_______________ of an algorithm, specifically in regards to a loop.

It is a property or set of properties of type b_________, that must be aligned with the goal of the algorithm.

It MUST hold (be true) at initialization, maintenance, and t__________.

Answer 5

correctness
boolean
termination