2022/week-9.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d2074055-b87d-4a90-a9a4-53ee4666ff78",
   "metadata": {},
   "source": [
    "Table of Contents:\n",
    "- [Introduction](#Welcome-to-CPG!)\n",
    "- [Week 9 Content](#Dynamic-Programming)\n",
    "- [An-Intuitive-Example](#An-Intuitive-Example)\n",
    "- [Why Does it Matter?](#Why-do-we-use-dynamic-programming?)\n",
    "- [Hackerrank Competition](#Hackerrank-Competition)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "605dc409-24ac-4be4-a4b9-d4a51d8d0574",
   "metadata": {},
   "source": [
    "## Welcome Back to CPG!\n",
    "\n",
    "I'm sure you missed us last week but alas, we are back!\n",
    "\n",
    "**Before we start...**\n",
    "\n",
    "If you'd like to follow along for yourself and run the code examples in our presentations, you can clone the repository and open up the Jupyter notebooks locally. Note this means you need to have installed [Jupyter](https://jupyter.org/install) - either JupyterLab or Jupyter Notebook will work fine. In the below example we use JupyterLab:\n",
    "```\n",
    "git clone git@github.com:UQComputingSociety/cpg\n",
    "cd cpg/2022\n",
    "jupyter-lab\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f710a76-436b-4672-bb54-0f0c4b73f958",
   "metadata": {},
   "source": [
    "## Dynamic Programming\n",
    "\n",
    "### What is dynamic programming?\n",
    "\n",
    "Similar to greedy algorithms, dynamic programming utilises divide and conquer in order to simplify complex problems. Where an order of differentiation comes in is that DP incorporates the concept of 'memoization'; essentially, in a recursive algoirthm, we 'remember' the prior solutions to subproblems we have alreaded solved for certain states/inputs, and store those solutions to be incorporated when solving subproblems that might incorproate it."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6622ccb-c542-476b-8a2e-fa55e51e2a9d",
   "metadata": {},
   "source": [
    "## Example: An Intuitive Example\n",
    "\n",
    "Calculate the result of (11 * 10)/5\n",
    "\n",
    "Calculate the result of ((11 * 10)/5) + 1\n",
    "\n",
    "Did you recalculate (11 * 10)/5 or did you remember the first solution and add 1? This is a dynamic programming solution"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f0fcf9a-c2e7-4812-97cc-b35a3e758c8e",
   "metadata": {},
   "source": [
    "## When do we use dynamic programming?\n",
    "\n",
    "Dynamic programming is applicable whenever you notive a recursive solution made up of overlapping sub-problems. It is important to know that dynamic programming simply trades between time complexity and space complexity. For example, the fibonacci sequence is considered a case where dynamic programming can be implemented. But how do we choose which states to save? All of them?\n",
    "\n",
    "## Why is dynamic programming important?\n",
    "\n",
    "Dynamic programming commonly comes up in interview questions, and has been used to solved some very useful algorithms.\n",
    "\n",
    "- Unix diff: File comparison in bash utilises dynamic programming\n",
    "- Google maps: Maps utilises dynamic programming for pathfinding between destinations\n",
    "- Git merge: Similar to unix diff\n",
    "- TeX hyphenations/justifications: Precursor to LaTeX, TeX uses DP to calculate the correc number of hyphenations and justifications. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1e5bb38-cb9a-4af4-a4ac-96a78f8c575b",
   "metadata": {},
   "source": [
    "## HackerRank Competition\n",
    "\n",
    "Follow this link to the Hackerrank to begin the mini competition and start solving some graph questions!\n",
    "\n",
    "https://www.hackerrank.com/cpg-week9-1663644919"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}