Intro - Dynamic Programming Flashcards
What is tabulation?
What type of approach is it?
What is the code for fibonacci using tabulation?
What is the run time of fibTabulation?
What is memoization? what type of approach is it?
What is the example fibonacci code for memoization approach?
what is the run time for the top down fib approach
Compare and contrast Tabulation vs Memoization.
Why use one over the other?
How do we know when to use:
Dynamic Programming
Greedy
Divide-and-Conquer
What must hold to use any of the above approaches?
What is a palindrome and what is the definition?
What is a subsequence?
What is the input of the longest palindromic subsequence problem?
What is the definition & required output of the longest palindromic subsequence problem?
What are the feasible solutions and correct output if there are no repeating characters in a palindrome sequence?
What is a solution in the following sequence?
What is the cost to brute force the longest palindromic subsequence problem?
What is the general recursive algorithm for the Longest palindromic subsequence
What is the running time of our first palendrome sequnce.
Which is Omega (2n)
Using the iteration method, what is the closed form of the following?
For the bottom-up version of the longest palendromic sequence, how is the table setup?
For the bottom up approach for the bottom-up version of longest palen, how do you setup the base cases?
Assume we have a table of n = 8
What is the order in which the table is filled out with the bottom-up approach for longest palen
Analyse the run time of this algorithm
What is the order in which this table is filled out?
What is the run time of this algo
What is the general optimal substructure format for longest palendrom (NOT the proof)
What is the optimal substructure proof for longest palendrome?
How does the overlapping subproblems work for longest palendrome/dynamic programming?
