Search Trees & Dynamic Programming

Go to:
> Material
> Lecture Recap

Material

• Slides: pre-class (w.o. solutions)
• Slides: with solutions & annotations
• Code:
  • minCostStairs - problem statement, Java CodeExpert template & test-cases
    • Copy the contents of the Main, custom.in and custom.out files into the corresponding files of the ”Welcome” exercise. You can run the tests by using the play button (not the flask).
  • solution

Lecture Recap

This week you learned about two topics:

Search Trees and How to Keep Them Balanced

You got introduced to the dictionary as an ADT that allows for searching values by some defined key. While linked lists and arrays face inefficiencies either with search or with insertions, search-trees enable efficient insertions and look-ups.

However, you also saw that to we need to maintain our search trees balanced to get a logarithmic runtime. Rebalancing complete binary search trees proves inefficient. Instead, we introduce the notion of 2-3 trees (careful, a non-standard definition), which relax some constraints but guarantee the important properties.

Dynamic Programming

Finally, we introduce Dynamic Programming (DP) as an algorithmic paradigm for problems that can be broken down into subproblems that occur frequently. By remembering the solutions to these subproblems, we only need to compute them once and can use them to compute the solutions to the next level of problems. Hence, we proceed very much like in Divide-and-Conquer.

In my experience, DP takes quite some practice to get familiar with. I would recommend:

• seeing many types of problems,
• drawing the analogies,
• and practicing implementations (CodeExpert, LeetCode).

To practice DP, I can recommend the following list of LeetCode problems. If you find some time on your hands, I would already start early and for each problem briefly think it through on paper (like we did in class) and test the solution on LeetCode (you can sign up for a free account).