Dynamic Programming

Question 1

Recursive Programming

Answer 1

Recurssive problems can always be solved using recursion. Example: Fibonacci

def F(n)
     return 1 if n>3
           else F(n-1) + F(n-2)

Question 2

Simple recurssive approaches are often very wasteful because we solve subproblems many times

Answer 2

an exponential number of times in the case of Fibonacci

Question 3

Dynamic Programming is a algorithmic paradigm

Answer 3

We will use pairwise alignment of sequence data

Question 4

Recurrsive programming

Answer 4

Many recurssive problems have recurrsive solutions. Breaking down into subprblems can lead to solution of overall problem

Subproblems on the boundaries of the problem space (the smallest ones) often have trivial solutions

Question 5

Factorial computation can be solved by a recurssive equation

Answer 5

..

Question 6

Dynamic programming is much faster than recurssive programmming

Answer 6

Dynamic programming is going to increase by linear to input value

Recurssive programming is going to increase exponentially to the input value

Question 7

Dynamic programming saving the output you compute instead of re-computing it again

Answer 7

..

Question 8

Challenging part of dynamic programming is how to divide it into subproblems

Answer 8

How and where you will save it into memory.

Fibonacci you save it into array.

Question 9

Dynamic programming allows going into polynomial run time algorithm

Answer 9

Number of subproblems should grow polynomically

algorithmically the runtime wil grow proportionally tonumber of EDGES (not vertex)

V | < | E | < | V | choose 2

Question 10

EDIT Distance

Answer 10

the mnimum number of mismatches across all possible aligments.

Want to try to come up with all possible alignments?

Better how to divide problem into subproblems

When thinking of subproblems think of how to reduce/reuse values

Question 11

Prefix alignment allows for recursion

Answer 11

..

Question 12

Backtracking

Answer 12

while filling the table, save which of the three possibilitieswe chose

• at the end, by following the arrows, we get an alignment
• • a match when we got diagonally up
• • a das

Question 13

Full graph is called….

Answer 13

Dependency Graph

Question 14

Waterfall Ordering

diagonal approach

Answer 14

Allows for parallel programming

How you order things can be important

For more information about waterfall ordering
Marc Snir Illinois

Question 15

Ordering has to deal with memory too.

Answer 15

The way table was created was not necessary. Anytime if we are trying to compute, only need previous row don’t need the much older rows. To find edit distance just keep previous row.

If just do one row at a time we will have asymptotic runtime

Question 16

Memoization

Answer 16

Dynamic programing is typicallly described in terms of multidimensional tables or arrays that are filled from one side to ther other. The table both gives the order and the memory.. But it not need be that way.

Memoization Dynamic programming can be implementated recurssively.

• use a recursive code, but simply save solutions to subproblems in the memory and look up the memory before the recursive call
• sometimes uses a data strcture other than an array (i.e. diciotnary)
• the order is defined by a bottom-up traversal of the subproblem DAG

Question 17

Local vs Global Alignment

Answer 17

Global Alignment :

Question 18

Penalize (beta)

Probability of having a insertion or deletion

Every time you add a gap you add a beta

Answer 18

.

Question 19

Unrooted tree

Answer 19

undirected graph in which any two nodes are connected by exactly one path

Question 20

Rooted Tree

Answer 20

Designating one node as the root and orientating all edges away form the root gives an undirected graph that repsrents a rooted tree

Question 21

many problems have obvious easy recursive solutions

Answer 21

the solution to the full problem can be formulated as a function of solutions to set of subproblems, which depends on smaller subproblems

boundary conditions (base case)

Question 22

Linearization of is any partial order of a full order that is compatible with that partial order

Answer 22

Child should come before the parent

Question 23

Save results in the memory to reduce recurssive computation

Answer 23

Before do a sub problem, check the memory

Question 24

If you know your subproblem ahead of time in advance…. (dependencies)

Answer 24

then you can design your program to be efficient