Week 5

Question 1

Merge Sort and Quick Sort Big-O?

Answer 1

O(n log n)

Question 2

Selection Sort Big-O?

Answer 2

O(n^2)

Question 3

Popular techniques in problem solving?

Answer 3

–  Greedy method
–  Dynamic Programming
–  Data compression
–  Backtracking
–  Branch and Bound

Question 4

A problem has?

Answer 4

A problem has:
– Universal solution
• all the possible solutions both right and wrong
– Feasible solution
• all possible correct solutions, but different levels of truth
– Objective function
• the function to measure the solution which is more correct (better)
– Optimal solution
• the most correct solution (best)

Question 5

What is Dynamic Programming?

Answer 5

Dynamic Programming is a method of solving a problem that can be used if the solution of a problem can be viewed as a sequence of several decisions.