DS_Exercise_Day2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# DS-Exercise Day2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- 昨天早上請大家 fork 的方式，請先拋在腦後，忘記他。\n",
    "- 交作業方式改為:\n",
    "- 於 GitHub 中，新增一個 Repo，命名為: X-Village-DS-Exercise\n",
    "- 並依照範例檔命名及完成作業，在上傳至 GitHub。\n",
    "\n",
    "\n",
    "- 歡迎用 [slido](https://app2.sli.do/event/bgcdkics/questions) (#4774) 匿名問問題和匿名交友，喔喔喔～～\n",
    "- 今日問卷: https://goo.gl/forms/VVqHhlvUuMMc3cez2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Quickstart"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from lib.queue import Queue\n",
    "\n",
    "q = Queue()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "| Lines | Queue Operation  | Queue Contents     | Return Value |\n",
    "|-------|------------------|--------------------|--------------|\n",
    "| 1     | q.isEmpty()      | []                 | True         |\n",
    "| 2     | q.enqueue(4)     | [4]                |              |\n",
    "| 3     | q.enqueue('dog') | ['dog',4]          |              |\n",
    "| 4     | q.enqueue(True)  | [True,'dog',4]     |              |\n",
    "| 5     | q.size()         | [True,'dog',4]     | 3            |\n",
    "| 6     | q.isEmpty()      | [True,'dog',4]     | False        |\n",
    "| 7     | q.enqueue(8.4)   | [8.4,True,'dog',4] |              |\n",
    "| 8     | q.dequeue()      | [8.4,True,'dog']   | 4            |\n",
    "| 9     | q.dequeue()      | [8.4,True]         | 'dog'        |\n",
    "| 10    | q.size()         | [8.4,True]         | 2            |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is empyty? True\n",
      "Queue size: 0\n",
      "Is empyty? False\n",
      "Queue size: 2\n"
     ]
    }
   ],
   "source": [
    "print('Is empyty?', q.isEmpty())\n",
    "print('Queue size:', q.size())\n",
    "\n",
    "q.enqueue(4)\n",
    "q.enqueue('dog')\n",
    "\n",
    "print('Is empyty?', q.isEmpty())\n",
    "print('Queue size:', q.size())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Removes the front item: 4\n",
      "Queue size: 1\n",
      "Removes the front item: dog\n",
      "Queue size: 0\n"
     ]
    }
   ],
   "source": [
    "print('Removes the front item:', q.dequeue())\n",
    "print('Queue size:', q.size())\n",
    "print('Removes the front item:', q.dequeue())\n",
    "print('Queue size:', q.size())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### The queue operations\n",
    "- `Queue()` creates a new queue that is empty. It needs no parameters and returns an empty queue.\n",
    "- `enqueue(item)` adds a new item to the rear of the queue. It needs the item and returns nothing.\n",
    "- `dequeue()` removes the front item from the queue. It needs no parameters and returns the item. The queue is modified.\n",
    "- `isEmpty()` tests to see whether the queue is empty. It needs no parameters and returns a boolean value.\n",
    "- `size()` returns the number of items in the queue. It needs no parameters and returns an integer.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Exercise2 傳燙馬鈴薯 (ex2.py)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "1. 拿著馬鈴薯的人，會在 front\n",
    "2. 傳遞馬鈴薯的過程，就是先 `dequeue` 後在 `enqueue`，將本來在 front 的人放到尾端\n",
    "3. 傳遞 `num` 次後，拿著馬鈴薯的人（位置在 front）會被淘汰\n",
    "4. 回到第一步，下一回合開始，直到剩最後一個人，為贏家"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "![potato](https://imgur.com/SkLz6mo.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- 利用 Queue, 定義一個function, 傳入名字列表和次數，回傳最後一人的名字"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def hot_potato(name_list, num):\n",
    "    ...\n",
    "    ...\n",
    "    return remaining_person\n",
    "\n",
    "hot_potato([\"Susan\",\"Brad\",\"Kent\",\"David\"], 6)               # 回傳 \"Brad\"\n",
    "hot_potato([\"Bill\",\"David\",\"Susan\",\"Jane\",\"Kent\",\"Brad\"], 7) # 回傳 \"Susan\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Binary Tree Traversal\n",
    "- Preorder\n",
    "- Inorder\n",
    "- Postorder\n",
    "- Level-Order"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- https://austingwalters.com/binary-trees-traversals-everyday-algorithms/ (動畫)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Binary Heap\n",
    "- insert\n",
    "- remove\n",
    "- initialize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- https://visualgo.net/en/heap (會動的視覺化)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "以 Max-Heap (越大的 node 在越上方) 為例：\n",
    "- insert an element:\n",
    "    1. 在 Heap 的尾端插入要新增的 node\n",
    "    2. 調整 Heap，使其符合 Max-Heap (大的 node 要在上方)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- remove the max element:\n",
    "    1. 刪除在最上方的 node (root)，也就是值最大的 node\n",
    "    2. 調整 Heap，使其符合 Max-Heap (大的 node 要在上方)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- initialize a max heap:\n",
    "    1. 從位置是 n/2 的 node 開始\n",
    "    2. 調整該 node 的子樹，使該子樹符合 Max-Heap\n",
    "    3. 往左一個 node，重複步驟2，直到整棵樹符合 Max-Heap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Exercise3 圖解 Min-Heap 運作 (紙本)\n",
    "\n",
    "1. initialize\n",
    "2. insert 5\n",
    "3. remove the min element"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Bonus2 實做 Min-Heap (bonus2.py)\n",
    "- 定義一個 class `MinHeap`\n",
    "- 有以下幾個 methods\n",
    "    - `build_heap(list)` builds a new heap from a list of keys.\n",
    "    - `insert(k)` adds a new item to the heap.\n",
    "    - `del_min()` returns the item with the minimum key value, removing the item from the heap.\n",
    "    - `display()` print the minimum heap on the screen.\n",
    "- template: https://github.com/x-village/data-structure-course/blob/master/exercise/bonus2.py"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}