# Victor's CS Site [ COP4531 ]

## Practice Questions

### Click on the questions below to reveal the answer

Define algorithm in your own words.

An algorithm is a recipe for achieving a goal.

More technically:

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function.

What is the difference between code and pseudocode?

When using pseudocode the emphasis is on conveying meaning. Pseudocode is not concerned with syntax specific to any programming language.

Code refers to syntactically correct code written for a specific programming language.

For example:

//This is C code:
printf("The number at position %d is %f", pos, num);

//This is equivalent pseudocode:
print pos and num

### [ Asymptotic Notation: Concepts ]

Write an informal definition of Big O

A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). The notation is read, "f of n is big oh of g of n".

Write a formal definition of Big O

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

Write an informal definition of Big $\Omega$

A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation $f(n) = \Omega(g(n))$ means it is more than some constant multiple of g(n).

Write a formal definition of Big $\Omega$

$f(n) = \Omega(g(n))$ means there are positive constants c and k, such that $0 \le cg(n) \le f(n)$ for all $n \ge k$. The values of c and k must be fixed for the function f and must not depend on n.

Write an informal definition of Big $\Theta$

A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation $f(n) = \Theta(g(n))$ means it is within a constant multiple of g(n). The equation is read, "f of n is theta g of n".

Write a formal definition of Big $\Theta$

### [ Dynamic Programming ]

What is the main idea behind dynamic programming.

If you have solved a problem with the given input, then save the result for future reference, and avoid solving the same problem again.

How can you tell an algorithm is a good candidate for dynamic programming?

What is the difference between dynamic programming and divide-and-conquer?

If the given problem can be broken up in to smaller sub-problems and these smaller subproblems are in turn divided in to still-smaller ones, and in this process, if you observe some OVERLAPPING subproblems, then its a good candidate for dynamic programming.

In divide-and-conquer algorithms we divide the problem in to NON-OVERLAPPING subproblems and solve them independently, like in mergesort and quick sort.

What is the difference between top-down(Memoization) and bottom-up(Dynamic programming) approaches to solving a problem?

Top-Down: Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is referred to as Memoization.

Bottom-Up : Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial subproblem, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Dynamic Programming.