{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521__MID_CP",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "e45ed80f-053a-4a5d-b096-b22226b6b0b3"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5fe40dad-eeb9-4363-d80b-824c4a862d64"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Key problem: human vs rational; thought vs behavior\n",
        "\n",
        "Four genres of AI research: \n",
        "\n",
        "a. Acting humanly - Turing test approach. To do the test the computer should be capable of: natural language processing, knowledge representation, automated reasoning, machine learning. Total turing test should also **interact** with the world, which additionally requires the following: computer vision, robotics. \n",
        "\n",
        "b.  Thinking humanly- Cognitive modeling. Learn about human thought through: introspection, brain imaging, psychological experiments. \n",
        "\n",
        "c. Thinking rationally - laws of thought; Syllogism by Aristotle; To reason logically. \n",
        "\n",
        "d. acting rationally - rational agent approach. This is the standard model. A **rational agent** is an agent which acts in an attempt to achive best outcome. If uncertainty is involved, it will try to achieve the expected best outcome. Advantages: more general than \"think rationally approach\" and more amenable to scientific computation. \n",
        "\n",
        "Value alignment problem: achieving the alignment between what we truly want and the actual object function we supplied into the model. \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Argument for disability: A statement like 'A machine can never do X' \n",
        "\n",
        "Turing test: measure intelligence by performance on some open-ended task\n",
        "\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" \n",
        "27.2.1 Chinese room\n",
        "\n",
        "27.2.2 Do machine have consciousness and does it matter?  \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" **Agent function**: maps a percept sequence to actions. An **agent program** is the implementation of agent function. \n",
        "\n",
        "**Difference**: Agent function is an abstract mathematical concept, agent program it the concrete realization residing in a system.  \"\"\"\n",
        "chapter2_2 = \"\"\" **Performance measure**: Evaluates how well the agent is performing according to preferences and desires set by people\n",
        "\n",
        "**Rational agent**: The agent should choose the action which could maximize its performance measure, based on its percept sequence up to date and the prior knowledge it has, for any given percept sequence. \n",
        "\n",
        "Rationality $\\\\neq$ omniscience, rationality $\\\\neq$ perfection. Rational agent maximizes *expected* performance, perfect agent maximizes *actual* performance. \n",
        "\n",
        "**Information gathering**: do something to change future percepts, like look both sides before crossing a street. \n",
        "\n",
        "**Autonomy**: the agent could do self-correction through learning and percepts, rather than heavily relying on prior knowledge.   \"\"\"\n",
        "chapter2_3 = \"\"\" How to define task environments: Fully or partially observable or unobservable, single or multi-agent, deterministic or not, epsodic or sequential, static or dynamic, discrete or continuous, known or unknown. \n",
        "\n",
        "**Episodic**: the process is divided into atomic episodes. In each episode the agent makes a percept and takes an action. The action in current episode will not depend on actions taken in previous ones, nor will it influence future decisions. For sequential case, current decision affect future conditions. \n",
        "\n",
        "**Dynamic**: the environment can change while the agent consider what action to take. **Semidynamic**: The environment does not change with time but the agent's performance measure does. \n",
        "\n",
        "**Known vs unknown**: whether the agent's state of knowledge about how the environment works \"\"\"\n",
        "chapter2_4 = \"\"\" agent = architecture + program \n",
        "\n",
        "**architecture**: the device or hardware with some sensors or actuators\n",
        "\n",
        "Four basic **agent programs**:\n",
        "\n",
        "a. simple reflex agents: Action is solely based on current percept; It will usually fail in partially observable environment. \n",
        "\n",
        "b. Model-based reflex agents: The agent maintains an **internal state** depending on percept history. To update the internal state, we need: the world's **transition model** and the agent's **sensor model** (how the changes in world is reflected in the percept)\n",
        "\n",
        "c. Goal-based agents: Add in goal information (on the basis of model-based agent) \n",
        "\n",
        "d. Utility-based agents: Uses utility function to measure how well the agent is approaching its goal. Utility function provides a way for tradeoff of conflicting goals. \n",
        "\n",
        "**Learning agent**: Learning element (make improvements) + performance element (evaluates how well it is doing, select actions) + critic (provides feedback) + problem generator (suggest exploratory advice for more long-term benefits)\n",
        "\n",
        "its **Mechanism**: learning element receives feedback from **critic** and modifies performance element to have better performance\n",
        "\n",
        "Any type of agent above could be built as a learning agent. Learning agent could operate in unknown environments.  \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive the environment through sensors and act upon it through actuators\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1393
        },
        "cellView": "form",
        "outputId": "41f36bb3-b787-4fcf-f8b2-5232f6825eed"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Key problem: human vs rational; thought vs behavior\n\nFour genres of AI research: \n\na. Acting humanly - Turing test approach. To do the test the computer should be capable of: natural language processing, knowledge representation, automated reasoning, machine learning. Total turing test should also **interact** with the world, which additionally requires the following: computer vision, robotics. \n\nb.  Thinking humanly- Cognitive modeling. Learn about human thought through: introspection, brain imaging, psychological experiments. \n\nc. Thinking rationally - laws of thought; Syllogism by Aristotle; To reason logically. \n\nd. acting rationally - rational agent approach. This is the standard model. A **rational agent** is an agent which acts in an attempt to achive best outcome. If uncertainty is involved, it will try to achieve the expected best outcome. Advantages: more general than \"think rationally approach\" and more amenable to scientific computation. \n\nValue alignment problem: achieving the alignment between what we truly want and the actual object function we supplied into the model. \n\n## AIMA Chapter 27.1 The Limits of AI\n Argument for disability: A statement like 'A machine can never do X' \n\nTuring test: measure intelligence by performance on some open-ended task\n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n \n27.2.1 Chinese room\n\n27.2.2 Do machine have consciousness and does it matter?  \n\n## AIMA 2.1 Agents and Environments\n **Agent function**: maps a percept sequence to actions. An **agent program** is the implementation of agent function. \n\n**Difference**: Agent function is an abstract mathematical concept, agent program it the concrete realization residing in a system.  \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n **Performance measure**: Evaluates how well the agent is performing according to preferences and desires set by people\n\n**Rational agent**: The agent should choose the action which could maximize its performance measure, based on its percept sequence up to date and the prior knowledge it has, for any given percept sequence. \n\nRationality $\\neq$ omniscience, rationality $\\neq$ perfection. Rational agent maximizes *expected* performance, perfect agent maximizes *actual* performance. \n\n**Information gathering**: do something to change future percepts, like look both sides before crossing a street. \n\n**Autonomy**: the agent could do self-correction through learning and percepts, rather than heavily relying on prior knowledge.   \n\n## AIMA 2.3 The Nature of Environments\n How to define task environments: Fully or partially observable or unobservable, single or multi-agent, deterministic or not, epsodic or sequential, static or dynamic, discrete or continuous, known or unknown. \n\n**Episodic**: the process is divided into atomic episodes. In each episode the agent makes a percept and takes an action. The action in current episode will not depend on actions taken in previous ones, nor will it influence future decisions. For sequential case, current decision affect future conditions. \n\n**Dynamic**: the environment can change while the agent consider what action to take. **Semidynamic**: The environment does not change with time but the agent's performance measure does. \n\n**Known vs unknown**: whether the agent's state of knowledge about how the environment works \n\n## AIMA 2.4 The Structure of Agents\n agent = architecture + program \n\n**architecture**: the device or hardware with some sensors or actuators\n\nFour basic **agent programs**:\n\na. simple reflex agents: Action is solely based on current percept; It will usually fail in partially observable environment. \n\nb. Model-based reflex agents: The agent maintains an **internal state** depending on percept history. To update the internal state, we need: the world's **transition model** and the agent's **sensor model** (how the changes in world is reflected in the percept)\n\nc. Goal-based agents: Add in goal information (on the basis of model-based agent) \n\nd. Utility-based agents: Uses utility function to measure how well the agent is approaching its goal. Utility function provides a way for tradeoff of conflicting goals. \n\n**Learning agent**: Learning element (make improvements) + performance element (evaluates how well it is doing, select actions) + critic (provides feedback) + problem generator (suggest exploratory advice for more long-term benefits)\n\nits **Mechanism**: learning element receives feedback from **critic** and modifies performance element to have better performance\n\nAny type of agent above could be built as a learning agent. Learning agent could operate in unknown environments.  \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive the environment through sensors and act upon it through actuators\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = r\"\"\" \n",
        "- Python is **strongly and dynamically** typed. Strong typing means that variables do have types and their types matter when performing operations upon them. Dynamic typing means the type of a variable could be changeda at run time.\n",
        "\n",
        "- Remember power in Python is star-star\n",
        "\n",
        "- Strings\n",
        "  - Concatenate: use + \n",
        "  - No need to escape special characters: r'\\\\n' \n",
        "  - Immutable\n",
        "  - Format: %s -> string, %d -> decimal (integer) eg: print('%s=%d'%('Harry', 3)) gives 'Harry=3' \n",
        "  - a = string1, b = a, then modify a, result: a and b differnet (deep copy)\n",
        "  - Cases: s.upper() converts to upper case, s.isupper() checks if all upper case, s.capitalize() to capitalized form\n",
        "  - s.split(c), c.join(list of strings), s.strip(c) remove trailing characters c \n",
        "- list\n",
        "  - a = [1,2,3], b = a, modify a, b modified as well\n",
        "  - b = a[:] produces a (shallow)copy. If a contains only primitive-typed elements, a deep copy will be created for b; if there is objects or structs, only a reference to each single object will be returned to b (that's why it's shallow) \n",
        "  - operations: append(e), insert(idx, e), index(e) (1st one), count(e), remove(e) (1st one from left), reverse() (reverse in place), sort(some_funct) (in-place). Usage: l.operation() \n",
        "  - l = sorted(l), returns a sorted copy \n",
        "- Dictionary \n",
        "  - from collections import Counter, Counter is a defaultdict, i.e. no error on invalid keys \n",
        "- Functions \n",
        "  - No function overloading. Functions cannot have the same name, even if with different parameters \n",
        "  - Multiple return values: a tuple\n",
        "  - Keyword arguments: Must be after all other arguments. myfunc(2, b=1, c=3) correct, myfunc(b=1, c=3, 2) syntax error \n",
        "  - *args: Accept a variable number of non-keyword arguments into the function. eg: l = ['a','b','c'], print_func(*l) => ('a', 'b', 'c')\n",
        "  - **kwargs: Accept a variable number of keyword arguments. e.g: kwargs should be dict. d={'a':1, 'b'=2}, print_func(**d) \n",
        "  - python functions are first-class objects: Could be dynamically created, destroyed, passed to a function, returned as a value, and have all rights as other vars in the language\n",
        "- Scope\n",
        "  - Dynamic scope: Intepreter sees the most recent value of variables\n",
        "- Class \n",
        "  - redefinition of methods: Redefine methods using the same name in subclass\n",
        "  - SuperClassName.methodName(self, parameters) == super().methodName(parameters) (for single inheritance)\n",
        "  - Operator overloading achieved using magic methods\n",
        "  - Magic methods: \\__str__(self): called when print an object, \\__len__: what len(object) will return, \\__copy__: how to copy an object, \\__cmp__: how == works, \\__add__: how + works on objects, \\__neg__: how unary negation works\n",
        "  - Duck typing: Checks for available methods. eg: Could call len(obj) for any class having a __len__ method. \n",
        "- Iterator \n",
        "  - Objects (class) with a __iter__ magic method are iterable\n",
        "  - Iterators are objects with a __next__ method. k=[1,2,3], i=iter(k), could call i.next() or next(i) or i.__next__() (equivalently). Returns StopIteration exception upon ending. No hasNext method!\n",
        "  - To be iterable: have __iter__, and returns an iterator object; to become iterator: have __next__ that throws StopIteration when done\n",
        "  - More memory-efficient than lists\n",
        "- Generator \n",
        "  - Function with 'yield' returns a generator. Basically is an iterator. \n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1049
        },
        "outputId": "187868f5-1d19-41a0-d0f5-4924166766d4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n \n- Python is **strongly and dynamically** typed. Strong typing means that variables do have types and their types matter when performing operations upon them. Dynamic typing means the type of a variable could be changeda at run time.\n\n- Remember power in Python is star-star\n\n- Strings\n  - Concatenate: use + \n  - No need to escape special characters: r'\\\\n' \n  - Immutable\n  - Format: %s -> string, %d -> decimal (integer) eg: print('%s=%d'%('Harry', 3)) gives 'Harry=3' \n  - a = string1, b = a, then modify a, result: a and b differnet (deep copy)\n  - Cases: s.upper() converts to upper case, s.isupper() checks if all upper case, s.capitalize() to capitalized form\n  - s.split(c), c.join(list of strings), s.strip(c) remove trailing characters c \n- list\n  - a = [1,2,3], b = a, modify a, b modified as well\n  - b = a[:] produces a (shallow)copy. If a contains only primitive-typed elements, a deep copy will be created for b; if there is objects or structs, only a reference to each single object will be returned to b (that's why it's shallow) \n  - operations: append(e), insert(idx, e), index(e) (1st one), count(e), remove(e) (1st one from left), reverse() (reverse in place), sort(some_funct) (in-place). Usage: l.operation() \n  - l = sorted(l), returns a sorted copy \n- Dictionary \n  - from collections import Counter, Counter is a defaultdict, i.e. no error on invalid keys \n- Functions \n  - No function overloading. Functions cannot have the same name, even if with different parameters \n  - Multiple return values: a tuple\n  - Keyword arguments: Must be after all other arguments. myfunc(2, b=1, c=3) correct, myfunc(b=1, c=3, 2) syntax error \n  - *args: Accept a variable number of non-keyword arguments into the function. eg: l = ['a','b','c'], print_func(*l) => ('a', 'b', 'c')\n  - **kwargs: Accept a variable number of keyword arguments. e.g: kwargs should be dict. d={'a':1, 'b'=2}, print_func(**d) \n  - python functions are first-class objects: Could be dynamically created, destroyed, passed to a function, returned as a value, and have all rights as other vars in the language\n- Scope\n  - Dynamic scope: Intepreter sees the most recent value of variables\n- Class \n  - redefinition of methods: Redefine methods using the same name in subclass\n  - SuperClassName.methodName(self, parameters) == super().methodName(parameters) (for single inheritance)\n  - Operator overloading achieved using magic methods\n  - Magic methods: \\__str__(self): called when print an object, \\__len__: what len(object) will return, \\__copy__: how to copy an object, \\__cmp__: how == works, \\__add__: how + works on objects, \\__neg__: how unary negation works\n  - Duck typing: Checks for available methods. eg: Could call len(obj) for any class having a __len__ method. \n- Iterator \n  - Objects (class) with a __iter__ magic method are iterable\n  - Iterators are objects with a __next__ method. k=[1,2,3], i=iter(k), could call i.next() or next(i) or i.__next__() (equivalently). Returns StopIteration exception upon ending. No hasNext method!\n  - To be iterable: have __iter__, and returns an iterator object; to become iterator: have __next__ that throws StopIteration when done\n  - More memory-efficient than lists\n- Generator \n  - Function with 'yield' returns a generator. Basically is an iterator. \n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" **problem solving agent** vs **planning agent**: Problem solving agent uses atomic representation of states, the internal structure of state is invisible; planning agent uses factored or structured representations of states. \n",
        "\n",
        "Search problem: \n",
        "\n",
        "a. state & state space b. initial space c. goal state d. actions e. transition model f. action cost function  \"\"\"\n",
        "chapter3_2 = \"\"\" Standardized problems vs real-world problems \"\"\"\n",
        "chapter3_3 = \"\"\" **frontier**: nodes that have been reached but not expanded; Outside frontier: not reached yet; Inside frontier: already expanded\n",
        "\n",
        "Note that **reached** is not equal to **expanded** (i.e. dequeued from the frontier)\n",
        "\n",
        "**redundant path**: eg. cycles. Can use extra memory to record states reached, to avoid forming redundant paths\n",
        "\n",
        "Evaluate search algo: *d*: depth of optimal path to a solution, *m*: maximum depth in any path, *b*: branching factor\n",
        "\n",
        "General search strategy: **Best-first Search** \n",
        "\n",
        "- Uses priority queue ordered by some metric *f*\n",
        "- Need space to store visited nodes, and corresponding f value\n",
        "- Graph search. Need to check each reached node. If reached the first time, or a better f value if found, node should be updated and enqueued. \n",
        "- Late goal test \"\"\"\n",
        "chapter3_4 = \"\"\" **Informed vs uninformed**: Uninformed search has no knowledge about its gap to reach a goal, while informed one has \n",
        "\n",
        "**Early goal test vs late goal test**: Early goal test checks if it's goal upon reaching (before enqueue). Late goal test checks that after dequeue\n",
        "\n",
        "**Breadth First Search**:  \n",
        "\n",
        "- Data structure: Queue, FIFO\n",
        "- Always finds a solution with min #actions (hops)\n",
        "- Needs to record states we have visited\n",
        "- Graph search -> faster while memory consuming\n",
        "- Pop one element each time; Store it into \"visited\" if not already in (Graph search) \n",
        "- Do early goal test\n",
        "- Optimal for problems where all actions have equal cost; Always complete. \n",
        "\n",
        "**Uniform-cost search** (Dijkstra)\n",
        "\n",
        "- Best-first search with f = path cost\n",
        "- late goal test & graph search\n",
        "- Time complexity: $C^*$ is cost of optimal solution, $\\epsilon$ lower bound for cost of each action; Could be MUCH larger than $O(b^d)$\n",
        "\n",
        "- Complete and optimal\n",
        "\n",
        "**Depth-first search**\n",
        "\n",
        "- best-first search with f = -depth, early goal test\n",
        "- often Tree search, no redundancy check\n",
        "- Not optimal, incomplete if certain path is infinite\n",
        "\n",
        "- Memory efficient than BFS, $O(bm)$. Store all successors when expanding each node (gives b), and do this for each node along path (multiplies by m). \n",
        "- Use **backtrack**: generates only one successor expanding each node. (DFS generates all successors). Memory: **$O(m)$**. \n",
        "\n",
        "**Depth-limited Search**\n",
        "\n",
        "- $l$: depth limit, a good value should be picked\n",
        "- not complete, not optimal\n",
        "- Uses stack, LIFO\n",
        "- late goal check & Tree search\n",
        "- Diameter: Any node can be reached from any other node in *diameter* steps\n",
        "\n",
        "**Iterative Deepening Search**\n",
        "\n",
        "- Do depth-limited search for $l=0,1,...,$ until either a solution is found or a failure is reported\n",
        "- Optimal if actions have equal costs, and complete\n",
        "- Memory complexity: $O(bd)$ if there exists solution, $O(bm)$ if there is not. \n",
        "- Time complexity: $O(b^d)$ if there is a solution, $O(b^m)$ if there isn't.\n",
        "- We should use iterative deepening search when memory is limited and depth of solution is unknown. \n",
        "- Tree like search, no need to store \"visitation\" information\n",
        "\n",
        "**Bidirectional Search**\n",
        "\n",
        "- Start from root and goal simultaneously\n",
        "- Keep two frontier queues, and two \"visited\" sets\n",
        "- Motivation: $b^{d/2}+b^{d/2}<<b^d$\n",
        "- Case: bidirectional best-first search \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",\n",
        "\"informed search\": \"Search problem in which an estimated distance to the goal is available\",\n",
        "\"completeness\": \"A complete algo is guaranteed to find a solution if there exists one, and correctly report failure otherwise.\",\n",
        "\"optimality\": \"An optimal algo finds a solution with lowest total cost before it finds any other solution.\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1545
        },
        "outputId": "5627a3eb-3563-4e0f-8c19-786262064f9a"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n **problem solving agent** vs **planning agent**: Problem solving agent uses atomic representation of states, the internal structure of state is invisible; planning agent uses factored or structured representations of states. \n\nSearch problem: \n\na. state & state space b. initial space c. goal state d. actions e. transition model f. action cost function  \n\n## AIMA Chapter 3.2 Example Problems\n Standardized problems vs real-world problems \n\n## AIMA Chapter 3.3 Search Algorithms\n **frontier**: nodes that have been reached but not expanded; Outside frontier: not reached yet; Inside frontier: already expanded\n\nNote that **reached** is not equal to **expanded** (i.e. dequeued from the frontier)\n\n**redundant path**: eg. cycles. Can use extra memory to record states reached, to avoid forming redundant paths\n\nEvaluate search algo: *d*: depth of optimal path to a solution, *m*: maximum depth in any path, *b*: branching factor\n\nGeneral search strategy: **Best-first Search** \n\n- Uses priority queue ordered by some metric *f*\n- Need space to store visited nodes, and corresponding f value\n- Graph search. Need to check each reached node. If reached the first time, or a better f value if found, node should be updated and enqueued. \n- Late goal test \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n **Informed vs uninformed**: Uninformed search has no knowledge about its gap to reach a goal, while informed one has \n\n**Early goal test vs late goal test**: Early goal test checks if it's goal upon reaching (before enqueue). Late goal test checks that after dequeue\n\n**Breadth First Search**:  \n\n- Data structure: Queue, FIFO\n- Always finds a solution with min #actions (hops)\n- Needs to record states we have visited\n- Graph search -> faster while memory consuming\n- Pop one element each time; Store it into \"visited\" if not already in (Graph search) \n- Do early goal test\n- Optimal for problems where all actions have equal cost; Always complete. \n\n**Uniform-cost search** (Dijkstra)\n\n- Best-first search with f = path cost\n- late goal test & graph search\n- Time complexity: $C^*$ is cost of optimal solution, $\\epsilon$ lower bound for cost of each action; Could be MUCH larger than $O(b^d)$\n\n- Complete and optimal\n\n**Depth-first search**\n\n- best-first search with f = -depth, early goal test\n- often Tree search, no redundancy check\n- Not optimal, incomplete if certain path is infinite\n\n- Memory efficient than BFS, $O(bm)$. Store all successors when expanding each node (gives b), and do this for each node along path (multiplies by m). \n- Use **backtrack**: generates only one successor expanding each node. (DFS generates all successors). Memory: **$O(m)$**. \n\n**Depth-limited Search**\n\n- $l$: depth limit, a good value should be picked\n- not complete, not optimal\n- Uses stack, LIFO\n- late goal check & Tree search\n- Diameter: Any node can be reached from any other node in *diameter* steps\n\n**Iterative Deepening Search**\n\n- Do depth-limited search for $l=0,1,...,$ until either a solution is found or a failure is reported\n- Optimal if actions have equal costs, and complete\n- Memory complexity: $O(bd)$ if there exists solution, $O(bm)$ if there is not. \n- Time complexity: $O(b^d)$ if there is a solution, $O(b^m)$ if there isn't.\n- We should use iterative deepening search when memory is limited and depth of solution is unknown. \n- Tree like search, no need to store \"visitation\" information\n\n**Bidirectional Search**\n\n- Start from root and goal simultaneously\n- Keep two frontier queues, and two \"visited\" sets\n- Motivation: $b^{d/2}+b^{d/2}<<b^d$\n- Case: bidirectional best-first search \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Informed search** - Search problem in which an estimated distance to the goal is available\n* **Completeness** - A complete algo is guaranteed to find a solution if there exists one, and correctly report failure otherwise.\n* **Optimality** - An optimal algo finds a solution with lowest total cost before it finds any other solution.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" **informed search**: Search problem which has access to domain-specific knowledge, $h(n)$ heuristics. \n",
        "\n",
        "$h(n)$: estimated lowest cost of reaching the goal from the current node n\n",
        "\n",
        "**Greedy Best-First Search**\n",
        "\n",
        "- Best-first search: $f(n)=h(n)$\n",
        "- Not optimal. Complete in finite space, not in infinite space. \n",
        "- Worst case time & space complexity: $O(|V|)$, where $V$ is the number of nodes.  \n",
        "\n",
        "**A* Search**\n",
        "\n",
        "- Best-first search with $f(n)=g(n)+h(n)$\n",
        "- late goal test\n",
        "- Time complexity: $O(b^d)$, branching factor b, shortest depth to a solution d\n",
        "- Complete; Optimal if $h(n)$ is admissible; Optimally efficient (don't understand, Section 3.5.3)\n",
        "- **Admissibility**: If $h(n)$ never overestimates the cost to reach a goal, then it is *admissible*.\n",
        "- **Consistency**: A heuristic $h(n)$ is consistent if for every node $n$ and its successor $n'$ through action $a$, we have $h(n)\\leq h(n')+c(n,a,n')$\n",
        "- Consistent $\\subset$ Admissible\n",
        "- If $h(n)$ is consistent, the first time we reach a state, it is on optimal path. Can do **early goal check**, there is no need for \"visitation\" set or its update\n",
        "- Contour: A* search concentric ovals, uniform-cost search concentric circles. \n",
        "- $f(n)$ is **monotonic** if and only if $h(n)$ is consistent.\n",
        "- A* search expands all nodes with $f(n)<C^*$, $C^*$ is the cost of optimal path. These are **surely expanded nodes**. A* might expand some of the nodes with $f(n)=C^*$ (on contour).\n",
        "No nodes with $f(n)>C^*$ gets expanded. Expansion: popped from queue\n",
        "- **Optimally efficient**: Any algo that extends search path from initial state and uses the same heuristic must expand all nodes that are surely expanded by A* \n",
        "\n",
        "**Satisficing search**\n",
        "\n",
        "Adopt an **inadmissible** heuristic to find a suboptimal but acceptable solution, expanding fewer nodes. \n",
        "\n",
        "**Weighted A* search**: $f(n)=g(n)+W \\\\times h(n),W>1$. \n",
        "\n",
        "**Bounded sub-optimal search:** find a solution with cost at most $W \\\\times C^*$. \n",
        "\n",
        "**Bounded cost search**: find a solution with cost at most $C'$ (some constant)\n",
        "\n",
        "**Speedy search:** find a solution as quickly as possible\"\"\"\n",
        "chapter3_6 = \"\"\" **Effective branching factor $b^*$**: If A* search generates $N$ nodes, and solution has depth $d$, then $b^*$ is the branching factor of a uniform tree of depth $d$ to accommodate $N+1$ nodes. $N+1=1+b^*+...+(b^*)^d$ \n",
        "\n",
        "**Usage of b***: measure #nodes generated => performance of A* search\n",
        "\n",
        "**Dominate:** if both $h_1(n),h_2(n)$ are admissible, $h_1(n)\\geq h_2(n)$ for any n, then *h_1 dominates h_2*.  \n",
        "\n",
        "**Generate h(n)**: Find an optimal solution to a relaxed problem. It will be a *consistent* heuristic to original problem. \n",
        "\n",
        "**pattern database**: stores exact solutions for subproblems, and combine them to form a solution for whole problem \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" **Effective branching factor $b^*$**: If A* search generates $N$ nodes, and solution has depth $d$, then $b^*$ is the branching factor of a uniform tree of depth $d$ to accommodate $N+1$ nodes. $N+1=1+b^*+...+(b^*)^d$ \n",
        "\n",
        "**Usage of b***: measure #nodes generated => performance of A* search\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1028
        },
        "outputId": "bf286322-3414-46e4-ce40-2032541880da"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n **informed search**: Search problem which has access to domain-specific knowledge, $h(n)$ heuristics. \n\n$h(n)$: estimated lowest cost of reaching the goal from the current node n\n\n**Greedy Best-First Search**\n\n- Best-first search: $f(n)=h(n)$\n- Not optimal. Complete in finite space, not in infinite space. \n- Worst case time & space complexity: $O(|V|)$, where $V$ is the number of nodes.  \n\n**A* Search**\n\n- Best-first search with $f(n)=g(n)+h(n)$\n- late goal test\n- Time complexity: $O(b^d)$, branching factor b, shortest depth to a solution d\n- Complete; Optimal if $h(n)$ is admissible; Optimally efficient (don't understand, Section 3.5.3)\n- **Admissibility**: If $h(n)$ never overestimates the cost to reach a goal, then it is *admissible*.\n- **Consistency**: A heuristic $h(n)$ is consistent if for every node $n$ and its successor $n'$ through action $a$, we have $h(n)\\leq h(n')+c(n,a,n')$\n- Consistent $\\subset$ Admissible\n- If $h(n)$ is consistent, the first time we reach a state, it is on optimal path. Can do **early goal check**, there is no need for \"visitation\" set or its update\n- Contour: A* search concentric ovals, uniform-cost search concentric circles. \n- $f(n)$ is **monotonic** if and only if $h(n)$ is consistent.\n- A* search expands all nodes with $f(n)<C^*$, $C^*$ is the cost of optimal path. These are **surely expanded nodes**. A* might expand some of the nodes with $f(n)=C^*$ (on contour).\nNo nodes with $f(n)>C^*$ gets expanded. Expansion: popped from queue\n- **Optimally efficient**: Any algo that extends search path from initial state and uses the same heuristic must expand all nodes that are surely expanded by A* \n\n**Satisficing search**\n\nAdopt an **inadmissible** heuristic to find a suboptimal but acceptable solution, expanding fewer nodes. \n\n**Weighted A* search**: $f(n)=g(n)+W \\times h(n),W>1$. \n\n**Bounded sub-optimal search:** find a solution with cost at most $W \\times C^*$. \n\n**Bounded cost search**: find a solution with cost at most $C'$ (some constant)\n\n**Speedy search:** find a solution as quickly as possible\n\n## AIMA Chapter 3.6 Heuristic Functions\n **Effective branching factor $b^*$**: If A* search generates $N$ nodes, and solution has depth $d$, then $b^*$ is the branching factor of a uniform tree of depth $d$ to accommodate $N+1$ nodes. $N+1=1+b^*+...+(b^*)^d$ \n\n**Usage of b***: measure #nodes generated => performance of A* search\n\n**Dominate:** if both $h_1(n),h_2(n)$ are admissible, $h_1(n)\\geq h_2(n)$ for any n, then *h_1 dominates h_2*.  \n\n**Generate h(n)**: Find an optimal solution to a relaxed problem. It will be a *consistent* heuristic to original problem. \n\n**pattern database**: stores exact solutions for subproblems, and combine them to form a solution for whole problem \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" **competitive environment**: >1 agents have conflicting goals\n",
        "\n",
        "**perfect information**: fully observable\n",
        "\n",
        "**How to find optimal strategy**: calculate *minimax* value for each node, assuming both players play optimally \"\"\"\n",
        "chapter5_2 = \"\"\" **Minimax search:** dept-first search\n",
        "\n",
        "Aims at solving perfect information, zero-sum games\n",
        "\n",
        "**Extend to n players**: \n",
        "\n",
        "- Use a utility vector for each node, recording value from each player's viewpoint\n",
        "- Players could form alliance\n",
        "\n",
        "**$ \\\\alpha-\\\\beta$ pruning**: \n",
        "\n",
        "$ \\\\alpha $: The highest value we have found for MAX player for any choice point along the path. MAX can achieve at least $\\\\alpha$. \n",
        "\n",
        "$ \\\\beta$: highest -> lowest. MIN can achieve at most $\\\\beta$ search the game tree.\n",
        "\n",
        "- The order of exhausting nodes MATTERS!  \n",
        "\n",
        "The change of $\\\\alpha,\\\\beta$ during search process: \n",
        "- Node can inherit values of alpha and beta from parent\n",
        "- When MAX player is in charge, only alpha get updated, while only beta gets updated when MIN's in charge\n",
        "- When a pruning message is issued, the alpha/beta will not be updated. The function will return directly \"\"\"\n",
        "chapter5_3 = r\"\"\" - Heuristic Alpha-Beta Tree Search\n",
        "\n",
        "- Utility -> uses evaluation function to estimate utility; terminal state -> cut-off test\n",
        "\n",
        "- $H-MINIMAX(s,d)= \\left\\{ \\begin{aligned} EVAL(s,MAX), \\ if\\ IS-CUTOFF(s,d)\\\\max_a H-MINMAX(RESULT(s,a),d+1),\\ if\\ TO-MOVE(s)=MAX \\\\ min_a H-MINMAX(RESULT(s,a),d+1),if\\ TO-MOVE(s)=MIN \\end{aligned}\\right.$\n",
        "\n",
        "- $EVAL(s,player)=Utility(s,p)$ for terminal states; For non-terminal states, $Utility(loss,player)\\leq EVAL(s,player) \\leq Utility(win,player)$\n",
        "\n",
        "- **features**: describes the chances of winning\n",
        "\n",
        "  **weighted linear function**: the evaluation EVAL could be a linear weighted sum of features. Underlying assumption: features are independent of each other\n",
        "\n",
        "- **quiescent search**: evaluation functions are only applied to non pending moves, i.e. quiescent move \n",
        "\n",
        "- **horizon effect**: When the opponent's certain move will cause series and inevitable damage, the player can temporarily delay it by some tricks. \n",
        "\n",
        "- **singular extensions**: moves that are obviously better than all others at certain positions. \n",
        "\n",
        "- **forward pruning**: prunes away nodes that seem bad according to some evaluation metric. However, it is possible that these are actually good moves. \n",
        "\n",
        "- **Beam search**: for each ply, consider only a beam of n best moves and none of the others. \n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" - Calculate **expectiminimax value**\n",
        "\n",
        "- The evaluation function must return a linear combination of the probability of winning \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = r\"\"\" Problem formulation: \n",
        "- probability of being in state s: $P(s)$, transiting to state $s'$ from state s taking action a: $P(s'|s,a)$\n",
        "- Agent preference: utility function $U(s)$ of a state s\n",
        "- $P(result(a)=s')=\\sum_s P(s'|s,a)$\n",
        "- Expected utility: $EU(a)=\\sum_{s'}P(result(a)=s')U(s')$ \n",
        "- Maximum Expected Utility (MEU): $action = argmax_a EU(a)$\n",
        " \"\"\"\n",
        "chapter16_2 = r\"\"\" A lottery L, getting different results with corresponding probs: [p1, R1; p2, R2; ...]\n",
        "Any reasonable preference relation must obey: \n",
        "- Oderability: Cannot refuse making decisions, exactly one of $A\\succ B$ or $B\\succ A$ or $A\\sim B$ holds. \n",
        "- Transitivity: $A\\succ B \\wedge B\\succ C \\Rightarrow A\\succ C$\n",
        "- Continuity: $A\\succ B \\succ C \\Rightarrow \\exists p, [p, A; 1-P, C] \\sim B$. The agent is indifferent between getting B for sure, or getting A/C with probabilities\n",
        "- Substitutability: $A\\sim B \\Rightarrow [p,A;1-p,C] \\sim [p,B;1-p,C]$. Also holds if we replace $\\sim$ by $\\succ$. \n",
        "- Monotonicity: $A\\succ B \\Rightarrow (p>q \\Leftrightarrow [p,A;1-p,B] \\succ [q, A;1-q,B]$)\n",
        "- Decomposability: $[p,A;1-p,[q,B;(1-q),C]] \\sim [p,A;(1-p)q,B;(1-p)(1-q),C]$\n",
        "\n",
        "Theorem: A utility function exists for any rational agent satisfying the above conditions, that is: \n",
        "\n",
        "$U(A)>U(B) \\Leftrightarrow A \\succ B$ and $U(A)=U(B) \\Leftrightarrow A \\sim B$ \n",
        "\n",
        "**Expected utility of a lottery:** $U([p_1,S_1;p_2,S_2;...,p_k,S_k])=\\sum_i p_i U(S_i)$\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" \n",
        "preference elicitation: To work out the users' utility function by asking them various questions\n",
        "\n",
        "Scaling utility: Best-possible prize: $U(S)=u_{\\\\top}$, worst-possible catastrophe: $U(s)=u_{\\\\bot}$ \n",
        "\n",
        "Get utility of any prize S: Ask user to choose between S and **standard lottery**: $[p,u_{\\\\top};1-p, u_{\\\\bot}]$ until user becomes indifferent between the two\n",
        "\n",
        "Micromort: One unit of risk, one in a million chance of death \n",
        "\n",
        "EMV: expected monetary value. Utility is not directly proportional to monetary value \n",
        "\n",
        "risk-averse: people tend to prefer a sure payoff less than the EMV of the gamble in the positive range\n",
        "\n",
        "risk-seeking: reversed behavior of risk-averse in negative monetary range \n",
        "\n",
        "Certainty equivalent: The amount that people would like to receive for sure rather than the uncertain gambling. eg. Receive 400 dollors, not 1/2 chance of 1000 while 1/2 chance of 0\n",
        "\n",
        "Risk-neutral: Has a linear utility-monetary curve \n",
        "\n",
        "insurance premium=EMV-certainty equivalent\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1885
        },
        "outputId": "e39e09ec-88b2-4ea2-dc22-4620c304132f"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n **competitive environment**: >1 agents have conflicting goals\n\n**perfect information**: fully observable\n\n**How to find optimal strategy**: calculate *minimax* value for each node, assuming both players play optimally \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n **Minimax search:** dept-first search\n\nAims at solving perfect information, zero-sum games\n\n**Extend to n players**: \n\n- Use a utility vector for each node, recording value from each player's viewpoint\n- Players could form alliance\n\n**$ \\alpha-\\beta$ pruning**: \n\n$ \\alpha $: The highest value we have found for MAX player for any choice point along the path. MAX can achieve at least $\\alpha$. \n\n$ \\beta$: highest -> lowest. MIN can achieve at most $\\beta$ search the game tree.\n\n- The order of exhausting nodes MATTERS!  \n\nThe change of $\\alpha,\\beta$ during search process: \n- Node can inherit values of alpha and beta from parent\n- When MAX player is in charge, only alpha get updated, while only beta gets updated when MIN's in charge\n- When a pruning message is issued, the alpha/beta will not be updated. The function will return directly \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n - Heuristic Alpha-Beta Tree Search\n\n- Utility -> uses evaluation function to estimate utility; terminal state -> cut-off test\n\n- $H-MINIMAX(s,d)= \\left\\{ \\begin{aligned} EVAL(s,MAX), \\ if\\ IS-CUTOFF(s,d)\\\\max_a H-MINMAX(RESULT(s,a),d+1),\\ if\\ TO-MOVE(s)=MAX \\\\ min_a H-MINMAX(RESULT(s,a),d+1),if\\ TO-MOVE(s)=MIN \\end{aligned}\\right.$\n\n- $EVAL(s,player)=Utility(s,p)$ for terminal states; For non-terminal states, $Utility(loss,player)\\leq EVAL(s,player) \\leq Utility(win,player)$\n\n- **features**: describes the chances of winning\n\n  **weighted linear function**: the evaluation EVAL could be a linear weighted sum of features. Underlying assumption: features are independent of each other\n\n- **quiescent search**: evaluation functions are only applied to non pending moves, i.e. quiescent move \n\n- **horizon effect**: When the opponent's certain move will cause series and inevitable damage, the player can temporarily delay it by some tricks. \n\n- **singular extensions**: moves that are obviously better than all others at certain positions. \n\n- **forward pruning**: prunes away nodes that seem bad according to some evaluation metric. However, it is possible that these are actually good moves. \n\n- **Beam search**: for each ply, consider only a beam of n best moves and none of the others. \n \n\n## AIMA Chapter 5.5 Stochastic Games\n - Calculate **expectiminimax value**\n\n- The evaluation function must return a linear combination of the probability of winning \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Problem formulation: \n- probability of being in state s: $P(s)$, transiting to state $s'$ from state s taking action a: $P(s'|s,a)$\n- Agent preference: utility function $U(s)$ of a state s\n- $P(result(a)=s')=\\sum_s P(s'|s,a)$\n- Expected utility: $EU(a)=\\sum_{s'}P(result(a)=s')U(s')$ \n- Maximum Expected Utility (MEU): $action = argmax_a EU(a)$\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n A lottery L, getting different results with corresponding probs: [p1, R1; p2, R2; ...]\nAny reasonable preference relation must obey: \n- Oderability: Cannot refuse making decisions, exactly one of $A\\succ B$ or $B\\succ A$ or $A\\sim B$ holds. \n- Transitivity: $A\\succ B \\wedge B\\succ C \\Rightarrow A\\succ C$\n- Continuity: $A\\succ B \\succ C \\Rightarrow \\exists p, [p, A; 1-P, C] \\sim B$. The agent is indifferent between getting B for sure, or getting A/C with probabilities\n- Substitutability: $A\\sim B \\Rightarrow [p,A;1-p,C] \\sim [p,B;1-p,C]$. Also holds if we replace $\\sim$ by $\\succ$. \n- Monotonicity: $A\\succ B \\Rightarrow (p>q \\Leftrightarrow [p,A;1-p,B] \\succ [q, A;1-q,B]$)\n- Decomposability: $[p,A;1-p,[q,B;(1-q),C]] \\sim [p,A;(1-p)q,B;(1-p)(1-q),C]$\n\nTheorem: A utility function exists for any rational agent satisfying the above conditions, that is: \n\n$U(A)>U(B) \\Leftrightarrow A \\succ B$ and $U(A)=U(B) \\Leftrightarrow A \\sim B$ \n\n**Expected utility of a lottery:** $U([p_1,S_1;p_2,S_2;...,p_k,S_k])=\\sum_i p_i U(S_i)$\n\n\n## AIMA Chapter 16.3 Utility Functions\n \npreference elicitation: To work out the users' utility function by asking them various questions\n\nScaling utility: Best-possible prize: $U(S)=u_{\\top}$, worst-possible catastrophe: $U(s)=u_{\\bot}$ \n\nGet utility of any prize S: Ask user to choose between S and **standard lottery**: $[p,u_{\\top};1-p, u_{\\bot}]$ until user becomes indifferent between the two\n\nMicromort: One unit of risk, one in a million chance of death \n\nEMV: expected monetary value. Utility is not directly proportional to monetary value \n\nrisk-averse: people tend to prefer a sure payoff less than the EMV of the gamble in the positive range\n\nrisk-seeking: reversed behavior of risk-averse in negative monetary range \n\nCertainty equivalent: The amount that people would like to receive for sure rather than the uncertain gambling. eg. Receive 400 dollors, not 1/2 chance of 1000 while 1/2 chance of 0\n\nRisk-neutral: Has a linear utility-monetary curve \n\ninsurance premium=EMV-certainty equivalent\n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" - **Consistent**: an assignment of variables is consistent if it does not violate any constraints. \n",
        "\n",
        "- **Complete**: every variable is assigned a value \n",
        "\n",
        "- A solution is a consistent and complete assignment.\n",
        "\n",
        "- Example formulations\n",
        "\n",
        "  - Graph coloring\n",
        "\n",
        "  - Job scheduling: **precedence** constraint: One event must happen before another has ended; disjunctive constraint: Two events must NOT have time-overlap;  \n",
        "\n",
        "  - Finite or infinite domain? Discrete or continuous domain? Unary or binary or higher order constraint (constraint hyper-graph)? \n",
        "\n",
        "  - **Global constraint**: a constraint involving an arbitrary number of variables \"\"\"\n",
        "\n",
        "chapter6_2 = \"\"\" - **\n",
        "AC-3 is used for removing inconsistency. Sometimes only AC-3 is sufficient to reach a complete solution, while in more difficult problems, search is also necessary. \n",
        "Search involves uncertainty, which means that we need to try different possibilities out, to see if each of them works. \n",
        "\n",
        "constraint propagation**: Iteratively reduce the number of legal values of certain variable according to the constraints\n",
        "\n",
        "- **Local consistency**: \n",
        "\n",
        "  - Node consistency: no unary constraint is violated\n",
        "\n",
        "  - Arc consistency: A variable $X_i$ is arc-consistent w.r.t another variable $X_j$ if for every value that $X_i$ can take, there exists some legal value in $X_j$'s domain. \n",
        "  \n",
        "  - Path-consistency: 3-consistency. A two variable set $[X_i,X_j]$ is path-consistent w.r.t a 3rd variable $X_k$ if for every valid assignment $X_i=a,X_j=b$ consistent with the binary constraint on $[X_i,X_j]$, there exists a value for $X_k$, such that the binary constraint for both $[X_i,X_k]$ and $[X_j,X_k]$ are satisfied. \n",
        "  \n",
        "  - k-consistency: For any legal assignment to a set of k-1 variables, there exists a valid assignment to the kth variable, so that no constraint is violated. \n",
        "  \n",
        "  - strongly k-consistent: k-consistent, (k-1)-consistent, ..., 1-consistent.  \n",
        "\n",
        "- Enforce arc-consistency: **AC-3**\n",
        "\n",
        "  How it works: Keep of queue of directed edges (initially all edges in the graph). Pop out an edge every time $(X_i,X_j)$, make $X_i$ arc-consistent w.r.t to $X_j$. If the domain of $X_i$ is not changed, directly proceed with the next edge. Otherwise, if its modified, add all $(X_k,X_i)$ to the queue, where k is a neighbor of i. Loop until queue becomes empty or an empty domain is found for certain variable, indicating a failure. \n",
        "\n",
        "  **Time complexity**: c binary constraints, n variables, each has domain size d, worse case: $O(cd^3)$. \n",
        "\n",
        "  Each constraint checked at most d times, check one constraint costs d^2. \n",
        "\n",
        "- **Global constraints**:\n",
        "\n",
        "  - Alldiff\n",
        "  \n",
        "  - resource constraint: total resources limited, prune away domain values which obviously goes above the limit\n",
        "  \n",
        "  - bound propagation \"\"\"\n",
        "chapter6_3 = \"\"\" - DFS + backtrack\n",
        "\n",
        "- Fix the order of variables to traverse, and backtrack w.r.t value assignments\n",
        "\n",
        "- Search strategy: \n",
        "\n",
        "  - How to choose the next variable: MRV, minimum remaining value heuristic (most-constrained or first-fail variable)\n",
        "\n",
        "  - degree heuristic: Choose the most constraining variable (has most constraints on other unassigned variables)\n",
        "\n",
        "  - least constraining value heuristic: prefers values that rule out fewest choices for neighbors\n",
        "\n",
        "- **Forward checking**: Whenever a variable X is assigned, AC-3 inference is performed to prune the domains for the neighboring variables.  Forward checking is not powerful enough in some case, since its check is not deep enough. \n",
        "\n",
        "- **Maintaining arc-consistency (MAC)**: Improvement of forward checking \n",
        "\n",
        "- chronological backtracking: revisit the nearest decision point. Better: conflict set and backjumping\n",
        "\n",
        "- Constraint learning: find a minimum subset of the conflict set that causes the problem. These variables are called \"*no good*\".  \"\"\"\n",
        "chapter6_4 = \"\"\" Local search: We initially assign a value to each variable. Then for each round, pick one element which violates constraints, and reassign its value according to min-conflict \n",
        "heuristic, i.e. change to a value with least conflicts. We do this until a solution is found, or we've reached a maximum (specified) depth and return. \"\"\"\n",
        "chapter6_5 = \"\"\" \n",
        "Key idea: Divide-and-conquer, Partition CSP into independent subproblems, solve each one and combine.  \n",
        "\n",
        "Why it is good: Significantly reduces time-complexity \n",
        "\n",
        "**Directional Arc Consistency (DAC)**: A CSP is directionally arc consistent under ordering $X_1, X_2, ..., X_n$ iff every $X_i$ is arc consistent with each $X_j$ for j>i. \n",
        "\n",
        "Any tree-structured CSP can be solved in **linear** time in the number of variables. How: \n",
        "- First form the topological sort of the constraint graph: pick any variable to be the root, then each node should appear after its parent in the tree \n",
        "- Make each node arc-consistent w.r.t its parent\n",
        "- Go through the tree starting from root, selecting value for each variable from remaining values -> No need to backtrack\n",
        "\n",
        "Reduce a CSP to tree structure: \n",
        "- Cutset conditioning \n",
        "  - Choose a subset of variables S, such that after removing S, the constraint graph becomes tree-structured. S is a **cycle cutset**. \n",
        "  - For each assignment to the variables in S that satisfy all constraints on S, we remove illegal values (inconsistent with the assignment in S) of remaining variables from domains, test if there exists \n",
        "  a solution for them. \n",
        "- Tree decomposition： Transform original constraint graph into a tree. Each node in tree may consist of multiple variables. \n",
        "  - New tree satisfies: Every variable in original problem appears in at least one node in the tree; If originally two variables have a constraint, they must appear together in tree; \n",
        "  if a variable appears in two nodes, it must appear in every node along the connecting path. \n",
        "- Tree decomposition is generally faster than cutset conditioning\n",
        "- Cutset conditioning can be executed in linear memory, while tree decomposition requries memory exponential in the tree width ww\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1758
        },
        "outputId": "0bc211d9-e85e-467e-8acd-adb685a75039"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n - **Consistent**: an assignment of variables is consistent if it does not violate any constraints. \n\n- **Complete**: every variable is assigned a value \n\n- A solution is a consistent and complete assignment.\n\n- Example formulations\n\n  - Graph coloring\n\n  - Job scheduling: **precedence** constraint: One event must happen before another has ended; disjunctive constraint: Two events must NOT have time-overlap;  \n\n  - Finite or infinite domain? Discrete or continuous domain? Unary or binary or higher order constraint (constraint hyper-graph)? \n\n  - **Global constraint**: a constraint involving an arbitrary number of variables \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n - **\nAC-3 is used for removing inconsistency. Sometimes only AC-3 is sufficient to reach a complete solution, while in more difficult problems, search is also necessary. \nSearch involves uncertainty, which means that we need to try different possibilities out, to see if each of them works. \n\nconstraint propagation**: Iteratively reduce the number of legal values of certain variable according to the constraints\n\n- **Local consistency**: \n\n  - Node consistency: no unary constraint is violated\n\n  - Arc consistency: A variable $X_i$ is arc-consistent w.r.t another variable $X_j$ if for every value that $X_i$ can take, there exists some legal value in $X_j$'s domain. \n  \n  - Path-consistency: 3-consistency. A two variable set $[X_i,X_j]$ is path-consistent w.r.t a 3rd variable $X_k$ if for every valid assignment $X_i=a,X_j=b$ consistent with the binary constraint on $[X_i,X_j]$, there exists a value for $X_k$, such that the binary constraint for both $[X_i,X_k]$ and $[X_j,X_k]$ are satisfied. \n  \n  - k-consistency: For any legal assignment to a set of k-1 variables, there exists a valid assignment to the kth variable, so that no constraint is violated. \n  \n  - strongly k-consistent: k-consistent, (k-1)-consistent, ..., 1-consistent.  \n\n- Enforce arc-consistency: **AC-3**\n\n  How it works: Keep of queue of directed edges (initially all edges in the graph). Pop out an edge every time $(X_i,X_j)$, make $X_i$ arc-consistent w.r.t to $X_j$. If the domain of $X_i$ is not changed, directly proceed with the next edge. Otherwise, if its modified, add all $(X_k,X_i)$ to the queue, where k is a neighbor of i. Loop until queue becomes empty or an empty domain is found for certain variable, indicating a failure. \n\n  **Time complexity**: c binary constraints, n variables, each has domain size d, worse case: $O(cd^3)$. \n\n  Each constraint checked at most d times, check one constraint costs d^2. \n\n- **Global constraints**:\n\n  - Alldiff\n  \n  - resource constraint: total resources limited, prune away domain values which obviously goes above the limit\n  \n  - bound propagation \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n - DFS + backtrack\n\n- Fix the order of variables to traverse, and backtrack w.r.t value assignments\n\n- Search strategy: \n\n  - How to choose the next variable: MRV, minimum remaining value heuristic (most-constrained or first-fail variable)\n\n  - degree heuristic: Choose the most constraining variable (has most constraints on other unassigned variables)\n\n  - least constraining value heuristic: prefers values that rule out fewest choices for neighbors\n\n- **Forward checking**: Whenever a variable X is assigned, AC-3 inference is performed to prune the domains for the neighboring variables.  Forward checking is not powerful enough in some case, since its check is not deep enough. \n\n- **Maintaining arc-consistency (MAC)**: Improvement of forward checking \n\n- chronological backtracking: revisit the nearest decision point. Better: conflict set and backjumping\n\n- Constraint learning: find a minimum subset of the conflict set that causes the problem. These variables are called \"*no good*\".  \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search: We initially assign a value to each variable. Then for each round, pick one element which violates constraints, and reassign its value according to min-conflict \nheuristic, i.e. change to a value with least conflicts. We do this until a solution is found, or we've reached a maximum (specified) depth and return. \n\n## AIMA Chapter 6.5 The Structure of Problems\n \nKey idea: Divide-and-conquer, Partition CSP into independent subproblems, solve each one and combine.  \n\nWhy it is good: Significantly reduces time-complexity \n\n**Directional Arc Consistency (DAC)**: A CSP is directionally arc consistent under ordering $X_1, X_2, ..., X_n$ iff every $X_i$ is arc consistent with each $X_j$ for j>i. \n\nAny tree-structured CSP can be solved in **linear** time in the number of variables. How: \n- First form the topological sort of the constraint graph: pick any variable to be the root, then each node should appear after its parent in the tree \n- Make each node arc-consistent w.r.t its parent\n- Go through the tree starting from root, selecting value for each variable from remaining values -> No need to backtrack\n\nReduce a CSP to tree structure: \n- Cutset conditioning \n  - Choose a subset of variables S, such that after removing S, the constraint graph becomes tree-structured. S is a **cycle cutset**. \n  - For each assignment to the variables in S that satisfy all constraints on S, we remove illegal values (inconsistent with the assignment in S) of remaining variables from domains, test if there exists \n  a solution for them. \n- Tree decomposition： Transform original constraint graph into a tree. Each node in tree may consist of multiple variables. \n  - New tree satisfies: Every variable in original problem appears in at least one node in the tree; If originally two variables have a constraint, they must appear together in tree; \n  if a variable appears in two nodes, it must appear in every node along the connecting path. \n- Tree decomposition is generally faster than cutset conditioning\n- Cutset conditioning can be executed in linear memory, while tree decomposition requries memory exponential in the tree width ww\n \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" - **axiom**: a sentence that is directly given in the knowledge base\n",
        "\n",
        "- **declarative**: Only tell the agent what goal it should a achieve; **procedural**: also present specific instructions how to achieve that goal \"\"\"\n",
        "\n",
        "chapter7_2 = \"\"\" Nothing important \"\"\"\n",
        "chapter7_3 = \"\"\" \n",
        "- $M(\\\\alpha)$: All models that satisfy sentence $\\\\alpha$\n",
        "\n",
        "- **Entailment**: $\\\\alpha \\\\models \\\\beta$ if and only if in every model $\\\\alpha$ is true, $\\\\beta$ is also true ($M(\\\\alpha) \\\\subset M(\\\\beta)$).  Relationship **between** sentences\n",
        "\n",
        "- **Inference**: $KB\\\\vdash _i \\\\alpha$, i.e. $\\\\alpha$ is derived for knowledge base KB by algorithm $i$. \n",
        "\n",
        "- **Sound**: An inference algorithm is sound if it only derives entailed (correct) sentences. Also called \"truth preserving\"\n",
        "\n",
        "- **Complete**: An inference algorithm is complete if it can derive all sentences entailed\n",
        "\n",
        "###  \"\"\"\n",
        "chapter7_4 = \"\"\" - **Logical connectives**: $\\\\neg, \\\\and, \\\\or, \\\\implies, \\\\iff$ negation, and, or, implication, bi-conditional (precedence decreasing)\n",
        "\n",
        "- **Implication**: $P\\\\implies Q$, P is called *premise* or *antecedent*, Q is *conclusion* or *consequent*.\n",
        "\n",
        "-  Syntax: Define the logical symbols, connectives, etc. Semantics: Determine their truth values in models\n",
        "\n",
        "- Semantics: \n",
        "  - $\\\\neg P$ is true iff P is false\n",
        "  \n",
        "  - $P\\\\and Q$ is true iff both P and Q are true\n",
        "  \n",
        "  - $P\\\\or Q$ is true iff either P or Q is true\n",
        "  \n",
        "  - $P\\\\implies Q$ is true unless P is true while Q is false\n",
        "  \n",
        "  - $P\\\\iff Q$ iff P and Q are both true or both false\n",
        "\n",
        "- There are two ways for inference: (1) Model checking, to exhaust all possible models and see if the sentence could be entailed, see if $\\\\alpha$ is true in every model which KB is true, sound and complete; with n symbols O(2^n); (2) Theorem proving \"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "- **logical equivalence**: Two sentences $\\\\alpha$ and $\\\\beta$ are logically equivalent if the are true in the same set of models, denoted by $\\\\alpha \\\\equiv \\\\beta$. Equivalent definition: $\\\\alpha$ and $\\\\beta$ are equivalent if they entails each other, $\\\\alpha \\\\models \\\\beta$ and $\\\\beta \\\\models \\\\alpha$. \n",
        "\n",
        "- **Validity**: A sentence is valid if it's true in all models. Also called **tautology**. \n",
        "\n",
        "- **Deduction theorem**: For any sentences $\\\\alpha$ and $\\\\beta$, $(\\\\alpha \\\\models \\\\beta)$ if and only if $\\\\alpha \\\\implies \\\\beta$ is valid. \n",
        "\n",
        "- **Satisfiability**: A sentence is satisfiable if it is true, or satisfied by, some model.\n",
        "\n",
        "- $\\\\alpha$ is valid iff $\\\\neg \\\\alpha$ is unsatisfiable, $\\\\alpha$ is satisfiable iff $\\\\neg \\\\alpha$ is not valid. \n",
        "\n",
        "- **inference rule**: \n",
        "\n",
        "  - Modus Ponens: if $\\\\alpha$ and $\\\\alpha \\\\implies \\\\beta$ are valid, then $\\\\beta$ is valid. \n",
        "\n",
        "  - and-elimination: if $\\\\alpha \\\\and \\\\beta$ is true, then $\\\\alpha$ is true. \n",
        "\n",
        "  - All logical equivalences could be converted into rules\n",
        "\n",
        "- **Monotonicity**: As information is added to the knowledge base, the set of entailed sentences can only increase. \n",
        "\n",
        "- **Resolution**: a complete inference rule.  Unit & Full resolution rules. NOTE: resolve one pair at a time. It could decide if $\\\\alpha \\\\models \\\\beta$ for any alpha, beta. \n",
        "\n",
        "- Resolution algorithm: proof by **contradiction**. To show $KB \\\\models \\\\alpha$, show $KB \\\\and \\\\neg \\\\alpha$ is unsatisfiable. \n",
        "\n",
        "- **CNF**:\n",
        "\n",
        "  - Conjunctive normal form, a conjunction of clauses (disjunctions)\n",
        "\n",
        "  - Aim: convert any propositional logic sentence into CNF, apply resolution rule to clauses to prove some conclusion\n",
        "\n",
        "\n",
        "- **Resolution algorithm**: proof by **contradiction**. To show $KB \\\\models \\\\alpha$, show $KB \\\\and \\\\neg \\\\alpha$ is unsatisfiable. \n",
        "\n",
        "- Resolution algorithm is complete and sound\n",
        "\n",
        "- Resolution closure of clause set S: A set of all derivable clauses from S (or its derivatives) by repeatedly apply the resolution rule. \n",
        "\n",
        "- **Ground resolution theorem**: If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains empty clause. (Used to prove the completeness of resolution algo)\n",
        "\n",
        "- **Definite clause**: one and only one literal is positive. **Goal clause**: no positive literals; **Horn clause**: at most one positive literal\n",
        "\n",
        "- Horn clauses are closed under resolution.  \n",
        "\n",
        "- Forward-chaining inference is data-driven, backward-chaining is goal-directed reasoning.  \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"logical inference\" : \"Logical reasoning of generating new conclusions from the knowledge base\",\n",
        "\"model checking\": \"Enumerate all possible models to see if certain entailment holds \",\n",
        "\"Proposition symbol\": \"P, X, Y...the truth of which could be determined. They are atomic sentences in propositional logic system.\",\n",
        "\"literal\": \"Either an atomic sentence (positive literal) or the negation of an atomic sentence (negative literal)\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1518
        },
        "outputId": "e879e824-081a-4a59-9330-f85368079213"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n - **axiom**: a sentence that is directly given in the knowledge base\n\n- **declarative**: Only tell the agent what goal it should a achieve; **procedural**: also present specific instructions how to achieve that goal \n\n## AIMA Chapter 7.2 The Wumpus World\n Nothing important \n\n## AIMA Chapter 7.3 Logic\n \n- $M(\\alpha)$: All models that satisfy sentence $\\alpha$\n\n- **Entailment**: $\\alpha \\models \\beta$ if and only if in every model $\\alpha$ is true, $\\beta$ is also true ($M(\\alpha) \\subset M(\\beta)$).  Relationship **between** sentences\n\n- **Inference**: $KB\\vdash _i \\alpha$, i.e. $\\alpha$ is derived for knowledge base KB by algorithm $i$. \n\n- **Sound**: An inference algorithm is sound if it only derives entailed (correct) sentences. Also called \"truth preserving\"\n\n- **Complete**: An inference algorithm is complete if it can derive all sentences entailed\n\n###  \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n - **Logical connectives**: $\\neg, \\and, \\or, \\implies, \\iff$ negation, and, or, implication, bi-conditional (precedence decreasing)\n\n- **Implication**: $P\\implies Q$, P is called *premise* or *antecedent*, Q is *conclusion* or *consequent*.\n\n-  Syntax: Define the logical symbols, connectives, etc. Semantics: Determine their truth values in models\n\n- Semantics: \n  - $\\neg P$ is true iff P is false\n  \n  - $P\\and Q$ is true iff both P and Q are true\n  \n  - $P\\or Q$ is true iff either P or Q is true\n  \n  - $P\\implies Q$ is true unless P is true while Q is false\n  \n  - $P\\iff Q$ iff P and Q are both true or both false\n\n- There are two ways for inference: (1) Model checking, to exhaust all possible models and see if the sentence could be entailed, see if $\\alpha$ is true in every model which KB is true, sound and complete; with n symbols O(2^n); (2) Theorem proving \n\n## AIMA 7.5 Propositional Theorem Proving\n \n- **logical equivalence**: Two sentences $\\alpha$ and $\\beta$ are logically equivalent if the are true in the same set of models, denoted by $\\alpha \\equiv \\beta$. Equivalent definition: $\\alpha$ and $\\beta$ are equivalent if they entails each other, $\\alpha \\models \\beta$ and $\\beta \\models \\alpha$. \n\n- **Validity**: A sentence is valid if it's true in all models. Also called **tautology**. \n\n- **Deduction theorem**: For any sentences $\\alpha$ and $\\beta$, $(\\alpha \\models \\beta)$ if and only if $\\alpha \\implies \\beta$ is valid. \n\n- **Satisfiability**: A sentence is satisfiable if it is true, or satisfied by, some model.\n\n- $\\alpha$ is valid iff $\\neg \\alpha$ is unsatisfiable, $\\alpha$ is satisfiable iff $\\neg \\alpha$ is not valid. \n\n- **inference rule**: \n\n  - Modus Ponens: if $\\alpha$ and $\\alpha \\implies \\beta$ are valid, then $\\beta$ is valid. \n\n  - and-elimination: if $\\alpha \\and \\beta$ is true, then $\\alpha$ is true. \n\n  - All logical equivalences could be converted into rules\n\n- **Monotonicity**: As information is added to the knowledge base, the set of entailed sentences can only increase. \n\n- **Resolution**: a complete inference rule.  Unit & Full resolution rules. NOTE: resolve one pair at a time. It could decide if $\\alpha \\models \\beta$ for any alpha, beta. \n\n- Resolution algorithm: proof by **contradiction**. To show $KB \\models \\alpha$, show $KB \\and \\neg \\alpha$ is unsatisfiable. \n\n- **CNF**:\n\n  - Conjunctive normal form, a conjunction of clauses (disjunctions)\n\n  - Aim: convert any propositional logic sentence into CNF, apply resolution rule to clauses to prove some conclusion\n\n\n- **Resolution algorithm**: proof by **contradiction**. To show $KB \\models \\alpha$, show $KB \\and \\neg \\alpha$ is unsatisfiable. \n\n- Resolution algorithm is complete and sound\n\n- Resolution closure of clause set S: A set of all derivable clauses from S (or its derivatives) by repeatedly apply the resolution rule. \n\n- **Ground resolution theorem**: If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains empty clause. (Used to prove the completeness of resolution algo)\n\n- **Definite clause**: one and only one literal is positive. **Goal clause**: no positive literals; **Horn clause**: at most one positive literal\n\n- Horn clauses are closed under resolution.  \n\n- Forward-chaining inference is data-driven, backward-chaining is goal-directed reasoning.  \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Logical inference** - Logical reasoning of generating new conclusions from the knowledge base\n* **Model checking** - Enumerate all possible models to see if certain entailment holds \n* **Proposition symbol** - P, X, Y...the truth of which could be determined. They are atomic sentences in propositional logic system.\n* **Literal** - Either an atomic sentence (positive literal) or the negation of an atomic sentence (negative literal)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 10036
        },
        "id": "T3cm1WV542_a",
        "outputId": "3e2d4b68-6a55-4451-9328-c0c93f86a326"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Key problem: human vs rational; thought vs behavior\n\nFour genres of AI research: \n\na. Acting humanly - Turing test approach. To do the test the computer should be capable of: natural language processing, knowledge representation, automated reasoning, machine learning. Total turing test should also **interact** with the world, which additionally requires the following: computer vision, robotics. \n\nb.  Thinking humanly- Cognitive modeling. Learn about human thought through: introspection, brain imaging, psychological experiments. \n\nc. Thinking rationally - laws of thought; Syllogism by Aristotle; To reason logically. \n\nd. acting rationally - rational agent approach. This is the standard model. A **rational agent** is an agent which acts in an attempt to achive best outcome. If uncertainty is involved, it will try to achieve the expected best outcome. Advantages: more general than \"think rationally approach\" and more amenable to scientific computation. \n\nValue alignment problem: achieving the alignment between what we truly want and the actual object function we supplied into the model. \n\n## AIMA Chapter 27.1 The Limits of AI\n Argument for disability: A statement like 'A machine can never do X' \n\nTuring test: measure intelligence by performance on some open-ended task\n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n \n27.2.1 Chinese room\n\n27.2.2 Do machine have consciousness and does it matter?  \n\n## AIMA 2.1 Agents and Environments\n **Agent function**: maps a percept sequence to actions. An **agent program** is the implementation of agent function. \n\n**Difference**: Agent function is an abstract mathematical concept, agent program it the concrete realization residing in a system.  \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n **Performance measure**: Evaluates how well the agent is performing according to preferences and desires set by people\n\n**Rational agent**: The agent should choose the action which could maximize its performance measure, based on its percept sequence up to date and the prior knowledge it has, for any given percept sequence. \n\nRationality $\\neq$ omniscience, rationality $\\neq$ perfection. Rational agent maximizes *expected* performance, perfect agent maximizes *actual* performance. \n\n**Information gathering**: do something to change future percepts, like look both sides before crossing a street. \n\n**Autonomy**: the agent could do self-correction through learning and percepts, rather than heavily relying on prior knowledge.   \n\n## AIMA 2.3 The Nature of Environments\n How to define task environments: Fully or partially observable or unobservable, single or multi-agent, deterministic or not, epsodic or sequential, static or dynamic, discrete or continuous, known or unknown. \n\n**Episodic**: the process is divided into atomic episodes. In each episode the agent makes a percept and takes an action. The action in current episode will not depend on actions taken in previous ones, nor will it influence future decisions. For sequential case, current decision affect future conditions. \n\n**Dynamic**: the environment can change while the agent consider what action to take. **Semidynamic**: The environment does not change with time but the agent's performance measure does. \n\n**Known vs unknown**: whether the agent's state of knowledge about how the environment works \n\n## AIMA 2.4 The Structure of Agents\n agent = architecture + program \n\n**architecture**: the device or hardware with some sensors or actuators\n\nFour basic **agent programs**:\n\na. simple reflex agents: Action is solely based on current percept; It will usually fail in partially observable environment. \n\nb. Model-based reflex agents: The agent maintains an **internal state** depending on percept history. To update the internal state, we need: the world's **transition model** and the agent's **sensor model** (how the changes in world is reflected in the percept)\n\nc. Goal-based agents: Add in goal information (on the basis of model-based agent) \n\nd. Utility-based agents: Uses utility function to measure how well the agent is approaching its goal. Utility function provides a way for tradeoff of conflicting goals. \n\n**Learning agent**: Learning element (make improvements) + performance element (evaluates how well it is doing, select actions) + critic (provides feedback) + problem generator (suggest exploratory advice for more long-term benefits)\n\nits **Mechanism**: learning element receives feedback from **critic** and modifies performance element to have better performance\n\nAny type of agent above could be built as a learning agent. Learning agent could operate in unknown environments.  \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive the environment through sensors and act upon it through actuators\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n \n- Python is **strongly and dynamically** typed. Strong typing means that variables do have types and their types matter when performing operations upon them. Dynamic typing means the type of a variable could be changeda at run time.\n\n- Remember power in Python is star-star\n\n- Strings\n  - Concatenate: use + \n  - No need to escape special characters: r'\\\\n' \n  - Immutable\n  - Format: %s -> string, %d -> decimal (integer) eg: print('%s=%d'%('Harry', 3)) gives 'Harry=3' \n  - a = string1, b = a, then modify a, result: a and b differnet (deep copy)\n  - Cases: s.upper() converts to upper case, s.isupper() checks if all upper case, s.capitalize() to capitalized form\n  - s.split(c), c.join(list of strings), s.strip(c) remove trailing characters c \n- list\n  - a = [1,2,3], b = a, modify a, b modified as well\n  - b = a[:] produces a (shallow)copy. If a contains only primitive-typed elements, a deep copy will be created for b; if there is objects or structs, only a reference to each single object will be returned to b (that's why it's shallow) \n  - operations: append(e), insert(idx, e), index(e) (1st one), count(e), remove(e) (1st one from left), reverse() (reverse in place), sort(some_funct) (in-place). Usage: l.operation() \n  - l = sorted(l), returns a sorted copy \n- Dictionary \n  - from collections import Counter, Counter is a defaultdict, i.e. no error on invalid keys \n- Functions \n  - No function overloading. Functions cannot have the same name, even if with different parameters \n  - Multiple return values: a tuple\n  - Keyword arguments: Must be after all other arguments. myfunc(2, b=1, c=3) correct, myfunc(b=1, c=3, 2) syntax error \n  - *args: Accept a variable number of non-keyword arguments into the function. eg: l = ['a','b','c'], print_func(*l) => ('a', 'b', 'c')\n  - **kwargs: Accept a variable number of keyword arguments. e.g: kwargs should be dict. d={'a':1, 'b'=2}, print_func(**d) \n  - python functions are first-class objects: Could be dynamically created, destroyed, passed to a function, returned as a value, and have all rights as other vars in the language\n- Scope\n  - Dynamic scope: Intepreter sees the most recent value of variables\n- Class \n  - redefinition of methods: Redefine methods using the same name in subclass\n  - SuperClassName.methodName(self, parameters) == super().methodName(parameters) (for single inheritance)\n  - Operator overloading achieved using magic methods\n  - Magic methods: \\__str__(self): called when print an object, \\__len__: what len(object) will return, \\__copy__: how to copy an object, \\__cmp__: how == works, \\__add__: how + works on objects, \\__neg__: how unary negation works\n  - Duck typing: Checks for available methods. eg: Could call len(obj) for any class having a __len__ method. \n- Iterator \n  - Objects (class) with a __iter__ magic method are iterable\n  - Iterators are objects with a __next__ method. k=[1,2,3], i=iter(k), could call i.next() or next(i) or i.__next__() (equivalently). Returns StopIteration exception upon ending. No hasNext method!\n  - To be iterable: have __iter__, and returns an iterator object; to become iterator: have __next__ that throws StopIteration when done\n  - More memory-efficient than lists\n- Generator \n  - Function with 'yield' returns a generator. Basically is an iterator. \n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n **problem solving agent** vs **planning agent**: Problem solving agent uses atomic representation of states, the internal structure of state is invisible; planning agent uses factored or structured representations of states. \n\nSearch problem: \n\na. state & state space b. initial space c. goal state d. actions e. transition model f. action cost function  \n\n## AIMA Chapter 3.2 Example Problems\n Standardized problems vs real-world problems \n\n## AIMA Chapter 3.3 Search Algorithms\n **frontier**: nodes that have been reached but not expanded; Outside frontier: not reached yet; Inside frontier: already expanded\n\nNote that **reached** is not equal to **expanded** (i.e. dequeued from the frontier)\n\n**redundant path**: eg. cycles. Can use extra memory to record states reached, to avoid forming redundant paths\n\nEvaluate search algo: *d*: depth of optimal path to a solution, *m*: maximum depth in any path, *b*: branching factor\n\nGeneral search strategy: **Best-first Search** \n\n- Uses priority queue ordered by some metric *f*\n- Need space to store visited nodes, and corresponding f value\n- Graph search. Need to check each reached node. If reached the first time, or a better f value if found, node should be updated and enqueued. \n- Late goal test \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n **Informed vs uninformed**: Uninformed search has no knowledge about its gap to reach a goal, while informed one has \n\n**Early goal test vs late goal test**: Early goal test checks if it's goal upon reaching (before enqueue). Late goal test checks that after dequeue\n\n**Breadth First Search**:  \n\n- Data structure: Queue, FIFO\n- Always finds a solution with min #actions (hops)\n- Needs to record states we have visited\n- Graph search -> faster while memory consuming\n- Pop one element each time; Store it into \"visited\" if not already in (Graph search) \n- Do early goal test\n- Optimal for problems where all actions have equal cost; Always complete. \n\n**Uniform-cost search** (Dijkstra)\n\n- Best-first search with f = path cost\n- late goal test & graph search\n- Time complexity: $C^*$ is cost of optimal solution, $\\epsilon$ lower bound for cost of each action; Could be MUCH larger than $O(b^d)$\n\n- Complete and optimal\n\n**Depth-first search**\n\n- best-first search with f = -depth, early goal test\n- often Tree search, no redundancy check\n- Not optimal, incomplete if certain path is infinite\n\n- Memory efficient than BFS, $O(bm)$. Store all successors when expanding each node (gives b), and do this for each node along path (multiplies by m). \n- Use **backtrack**: generates only one successor expanding each node. (DFS generates all successors). Memory: **$O(m)$**. \n\n**Depth-limited Search**\n\n- $l$: depth limit, a good value should be picked\n- not complete, not optimal\n- Uses stack, LIFO\n- late goal check & Tree search\n- Diameter: Any node can be reached from any other node in *diameter* steps\n\n**Iterative Deepening Search**\n\n- Do depth-limited search for $l=0,1,...,$ until either a solution is found or a failure is reported\n- Optimal if actions have equal costs, and complete\n- Memory complexity: $O(bd)$ if there exists solution, $O(bm)$ if there is not. \n- Time complexity: $O(b^d)$ if there is a solution, $O(b^m)$ if there isn't.\n- We should use iterative deepening search when memory is limited and depth of solution is unknown. \n- Tree like search, no need to store \"visitation\" information\n\n**Bidirectional Search**\n\n- Start from root and goal simultaneously\n- Keep two frontier queues, and two \"visited\" sets\n- Motivation: $b^{d/2}+b^{d/2}<<b^d$\n- Case: bidirectional best-first search \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Informed search** - Search problem in which an estimated distance to the goal is available\n* **Completeness** - A complete algo is guaranteed to find a solution if there exists one, and correctly report failure otherwise.\n* **Optimality** - An optimal algo finds a solution with lowest total cost before it finds any other solution.\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n **informed search**: Search problem which has access to domain-specific knowledge, $h(n)$ heuristics. \n\n$h(n)$: estimated lowest cost of reaching the goal from the current node n\n\n**Greedy Best-First Search**\n\n- Best-first search: $f(n)=h(n)$\n- Not optimal. Complete in finite space, not in infinite space. \n- Worst case time & space complexity: $O(|V|)$, where $V$ is the number of nodes.  \n\n**A* Search**\n\n- Best-first search with $f(n)=g(n)+h(n)$\n- late goal test\n- Time complexity: $O(b^d)$, branching factor b, shortest depth to a solution d\n- Complete; Optimal if $h(n)$ is admissible; Optimally efficient (don't understand, Section 3.5.3)\n- **Admissibility**: If $h(n)$ never overestimates the cost to reach a goal, then it is *admissible*.\n- **Consistency**: A heuristic $h(n)$ is consistent if for every node $n$ and its successor $n'$ through action $a$, we have $h(n)\\leq h(n')+c(n,a,n')$\n- Consistent $\\subset$ Admissible\n- If $h(n)$ is consistent, the first time we reach a state, it is on optimal path. Can do **early goal check**, there is no need for \"visitation\" set or its update\n- Contour: A* search concentric ovals, uniform-cost search concentric circles. \n- $f(n)$ is **monotonic** if and only if $h(n)$ is consistent.\n- A* search expands all nodes with $f(n)<C^*$, $C^*$ is the cost of optimal path. These are **surely expanded nodes**. A* might expand some of the nodes with $f(n)=C^*$ (on contour).\nNo nodes with $f(n)>C^*$ gets expanded. Expansion: popped from queue\n- **Optimally efficient**: Any algo that extends search path from initial state and uses the same heuristic must expand all nodes that are surely expanded by A* \n\n**Satisficing search**\n\nAdopt an **inadmissible** heuristic to find a suboptimal but acceptable solution, expanding fewer nodes. \n\n**Weighted A* search**: $f(n)=g(n)+W \\times h(n),W>1$. \n\n**Bounded sub-optimal search:** find a solution with cost at most $W \\times C^*$. \n\n**Bounded cost search**: find a solution with cost at most $C'$ (some constant)\n\n**Speedy search:** find a solution as quickly as possible\n\n## AIMA Chapter 3.6 Heuristic Functions\n **Effective branching factor $b^*$**: If A* search generates $N$ nodes, and solution has depth $d$, then $b^*$ is the branching factor of a uniform tree of depth $d$ to accommodate $N+1$ nodes. $N+1=1+b^*+...+(b^*)^d$ \n\n**Usage of b***: measure #nodes generated => performance of A* search\n\n**Dominate:** if both $h_1(n),h_2(n)$ are admissible, $h_1(n)\\geq h_2(n)$ for any n, then *h_1 dominates h_2*.  \n\n**Generate h(n)**: Find an optimal solution to a relaxed problem. It will be a *consistent* heuristic to original problem. \n\n**pattern database**: stores exact solutions for subproblems, and combine them to form a solution for whole problem \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n **competitive environment**: >1 agents have conflicting goals\n\n**perfect information**: fully observable\n\n**How to find optimal strategy**: calculate *minimax* value for each node, assuming both players play optimally \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n **Minimax search:** dept-first search\n\nAims at solving perfect information, zero-sum games\n\n**Extend to n players**: \n\n- Use a utility vector for each node, recording value from each player's viewpoint\n- Players could form alliance\n\n**$ \\alpha-\\beta$ pruning**: \n\n$ \\alpha $: The highest value we have found for MAX player for any choice point along the path. MAX can achieve at least $\\alpha$. \n\n$ \\beta$: highest -> lowest. MIN can achieve at most $\\beta$ search the game tree.\n\n- The order of exhausting nodes MATTERS!  \n\nThe change of $\\alpha,\\beta$ during search process: \n- Node can inherit values of alpha and beta from parent\n- When MAX player is in charge, only alpha get updated, while only beta gets updated when MIN's in charge\n- When a pruning message is issued, the alpha/beta will not be updated. The function will return directly \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n - Heuristic Alpha-Beta Tree Search\n\n- Utility -> uses evaluation function to estimate utility; terminal state -> cut-off test\n\n- $H-MINIMAX(s,d)= \\left\\{ \\begin{aligned} EVAL(s,MAX), \\ if\\ IS-CUTOFF(s,d)\\\\max_a H-MINMAX(RESULT(s,a),d+1),\\ if\\ TO-MOVE(s)=MAX \\\\ min_a H-MINMAX(RESULT(s,a),d+1),if\\ TO-MOVE(s)=MIN \\end{aligned}\\right.$\n\n- $EVAL(s,player)=Utility(s,p)$ for terminal states; For non-terminal states, $Utility(loss,player)\\leq EVAL(s,player) \\leq Utility(win,player)$\n\n- **features**: describes the chances of winning\n\n  **weighted linear function**: the evaluation EVAL could be a linear weighted sum of features. Underlying assumption: features are independent of each other\n\n- **quiescent search**: evaluation functions are only applied to non pending moves, i.e. quiescent move \n\n- **horizon effect**: When the opponent's certain move will cause series and inevitable damage, the player can temporarily delay it by some tricks. \n\n- **singular extensions**: moves that are obviously better than all others at certain positions. \n\n- **forward pruning**: prunes away nodes that seem bad according to some evaluation metric. However, it is possible that these are actually good moves. \n\n- **Beam search**: for each ply, consider only a beam of n best moves and none of the others. \n \n\n## AIMA Chapter 5.5 Stochastic Games\n - Calculate **expectiminimax value**\n\n- The evaluation function must return a linear combination of the probability of winning \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Problem formulation: \n- probability of being in state s: $P(s)$, transiting to state $s'$ from state s taking action a: $P(s'|s,a)$\n- Agent preference: utility function $U(s)$ of a state s\n- $P(result(a)=s')=\\sum_s P(s'|s,a)$\n- Expected utility: $EU(a)=\\sum_{s'}P(result(a)=s')U(s')$ \n- Maximum Expected Utility (MEU): $action = argmax_a EU(a)$\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n A lottery L, getting different results with corresponding probs: [p1, R1; p2, R2; ...]\nAny reasonable preference relation must obey: \n- Oderability: Cannot refuse making decisions, exactly one of $A\\succ B$ or $B\\succ A$ or $A\\sim B$ holds. \n- Transitivity: $A\\succ B \\wedge B\\succ C \\Rightarrow A\\succ C$\n- Continuity: $A\\succ B \\succ C \\Rightarrow \\exists p, [p, A; 1-P, C] \\sim B$. The agent is indifferent between getting B for sure, or getting A/C with probabilities\n- Substitutability: $A\\sim B \\Rightarrow [p,A;1-p,C] \\sim [p,B;1-p,C]$. Also holds if we replace $\\sim$ by $\\succ$. \n- Monotonicity: $A\\succ B \\Rightarrow (p>q \\Leftrightarrow [p,A;1-p,B] \\succ [q, A;1-q,B]$)\n- Decomposability: $[p,A;1-p,[q,B;(1-q),C]] \\sim [p,A;(1-p)q,B;(1-p)(1-q),C]$\n\nTheorem: A utility function exists for any rational agent satisfying the above conditions, that is: \n\n$U(A)>U(B) \\Leftrightarrow A \\succ B$ and $U(A)=U(B) \\Leftrightarrow A \\sim B$ \n\n**Expected utility of a lottery:** $U([p_1,S_1;p_2,S_2;...,p_k,S_k])=\\sum_i p_i U(S_i)$\n\n\n## AIMA Chapter 16.3 Utility Functions\n \npreference elicitation: To work out the users' utility function by asking them various questions\n\nScaling utility: Best-possible prize: $U(S)=u_{\\top}$, worst-possible catastrophe: $U(s)=u_{\\bot}$ \n\nGet utility of any prize S: Ask user to choose between S and **standard lottery**: $[p,u_{\\top};1-p, u_{\\bot}]$ until user becomes indifferent between the two\n\nMicromort: One unit of risk, one in a million chance of death \n\nEMV: expected monetary value. Utility is not directly proportional to monetary value \n\nrisk-averse: people tend to prefer a sure payoff less than the EMV of the gamble in the positive range\n\nrisk-seeking: reversed behavior of risk-averse in negative monetary range \n\nCertainty equivalent: The amount that people would like to receive for sure rather than the uncertain gambling. eg. Receive 400 dollors, not 1/2 chance of 1000 while 1/2 chance of 0\n\nRisk-neutral: Has a linear utility-monetary curve \n\ninsurance premium=EMV-certainty equivalent\n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n - **Consistent**: an assignment of variables is consistent if it does not violate any constraints. \n\n- **Complete**: every variable is assigned a value \n\n- A solution is a consistent and complete assignment.\n\n- Example formulations\n\n  - Graph coloring\n\n  - Job scheduling: **precedence** constraint: One event must happen before another has ended; disjunctive constraint: Two events must NOT have time-overlap;  \n\n  - Finite or infinite domain? Discrete or continuous domain? Unary or binary or higher order constraint (constraint hyper-graph)? \n\n  - **Global constraint**: a constraint involving an arbitrary number of variables \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n - **\nAC-3 is used for removing inconsistency. Sometimes only AC-3 is sufficient to reach a complete solution, while in more difficult problems, search is also necessary. \nSearch involves uncertainty, which means that we need to try different possibilities out, to see if each of them works. \n\nconstraint propagation**: Iteratively reduce the number of legal values of certain variable according to the constraints\n\n- **Local consistency**: \n\n  - Node consistency: no unary constraint is violated\n\n  - Arc consistency: A variable $X_i$ is arc-consistent w.r.t another variable $X_j$ if for every value that $X_i$ can take, there exists some legal value in $X_j$'s domain. \n  \n  - Path-consistency: 3-consistency. A two variable set $[X_i,X_j]$ is path-consistent w.r.t a 3rd variable $X_k$ if for every valid assignment $X_i=a,X_j=b$ consistent with the binary constraint on $[X_i,X_j]$, there exists a value for $X_k$, such that the binary constraint for both $[X_i,X_k]$ and $[X_j,X_k]$ are satisfied. \n  \n  - k-consistency: For any legal assignment to a set of k-1 variables, there exists a valid assignment to the kth variable, so that no constraint is violated. \n  \n  - strongly k-consistent: k-consistent, (k-1)-consistent, ..., 1-consistent.  \n\n- Enforce arc-consistency: **AC-3**\n\n  How it works: Keep of queue of directed edges (initially all edges in the graph). Pop out an edge every time $(X_i,X_j)$, make $X_i$ arc-consistent w.r.t to $X_j$. If the domain of $X_i$ is not changed, directly proceed with the next edge. Otherwise, if its modified, add all $(X_k,X_i)$ to the queue, where k is a neighbor of i. Loop until queue becomes empty or an empty domain is found for certain variable, indicating a failure. \n\n  **Time complexity**: c binary constraints, n variables, each has domain size d, worse case: $O(cd^3)$. \n\n  Each constraint checked at most d times, check one constraint costs d^2. \n\n- **Global constraints**:\n\n  - Alldiff\n  \n  - resource constraint: total resources limited, prune away domain values which obviously goes above the limit\n  \n  - bound propagation \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n - DFS + backtrack\n\n- Fix the order of variables to traverse, and backtrack w.r.t value assignments\n\n- Search strategy: \n\n  - How to choose the next variable: MRV, minimum remaining value heuristic (most-constrained or first-fail variable)\n\n  - degree heuristic: Choose the most constraining variable (has most constraints on other unassigned variables)\n\n  - least constraining value heuristic: prefers values that rule out fewest choices for neighbors\n\n- **Forward checking**: Whenever a variable X is assigned, AC-3 inference is performed to prune the domains for the neighboring variables.  Forward checking is not powerful enough in some case, since its check is not deep enough. \n\n- **Maintaining arc-consistency (MAC)**: Improvement of forward checking \n\n- chronological backtracking: revisit the nearest decision point. Better: conflict set and backjumping\n\n- Constraint learning: find a minimum subset of the conflict set that causes the problem. These variables are called \"*no good*\".  \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search: We initially assign a value to each variable. Then for each round, pick one element which violates constraints, and reassign its value according to min-conflict \nheuristic, i.e. change to a value with least conflicts. We do this until a solution is found, or we've reached a maximum (specified) depth and return. \n\n## AIMA Chapter 6.5 The Structure of Problems\n \nKey idea: Divide-and-conquer, Partition CSP into independent subproblems, solve each one and combine.  \n\nWhy it is good: Significantly reduces time-complexity \n\n**Directional Arc Consistency (DAC)**: A CSP is directionally arc consistent under ordering $X_1, X_2, ..., X_n$ iff every $X_i$ is arc consistent with each $X_j$ for j>i. \n\nAny tree-structured CSP can be solved in **linear** time in the number of variables. How: \n- First form the topological sort of the constraint graph: pick any variable to be the root, then each node should appear after its parent in the tree \n- Make each node arc-consistent w.r.t its parent\n- Go through the tree starting from root, selecting value for each variable from remaining values -> No need to backtrack\n\nReduce a CSP to tree structure: \n- Cutset conditioning \n  - Choose a subset of variables S, such that after removing S, the constraint graph becomes tree-structured. S is a **cycle cutset**. \n  - For each assignment to the variables in S that satisfy all constraints on S, we remove illegal values (inconsistent with the assignment in S) of remaining variables from domains, test if there exists \n  a solution for them. \n- Tree decomposition： Transform original constraint graph into a tree. Each node in tree may consist of multiple variables. \n  - New tree satisfies: Every variable in original problem appears in at least one node in the tree; If originally two variables have a constraint, they must appear together in tree; \n  if a variable appears in two nodes, it must appear in every node along the connecting path. \n- Tree decomposition is generally faster than cutset conditioning\n- Cutset conditioning can be executed in linear memory, while tree decomposition requries memory exponential in the tree width ww\n \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n - **axiom**: a sentence that is directly given in the knowledge base\n\n- **declarative**: Only tell the agent what goal it should a achieve; **procedural**: also present specific instructions how to achieve that goal \n\n## AIMA Chapter 7.2 The Wumpus World\n Nothing important \n\n## AIMA Chapter 7.3 Logic\n \n- $M(\\alpha)$: All models that satisfy sentence $\\alpha$\n\n- **Entailment**: $\\alpha \\models \\beta$ if and only if in every model $\\alpha$ is true, $\\beta$ is also true ($M(\\alpha) \\subset M(\\beta)$).  Relationship **between** sentences\n\n- **Inference**: $KB\\vdash _i \\alpha$, i.e. $\\alpha$ is derived for knowledge base KB by algorithm $i$. \n\n- **Sound**: An inference algorithm is sound if it only derives entailed (correct) sentences. Also called \"truth preserving\"\n\n- **Complete**: An inference algorithm is complete if it can derive all sentences entailed\n\n###  \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n - **Logical connectives**: $\\neg, \\and, \\or, \\implies, \\iff$ negation, and, or, implication, bi-conditional (precedence decreasing)\n\n- **Implication**: $P\\implies Q$, P is called *premise* or *antecedent*, Q is *conclusion* or *consequent*.\n\n-  Syntax: Define the logical symbols, connectives, etc. Semantics: Determine their truth values in models\n\n- Semantics: \n  - $\\neg P$ is true iff P is false\n  \n  - $P\\and Q$ is true iff both P and Q are true\n  \n  - $P\\or Q$ is true iff either P or Q is true\n  \n  - $P\\implies Q$ is true unless P is true while Q is false\n  \n  - $P\\iff Q$ iff P and Q are both true or both false\n\n- There are two ways for inference: (1) Model checking, to exhaust all possible models and see if the sentence could be entailed, see if $\\alpha$ is true in every model which KB is true, sound and complete; with n symbols O(2^n); (2) Theorem proving \n\n## AIMA 7.5 Propositional Theorem Proving\n \n- **logical equivalence**: Two sentences $\\alpha$ and $\\beta$ are logically equivalent if the are true in the same set of models, denoted by $\\alpha \\equiv \\beta$. Equivalent definition: $\\alpha$ and $\\beta$ are equivalent if they entails each other, $\\alpha \\models \\beta$ and $\\beta \\models \\alpha$. \n\n- **Validity**: A sentence is valid if it's true in all models. Also called **tautology**. \n\n- **Deduction theorem**: For any sentences $\\alpha$ and $\\beta$, $(\\alpha \\models \\beta)$ if and only if $\\alpha \\implies \\beta$ is valid. \n\n- **Satisfiability**: A sentence is satisfiable if it is true, or satisfied by, some model.\n\n- $\\alpha$ is valid iff $\\neg \\alpha$ is unsatisfiable, $\\alpha$ is satisfiable iff $\\neg \\alpha$ is not valid. \n\n- **inference rule**: \n\n  - Modus Ponens: if $\\alpha$ and $\\alpha \\implies \\beta$ are valid, then $\\beta$ is valid. \n\n  - and-elimination: if $\\alpha \\and \\beta$ is true, then $\\alpha$ is true. \n\n  - All logical equivalences could be converted into rules\n\n- **Monotonicity**: As information is added to the knowledge base, the set of entailed sentences can only increase. \n\n- **Resolution**: a complete inference rule.  Unit & Full resolution rules. NOTE: resolve one pair at a time. It could decide if $\\alpha \\models \\beta$ for any alpha, beta. \n\n- Resolution algorithm: proof by **contradiction**. To show $KB \\models \\alpha$, show $KB \\and \\neg \\alpha$ is unsatisfiable. \n\n- **CNF**:\n\n  - Conjunctive normal form, a conjunction of clauses (disjunctions)\n\n  - Aim: convert any propositional logic sentence into CNF, apply resolution rule to clauses to prove some conclusion\n\n\n- **Resolution algorithm**: proof by **contradiction**. To show $KB \\models \\alpha$, show $KB \\and \\neg \\alpha$ is unsatisfiable. \n\n- Resolution algorithm is complete and sound\n\n- Resolution closure of clause set S: A set of all derivable clauses from S (or its derivatives) by repeatedly apply the resolution rule. \n\n- **Ground resolution theorem**: If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains empty clause. (Used to prove the completeness of resolution algo)\n\n- **Definite clause**: one and only one literal is positive. **Goal clause**: no positive literals; **Horn clause**: at most one positive literal\n\n- Horn clauses are closed under resolution.  \n\n- Forward-chaining inference is data-driven, backward-chaining is goal-directed reasoning.  \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Logical inference** - Logical reasoning of generating new conclusions from the knowledge base\n* **Model checking** - Enumerate all possible models to see if certain entailment holds \n* **Proposition symbol** - P, X, Y...the truth of which could be determined. They are atomic sentences in propositional logic system.\n* **Literal** - Either an atomic sentence (positive literal) or the negation of an atomic sentence (negative literal)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "Kl4OnglWFIn4",
        "outputId": "7d03a59a-4d7e-4b28-9a05-dc965b449d02"
      },
      "source": [
        "# generate pdf\n",
        "# %%capture\n",
        "!git clone https://gist.github.com/bc5f1add34fef7c7f9fb83d3783311e2.git\n",
        "!cp bc5f1add34fef7c7f9fb83d3783311e2/colab_pdf.py colab_pdf.py\n",
        "from colab_pdf import colab_pdf\n",
        "# change the name to your ipynb file name shown on the top left of Colab window\n",
        "# Important: make sure that your file name does not contain spaces!\n",
        "colab_pdf('CIS521__MID_CP')"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "fatal: destination path 'bc5f1add34fef7c7f9fb83d3783311e2' already exists and is not an empty directory.\n",
            "Get:1 http://security.ubuntu.com/ubuntu bionic-security InRelease [88.7 kB]\n",
            "Get:2 https://cloud.r-project.org/bin/linux/ubuntu bionic-cran40/ InRelease [3,626 B]\n",
            "Ign:3 https://developer.download.nvidia.com/compute/cuda/repos/ubuntu1804/x86_64  InRelease\n",
            "Get:4 http://ppa.launchpad.net/c2d4u.team/c2d4u4.0+/ubuntu bionic InRelease [15.9 kB]\n",
            "Ign:5 https://developer.download.nvidia.com/compute/machine-learning/repos/ubuntu1804/x86_64  InRelease\n",
            "Hit:6 http://archive.ubuntu.com/ubuntu bionic InRelease\n",
            "Get:7 https://developer.download.nvidia.com/compute/cuda/repos/ubuntu1804/x86_64  Release [696 B]\n",
            "Hit:8 https://developer.download.nvidia.com/compute/machine-learning/repos/ubuntu1804/x86_64  Release\n",
            "Get:9 https://developer.download.nvidia.com/compute/cuda/repos/ubuntu1804/x86_64  Release.gpg [836 B]\n",
            "Get:10 http://archive.ubuntu.com/ubuntu bionic-updates InRelease [88.7 kB]\n",
            "Get:11 https://cloud.r-project.org/bin/linux/ubuntu bionic-cran40/ Packages [69.5 kB]\n",
            "Hit:12 http://ppa.launchpad.net/cran/libgit2/ubuntu bionic InRelease\n",
            "Get:13 http://archive.ubuntu.com/ubuntu bionic-backports InRelease [74.6 kB]\n",
            "Get:14 http://ppa.launchpad.net/deadsnakes/ppa/ubuntu bionic InRelease [15.9 kB]\n",
            "Get:15 http://security.ubuntu.com/ubuntu bionic-security/main amd64 Packages [2,396 kB]\n",
            "Get:16 http://security.ubuntu.com/ubuntu bionic-security/universe amd64 Packages [1,434 kB]\n",
            "Get:17 http://security.ubuntu.com/ubuntu bionic-security/restricted amd64 Packages [630 kB]\n",
            "Hit:18 http://ppa.launchpad.net/graphics-drivers/ppa/ubuntu bionic InRelease\n",
            "Get:20 https://developer.download.nvidia.com/compute/cuda/repos/ubuntu1804/x86_64  Packages [753 kB]\n",
            "Get:21 http://ppa.launchpad.net/c2d4u.team/c2d4u4.0+/ubuntu bionic/main Sources [1,809 kB]\n",
            "Get:22 http://archive.ubuntu.com/ubuntu bionic-updates/main amd64 Packages [2,835 kB]\n",
            "Get:23 http://ppa.launchpad.net/c2d4u.team/c2d4u4.0+/ubuntu bionic/main amd64 Packages [926 kB]\n",
            "Get:24 http://archive.ubuntu.com/ubuntu bionic-updates/restricted amd64 Packages [665 kB]\n",
            "Get:25 http://archive.ubuntu.com/ubuntu bionic-updates/universe amd64 Packages [2,213 kB]\n",
            "Get:26 http://ppa.launchpad.net/deadsnakes/ppa/ubuntu bionic/main amd64 Packages [45.3 kB]\n",
            "Fetched 14.1 MB in 4s (3,795 kB/s)\n",
            "Reading package lists... Done\n",
            "Building dependency tree       \n",
            "Reading state information... Done\n",
            "70 packages can be upgraded. Run 'apt list --upgradable' to see them.\n",
            "Reading package lists... Done\n",
            "Building dependency tree       \n",
            "Reading state information... Done\n",
            "The following additional packages will be installed:\n",
            "  fonts-droid-fallback fonts-lato fonts-lmodern fonts-noto-mono fonts-texgyre\n",
            "  javascript-common libcupsfilters1 libcupsimage2 libgs9 libgs9-common\n",
            "  libijs-0.35 libjbig2dec0 libjs-jquery libkpathsea6 libpotrace0 libptexenc1\n",
            "  libruby2.5 libsynctex1 libtexlua52 libtexluajit2 libzzip-0-13 lmodern\n",
            "  poppler-data preview-latex-style rake ruby ruby-did-you-mean ruby-minitest\n",
            "  ruby-net-telnet ruby-power-assert ruby-test-unit ruby2.5\n",
            "  rubygems-integration t1utils tex-common tex-gyre texlive-base\n",
            "  texlive-binaries texlive-latex-base texlive-latex-extra\n",
            "  texlive-latex-recommended texlive-pictures texlive-plain-generic tipa\n",
            "Suggested packages:\n",
            "  fonts-noto apache2 | lighttpd | httpd poppler-utils ghostscript\n",
            "  fonts-japanese-mincho | fonts-ipafont-mincho fonts-japanese-gothic\n",
            "  | fonts-ipafont-gothic fonts-arphic-ukai fonts-arphic-uming fonts-nanum ri\n",
            "  ruby-dev bundler debhelper gv | postscript-viewer perl-tk xpdf-reader\n",
            "  | pdf-viewer texlive-fonts-recommended-doc texlive-latex-base-doc\n",
            "  python-pygments icc-profiles libfile-which-perl\n",
            "  libspreadsheet-parseexcel-perl texlive-latex-extra-doc\n",
            "  texlive-latex-recommended-doc texlive-pstricks dot2tex prerex ruby-tcltk\n",
            "  | libtcltk-ruby texlive-pictures-doc vprerex\n",
            "The following NEW packages will be installed:\n",
            "  fonts-droid-fallback fonts-lato fonts-lmodern fonts-noto-mono fonts-texgyre\n",
            "  javascript-common libcupsfilters1 libcupsimage2 libgs9 libgs9-common\n",
            "  libijs-0.35 libjbig2dec0 libjs-jquery libkpathsea6 libpotrace0 libptexenc1\n",
            "  libruby2.5 libsynctex1 libtexlua52 libtexluajit2 libzzip-0-13 lmodern\n",
            "  poppler-data preview-latex-style rake ruby ruby-did-you-mean ruby-minitest\n",
            "  ruby-net-telnet ruby-power-assert ruby-test-unit ruby2.5\n",
            "  rubygems-integration t1utils tex-common tex-gyre texlive-base\n",
            "  texlive-binaries texlive-fonts-recommended texlive-generic-recommended\n",
            "  texlive-latex-base texlive-latex-extra texlive-latex-recommended\n",
            "  texlive-pictures texlive-plain-generic texlive-xetex tipa\n",
            "0 upgraded, 47 newly installed, 0 to remove and 70 not upgraded.\n",
            "Need to get 146 MB of archives.\n",
            "After this operation, 460 MB of additional disk space will be used.\n",
            "Get:1 http://archive.ubuntu.com/ubuntu bionic/main amd64 fonts-droid-fallback all 1:6.0.1r16-1.1 [1,805 kB]\n",
            "Get:2 http://archive.ubuntu.com/ubuntu bionic/main amd64 fonts-lato all 2.0-2 [2,698 kB]\n",
            "Get:3 http://archive.ubuntu.com/ubuntu bionic/main amd64 poppler-data all 0.4.8-2 [1,479 kB]\n",
            "Get:4 http://archive.ubuntu.com/ubuntu bionic/main amd64 tex-common all 6.09 [33.0 kB]\n",
            "Get:5 http://archive.ubuntu.com/ubuntu bionic/main amd64 fonts-lmodern all 2.004.5-3 [4,551 kB]\n",
            "Get:6 http://archive.ubuntu.com/ubuntu bionic/main amd64 fonts-noto-mono all 20171026-2 [75.5 kB]\n",
            "Get:7 http://archive.ubuntu.com/ubuntu bionic/universe amd64 fonts-texgyre all 20160520-1 [8,761 kB]\n",
            "Get:8 http://archive.ubuntu.com/ubuntu bionic/main amd64 javascript-common all 11 [6,066 B]\n",
            "Get:9 http://archive.ubuntu.com/ubuntu bionic-updates/main amd64 libcupsfilters1 amd64 1.20.2-0ubuntu3.1 [108 kB]\n",
            "Get:10 http://archive.ubuntu.com/ubuntu bionic-updates/main amd64 libcupsimage2 amd64 2.2.7-1ubuntu2.8 [18.6 kB]\n",
            "Get:11 http://archive.ubuntu.com/ubuntu bionic/main amd64 libijs-0.35 amd64 0.35-13 [15.5 kB]\n",
            "Get:12 http://archive.ubuntu.com/ubuntu bionic/main amd64 libjbig2dec0 amd64 0.13-6 [55.9 kB]\n",
            "Get:13 http://archive.ubuntu.com/ubuntu bionic-updates/main amd64 libgs9-common all 9.26~dfsg+0-0ubuntu0.18.04.14 [5,092 kB]\n",
            "Get:14 http://archive.ubuntu.com/ubuntu bionic-updates/main amd64 libgs9 amd64 9.26~dfsg+0-0ubuntu0.18.04.14 [2,265 kB]\n",
            "Get:15 http://archive.ubuntu.com/ubuntu bionic/main amd64 libjs-jquery all 3.2.1-1 [152 kB]\n",
            "Get:16 http://archive.ubuntu.com/ubuntu bionic-updates/main amd64 libkpathsea6 amd64 2017.20170613.44572-8ubuntu0.1 [54.9 kB]\n",
            "Get:17 http://archive.ubuntu.com/ubuntu bionic/main amd64 libpotrace0 amd64 1.14-2 [17.4 kB]\n",
            "Get:18 http://archive.ubuntu.com/ubuntu bionic-updates/main amd64 libptexenc1 amd64 2017.20170613.44572-8ubuntu0.1 [34.5 kB]\n",
            "Get:19 http://archive.ubuntu.com/ubuntu bionic/main amd64 rubygems-integration all 1.11 [4,994 B]\n",
            "Get:20 http://archive.ubuntu.com/ubuntu bionic-updates/main amd64 ruby2.5 amd64 2.5.1-1ubuntu1.10 [48.6 kB]\n",
            "Get:21 http://archive.ubuntu.com/ubuntu bionic/main amd64 ruby amd64 1:2.5.1 [5,712 B]\n",
            "Get:22 http://archive.ubuntu.com/ubuntu bionic-updates/main amd64 rake all 12.3.1-1ubuntu0.1 [44.9 kB]\n",
            "Get:23 http://archive.ubuntu.com/ubuntu bionic/main amd64 ruby-did-you-mean all 1.2.0-2 [9,700 B]\n",
            "Get:24 http://archive.ubuntu.com/ubuntu bionic/main amd64 ruby-minitest all 5.10.3-1 [38.6 kB]\n",
            "Get:25 http://archive.ubuntu.com/ubuntu bionic/main amd64 ruby-net-telnet all 0.1.1-2 [12.6 kB]\n",
            "Get:26 http://archive.ubuntu.com/ubuntu bionic/main amd64 ruby-power-assert all 0.3.0-1 [7,952 B]\n",
            "Get:27 http://archive.ubuntu.com/ubuntu bionic/main amd64 ruby-test-unit all 3.2.5-1 [61.1 kB]\n",
            "Get:28 http://archive.ubuntu.com/ubuntu bionic-updates/main amd64 libruby2.5 amd64 2.5.1-1ubuntu1.10 [3,071 kB]\n",
            "Get:29 http://archive.ubuntu.com/ubuntu bionic-updates/main amd64 libsynctex1 amd64 2017.20170613.44572-8ubuntu0.1 [41.4 kB]\n",
            "Get:30 http://archive.ubuntu.com/ubuntu bionic-updates/main amd64 libtexlua52 amd64 2017.20170613.44572-8ubuntu0.1 [91.2 kB]\n",
            "Get:31 http://archive.ubuntu.com/ubuntu bionic-updates/main amd64 libtexluajit2 amd64 2017.20170613.44572-8ubuntu0.1 [230 kB]\n",
            "Get:32 http://archive.ubuntu.com/ubuntu bionic-updates/main amd64 libzzip-0-13 amd64 0.13.62-3.1ubuntu0.18.04.1 [26.0 kB]\n",
            "Get:33 http://archive.ubuntu.com/ubuntu bionic/main amd64 lmodern all 2.004.5-3 [9,631 kB]\n",
            "Get:34 http://archive.ubuntu.com/ubuntu bionic/main amd64 preview-latex-style all 11.91-1ubuntu1 [185 kB]\n",
            "Get:35 http://archive.ubuntu.com/ubuntu bionic/main amd64 t1utils amd64 1.41-2 [56.0 kB]\n",
            "Get:36 http://archive.ubuntu.com/ubuntu bionic/universe amd64 tex-gyre all 20160520-1 [4,998 kB]\n",
            "Get:37 http://archive.ubuntu.com/ubuntu bionic-updates/main amd64 texlive-binaries amd64 2017.20170613.44572-8ubuntu0.1 [8,179 kB]\n",
            "Get:38 http://archive.ubuntu.com/ubuntu bionic/main amd64 texlive-base all 2017.20180305-1 [18.7 MB]\n",
            "Get:39 http://archive.ubuntu.com/ubuntu bionic/universe amd64 texlive-fonts-recommended all 2017.20180305-1 [5,262 kB]\n",
            "Get:40 http://archive.ubuntu.com/ubuntu bionic/universe amd64 texlive-plain-generic all 2017.20180305-2 [23.6 MB]\n",
            "Get:41 http://archive.ubuntu.com/ubuntu bionic/universe amd64 texlive-generic-recommended all 2017.20180305-1 [15.9 kB]\n",
            "Get:42 http://archive.ubuntu.com/ubuntu bionic/main amd64 texlive-latex-base all 2017.20180305-1 [951 kB]\n",
            "Get:43 http://archive.ubuntu.com/ubuntu bionic/main amd64 texlive-latex-recommended all 2017.20180305-1 [14.9 MB]\n",
            "Get:44 http://archive.ubuntu.com/ubuntu bionic/universe amd64 texlive-pictures all 2017.20180305-1 [4,026 kB]\n",
            "Get:45 http://archive.ubuntu.com/ubuntu bionic/universe amd64 texlive-latex-extra all 2017.20180305-2 [10.6 MB]\n",
            "Get:46 http://archive.ubuntu.com/ubuntu bionic/universe amd64 tipa all 2:1.3-20 [2,978 kB]\n",
            "Get:47 http://archive.ubuntu.com/ubuntu bionic/universe amd64 texlive-xetex all 2017.20180305-1 [10.7 MB]\n",
            "Fetched 146 MB in 6s (24.9 MB/s)\n",
            "Extracting templates from packages: 100%\n",
            "Preconfiguring packages ...\n",
            "Selecting previously unselected package fonts-droid-fallback.\n",
            "(Reading database ... 155047 files and directories currently installed.)\n",
            "Preparing to unpack .../00-fonts-droid-fallback_1%3a6.0.1r16-1.1_all.deb ...\n",
            "Unpacking fonts-droid-fallback (1:6.0.1r16-1.1) ...\n",
            "Selecting previously unselected package fonts-lato.\n",
            "Preparing to unpack .../01-fonts-lato_2.0-2_all.deb ...\n",
            "Unpacking fonts-lato (2.0-2) ...\n",
            "Selecting previously unselected package poppler-data.\n",
            "Preparing to unpack .../02-poppler-data_0.4.8-2_all.deb ...\n",
            "Unpacking poppler-data (0.4.8-2) ...\n",
            "Selecting previously unselected package tex-common.\n",
            "Preparing to unpack .../03-tex-common_6.09_all.deb ...\n",
            "Unpacking tex-common (6.09) ...\n",
            "Selecting previously unselected package fonts-lmodern.\n",
            "Preparing to unpack .../04-fonts-lmodern_2.004.5-3_all.deb ...\n",
            "Unpacking fonts-lmodern (2.004.5-3) ...\n",
            "Selecting previously unselected package fonts-noto-mono.\n",
            "Preparing to unpack .../05-fonts-noto-mono_20171026-2_all.deb ...\n",
            "Unpacking fonts-noto-mono (20171026-2) ...\n",
            "Selecting previously unselected package fonts-texgyre.\n",
            "Preparing to unpack .../06-fonts-texgyre_20160520-1_all.deb ...\n",
            "Unpacking fonts-texgyre (20160520-1) ...\n",
            "Selecting previously unselected package javascript-common.\n",
            "Preparing to unpack .../07-javascript-common_11_all.deb ...\n",
            "Unpacking javascript-common (11) ...\n",
            "Selecting previously unselected package libcupsfilters1:amd64.\n",
            "Preparing to unpack .../08-libcupsfilters1_1.20.2-0ubuntu3.1_amd64.deb ...\n",
            "Unpacking libcupsfilters1:amd64 (1.20.2-0ubuntu3.1) ...\n",
            "Selecting previously unselected package libcupsimage2:amd64.\n",
            "Preparing to unpack .../09-libcupsimage2_2.2.7-1ubuntu2.8_amd64.deb ...\n",
            "Unpacking libcupsimage2:amd64 (2.2.7-1ubuntu2.8) ...\n",
            "Selecting previously unselected package libijs-0.35:amd64.\n",
            "Preparing to unpack .../10-libijs-0.35_0.35-13_amd64.deb ...\n",
            "Unpacking libijs-0.35:amd64 (0.35-13) ...\n",
            "Selecting previously unselected package libjbig2dec0:amd64.\n",
            "Preparing to unpack .../11-libjbig2dec0_0.13-6_amd64.deb ...\n",
            "Unpacking libjbig2dec0:amd64 (0.13-6) ...\n",
            "Selecting previously unselected package libgs9-common.\n",
            "Preparing to unpack .../12-libgs9-common_9.26~dfsg+0-0ubuntu0.18.04.14_all.deb ...\n",
            "Unpacking libgs9-common (9.26~dfsg+0-0ubuntu0.18.04.14) ...\n",
            "Selecting previously unselected package libgs9:amd64.\n",
            "Preparing to unpack .../13-libgs9_9.26~dfsg+0-0ubuntu0.18.04.14_amd64.deb ...\n",
            "Unpacking libgs9:amd64 (9.26~dfsg+0-0ubuntu0.18.04.14) ...\n",
            "Selecting previously unselected package libjs-jquery.\n",
            "Preparing to unpack .../14-libjs-jquery_3.2.1-1_all.deb ...\n",
            "Unpacking libjs-jquery (3.2.1-1) ...\n",
            "Selecting previously unselected package libkpathsea6:amd64.\n",
            "Preparing to unpack .../15-libkpathsea6_2017.20170613.44572-8ubuntu0.1_amd64.deb ...\n",
            "Unpacking libkpathsea6:amd64 (2017.20170613.44572-8ubuntu0.1) ...\n",
            "Selecting previously unselected package libpotrace0.\n",
            "Preparing to unpack .../16-libpotrace0_1.14-2_amd64.deb ...\n",
            "Unpacking libpotrace0 (1.14-2) ...\n",
            "Selecting previously unselected package libptexenc1:amd64.\n",
            "Preparing to unpack .../17-libptexenc1_2017.20170613.44572-8ubuntu0.1_amd64.deb ...\n",
            "Unpacking libptexenc1:amd64 (2017.20170613.44572-8ubuntu0.1) ...\n",
            "Selecting previously unselected package rubygems-integration.\n",
            "Preparing to unpack .../18-rubygems-integration_1.11_all.deb ...\n",
            "Unpacking rubygems-integration (1.11) ...\n",
            "Selecting previously unselected package ruby2.5.\n",
            "Preparing to unpack .../19-ruby2.5_2.5.1-1ubuntu1.10_amd64.deb ...\n",
            "Unpacking ruby2.5 (2.5.1-1ubuntu1.10) ...\n",
            "Selecting previously unselected package ruby.\n",
            "Preparing to unpack .../20-ruby_1%3a2.5.1_amd64.deb ...\n",
            "Unpacking ruby (1:2.5.1) ...\n",
            "Selecting previously unselected package rake.\n",
            "Preparing to unpack .../21-rake_12.3.1-1ubuntu0.1_all.deb ...\n",
            "Unpacking rake (12.3.1-1ubuntu0.1) ...\n",
            "Selecting previously unselected package ruby-did-you-mean.\n",
            "Preparing to unpack .../22-ruby-did-you-mean_1.2.0-2_all.deb ...\n",
            "Unpacking ruby-did-you-mean (1.2.0-2) ...\n",
            "Selecting previously unselected package ruby-minitest.\n",
            "Preparing to unpack .../23-ruby-minitest_5.10.3-1_all.deb ...\n",
            "Unpacking ruby-minitest (5.10.3-1) ...\n",
            "Selecting previously unselected package ruby-net-telnet.\n",
            "Preparing to unpack .../24-ruby-net-telnet_0.1.1-2_all.deb ...\n",
            "Unpacking ruby-net-telnet (0.1.1-2) ...\n",
            "Selecting previously unselected package ruby-power-assert.\n",
            "Preparing to unpack .../25-ruby-power-assert_0.3.0-1_all.deb ...\n",
            "Unpacking ruby-power-assert (0.3.0-1) ...\n",
            "Selecting previously unselected package ruby-test-unit.\n",
            "Preparing to unpack .../26-ruby-test-unit_3.2.5-1_all.deb ...\n",
            "Unpacking ruby-test-unit (3.2.5-1) ...\n",
            "Selecting previously unselected package libruby2.5:amd64.\n",
            "Preparing to unpack .../27-libruby2.5_2.5.1-1ubuntu1.10_amd64.deb ...\n",
            "Unpacking libruby2.5:amd64 (2.5.1-1ubuntu1.10) ...\n",
            "Selecting previously unselected package libsynctex1:amd64.\n",
            "Preparing to unpack .../28-libsynctex1_2017.20170613.44572-8ubuntu0.1_amd64.deb ...\n",
            "Unpacking libsynctex1:amd64 (2017.20170613.44572-8ubuntu0.1) ...\n",
            "Selecting previously unselected package libtexlua52:amd64.\n",
            "Preparing to unpack .../29-libtexlua52_2017.20170613.44572-8ubuntu0.1_amd64.deb ...\n",
            "Unpacking libtexlua52:amd64 (2017.20170613.44572-8ubuntu0.1) ...\n",
            "Selecting previously unselected package libtexluajit2:amd64.\n",
            "Preparing to unpack .../30-libtexluajit2_2017.20170613.44572-8ubuntu0.1_amd64.deb ...\n",
            "Unpacking libtexluajit2:amd64 (2017.20170613.44572-8ubuntu0.1) ...\n",
            "Selecting previously unselected package libzzip-0-13:amd64.\n",
            "Preparing to unpack .../31-libzzip-0-13_0.13.62-3.1ubuntu0.18.04.1_amd64.deb ...\n",
            "Unpacking libzzip-0-13:amd64 (0.13.62-3.1ubuntu0.18.04.1) ...\n",
            "Selecting previously unselected package lmodern.\n",
            "Preparing to unpack .../32-lmodern_2.004.5-3_all.deb ...\n",
            "Unpacking lmodern (2.004.5-3) ...\n",
            "Selecting previously unselected package preview-latex-style.\n",
            "Preparing to unpack .../33-preview-latex-style_11.91-1ubuntu1_all.deb ...\n",
            "Unpacking preview-latex-style (11.91-1ubuntu1) ...\n",
            "Selecting previously unselected package t1utils.\n",
            "Preparing to unpack .../34-t1utils_1.41-2_amd64.deb ...\n",
            "Unpacking t1utils (1.41-2) ...\n",
            "Selecting previously unselected package tex-gyre.\n",
            "Preparing to unpack .../35-tex-gyre_20160520-1_all.deb ...\n",
            "Unpacking tex-gyre (20160520-1) ...\n",
            "Selecting previously unselected package texlive-binaries.\n",
            "Preparing to unpack .../36-texlive-binaries_2017.20170613.44572-8ubuntu0.1_amd64.deb ...\n",
            "Unpacking texlive-binaries (2017.20170613.44572-8ubuntu0.1) ...\n",
            "Selecting previously unselected package texlive-base.\n",
            "Preparing to unpack .../37-texlive-base_2017.20180305-1_all.deb ...\n",
            "Unpacking texlive-base (2017.20180305-1) ...\n",
            "Selecting previously unselected package texlive-fonts-recommended.\n",
            "Preparing to unpack .../38-texlive-fonts-recommended_2017.20180305-1_all.deb ...\n",
            "Unpacking texlive-fonts-recommended (2017.20180305-1) ...\n",
            "Selecting previously unselected package texlive-plain-generic.\n",
            "Preparing to unpack .../39-texlive-plain-generic_2017.20180305-2_all.deb ...\n",
            "Unpacking texlive-plain-generic (2017.20180305-2) ...\n",
            "Selecting previously unselected package texlive-generic-recommended.\n",
            "Preparing to unpack .../40-texlive-generic-recommended_2017.20180305-1_all.deb ...\n",
            "Unpacking texlive-generic-recommended (2017.20180305-1) ...\n",
            "Selecting previously unselected package texlive-latex-base.\n",
            "Preparing to unpack .../41-texlive-latex-base_2017.20180305-1_all.deb ...\n",
            "Unpacking texlive-latex-base (2017.20180305-1) ...\n",
            "Selecting previously unselected package texlive-latex-recommended.\n",
            "Preparing to unpack .../42-texlive-latex-recommended_2017.20180305-1_all.deb ...\n",
            "Unpacking texlive-latex-recommended (2017.20180305-1) ...\n",
            "Selecting previously unselected package texlive-pictures.\n",
            "Preparing to unpack .../43-texlive-pictures_2017.20180305-1_all.deb ...\n",
            "Unpacking texlive-pictures (2017.20180305-1) ...\n",
            "Selecting previously unselected package texlive-latex-extra.\n",
            "Preparing to unpack .../44-texlive-latex-extra_2017.20180305-2_all.deb ...\n",
            "Unpacking texlive-latex-extra (2017.20180305-2) ...\n",
            "Selecting previously unselected package tipa.\n",
            "Preparing to unpack .../45-tipa_2%3a1.3-20_all.deb ...\n",
            "Unpacking tipa (2:1.3-20) ...\n",
            "Selecting previously unselected package texlive-xetex.\n",
            "Preparing to unpack .../46-texlive-xetex_2017.20180305-1_all.deb ...\n",
            "Unpacking texlive-xetex (2017.20180305-1) ...\n",
            "Setting up libgs9-common (9.26~dfsg+0-0ubuntu0.18.04.14) ...\n",
            "Setting up libkpathsea6:amd64 (2017.20170613.44572-8ubuntu0.1) ...\n",
            "Setting up libjs-jquery (3.2.1-1) ...\n",
            "Setting up libtexlua52:amd64 (2017.20170613.44572-8ubuntu0.1) ...\n",
            "Setting up fonts-droid-fallback (1:6.0.1r16-1.1) ...\n",
            "Setting up libsynctex1:amd64 (2017.20170613.44572-8ubuntu0.1) ...\n",
            "Setting up libptexenc1:amd64 (2017.20170613.44572-8ubuntu0.1) ...\n",
            "Setting up tex-common (6.09) ...\n",
            "update-language: texlive-base not installed and configured, doing nothing!\n",
            "Setting up poppler-data (0.4.8-2) ...\n",
            "Setting up tex-gyre (20160520-1) ...\n",
            "Setting up preview-latex-style (11.91-1ubuntu1) ...\n",
            "Setting up fonts-texgyre (20160520-1) ...\n",
            "Setting up fonts-noto-mono (20171026-2) ...\n",
            "Setting up fonts-lato (2.0-2) ...\n",
            "Setting up libcupsfilters1:amd64 (1.20.2-0ubuntu3.1) ...\n",
            "Setting up libcupsimage2:amd64 (2.2.7-1ubuntu2.8) ...\n",
            "Setting up libjbig2dec0:amd64 (0.13-6) ...\n",
            "Setting up ruby-did-you-mean (1.2.0-2) ...\n",
            "Setting up t1utils (1.41-2) ...\n",
            "Setting up ruby-net-telnet (0.1.1-2) ...\n",
            "Setting up libijs-0.35:amd64 (0.35-13) ...\n",
            "Setting up rubygems-integration (1.11) ...\n",
            "Setting up libpotrace0 (1.14-2) ...\n",
            "Setting up javascript-common (11) ...\n",
            "Setting up ruby-minitest (5.10.3-1) ...\n",
            "Setting up libzzip-0-13:amd64 (0.13.62-3.1ubuntu0.18.04.1) ...\n",
            "Setting up libgs9:amd64 (9.26~dfsg+0-0ubuntu0.18.04.14) ...\n",
            "Setting up libtexluajit2:amd64 (2017.20170613.44572-8ubuntu0.1) ...\n",
            "Setting up fonts-lmodern (2.004.5-3) ...\n",
            "Setting up ruby-power-assert (0.3.0-1) ...\n",
            "Setting up texlive-binaries (2017.20170613.44572-8ubuntu0.1) ...\n",
            "update-alternatives: using /usr/bin/xdvi-xaw to provide /usr/bin/xdvi.bin (xdvi.bin) in auto mode\n",
            "update-alternatives: using /usr/bin/bibtex.original to provide /usr/bin/bibtex (bibtex) in auto mode\n",
            "Setting up texlive-base (2017.20180305-1) ...\n",
            "mktexlsr: Updating /var/lib/texmf/ls-R-TEXLIVEDIST... \n",
            "mktexlsr: Updating /var/lib/texmf/ls-R-TEXMFMAIN... \n",
            "mktexlsr: Updating /var/lib/texmf/ls-R... \n",
            "mktexlsr: Done.\n",
            "tl-paper: setting paper size for dvips to a4: /var/lib/texmf/dvips/config/config-paper.ps\n",
            "tl-paper: setting paper size for dvipdfmx to a4: /var/lib/texmf/dvipdfmx/dvipdfmx-paper.cfg\n",
            "tl-paper: setting paper size for xdvi to a4: /var/lib/texmf/xdvi/XDvi-paper\n",
            "tl-paper: setting paper size for pdftex to a4: /var/lib/texmf/tex/generic/config/pdftexconfig.tex\n",
            "Setting up texlive-fonts-recommended (2017.20180305-1) ...\n",
            "Setting up texlive-plain-generic (2017.20180305-2) ...\n",
            "Setting up texlive-generic-recommended (2017.20180305-1) ...\n",
            "Setting up texlive-latex-base (2017.20180305-1) ...\n",
            "Setting up lmodern (2.004.5-3) ...\n",
            "Setting up texlive-latex-recommended (2017.20180305-1) ...\n",
            "Setting up texlive-pictures (2017.20180305-1) ...\n",
            "Setting up tipa (2:1.3-20) ...\n",
            "Regenerating '/var/lib/texmf/fmtutil.cnf-DEBIAN'... done.\n",
            "Regenerating '/var/lib/texmf/fmtutil.cnf-TEXLIVEDIST'... done.\n",
            "update-fmtutil has updated the following file(s):\n",
            "\t/var/lib/texmf/fmtutil.cnf-DEBIAN\n",
            "\t/var/lib/texmf/fmtutil.cnf-TEXLIVEDIST\n",
            "If you want to activate the changes in the above file(s),\n",
            "you should run fmtutil-sys or fmtutil.\n",
            "Setting up texlive-latex-extra (2017.20180305-2) ...\n",
            "Setting up texlive-xetex (2017.20180305-1) ...\n",
            "Setting up ruby2.5 (2.5.1-1ubuntu1.10) ...\n",
            "Setting up ruby (1:2.5.1) ...\n",
            "Setting up ruby-test-unit (3.2.5-1) ...\n",
            "Setting up rake (12.3.1-1ubuntu0.1) ...\n",
            "Setting up libruby2.5:amd64 (2.5.1-1ubuntu1.10) ...\n",
            "Processing triggers for mime-support (3.60ubuntu1) ...\n",
            "Processing triggers for libc-bin (2.27-3ubuntu1.3) ...\n",
            "/sbin/ldconfig.real: /usr/local/lib/python3.7/dist-packages/ideep4py/lib/libmkldnn.so.0 is not a symbolic link\n",
            "\n",
            "Processing triggers for man-db (2.8.3-2ubuntu0.1) ...\n",
            "Processing triggers for fontconfig (2.12.6-0ubuntu2) ...\n",
            "Processing triggers for tex-common (6.09) ...\n",
            "Running updmap-sys. This may take some time... done.\n",
            "Running mktexlsr /var/lib/texmf ... done.\n",
            "Building format(s) --all.\n",
            "\tThis may take some time... done.\n",
            "[NbConvertApp] Converting notebook /content/drive/My Drive/Colab Notebooks/CIS521__MID_CP to pdf\n",
            "[NbConvertApp] Writing 206590 bytes to ./notebook.tex\n",
            "[NbConvertApp] Building PDF\n",
            "[NbConvertApp] Running xelatex 3 times: [u'xelatex', u'./notebook.tex', '-quiet']\n",
            "[NbConvertApp] CRITICAL | xelatex failed: [u'xelatex', u'./notebook.tex', '-quiet']\n",
            "This is XeTeX, Version 3.14159265-2.6-0.99998 (TeX Live 2017/Debian) (preloaded format=xelatex)\n",
            " restricted \\write18 enabled.\n",
            "entering extended mode\n",
            "(./notebook.tex\n",
            "LaTeX2e <2017-04-15>\n",
            "Babel <3.18> and hyphenation patterns for 3 language(s) loaded.\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/base/article.cls\n",
            "Document Class: article 2014/09/29 v1.4h Standard LaTeX document class\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/base/size11.clo))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/tcolorbox/tcolorbox.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/pgf/basiclayer/pgf.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/pgf/utilities/pgfrcs.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfutil-common.tex\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfutil-common-lists.t\n",
            "ex)) (/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfutil-latex.def\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/ms/everyshi.sty))\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfrcs.code.tex))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/pgf/basiclayer/pgfcore.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/graphics/graphicx.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/graphics/keyval.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/graphics/graphics.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/graphics/trig.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/graphics-cfg/graphics.cfg)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/graphics-def/xetex.def)))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/pgf/systemlayer/pgfsys.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgfsys.code.tex\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfkeys.code.tex\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfkeysfiltered.code.t\n",
            "ex)) (/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgf.cfg)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgfsys-xetex.def\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgfsys-dvipdfmx.def\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgfsys-common-pdf.de\n",
            "f))))\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgfsyssoftpath.code.\n",
            "tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgfsysprotocol.code.\n",
            "tex)) (/usr/share/texlive/texmf-dist/tex/latex/xcolor/xcolor.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/graphics-cfg/color.cfg))\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcore.code.tex\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmath.code.tex\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathcalc.code.tex\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathutil.code.tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathparser.code.tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.code.tex\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.basic.code\n",
            ".tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.trigonomet\n",
            "ric.code.tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.random.cod\n",
            "e.tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.comparison\n",
            ".code.tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.base.code.\n",
            "tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.round.code\n",
            ".tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.misc.code.\n",
            "tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.integerari\n",
            "thmetics.code.tex)))\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfloat.code.tex))\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepoints.code.te\n",
            "x)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepathconstruct.\n",
            "code.tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepathusage.code\n",
            ".tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorescopes.code.te\n",
            "x)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoregraphicstate.c\n",
            "ode.tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoretransformation\n",
            "s.code.tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorequick.code.tex\n",
            ")\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreobjects.code.t\n",
            "ex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepathprocessing\n",
            ".code.tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorearrows.code.te\n",
            "x)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreshade.code.tex\n",
            ")\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreimage.code.tex\n",
            "\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreexternal.code.\n",
            "tex))\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorelayers.code.te\n",
            "x)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoretransparency.c\n",
            "ode.tex)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepatterns.code.\n",
            "tex)))\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/pgf/modules/pgfmoduleshapes.code.tex\n",
            ") (/usr/share/texlive/texmf-dist/tex/generic/pgf/modules/pgfmoduleplot.code.tex\n",
            ")\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/pgf/compatibility/pgfcomp-version-0-65\n",
            ".sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/pgf/compatibility/pgfcomp-version-1-18\n",
            ".sty)) (/usr/share/texlive/texmf-dist/tex/latex/tools/verbatim.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/environ/environ.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/trimspaces/trimspaces.sty))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/etoolbox/etoolbox.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/tcolorbox/tcbbreakable.code.tex\n",
            "Library (tcolorbox): 'tcbbreakable.code.tex' version '4.12'\n",
            ")) (/usr/share/texlive/texmf-dist/tex/latex/float/float.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/base/fontenc.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/base/t1enc.def)\n",
            "(/usr/share/texmf/tex/latex/lm/t1lmr.fd))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/psnfss/mathpazo.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/caption/caption.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/caption/caption3.sty))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/adjustbox/adjustbox.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/xkeyval/xkeyval.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/xkeyval/xkeyval.tex\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/xkeyval/xkvutils.tex)))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/adjustbox/adjcalc.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/adjustbox/trimclip.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/collectbox/collectbox.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/adjustbox/tc-xetex.def))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/ifoddpage/ifoddpage.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/varwidth/varwidth.sty))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/tools/enumerate.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/geometry/geometry.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/ifpdf.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/ifvtex.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/ifxetex/ifxetex.sty))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsmath.sty\n",
            "For additional information on amsmath, use the `?' option.\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amstext.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsgen.sty))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsbsy.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsopn.sty))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amssymb.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amsfonts.sty))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/base/textcomp.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/base/ts1enc.def))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/upquote/upquote.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/eurosym/eurosym.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/ucs/ucs.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/ucs/data/uni-global.def))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty\n",
            "\n",
            "Package inputenc Warning: inputenc package ignored with utf8 based engines.\n",
            "\n",
            ") (/usr/share/texlive/texmf-dist/tex/latex/fancyvrb/fancyvrb.sty\n",
            "Style option: `fancyvrb' v2.7a, with DG/SPQR fixes, and firstline=lastline fix \n",
            "<2008/02/07> (tvz))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/oberdiek/grffile.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/oberdiek/kvoptions.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/ltxcmds.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/kvsetkeys.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/infwarerr.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/etexcmds.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/ifluatex.sty))))\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/pdftexcmds.sty))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/hyperref/hyperref.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/hobsub-hyperref.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/hobsub-generic.sty))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/oberdiek/auxhook.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/hyperref/pd1enc.def)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/latexconfig/hyperref.cfg)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/url/url.sty))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/hyperref/hxetex.def\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/hyperref/puenc.def)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/stringenc.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/oberdiek/rerunfilecheck.sty))\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/tools/longtable.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/booktabs/booktabs.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/enumitem/enumitem.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/ulem/ulem.sty)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/jknapltx/mathrsfs.sty)\n",
            "No file notebook.aux.\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/base/ts1cmr.fd)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/psnfss/t1ppl.fd)\n",
            "ABD: EveryShipout initializing macros\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/caption/ltcaption.sty)\n",
            "*geometry* driver: auto-detecting\n",
            "*geometry* detected driver: xetex\n",
            "*geometry* verbose mode - [ preamble ] result:\n",
            "* driver: xetex\n",
            "* paper: <default>\n",
            "* layout: <same size as paper>\n",
            "* layoutoffset:(h,v)=(0.0pt,0.0pt)\n",
            "* modes: \n",
            "* h-part:(L,W,R)=(72.26999pt, 469.75502pt, 72.26999pt)\n",
            "* v-part:(T,H,B)=(72.26999pt, 650.43001pt, 72.26999pt)\n",
            "* \\paperwidth=614.295pt\n",
            "* \\paperheight=794.96999pt\n",
            "* \\textwidth=469.75502pt\n",
            "* \\textheight=650.43001pt\n",
            "* \\oddsidemargin=0.0pt\n",
            "* \\evensidemargin=0.0pt\n",
            "* \\topmargin=-37.0pt\n",
            "* \\headheight=12.0pt\n",
            "* \\headsep=25.0pt\n",
            "* \\topskip=11.0pt\n",
            "* \\footskip=30.0pt\n",
            "* \\marginparwidth=59.0pt\n",
            "* \\marginparsep=10.0pt\n",
            "* \\columnsep=10.0pt\n",
            "* \\skip\\footins=10.0pt plus 4.0pt minus 2.0pt\n",
            "* \\hoffset=0.0pt\n",
            "* \\voffset=0.0pt\n",
            "* \\mag=1000\n",
            "* \\@twocolumnfalse\n",
            "* \\@twosidefalse\n",
            "* \\@mparswitchfalse\n",
            "* \\@reversemarginfalse\n",
            "* (1in=72.27pt=25.4mm, 1cm=28.453pt)\n",
            "\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/ucs/ucsencs.def)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/hyperref/nameref.sty\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/gettitlestring.sty))\n",
            "\n",
            "Package hyperref Warning: Rerun to get /PageLabels entry.\n",
            "\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/psnfss/ot1ppl.fd)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/psnfss/omlzplm.fd)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/psnfss/omszplm.fd)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/psnfss/omxzplm.fd)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/psnfss/ot1zplm.fd)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/jknapltx/ursfs.fd)\n",
            "\n",
            "LaTeX Warning: No \\author given.\n",
            "\n",
            "(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/se-ascii-print.def)\n",
            "(/usr/share/texlive/texmf-dist/tex/latex/psnfss/ts1ppl.fd)\n",
            "Underfull \\hbox (badness 10000) in paragraph at lines 416--420\n",
            "\n",
            "\n",
            "Underfull \\hbox (badness 10000) in paragraph at lines 420--423\n",
            "\n",
            "[1] (/usr/share/texmf/tex/latex/lm/t1lmtt.fd)\n",
            "(/usr/share/texmf/tex/latex/lm/ts1lmtt.fd)\n",
            "Overfull \\vbox (6.0pt too high) has occurred while \\output is active [2]\n",
            "[3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18]\n",
            "[19] [20] [21] [22] [23] [24] [25] [26]\n",
            "! Missing $ inserted.\n",
            "<inserted text> \n",
            "                $\n",
            "l.1786 \\textbf{\\$ \\alpha-\\beta\\$ pruning}\n",
            "                                         :\n",
            "? \n",
            "! Emergency stop.\n",
            "<inserted text> \n",
            "                $\n",
            "l.1786 \\textbf{\\$ \\alpha-\\beta\\$ pruning}\n",
            "                                         :\n",
            "Output written on notebook.pdf (26 pages).\n",
            "Transcript written on notebook.log.\n",
            "\n",
            "[NbConvertApp] PDF successfully created\n",
            "[NbConvertApp] Writing 111914 bytes to /content/drive/My Drive/CIS521__MID_C.pdf\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'File Download Unsuccessful. Saved in Google Drive'"
            ]
          },
          "metadata": {},
          "execution_count": 64
        }
      ]
    }
  ]
}