Chapter 17

Question 1

What algorithm is used by fibonacci number: iterative algorithm

Answer 1

O(n)

Question 2

What are 2 steps for dynamic programming

Answer 2

1- Formulate problem recursively (write down formula for whole problem as a simple combination of answers to smaller sub problems)
2- Build solution to recurrence from bottom up. (write an algorithm that starts with base cases and works its way up to the final solution)

Question 3

Does factorial have recursive foundation

Answer 3

Yes

Question 4

What is edit distance algorithm

Answer 4

It introduced in 1966 by molecular biology. It says that we can change for example a word to another word by 4 types of operations.
1. Replace
2. Insert
3. Delete
4. Leave it
Edit distance tells how much number of operations required to change word. e.g. spell check, plagiarism, speech recognition

Question 5

What is longest common sequence

Answer 5

Its a variation of edit distance. If we have 2 data sets and it is possible that there is sub sequence in it. It does not means a matching portion between 2, but frequency of common occurrence of letters. It is called LCS (longest common sequence problem).

Question 6

Is there a separate algorithm to find short string in long string

Answer 6

Yes. e.g. search a word in file