Does dynamic progrmming seem like dark magic to you?
Do you wish there was a step-by-step approach to any dynamic programming problem thrown at you?
Join me in this virtual classroom where I will teach you a method to design your own beautiful algorithms.
Author: Rachel Yeshurun
-
When you click on the Launch Binder badge the lessons will be launched on a JupyterHub server. A tabbed 'binder' of notebooks will open in your browser without any installation.
Clicking on a lesson name below will launch Binder with that lesson open and ready.
* By the end of this lesson, you will have reviewed recursive algorithms and along the way you'll learn how to use these notebooks and their interactive elements.
* The worked problem in this lesson is 'Find the sum of n numbers'.
* By the end of this lesson, you will know when and how to memoize a function.
* The worked problem in this lesson is 'Factorial'.
* By the end of this lesson, you will know how to memoize a recursive algorithm and you will see the magical effect memoization has on the naive Fibonacci algorithm.
* The worked problem for this lesson is 'Find the n'th Fibonacci number'
* By the end of this lesson, you will know the right way to make a start on any dynamic programming problem.
* You will learn the 4 steps to solving any dynamic programming problem.
* The worked problem for this lesson is 'The Drinking Game'.
- [Lesson 4: Paths in a Grid]
* By the end of this lesson, you will have practiced the 4 steps on a 2 dimensional problem.
* You will learn to recognize the 'count the number of' pattern
* The worked problem for this lesson is 'Paths in a Grid'.
* By the end of this lesson, you will know how to solve the 'longest common subsequence' problem.
* You will learn to recognize another common subproblem pattern.
* The worked problem for this lesson is 'Happiness and Pinecones'.
* By the end of this lesson, you will know how to solve the 'longest increasing subsequence' problem.
* The worked problem for this lesson is 'Flower Picking'.
- [Lesson 7: Knapsack]
* By the end of this lesson, you will encounter a class of dynamic programming problems that run in pseudo-polynomial time
* The worked problem for this lesson is 'Knapsack'.
- [Lesson 8: DAGs]
* By the end of this lesson, you will understand how all dynamic programming problems can be represented by directed acyclical graphs.
Dynamic programming has the reputation for being tricky to master, but once you understand the basic concepts and practice them enough, the algorithms do not seem so difficult anymore.
My hope is that this lightweight course will serve as a primer for students to prepare for other, more rigorous algorithm courses at university.
This course requires the level of computer science knowledge of a first year, first degree student. Some knowledge of Python is necessary to complete the coding exercises.
This course is designed to be taken over a few hours, for example as a weekend project.
To see all the notebooks click on this link
Alternatively, navigate to each notebook from the table of contents above. When you click on a notebook link, a fully interactive classroom session will launch within 30 seconds in your browser without any setup or installation!
Note: The session might take some time to open, or it might not build on your first try. Be patient or try clicking the link again.
The notebooks have short embedded videos to start off each new topic. Watch the video, read the explanation and test your understanding with some quick quizzes.
Follow along with a worked example, then try your hand at the coding exercises. In these problem sets you will get a chance to apply the techniques learned up to that point. Try to work the problems out on your own before peeking at the answers 😉
The notebooks should be viewed in order!! The lessons build on each other, so skipping around is not recommended.
When the notebooks load, most elements such as videos, text and diagrams will be visible. If quizzes don't show up, just run the whole notebook (Run All Cells) and the quizzes should appear within a few seconds
Sometimes the quizzes show up with little broken links. Again, just run all cells and that should fix the problem.
This course was born as a final project for the course CS6460 Education Technologoy taken during my Master's degree in Computer Science.
Aside from the obligation to give credit where it's due, the following links may be of interest to the reader.
This course is an implementation of the article 'Towards a Better Way to Teach Dynamic Programming' (Forišek, 2015).
The notebooks follow the 8 lesson plans described in the article, expanding the lesson outlines with additional explanations and original content.
The following notebooks stand out as the ones I most relied upon for inspiration:
The organization of this readme is copied, inspired by my Georgia Tech classmate Yogesh Pandey's course Mathematics for Digital Technologies in Python which incidentally, makes an excellent companion course for this one if you're using these notebooks to prepare for a deeper dive in to machine learning, computer vision, NLP etc.
This question and the answer by Xiang Zhai formed the base for the quiz infrastructure
Please use the issues tab of this repository to report any bugs and request new features.
