Lesson 4 - Recursion and Dynamic Programming

Data Structures and Algorithms in Python Lesson 4 - Recursion and Dynamic Programming
#1

Please visit the Lesson Page for more detailed info :point_up:

:play_or_pause_button: Session Recordings:
English: https://youtu.be/bCPsBxEyQgc
Hindi: https://youtu.be/c6AYl5bONRI

:zap: This lecture covers recursion, memoization, and dynamic programming. We look at two common problems in dynamic programming: longest common subsequences and knapsack problems.

Notebooks used in this lesson:

:question: Asking/Answering Questions :
Reply to this thread to ask questions. Before asking, scroll through the thread and check if your question (or a similar one) is already present. If yes, just like it. We will give priority to the questions with the most likes. The rest will be answered by our mentors or the community. If you see a question you know the answer to, please post your answer as a reply to that question. Let’s help each other learn!

#2
#3

I didn’t quite understand the recurese(0,0) call in the lcs_memo function.
Can anyone explain?

#4

Has anyone worked out how to return all the items in the knapsack using recursion? I’ve been trying to work it out for a few hours and I just keep digging a bigger hole for myself. I’ve searched online and can’t find an answer there either.

#6

I think you are asking how this line of code…return max(option1, option2) work in max_profit_recursive function? right?

#7

The challenge exercise is to alter the function so that it returns the best list of items in the knapsack as well.

1 Like
#8

Oh the knapsack memoization solution?..i can share an online lecture on knapsack memoization…https://youtu.be/dT6dvdbpChA. And i also need to work on it too. Sorry for late reply. Thanks

#9

Maybe you can look at this link:

With its help, I created a function to return a list of tuples indicating the weight and the profit of elements selected.

Hope this help.

#10

same. if you know could you explain now?

#11

Can you please explain how the time complexity of the recursive solution is 2^(m+n) ? I am not able to understand the m + n part.

#12

m and n are the lengths of the given two strings.

Since for the worst-case scenario, the LCS would be zero.
Therefore, both the strings would generate 2 strings at every step.

So, the time complexity would be 2^m.2^n = 2^(m+n).
i.e. O(2^(m+n))

Since m and n are assumed to be Indefinitely large numbers.
We can say m+n = N where N is an indefinitely large number

Therefore, the time complexity for the worst-case scenario would essentially be
O(2^N).

1 Like
#13

hello guys, i was thinking too much about how to get the road of what recursion chose ? i mean for example we get max_profit or max-subsequence , the answer is only the result of the best road to get best result , so what should i do if i want to see the road what we have taken, for example not only the range of subsequence , i want to know what largest subsequence those both sequence have too, so pls dont give me new code about other problem just change those examples from lesson 4

#14

I read the explanation of complexity of lcs_recursive function written in the above notebook by Aakash sir. It says that all the leaf nodes would become (0,0) meaning the length of both the sequences would boil down to 0.
But I disagree.
The terminating condition is following:

if len(seq1) == idx1 or len(seq2) == idx2:
    return 0

This condition will not allow both the sequences to boil down to a length of 0. Then how can we calculate the complexity assuming the leaf nodes to be (0,0).
By the way I am refering to the following tree:

#15

Also working on this.
If you comment out the #return recurse(0,0) and run, the tests will output None.
I’m guessing the way the key is initially assigned, doesn’t trigger a True or False return from the if-else, and returns nothing.
Then the recurse(0,0) at the bottom, starts off the initial recursion.
Why that is, looks like something I have to review.