Algo: Misc

Question 1

Types of Algorithms

Answer 1

1. Brute Force
2. Greedy
3. Divide and Conquer
4. Dynamic Programming

Question 2

Describe Brute Force algorithm

Answer 2

Generally the most straightforward and exhaustive option. Go over each and every possible solutions to the problem

Generally the first one that pops in the head to solve the problem.

Question 3

Describe Greedy algorithm

Answer 3

Successful in very specific problem set like Huffman Encoding to compress data or to find shortest path through a graph.

This is done by making an optimal choice at each step in an attempt to find optimal solution to overall problem. Recursion is generally used.

In many cases where Greedy Algorithms fail, Dynamic Programming might be better choice

Question 4

Describe Divide & Conquer algorithm

Answer 4

The problem is repeatedly divided into sub-problems until we reach a base case. At that point, we start solving the base cases and combining the answers from the base case to eventually provide answer for original problem.

Application: Sorting

Question 5

Describe Dynamic Programming algorithm

Answer 5

DP algorithms solve by combining results of sub-problems like Divide and Conquer. It depends on “remembering” the past.

Two patterns:

1. Memoization
2. Tabulation

Question 6

What is Memoization in DP

Answer 6

Memoization pattern is top-down pattern. Uses recursion.
Starts from a large problem and then breaks into small parts. And it looks for the solutions of a subproblem in a lookup table before computing solution,

Question 7

What is Tabulation in DP

Answer 7

Tabulation is bottom-up pattern in DP. Avoids recursion.

Start from a small problem and populate the lookup table. Compute solution for original problem based on look up table.