{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Unit 3 Sections 17 and 18 Lesson\n",
    "> Algorithmic Efficiency and Undecidable Problems\n",
    "\n",
    "- title: Unit 3 Sections 17-18\n",
    "- toc: true\n",
    "- badges: false\n",
    "- categories: [lessons]\n",
    "- permalink: /lesson"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Do Now!!!\n",
    "\n",
    "- Set up your notebook by either wgetting the lesson or tracking it by your own (We would recommend wgetting since there are some fill in the blanks!)\n",
    "- **wget here:** https://raw.githubusercontent.com/mmaxwu/Tri2-GroupFastpages/master/_notebooks/2022-12-dd-lesson.ipynb"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.17: Algorithm Efficiency\n",
    "Purpose:\n",
    "\n",
    "The purpose of this lesson is to help students understand how to make an efficient program and optimize it and understand its importance to the CSP curriculum.\n",
    "\n",
    "### What is Algorithmic Efficiency?\n",
    "- The ability of an algorithm to solve a problem in an efficient way\n",
    " - An efficient algorithm solves a problem _______ and with a _____________, such as time and memory.\n",
    "- How do we determine if an algorithm is efficient or not?\n",
    " - One way we can do this is by determining the _________ of the algorithm.\n",
    " - Another way is through _________. \n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Traveling Merchant Problem Hacks:\n",
    "What did you and your team discuss? (record below)\n",
    "\n",
    "\n",
    "- An ________ solution is __________________ that produces a solution that isn't necessarily _____ but can be used when normal methods take forever \n",
    "\n",
    "Describe the method used to solve the traveling merchant problem. (record below)\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.18: Undecidable Problems\n",
    "Purpose:\n",
    "\n",
    "The purpose of this lesson is to introduce students to the concept of undecidable problems in computer science and to explain why these problems are important.\n",
    "\n",
    "**Key vocabulary**:\n",
    "- Decision problem\n",
    "- Decidable problem\n",
    "- Undecidable problem\n",
    "\n",
    "### Decision Problem\n",
    ">A decision problem is a problem in computer science and mathematics that can be solved by a yes-no answer, also known as a binary answer. In other words, a decision problem is a problem for which there are only two possible outputs: \"yes\" or \"no\".\n",
    "\n",
    "There are two types of decision problems that Collegeboard goes over:\n",
    "- Decidable Problems\n",
    "- Undecidable Problems\n",
    "\n",
    ">A ________ is a problem in computer science and mathematics for which an algorithm can be created that can always produce a correct answer or solution. In other words, a decidable problem is a problem for which there exists an algorithm that can be used to determine whether a given input is a valid solution or not.\n",
    "\n",
    ">An ________ problem is a problem in computer science and mathematics for which it is impossible to create an algorithm that can always provide a correct answer or solution. This means that it is not possible for an algorithm to always determine whether a given input is a valid solution to an undecidable problem."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decidable Problems\n",
    "A decidable problem is an algorithm that can always have an output of `yes` or `no` given any input. It is always correct."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example of a Decidable Problem\n",
    "The procedure below tests to see if a number is divisible by 13. If it is, it returns `true`. If it isn't, it returns `false`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "def divideThirteen(number):\n",
    "    if number % 13 == 0:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "print(divideThirteen(26))\n",
    "print(divideThirteen(30))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Undecidable Problems"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### An Example of a Forever Running Code\n",
    "The code keeps adding `1` to the variable `number` until `number` is no longer an integer(This is not the python data type \"integer\", it's the integer in number theory). However, there is no end to this code, making the computer run forever. There is no halt to the code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "i = 0\n",
    "number = 1\n",
    "def integerTest(n):\n",
    "    # Testing if the number is an integer\n",
    "    if n%1 ==0:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "# Using while loop to keep searching an a non-integer above 1. Note that the computer runs forever.\n",
    "while i == 0:\n",
    "    number += 1\n",
    "    if integerTest(number) == False:\n",
    "        i +=1\n",
    "        print(\"Done\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Halting Problem\n",
    "The halting problem is an example of an ________. It states that it is not always possible to correctly determine whether a code halts or runs forever.\n",
    "> There is ________ to write an algorithm to analyze and determine whether a body of code can run forever or not."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Halting Problem Example:\n",
    "- In order to understand this, suppose that an algorithm was able to analyze whether a code halts or not. Let's call this algorithm `HaltChecker`.\n",
    "- `HaltChecker` analyzes the program,`program P`, and its input,`input I`. If `program P` halts with `input I`, `HaltChecker` returns an output of \"halts\". If `program P` doesn't halt(runs forever) with `input I`, `HaltChecker` returns an output of \"never\". For example, in the code where it tests if variable **number**, the ________, so `HaltChecker` returns an output of ________.\n",
    "- Then, we add another algorithm called `Reverser` which reverses `HaltChecker`'s output. So, if \"never\" is the output of `HaltChecker`, then the output of `Reverser` is ________. It's also the same the other way around: if `HaltChecker` has an output of \"halts\", then `Reverser` has an output of ________.\n",
    "- We combine these algorithms into one entire body of code.\n",
    "- **Since `Reverser` is the algorithm at the end, hence giving the ultimate output, notice how it prints \"never\" when in fact there is an end(As proved by `HaltChecker`), and how it also prints \"halts\" when there is in fact is no end to the code(Also proved by `HaltChecker`). As a result, `HaltChecker` is inaccurate and this is an undecidable problem.**\n",
    "\n",
    "#### This Diagram Sums up the Entire Process in the Bulleted List:\n",
    "![reverser](https://github.com/mmaxwu/Tri2-GroupFastpages/blob/master/images/reverser.png?raw=true)\n",
    "\n",
    "Credits of diagram and example to Khan Academy"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### FAQ\n",
    "- **Q**: If `Reverser` is causing the problem, why not remove it?\n",
    "- **A**: Removing `Reverser` will remove the problems, however, we are looking for ways which create the problem of not outputting a correct result. One example is enough to prove that it is an undecidable problem since it proves that the code is not completely accurate.\n",
    "\n",
    "### Extra Things to Notice\n",
    "- Note that while a computer may take a long time to run a section of code, it does not mean that the computer is going to run forever.\n",
    "- Humans are able to solve some undecidable problems. The entire Halting Problem example was to prove that computers cannot solve undecidable problems."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hacks\n",
    "Come up with one situation in which a computer runs into an undecidable problem. Explain why it is considered an undecidable problem."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.17 Homework \n",
    "Your homework for Algorithmic Efficiency is pretty simple.\n",
    "1. Use the 1st code below and graph it (Desmos, TI Inpire Cas, e.t.c), change the x value only! (Plot 5 Points Minimum)\n",
    "2. Label the number of loops done as x and the time (microseconds) to find the index as y\n",
    "3. Connect the points \n",
    "4. Do the same thing with the 2nd code\n",
    "5. Compare the two graphs and explain which one of the two is more efficient and why (min. 2 sentences)\n",
    "6. Insert images of the graph either in your blog or on review ticket"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "def linear_search(lst, x):\n",
    "    start_time = time.perf_counter_ns() # records time (nanoseconds)\n",
    "    for i in range(len(lst)): # loops through the entire list \n",
    "\n",
    "        if lst[i] == x: # until the x value we are looking for is found\n",
    "            end_time = time.perf_counter_ns() # records time again\n",
    "            total_time = (end_time - start_time) // 1000 # subtracts last recorded time and first recorded time\n",
    "            print(\"Found element after {} loops in {} microseconds\".format(i+1, total_time)) # prints the results\n",
    "            return print(\"Your number was found at\", i)\n",
    "            \n",
    "    end_time = time.perf_counter_ns() # records the time again\n",
    "    total_time = (end_time - start_time) // 1000 # subtracts last recorded time and first recorded time\n",
    "    print(\"Element not found after {} loops in {} microseconds\".format(len(lst), total_time)) # prints the results\n",
    "    return \"Your number wasn't found :(\"\n",
    "\n",
    "\n",
    "lst = list(range(1, 10001)) # list with numbers 1-10000\n",
    "\n",
    "x = 5000 # replace with an integer between 1 and 10000 (I suggest big numbers like 500, 2000, so on)\n",
    "\n",
    "linear_search(lst, x) # runs procedure"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time \n",
    "\n",
    "def binary_search(lt, x):\n",
    "    start_time = time.perf_counter_ns() # starts timer\n",
    "    low = 0 # sets the lower side \n",
    "    mid = 0 # sets mid value\n",
    "    high = len(lt) -1 # sets the higher side\n",
    "    num_loops = 0 # number of loops the search undergoes to find the x value\n",
    "\n",
    "    while low<=high: # Loop ran until mid is reached\n",
    "        num_loops += 1 # adds one loop each time process is repeated\n",
    "        mid = (low + high) // 2 # takes the lowest and highest possible numbers and divides by 2 and rounds to closest whole #\n",
    "\n",
    "        if lt[mid] == x:\n",
    "            end_time = time.perf_counter_ns() # records time\n",
    "            total_time = (end_time - start_time) // 1000 # time in microseconds\n",
    "            print(\"Element found after {} loops in {} microseconds\".format(num_loops, total_time)) # prints the results\n",
    "            return mid # returns the index value\n",
    "\n",
    "        elif lt[mid] > x: # if mid was higher than x value, then sets new highest value as mid -1 \n",
    "            high = mid -1 \n",
    "\n",
    "        elif lt[mid] < x:\n",
    "            low = mid + 1 # if mid was lower than x, sets the new low as mid + 1\n",
    "            \n",
    "    end_time = time.perf_counter_ns()\n",
    "    total_time = (end_time - start_time) // 1000 \n",
    "    print(\"Element not found after {} loops in {} microseconds\".format(num_loops, total_time)) # prints the results\n",
    "    return \"Your number wasn't found :(\"\n",
    "\n",
    "\n",
    "lt = list(range(1, 10001)) # list with numbers 1-10000\n",
    "\n",
    "x = 149 # replace with an integer between 1 and 10000 (I suggest big numbers like 500, 2000, so on)\n",
    "\n",
    "binary_search(lt, x) # runs procedure"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.18 Homework:\n",
    "\n",
    "1. Use the Jupyter notebook to write an algorithm that solves a decidable problem. You can use math or whatever else you would like to do.\n",
    "2. Write code to get the computer to run forever. Check [this example](https://mmaxwu.github.io/Tri2-GroupFastpages/lesson#An-Example-of-a-Forever-Running-Code) if you need help, but please come up with your own idea.\n",
    "\n",
    "##### Homeworks, hacks, and classwork(filled in blanks) for both 3.17 and 3.18 are due on Thursday at 9:00 pm. -0.1 points for each day late."
   ]
  }
 ],
 "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.8.10 (default, Jun 22 2022, 20:18:18) \n[GCC 9.4.0]"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}