Implement the article 'Towards a Better Way to Teach Dynamic Programming' (Forišek, 2015) as a series of Jupyter notebooks
11
stars
1
forks
source link
readme
Magic of Dynamic Programming
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.
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 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 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.
Introduction
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.
Who is this course for?
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.
How to view this course
To see all the notebooks click on this [link](https://mybinder.org/v2/gh/rachelyeshurun/magic-of-dynamic-programming/master?urlpath=lab%2Ftree%2Fnotebooks)
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.
Binder launches the course notebooks
After launching the binder of notebooks, click on a notebook in the left panel
Recommended learning path
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 :wink:
The notebooks should be __viewed in order!!__ The lessons build on each other, so skipping around is not recommended.
Viewing quizzes
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.
Behind the Scenes
This course was born as a final project for the course [CS6460 Education Technologoy](https://omscs.gatech.edu/cs-6460-educational-technology) taken during my Master's degree in Computer Science.
[](https://youtu.be/bh4HpT7Da2s?t=0s "milestone 1")
Credit and Thanks
Aside from the obligation to give credit where it's due, the following links may be of interest to the reader.
Lesson Plans
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.
Other great notebooks
In developing this course I was inspired by many other educational projects
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](https://github.com/yogeshmpandey/M4DT) course [Mathematics for Digital Technologies in Python](https://github.com/yogeshmpandey/M4DT) 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](https://github.com/jupyter-widgets/ipywidgets/issues/2487) by Xiang Zhai formed the base for the quiz infrastructure
Questions?
Please use the `issues` tab of this repository to report any bugs and request new features.
