Introduction

Question 1

What are some of the common algorithm design techniques? Name one example for each.

Answer 1

• Incremental. Example: Insertion sort.
• Divide-and-conquer. Example: Merge sort.
• Using a data structure. Example: Heap sort.
• Greedy algorithms. Example: Minimum-spanning tree.

Question 2

What is loop invariant?

Answer 2

Loop invariant is a technique used to help us understand why an algorithm is correct. We must show three things about a loop invariant:

• Initialization: It is true prior to the first iteration of the loop.
• Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
• Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

Question 3

Describe divide-and-conquer algorithm approach.

Answer 3

These algorithms break the problem into several subproblems that are similar to the original but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem.

Question 4

What are commonly used asymptotic notations for describing algorithm running time?

Answer 4

• Big O
• Big Theta
• Big Omega

Question 5

What is Big O notation?

Answer 5

Big O asymptotic notation gives an upper bound for a function to within a constant factor.

Question 6

What is Big Theta notation?

Answer 6

Big Theta asymptotic notation bounds a function to within constant factors from above and below.

Question 7

What is Big Omega notation?

Answer 7

Big Omega asymptotic notation gives a lower bound for a function to within a constant factor.