Part 03 - Chapter 11 - Last Chapter.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ten <small>(useful)</small> algorithms that were NOT covered in this book."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x01 - Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's talk about *<u>binary search tree</u>* data structure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose we logins to FB \n",
    "- FB has to look through a big array to **see if the username exists**.\n",
    "- Every time a **new user signs up**, you **insert their username** into the array.\n",
    "\n",
    "use *Binary Search* ?\n",
    "- It's awesome. \n",
    "- BUT, once a new user signs up, you MUST re-sort the arrary again. (that? takes time!)\n",
    "\n",
    "What if we don't have to *re-sort* \n",
    "- Here's illustration of *binary search tree*\n",
    "\n",
    "![ ](./img/seemore_01_tree_01.jpg)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For every node, \n",
    "- the **node to its left** are ***smaller*** in value.\n",
    "- For people in the graph, it's kind of \"inserting order\".\n",
    "\n",
    "We need find *MAGGIE*\n",
    "1. root (DAVID) \n",
    "2. root-**right** (MANNING), MAGGIE comes **after** DAVID.\n",
    "3. root-right-**left** (MAGGIE), MAGGIE comes **before** MANNING. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It (the ds) is **fast** even comparingt to *binary search*\n",
    "\n",
    "| \\ | Array | BinSearchTree |\n",
    "| :--: | :--: | :--: | \n",
    "| Search | O(log n) | O(log n) | \n",
    "| Insert | O(n) | O(log n) | \n",
    "| Delete | O(n) | O(log n) |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But, it may don't have very good performances.<br>\n",
    "This kind of *tree* we call it <q>**unbalanced**</q> .\n",
    "\n",
    "Like this:\n",
    "\n",
    "![ ](./img/seemore_01_tree_02.jpg)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There're special *binary search trees* that **balance themselves**. \n",
    "\n",
    "More advanced data structures\n",
    "- B-trees\n",
    "- Red-black trees\n",
    "- Heaps \n",
    "- Splay trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x02 - Inverted indexes\n",
    "\n",
    "__A very very simplified version of how search engine works__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Suppose u've got three webpages with these content\n",
    "\n",
    "![ ](./img/seemore_02_search_01.jpg)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "then we can build a hash table (?dict) from it.\n",
    "\n",
    "![ ](./img/seemore_02_search_02.jpg)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's search! (just-examples)\n",
    "\n",
    "| cond | result | \n",
    "| :--- | :----  | \n",
    "| If I searched 'Hi' | The webpages A, B should be appeared |  \n",
    "| If I searched 'WE' | There should be a webpage C |  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x03 - The Fourier transform "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Well, ... I (only) added these articles to read-later XDDDD.\n",
    "\n",
    "Resources \n",
    "- [thefouriertransform-#introduction](http://www.thefouriertransform.com/#introduction)\n",
    "- [math-stackexchange_fourier-transform-for-dummies](https://math.stackexchange.com/questions/1002/fourier-transform-for-dummies)\n",
    "- [betterexplained_guide-to-the-fourier-transform/](https://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x04 - Parallel algorithms "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In short, it could make your algorithms *faster*.\n",
    "\n",
    "But, parallel algorithms are hard to design.\n",
    "- It's hard to make sure they worked correctly, \n",
    "- and to figure out what type of speed boost you'll see.\n",
    "\n",
    "And the time gains aren't *linear*. (e.g. 2 core != 2x speed)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A couple of reasons for this. (examples)\n",
    "\n",
    "1. Suppose you have to sort an array of 1000 items\n",
    "    - How do divide this task among the two cores?\n",
    "    - Even you divide it efficiently, when it comes to ***merge***, that also **takes time**.\n",
    "    \n",
    "2. Suppose you have 10 tasks to do\n",
    "    - Each core gets a half. \n",
    "    - A gets all easy tasks (10s), and B get all the hard tasks (1min).\n",
    "    - For now, it means that <q>*A need sitting idle for 50s*</q> (in contrast to B)\n",
    "    \n",
    "All right! <br>\n",
    "these are my basic understanding (or *reading-note*) of parallel algorithms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x05 - MapReduce"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A *distributed algorithm* was used in **Apache Hadoop**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x06 - Bloom filters and HyperLogLog\n",
    "\n",
    "Wiki: [Bloom filters](https://en.wikipedia.org/wiki/Bloom_filter), [HyperLogLog](https://en.wikipedia.org/wiki/HyperLogLog)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x07 - The SHA algorithms\n",
    "\n",
    "- I've got some basics, so I'll just leave this blank :)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x08 - Locality-sensitive hashing\n",
    "\n",
    "Wiki: [Locality-sensitive hashing](https://en.wikipedia.org/wiki/Locality-sensitive_hashing)\n",
    "\n",
    "- Similar items map to the same “buckets” with high probability.\n",
    "\n",
    "- It differs from conventional and cryptographic hash functions <br>because it aims to maximize the probability of a “collision” for similar items."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x09 - Diffie-Hellman key exchange"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wiki: [迪菲-赫爾曼密鑰交換](https://zh.wikipedia.org/wiki/迪菲-赫爾曼密鑰交換)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0x10 - Linear programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wiki: [線性規劃](https://zh.wikipedia.org/wiki/线性规划)"
   ]
  }
 ],
 "metadata": {
  "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
}