{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "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": "76680eb8-ca17-451a-87be-7b5e593ec8ed"
      },
      "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": "332464dc-a0a2-41ff-d5ff-e0a7fc17bad5"
      },
      "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 = False"
      ],
      "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 = \"\"\"the standard model is study and construction of agents that do the\n",
        "right thing.\"\"\" \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 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" can machines really think? qualia: intrinsic nature of experiences\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" \"\"\"\n",
        "chapter2_2 = \"\"\" In AI, we use consequentialism: evaluate an agent's behavior by its consequences.\n",
        "Should design performance measures based on what we want to be achieved in the\n",
        "environment rather than according to how we think the agent should behave\"\"\"\n",
        "chapter2_3 = \"\"\"Rationality depends on four factors: (1) Performance measure\n",
        "(2) Agent's prior knowledge of the environment\n",
        "(3) Possible actions that the agent can perform\n",
        "(4) Percept sequence so far\n",
        "\n",
        "Rationality is not the same thing as omniscience.\n",
        "Rational agents need to be able to both gather information and learn from\n",
        "what it perceives, i.e. should be autonomous.\n",
        "\n",
        " Competitive vs. cooperative multiagent environments\n",
        "episodic (current decisions don't affect next episode) vs. sequential\n",
        "static (env cannot change while agent is deliberating) vs. dynamic\"\"\"\n",
        "chapter2_4 = \"\"\"model-based agent: uses transition model & sensor\n",
        "utility function internalizes perfrmance measure\n",
        "simple reflex agents respond directly (and only) to percepts\n",
        "goal-based agents have a goal to achieve\n",
        "utility-based agents aim to maximize utility\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"An agent is anything that:\n",
        "perceives its environment through sensors and\n",
        "can act on its environment through actuators\n",
        "- Percept = agent’s perceptual inputs at any given instance\n",
        "- Agent function f: maps sequence of percept vectors P to an action a from a set A\n",
        "- Agent program: runs on the physical architecture to produce f\n",
        "\n",
        "Rational agent:\n",
        "- For each possible percept sequence P\n",
        "- A rational agent selects an action a\n",
        "- To maximize expected value of its performance measure\n",
        "- (given perecept sequence and built-in knowledge)\n",
        "\n",
        "Performance measure: objective criterion for success of an agent’s behavior\n",
        "\n",
        "Task environment: problem specification for which the agent is a solution (PEAS)\n",
        "- Performance measure\n",
        "- Environment\n",
        "- Actuators\n",
        "- Sensors\n",
        "\n",
        "Reflex agent selects action based on current percept, ignores percept history. \n",
        "\n",
        "Problem-solving agent must plan ahead.\n",
        "\n",
        "Randomized behavior can be rational in some environments\n",
        "\"\"\"\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",
        "\"deterministic\" : \"next state determined by current state + action\",\n",
        "\"stochastic\" : \"nondeterministic with explicit probabilities\",\n",
        "\"actuator\" : \"the means by which the agent acts on its environment\",\n",
        "\"Percept sequence\" : \"agen'ts complete history of everything it has ever perceived\"\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": 1000
        },
        "cellView": "form",
        "outputId": "40b15ad7-8574-47f1-a84f-c9a90aaea7e0"
      },
      "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?\nthe standard model is study and construction of agents that do the\nright thing.\n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n can machines really think? qualia: intrinsic nature of experiences\n\n## AIMA 2.1 Agents and Environments\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n In AI, we use consequentialism: evaluate an agent's behavior by its consequences.\nShould design performance measures based on what we want to be achieved in the\nenvironment rather than according to how we think the agent should behave\n\n## AIMA 2.3 The Nature of Environments\nRationality depends on four factors: (1) Performance measure\n(2) Agent's prior knowledge of the environment\n(3) Possible actions that the agent can perform\n(4) Percept sequence so far\n\nRationality is not the same thing as omniscience.\nRational agents need to be able to both gather information and learn from\nwhat it perceives, i.e. should be autonomous.\n\n Competitive vs. cooperative multiagent environments\nepisodic (current decisions don't affect next episode) vs. sequential\nstatic (env cannot change while agent is deliberating) vs. dynamic\n\n## AIMA 2.4 The Structure of Agents\nmodel-based agent: uses transition model & sensor\nutility function internalizes perfrmance measure\nsimple reflex agents respond directly (and only) to percepts\ngoal-based agents have a goal to achieve\nutility-based agents aim to maximize utility\n\n## Module 1 Lecture Notes\nAn agent is anything that:\nperceives its environment through sensors and\ncan act on its environment through actuators\n- Percept = agent’s perceptual inputs at any given instance\n- Agent function f: maps sequence of percept vectors P to an action a from a set A\n- Agent program: runs on the physical architecture to produce f\n\nRational agent:\n- For each possible percept sequence P\n- A rational agent selects an action a\n- To maximize expected value of its performance measure\n- (given perecept sequence and built-in knowledge)\n\nPerformance measure: objective criterion for success of an agent’s behavior\n\nTask environment: problem specification for which the agent is a solution (PEAS)\n- Performance measure\n- Environment\n- Actuators\n- Sensors\n\nReflex agent selects action based on current percept, ignores percept history. \n\nProblem-solving agent must plan ahead.\n\nRandomized behavior can be rational in some environments\n\n\n## Module 1 Definitions\n* **Deterministic** - next state determined by current state + action\n* **Stochastic** - nondeterministic with explicit probabilities\n* **Actuator** - the means by which the agent acts on its environment\n* **Percept sequence** - agen'ts complete history of everything it has ever perceived\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 = \"\"\"\n",
        "- All data treated as objects\n",
        "- Strong typing: every object has a fixed type\n",
        "--type(object)\n",
        "--isinstance(object, type)\n",
        "-Dynamic typing: variable comes into existence when first assigned. \n",
        "If assigned again, type is updated. Functions have no type signatures.\n",
        "-Python uses dynamic typing.\n",
        "-No ++ or --\n",
        "-== checks objects of same value\n",
        "-is checks point to same object\n",
        "-Tuples and strings are immutable. Lists are mutable. Tuples and lists can have multiple types. You can slice all 3 types\n",
        "of sequences.\n",
        "- Keys in dict are immutable. .keys(), .values(), .items() [returns tuples]\n",
        "- Defaultdict imported from collections, initializes nonexistent dict values\n",
        "- No function overloading in Python\n",
        "- Keyword arguments can be used after other args\n",
        "- *args allows you to accept a variable number of non-kwargs\n",
        "- **kwargs allows the samne for kwargs. comes after *args\n",
        "- dynamic scope: functions see most current value of variables\n",
        "- functions are first-class\n",
        "- classes: __init__ instatiates. every method begins with (slf).\n",
        "- subclass: name of superclass as arg to class def'n\n",
        "- magic methods: init, len, copy, cmp, add, neg\n",
        "- list comprehension: [x for x in y if z]\n",
        "- set & dict comprehension\n",
        "- i = iter(k) creates iterator\n",
        "- yield: automatically return a generator when called. Crucial for processing infinite list\n",
        "- Will have key error if try to remove something not in the set\n",
        "- Cannot use + to concatenate dicts\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": 651
        },
        "outputId": "78b1e155-5457-4c49-c284-9b500ae57205"
      },
      "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- All data treated as objects\n- Strong typing: every object has a fixed type\n--type(object)\n--isinstance(object, type)\n-Dynamic typing: variable comes into existence when first assigned. \nIf assigned again, type is updated. Functions have no type signatures.\n-Python uses dynamic typing.\n-No ++ or --\n-== checks objects of same value\n-is checks point to same object\n-Tuples and strings are immutable. Lists are mutable. Tuples and lists can have multiple types. You can slice all 3 types\nof sequences.\n- Keys in dict are immutable. .keys(), .values(), .items() [returns tuples]\n- Defaultdict imported from collections, initializes nonexistent dict values\n- No function overloading in Python\n- Keyword arguments can be used after other args\n- *args allows you to accept a variable number of non-kwargs\n- **kwargs allows the samne for kwargs. comes after *args\n- dynamic scope: functions see most current value of variables\n- functions are first-class\n- classes: __init__ instatiates. every method begins with (slf).\n- subclass: name of superclass as arg to class def'n\n- magic methods: init, len, copy, cmp, add, neg\n- list comprehension: [x for x in y if z]\n- set & dict comprehension\n- i = iter(k) creates iterator\n- yield: automatically return a generator when called. Crucial for processing infinite list\n- Will have key error if try to remove something not in the set\n- Cannot use + to concatenate dicts\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_4 = \"\"\" \n",
        "- Uniform-cost search is uninformed. Djikstra's \n",
        "is the same thing (no goal)\n",
        "- Bidirectonal search: searches forward from s_i and backwards from goal state(s).\n",
        "There are many versions of this. Is complete and optimal, if applicable at all. \n",
        "TC = O(b^{d/2}), SC = O(b^{d/2})\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "### Search Problems\n",
        "- Agents that perform search are called “Problem-solving agents”\n",
        "    - Plan ahead: computational process is called search\n",
        "    - Consider sequence of actions (solution) that form path to goal state\n",
        "- Reflex agents: \n",
        "    - selects action only based on current percept\n",
        "    - Ignores rest of percept history\n",
        "- 8-Puzzle example: \n",
        "    - Puzzles are deterministic and known\n",
        "    - Formulate goal, search problem and solution\n",
        "    - Search problem:\n",
        "        - States: configurations of puzzle\n",
        "        - Actions: Move one of movable pieces\n",
        "        - Performance measure: Minimize total moves\n",
        "    - Solution: sequence of pieces moved\n",
        "- Holiday in Romania example:\n",
        "    - Goal: Be in Bucharest\n",
        "    - Search Problem:\n",
        "        - States: various cities\n",
        "        - Actions: drive between cities:\n",
        "        - Performance measure: minimize travel time/distance\n",
        "    - Solution: sequence of cities\n",
        "### Formulating search problem\n",
        "1. States: a set S\n",
        "2. Initial state: s_i\n",
        "3. Actions: a set A, for all s in Actions(s) = the set of actions that can be\n",
        "executed in s that are applicable in s\n",
        "4. Transition Model: Function that maps (s, a) --> s_r, where s_r is a \n",
        "successor of s. {s_i} U Successors(s_i) = state space \n",
        "5. Path cost (performance measure): must be additive, c(x, a, y) is step cost\n",
        "6. Goal cost: Goal(s) is true if s is a goal state\n",
        "\n",
        "Think of it this way:\n",
        "- Which properties matter: initial state, goal state, intermediate states\n",
        "- Which actions are possible: operator set—actions & transition model\n",
        "- Which action is next: path cost\n",
        "\n",
        "Useful concepts:\n",
        "- State space: set of all states rechable from initial state by any sequence\n",
        "- Path: sequence of actions leading from one state s_j to another state s_k\n",
        "- Frontier: those states that are available for expanding (applying legal actions to)\n",
        "- Solution: path from initial states s_i to state s_f that satisfies goal test\n",
        "\n",
        "### Algos\n",
        "BFS: \n",
        "- Expand shallowest unexpanded node\n",
        "- Use a FIFO queue, put successors at the end of frontier successor list \n",
        "- Complete, optimal, TC: O(bd), SC: O(bd) [not good], where:\n",
        "    - B = max branching factor of search tree\n",
        "    - D = depth of least cost solution\n",
        "    - M = max depth of state space\n",
        "    - Use if possible infinite paths\n",
        "\n",
        "DFS:\n",
        "- Expand deepest unexpanded node\n",
        "- Frontier is LIFO queue\n",
        "- Not complete (bc infinite paths), Not optimal, TC: O(bm) [terrible], SC: O(b*m)\n",
        "- Use if space is restricted\n",
        "\n",
        "Depth-limited search:\n",
        "- DFS with depth limit l, where nodes at depth l have no successors\n",
        "- Complete if d<= l, optimal if d>= l, TC: O(bl), SC: O(bl)\n",
        "\n",
        "Iterative deepening search:\n",
        "- Helps find best depth limit l\n",
        "- Use Depth-limited search as subroutine with increasing l\n",
        "- Complete, optimal if step/edge cost is 1 (finds goal at d), TC: O(bd), SC: O(bd)\n",
        "\"\"\"\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",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "fae7dba2-af07-4e64-d602-d084712e3c8f"
      },
      "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 Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n- Uniform-cost search is uninformed. Djikstra's \nis the same thing (no goal)\n- Bidirectonal search: searches forward from s_i and backwards from goal state(s).\nThere are many versions of this. Is complete and optimal, if applicable at all. \nTC = O(b^{d/2}), SC = O(b^{d/2})\n\n\n## Module 3 Lecture Notes\n\n### Search Problems\n- Agents that perform search are called “Problem-solving agents”\n    - Plan ahead: computational process is called search\n    - Consider sequence of actions (solution) that form path to goal state\n- Reflex agents: \n    - selects action only based on current percept\n    - Ignores rest of percept history\n- 8-Puzzle example: \n    - Puzzles are deterministic and known\n    - Formulate goal, search problem and solution\n    - Search problem:\n        - States: configurations of puzzle\n        - Actions: Move one of movable pieces\n        - Performance measure: Minimize total moves\n    - Solution: sequence of pieces moved\n- Holiday in Romania example:\n    - Goal: Be in Bucharest\n    - Search Problem:\n        - States: various cities\n        - Actions: drive between cities:\n        - Performance measure: minimize travel time/distance\n    - Solution: sequence of cities\n### Formulating search problem\n1. States: a set S\n2. Initial state: s_i\n3. Actions: a set A, for all s in Actions(s) = the set of actions that can be\nexecuted in s that are applicable in s\n4. Transition Model: Function that maps (s, a) --> s_r, where s_r is a \nsuccessor of s. {s_i} U Successors(s_i) = state space \n5. Path cost (performance measure): must be additive, c(x, a, y) is step cost\n6. Goal cost: Goal(s) is true if s is a goal state\n\nThink of it this way:\n- Which properties matter: initial state, goal state, intermediate states\n- Which actions are possible: operator set—actions & transition model\n- Which action is next: path cost\n\nUseful concepts:\n- State space: set of all states rechable from initial state by any sequence\n- Path: sequence of actions leading from one state s_j to another state s_k\n- Frontier: those states that are available for expanding (applying legal actions to)\n- Solution: path from initial states s_i to state s_f that satisfies goal test\n\n### Algos\nBFS: \n- Expand shallowest unexpanded node\n- Use a FIFO queue, put successors at the end of frontier successor list \n- Complete, optimal, TC: O(bd), SC: O(bd) [not good], where:\n    - B = max branching factor of search tree\n    - D = depth of least cost solution\n    - M = max depth of state space\n    - Use if possible infinite paths\n\nDFS:\n- Expand deepest unexpanded node\n- Frontier is LIFO queue\n- Not complete (bc infinite paths), Not optimal, TC: O(bm) [terrible], SC: O(b*m)\n- Use if space is restricted\n\nDepth-limited search:\n- DFS with depth limit l, where nodes at depth l have no successors\n- Complete if d<= l, optimal if d>= l, TC: O(bl), SC: O(bl)\n\nIterative deepening search:\n- Helps find best depth limit l\n- Use Depth-limited search as subroutine with increasing l\n- Complete, optimal if step/edge cost is 1 (finds goal at d), TC: O(bd), SC: O(bd)\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\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 = \"\"\" Path costs are monotonic. A* with consistent heuristic is optimally \n",
        "efficient. Prunes away nodes that are unnecessary.Beam search limits size of frontier or keeps nodes with scores \n",
        "within a delta to conseve memory usage. Can also use iterative-deepening A* search\n",
        "or recursive best-first search. Bidirectional search can be but is often not more efficient\n",
        "than unidirectional search.\"\"\"\n",
        "chapter3_6 = \"\"\"Effective branching factor b* can represent quality of a heuristic, \n",
        "where b* is the branching factor that a uniform tree of depth d would need to contain\n",
        "N+1 nodes, and d is the depth of the solution. Good heuristic would have b* close to 1.\n",
        "Domination means more efficient. Cost of optimal sol'n to relaxed version of problem\n",
        "P or to subproblem is always admissible heuristic for P. Can use landmarks\n",
        "for differential heuristic.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "### Uniform Cost Search (also uninformed)\n",
        "- For weighted graphs\n",
        "- g(N): path cost function, adds cost of the path up to that node\n",
        "- Extension of BFS, expand node with lowest path cost\n",
        "- Frontier = priority queue ordered by g(n)\n",
        "- Tests if node is goal state when selected for expansion, not when added to frontier\n",
        "- Complete, optimal\n",
        "- Dijkstra’s algo is UCS without a goal\n",
        "### Heuristic Functions\n",
        "- Imagine we had a table of distances (that is an approximation, not the actual distance)\n",
        "- h(n) takes a state n and returns an estimate of the distance from n to the goal\n",
        "### Greedy best-first search\n",
        "- Select node for expansion with minimal evaluation function f(n)\n",
        "- f(n) = estimate heuristic h(n)\n",
        "- Do UCS with f(n) = h(n) instead of g(n)\n",
        "- Not optimal, doesn’t always find the shortest path\n",
        "- Not complete, can get stuck in loops\n",
        "\n",
        "`frontier = pq`\n",
        "`frontier.put(start, 0)`\n",
        "`came_from = {}`\n",
        "`came_from[start] = None`\n",
        "`while not frontier.empty(): get current; break if goal; for next in neighbors`\n",
        "`if next not in came_from: p = heurstic(goal, next); frontier.put(next, prority);\n",
        "came_from[next] = current`\n",
        "\n",
        "### A* search\n",
        "- f(n) = g(n) + h(n)\n",
        "    - g(n) = actual cost (so far) to reach node\n",
        "    - h(n) = estimated cost to get from the node to the goal\n",
        "    - f(n) = estimated total cost of path through n to goal\n",
        "- h(n) needs to be admissible:\n",
        "    - Never overestimates the cost to reach the goal (optimistic)\n",
        "    - Heuristics slow down bad plans but never break optimality\n",
        "    - The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n",
        "- Dominance:\n",
        "    - If h2(n) \\geq h1(n) for all n (and both are admissible) then h2 dominates h1\n",
        "    - Best admissible heuristic is true, worst is 0 (teleportation)\n",
        "- Proof that A* is optimal\n",
        "- A* has space complexity O(b^d) [like BFS]\n",
        "    - Can be lower if has a better heuristic\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "93fe7d39-4d8d-4430-aae5-56dbc1377985"
      },
      "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\", module4_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 Path costs are monotonic. A* with consistent heuristic is optimally \nefficient. Prunes away nodes that are unnecessary.Beam search limits size of frontier or keeps nodes with scores \nwithin a delta to conseve memory usage. Can also use iterative-deepening A* search\nor recursive best-first search. Bidirectional search can be but is often not more efficient\nthan unidirectional search.\n\n## AIMA Chapter 3.6 Heuristic Functions\nEffective branching factor b* can represent quality of a heuristic, \nwhere b* is the branching factor that a uniform tree of depth d would need to contain\nN+1 nodes, and d is the depth of the solution. Good heuristic would have b* close to 1.\nDomination means more efficient. Cost of optimal sol'n to relaxed version of problem\nP or to subproblem is always admissible heuristic for P. Can use landmarks\nfor differential heuristic.\n\n## Module 4 Lecture Notes\n \n### Uniform Cost Search (also uninformed)\n- For weighted graphs\n- g(N): path cost function, adds cost of the path up to that node\n- Extension of BFS, expand node with lowest path cost\n- Frontier = priority queue ordered by g(n)\n- Tests if node is goal state when selected for expansion, not when added to frontier\n- Complete, optimal\n- Dijkstra’s algo is UCS without a goal\n### Heuristic Functions\n- Imagine we had a table of distances (that is an approximation, not the actual distance)\n- h(n) takes a state n and returns an estimate of the distance from n to the goal\n### Greedy best-first search\n- Select node for expansion with minimal evaluation function f(n)\n- f(n) = estimate heuristic h(n)\n- Do UCS with f(n) = h(n) instead of g(n)\n- Not optimal, doesn’t always find the shortest path\n- Not complete, can get stuck in loops\n\n`frontier = pq`\n`frontier.put(start, 0)`\n`came_from = {}`\n`came_from[start] = None`\n`while not frontier.empty(): get current; break if goal; for next in neighbors`\n`if next not in came_from: p = heurstic(goal, next); frontier.put(next, prority);\ncame_from[next] = current`\n\n### A* search\n- f(n) = g(n) + h(n)\n    - g(n) = actual cost (so far) to reach node\n    - h(n) = estimated cost to get from the node to the goal\n    - f(n) = estimated total cost of path through n to goal\n- h(n) needs to be admissible:\n    - Never overestimates the cost to reach the goal (optimistic)\n    - Heuristics slow down bad plans but never break optimality\n    - The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n- Dominance:\n    - If h2(n) \\geq h1(n) for all n (and both are admissible) then h2 dominates h1\n    - Best admissible heuristic is true, worst is 0 (teleportation)\n- Proof that A* is optimal\n- A* has space complexity O(b^d) [like BFS]\n    - Can be lower if has a better heuristic\n\n\n \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 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_2 = \"\"\" Effectiveness of a-b pruning depends on order of examination.\n",
        "Can use iterative deepening, rank moves based on evaluations one ply at a time.\n",
        "\n",
        "Type A strategy: wide but shallow\n",
        "Type B strategy: deep but narrow \"\"\"\n",
        "chapter5_3 = \"\"\" \n",
        "- Can apply evaluation function to states\n",
        "and cut off search when appropriate. Eval function applies only\n",
        "to quiescent positions (no upcoming move will make a big difference \n",
        "in evaluation), may have to do quiescence search\n",
        "- Forward pruning: prunes moves that appear to be bad, can use beam search\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" axioms of utility theory: orderability, transivity, continuity, substitutability,\n",
        "monotonicity, decomposability (compound lotteries are reducible) \"\"\"\n",
        "chapter16_3 = \"\"\" Utility function is a map from a lottery to R. can be hard\n",
        "to figure out what people's preferences actually are. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "### Game Formulatin, Game Trees\n",
        "- Simplest Game Environment:\n",
        "    - Multiagent\n",
        "    - Static: No change while agent is deliberating\n",
        "    - Discrete, Fully Observable Strategic\n",
        "- Our games:\n",
        "    - Two players alternate moves (max & min, max moves first)\n",
        "        - Root is labelled MAX\n",
        "    - Zero-sum\n",
        "    - Clear set of legal moves\n",
        "    - Well-defined outcomes\n",
        "- Game as search: \n",
        "    - Initial state: board configuration of chess\n",
        "    - Successor function: list of (move, state) pairs specifying legal moves\n",
        "    - Terminal test: is the game finished?\n",
        "    - Utility function: gives numerical value of terminal states\n",
        "    - MAX uses search tree to determine next move\n",
        "- Game Tree:\n",
        "    - Ply = tree level\n",
        "    - Nodes represent ‘board positions’: edges represent legal moves. Root node is first position in which decision must be made.\n",
        "    - Evaluation function f assigns real-number scores to `board positions’ w/o reference to path\n",
        "        - Based on static features of board alone\n",
        "        - f(n) > 0 if MAX winning in position n\n",
        "    - Terminal nodes labeled with desirability\n",
        "\n",
        "### Minimax and Alpha-Beta Pruning\n",
        "    - Procedure: until game is over\n",
        "    - Start with current position as a MAX node\n",
        "    - Expand game tree as a fixed number of ply\n",
        "    - Apply the evaluation function to the leaf positions\n",
        "    - Calculate back-up values bottom-up\n",
        "    - Pick the move assigned to MAX at the root\n",
        "    - Wait for MIN to respond\n",
        "\n",
        "def max-value(state): if the state is a terminatal state, return\n",
        "utility; initalize v = -inf; for each successor: v = max(v, min-val(succ)); return v\n",
        "\n",
        "Two additional values:\n",
        "- Alpha: max’s current lower bound on max’s outcome, aka max’s best already explored option on path to root\n",
        "- Beta: min’s current upper bound on min’s outcome, aka min’s best already explored option on path to root\n",
        "- Stop evaluating a branch whenever value greater than beta (for min) or less than alpha (for max) is found\n",
        "- Node values are passed back up the tree instead of values alpha and beta\n",
        "- Only pass alpha, beta values to child nodes\n",
        "- Alpha >= beta → prune (should always have alpha <= beta)\n",
        "\n",
        "### Expectimax:\n",
        "If next agent is EXP: return def exp-value(state) where\n",
        "\n",
        "def exp-value(state):\n",
        "  initialize v = 0; for each succ: p = probability(succ), v += p * value(succ); return v\n",
        "\n",
        " \"\"\"\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": 1000
        },
        "outputId": "2560bbde-abe5-4daa-e67c-6d5198744c65"
      },
      "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 Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Effectiveness of a-b pruning depends on order of examination.\nCan use iterative deepening, rank moves based on evaluations one ply at a time.\n\nType A strategy: wide but shallow\nType B strategy: deep but narrow \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \n- Can apply evaluation function to states\nand cut off search when appropriate. Eval function applies only\nto quiescent positions (no upcoming move will make a big difference \nin evaluation), may have to do quiescence search\n- Forward pruning: prunes moves that appear to be bad, can use beam search\n\n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n axioms of utility theory: orderability, transivity, continuity, substitutability,\nmonotonicity, decomposability (compound lotteries are reducible) \n\n## AIMA Chapter 16.3 Utility Functions\n Utility function is a map from a lottery to R. can be hard\nto figure out what people's preferences actually are. \n\n## Module 5 Lecture Notes\n \n### Game Formulatin, Game Trees\n- Simplest Game Environment:\n    - Multiagent\n    - Static: No change while agent is deliberating\n    - Discrete, Fully Observable Strategic\n- Our games:\n    - Two players alternate moves (max & min, max moves first)\n        - Root is labelled MAX\n    - Zero-sum\n    - Clear set of legal moves\n    - Well-defined outcomes\n- Game as search: \n    - Initial state: board configuration of chess\n    - Successor function: list of (move, state) pairs specifying legal moves\n    - Terminal test: is the game finished?\n    - Utility function: gives numerical value of terminal states\n    - MAX uses search tree to determine next move\n- Game Tree:\n    - Ply = tree level\n    - Nodes represent ‘board positions’: edges represent legal moves. Root node is first position in which decision must be made.\n    - Evaluation function f assigns real-number scores to `board positions’ w/o reference to path\n        - Based on static features of board alone\n        - f(n) > 0 if MAX winning in position n\n    - Terminal nodes labeled with desirability\n\n### Minimax and Alpha-Beta Pruning\n    - Procedure: until game is over\n    - Start with current position as a MAX node\n    - Expand game tree as a fixed number of ply\n    - Apply the evaluation function to the leaf positions\n    - Calculate back-up values bottom-up\n    - Pick the move assigned to MAX at the root\n    - Wait for MIN to respond\n\ndef max-value(state): if the state is a terminatal state, return\nutility; initalize v = -inf; for each successor: v = max(v, min-val(succ)); return v\n\nTwo additional values:\n- Alpha: max’s current lower bound on max’s outcome, aka max’s best already explored option on path to root\n- Beta: min’s current upper bound on min’s outcome, aka min’s best already explored option on path to root\n- Stop evaluating a branch whenever value greater than beta (for min) or less than alpha (for max) is found\n- Node values are passed back up the tree instead of values alpha and beta\n- Only pass alpha, beta values to child nodes\n- Alpha >= beta → prune (should always have alpha <= beta)\n\n### Expectimax:\nIf next agent is EXP: return def exp-value(state) where\n\ndef exp-value(state):\n  initialize v = 0; for each succ: p = probability(succ), v += p * value(succ); return v\n\n \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 = \"\"\" \n",
        "CSP = (X, D, C) where X: set of variables, D: set of domains for each variable,\n",
        "C: set of constraints (scope, relation)\n",
        "- unary constraint: restricts single variable value\n",
        "- global constraint: arbitrary number of variables\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "- Constraint propogation reduces number of values for variable using constraints\n",
        "- k-consistency: consistent value can be assigned to kth variable\n",
        "- strongly k-consistent: consistent for all j up to k\n",
        "- resource constraint: at most\n",
        "- bounds propagation\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" Backtracking search\n",
        "- Minimum remaining values heuristic: choose var with fewest legal values\n",
        "- Degree heuristic: select variable with most constraints on other unassigned vars\n",
        "- Least-constraining value: value that rules out fewest choices for neighboring vars\n",
        "Variable selection is fail-first (backtrack less), but value selection is fail-last (only need one solutoin)\n",
        "\n",
        "Inference:\n",
        "- Forward checking: when X is assigned a vlue, then for each unassigned var Y that X\n",
        "has a constraint with, delete inconsistent values from Y\n",
        "- Maintaining arc consistency: after variable X_i is assigned a value, \n",
        "call AC-3 for the arcs that contain X_i and its neighbors. assigns variables in backtracking search.\n",
        "\n",
        "- Backtrack to most recent preceding variable = chronological backtracking\n",
        "- backjumping is backtracing to most recent assignment in conflict set,\n",
        "which are the assignments that conflict with some value for SA\n",
        "- conflict-directed backjumping\n",
        "- constraing learning: find min set of vars from conflict set that causes problem\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" Min-conflicts heuristic: pick what leads to fewest conflicts \n",
        "Constraint weighting \"\"\"\n",
        "chapter6_5 = \"\"\" \n",
        "Independent subproblems are separate CC's\n",
        "Can use toposort on a tree constraint graph and choose\n",
        "any remaining value. (O(nd^2)), d is size of largest domain\n",
        "- cutset conditioning: assign value so that remaining vars are a tree, O(d^c (n-c)d^2)\n",
        "- tree decomposition: each node in tree contains set of nodes. O(nd^(w+1))\n",
        "where w is minimum width (one less than size of largest node) of tree components\n",
        "- Value symmetry: can intrduce symmetry-breaking conostraint, like NT <SA < WA\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "### CSP Overview\n",
        "- Finite set of variables, nonempty domain of possible values for each variable, finite set of constraints\n",
        "- Consistent = assignment does not violate the constraints\n",
        "- Complete = every variable is assigned a value\n",
        "- Solution = complete, consistent assignment\n",
        "- We use a general purpose algorithm, but can also have an objective function\n",
        "- Constraint graph: nodes are variables, arcs are (binary) constraints\n",
        "\n",
        "### Heuristics\n",
        "- Most constrained variable: minimum remaining values (MRV)\n",
        "- Most constraining (to remaining variables) variable [for tiebreakers]\n",
        "- Least constraining value: the one that rules out the fewest values in the remaining variables\n",
        "- Forward checking: Keep track of remaining legal values for unassigned variables. \n",
        "Terminate search when any unassigned variable has no remaining legal values. \n",
        "(But don't keep going), helps detect total failure early\n",
        "  - Propogates info from assigned to unassigned variables\n",
        "  - Basically maintain arc consistency for that variable after you assign to it\n",
        "\n",
        "### Arc Consistency\n",
        "- Constraint propagation (inference) = eliminates possible values for a variable if the value would violate local consistency\n",
        "- Arc consistency satisfies binary constraint\n",
        "- A directed arc represents a constraint\n",
        "- X → Y is consistent iff for every value x of X there is some allowed y\n",
        "- To make an arc (i,j) arc consistent, for each value v on Xi , if there is no label on Yj consistent with v then remove v from Xi\n",
        "- Given d values, checking arc (i,j) takes O(d2 ) time worst case\n",
        "- Waltz/Mackworth Constraint Propagation:\n",
        "  - Assign every node in constraint graph set of all possible values\n",
        "  - Repeat until there is no change in the set of values associated with any node:\n",
        "    - For each node i:\n",
        "      - For each neighboring node j:\n",
        "        - Remove any value from i which is not arc consistent with j\n",
        "- AC-3\n",
        "  - Add all arcs to a queue in the CSP\n",
        "  - while the queue is not empty, pop an arc (x, y) from the queue and remove inconsistent\n",
        "  values. For each neighbor n that you remove inconsistent values from x, add\n",
        "  (x, n) to the queue\n",
        "  - Remove inconsistent values (x, y) means for each value in x, if no value\n",
        "  in y allows (x, y) to be consistent, delete that value from x\n",
        "  - Complexity:\n",
        "    - Number of arcs is O(n^2)\n",
        "    - D values: checking single arc takes O(d^2)\n",
        "    - Each arc can only be inserted into the queue d times\n",
        "    - Worst case: O((n^2)(d^3))\n",
        "    - Planar graphs: # arcs can only be linear in N and time complexity is only O(nd^3)\n",
        "\n",
        "\n",
        "\"\"\"\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": 1000
        },
        "outputId": "60c8ae84-8c88-483b-8036-d0f80ceec707"
      },
      "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 \nCSP = (X, D, C) where X: set of variables, D: set of domains for each variable,\nC: set of constraints (scope, relation)\n- unary constraint: restricts single variable value\n- global constraint: arbitrary number of variables\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n- Constraint propogation reduces number of values for variable using constraints\n- k-consistency: consistent value can be assigned to kth variable\n- strongly k-consistent: consistent for all j up to k\n- resource constraint: at most\n- bounds propagation\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Backtracking search\n- Minimum remaining values heuristic: choose var with fewest legal values\n- Degree heuristic: select variable with most constraints on other unassigned vars\n- Least-constraining value: value that rules out fewest choices for neighboring vars\nVariable selection is fail-first (backtrack less), but value selection is fail-last (only need one solutoin)\n\nInference:\n- Forward checking: when X is assigned a vlue, then for each unassigned var Y that X\nhas a constraint with, delete inconsistent values from Y\n- Maintaining arc consistency: after variable X_i is assigned a value, \ncall AC-3 for the arcs that contain X_i and its neighbors. assigns variables in backtracking search.\n\n- Backtrack to most recent preceding variable = chronological backtracking\n- backjumping is backtracing to most recent assignment in conflict set,\nwhich are the assignments that conflict with some value for SA\n- conflict-directed backjumping\n- constraing learning: find min set of vars from conflict set that causes problem\n\n\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Min-conflicts heuristic: pick what leads to fewest conflicts \nConstraint weighting \n\n## AIMA Chapter 6.5 The Structure of Problems\n \nIndependent subproblems are separate CC's\nCan use toposort on a tree constraint graph and choose\nany remaining value. (O(nd^2)), d is size of largest domain\n- cutset conditioning: assign value so that remaining vars are a tree, O(d^c (n-c)d^2)\n- tree decomposition: each node in tree contains set of nodes. O(nd^(w+1))\nwhere w is minimum width (one less than size of largest node) of tree components\n- Value symmetry: can intrduce symmetry-breaking conostraint, like NT <SA < WA\n\n\n\n\n## Module 6 Lecture Notes\n\n### CSP Overview\n- Finite set of variables, nonempty domain of possible values for each variable, finite set of constraints\n- Consistent = assignment does not violate the constraints\n- Complete = every variable is assigned a value\n- Solution = complete, consistent assignment\n- We use a general purpose algorithm, but can also have an objective function\n- Constraint graph: nodes are variables, arcs are (binary) constraints\n\n### Heuristics\n- Most constrained variable: minimum remaining values (MRV)\n- Most constraining (to remaining variables) variable [for tiebreakers]\n- Least constraining value: the one that rules out the fewest values in the remaining variables\n- Forward checking: Keep track of remaining legal values for unassigned variables. \nTerminate search when any unassigned variable has no remaining legal values. \n(But don't keep going), helps detect total failure early\n  - Propogates info from assigned to unassigned variables\n  - Basically maintain arc consistency for that variable after you assign to it\n\n### Arc Consistency\n- Constraint propagation (inference) = eliminates possible values for a variable if the value would violate local consistency\n- Arc consistency satisfies binary constraint\n- A directed arc represents a constraint\n- X → Y is consistent iff for every value x of X there is some allowed y\n- To make an arc (i,j) arc consistent, for each value v on Xi , if there is no label on Yj consistent with v then remove v from Xi\n- Given d values, checking arc (i,j) takes O(d2 ) time worst case\n- Waltz/Mackworth Constraint Propagation:\n  - Assign every node in constraint graph set of all possible values\n  - Repeat until there is no change in the set of values associated with any node:\n    - For each node i:\n      - For each neighboring node j:\n        - Remove any value from i which is not arc consistent with j\n- AC-3\n  - Add all arcs to a queue in the CSP\n  - while the queue is not empty, pop an arc (x, y) from the queue and remove inconsistent\n  values. For each neighbor n that you remove inconsistent values from x, add\n  (x, n) to the queue\n  - Remove inconsistent values (x, y) means for each value in x, if no value\n  in y allows (x, y) to be consistent, delete that value from x\n  - Complexity:\n    - Number of arcs is O(n^2)\n    - D values: checking single arc takes O(d^2)\n    - Each arc can only be inserted into the queue d times\n    - Worst case: O((n^2)(d^3))\n    - Planar graphs: # arcs can only be linear in N and time complexity is only O(nd^3)\n\n\n\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Model-checking algos include backtrackng & local search (sound, not complete) \"\"\"\n",
        "chapter7_4 = \"\"\" Ystate estimation: maintain logcal sentence, describes set of possible states \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "### Knowledge-based Agents\n",
        "- So far, agents perform search over states that are atomic\n",
        "-  Knowledge base contains a set of sentences that are written in a knowledge representation language\n",
        "  - Two kinds of sentences:\n",
        "    - Axioms: a sentence that is given\n",
        "    - Derived sentences: new sentence derived from other sentences\n",
        "  - Process of derivation is called inference\n",
        "  - KB can initially contain background info, then agent adds to info through observations. Can also query or ask to derive new knowledge.\n",
        "  - KB false in models that contradict what the agent knows\n",
        "- Models: fixed set of truth values for each sentence\n",
        "  - M(a) = set of models of a sentence a\n",
        "  - Model checking is process of enumerating all possible models compatible with the KB\n",
        "- Logical entailment: sentence entails another sentence, can be applied to derive conclusions (logical inference)\n",
        "  - Inference algorithms enumerate sentences that are entailed\n",
        "  - Care about:\n",
        "    - Soundness: inference algo should only derive entailed sentences\n",
        "    - Complete: generate all valid entailments\n",
        "- Logical equivalence:\n",
        "  - If they are have the same models\n",
        "  - Iff a entails b and b entails a\n",
        "### Knowledge base\n",
        "- Construct sentences using propositional logic\n",
        "- Beta entails alpha iff m(beta) is a subset of m(alpha)\n",
        "- Monotonicity: if KB |= a then KB & B |= a\n",
        "- Inference rules:\n",
        "  - Modus ponens\n",
        "  - And elimination\n",
        "  - Biconditional elimination\n",
        "- Search for a proof:\n",
        "  - Initial state: initial knowledge base\n",
        "  - Actions: all inference rules applied to all sentences that match the top half of the inference rule\n",
        "  - Result: add sentence on bottom half to KB\n",
        "  - Goal: state that contains the sentence we are trying to prove\n",
        "- Monotonicity implies soundness\n",
        "- Resolution yields complete inference algo when coupled with any complete search algorithm\n",
        "  - If A or B, and not A, then B\n",
        "  - If l and m are complementary literals, then we can eliminate them via unit resolution\n",
        "- Conjunctive normal form: every sentence is a set of conjunctions of literals\n",
        "  - Use proof by contradiction\n",
        "  - Convert KB and \\lnot a into CNF\n",
        "  - Apply resolution rule to resulting clauses.\n",
        "  - Resolve every pair that contains complementary literals\n",
        "  - If that new clause isn’t already present, add it to the set\n",
        "  - Continue until either no new clauses can be added (KB does not entail a) or two clauses resolve to yield the empty clause (KB does entail a)\n",
        "- Practice using PL rules\n",
        "  - Eliminate ⇔ by replacing a ⇔ b with (a => b) && (b => a)\n",
        "  - Eliminate => by replacing a => b with (!a || b)\n",
        "  - Move ! inwards, eliminate double negation and apply De Morgan’s\n",
        "  - Apply distributive law to distribute || over && and && over ||: \n",
        "    - a || (b && c) = (a || b) && (a || c)\n",
        "    - a && (b || c) = (a && b) || (a && c)\n",
        "- Horn clauses and definite clauses\n",
        "  - Definite clauses: disjunction of literals where exactly one is positive\n",
        "    - Can be written as an implication whose premise is conjunction of positive literals whose conclusion is positive literal\n",
        "  - Horn clause: disjunction of literals where at most one is positive\n",
        "    - Closed under resolution\n",
        "    - Deciding entailment can be done in linear time wrt size of KB\n",
        "  - Forward chaining\n",
        "    - Data-driven reasoning\n",
        "    - Start with known data, add premise as new percepts come in, incrementally apply forward chaining\n",
        "  - Backward chaining\n",
        "    - Goal-directed reasoning\n",
        "    - Start with query, find implications in the KB whose conclusion is the query, if all the premises of one of those can eb proved to be true then the query is true\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ab5635ad-ba89-4beb-d57f-c8fe5331234c"
      },
      "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 Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Model-checking algos include backtrackng & local search (sound, not complete) \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Ystate estimation: maintain logcal sentence, describes set of possible states \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n\n### Knowledge-based Agents\n- So far, agents perform search over states that are atomic\n-  Knowledge base contains a set of sentences that are written in a knowledge representation language\n  - Two kinds of sentences:\n    - Axioms: a sentence that is given\n    - Derived sentences: new sentence derived from other sentences\n  - Process of derivation is called inference\n  - KB can initially contain background info, then agent adds to info through observations. Can also query or ask to derive new knowledge.\n  - KB false in models that contradict what the agent knows\n- Models: fixed set of truth values for each sentence\n  - M(a) = set of models of a sentence a\n  - Model checking is process of enumerating all possible models compatible with the KB\n- Logical entailment: sentence entails another sentence, can be applied to derive conclusions (logical inference)\n  - Inference algorithms enumerate sentences that are entailed\n  - Care about:\n    - Soundness: inference algo should only derive entailed sentences\n    - Complete: generate all valid entailments\n- Logical equivalence:\n  - If they are have the same models\n  - Iff a entails b and b entails a\n### Knowledge base\n- Construct sentences using propositional logic\n- Beta entails alpha iff m(beta) is a subset of m(alpha)\n- Monotonicity: if KB |= a then KB & B |= a\n- Inference rules:\n  - Modus ponens\n  - And elimination\n  - Biconditional elimination\n- Search for a proof:\n  - Initial state: initial knowledge base\n  - Actions: all inference rules applied to all sentences that match the top half of the inference rule\n  - Result: add sentence on bottom half to KB\n  - Goal: state that contains the sentence we are trying to prove\n- Monotonicity implies soundness\n- Resolution yields complete inference algo when coupled with any complete search algorithm\n  - If A or B, and not A, then B\n  - If l and m are complementary literals, then we can eliminate them via unit resolution\n- Conjunctive normal form: every sentence is a set of conjunctions of literals\n  - Use proof by contradiction\n  - Convert KB and \\lnot a into CNF\n  - Apply resolution rule to resulting clauses.\n  - Resolve every pair that contains complementary literals\n  - If that new clause isn’t already present, add it to the set\n  - Continue until either no new clauses can be added (KB does not entail a) or two clauses resolve to yield the empty clause (KB does entail a)\n- Practice using PL rules\n  - Eliminate ⇔ by replacing a ⇔ b with (a => b) && (b => a)\n  - Eliminate => by replacing a => b with (!a || b)\n  - Move ! inwards, eliminate double negation and apply De Morgan’s\n  - Apply distributive law to distribute || over && and && over ||: \n    - a || (b && c) = (a || b) && (a || c)\n    - a && (b || c) = (a && b) || (a && c)\n- Horn clauses and definite clauses\n  - Definite clauses: disjunction of literals where exactly one is positive\n    - Can be written as an implication whose premise is conjunction of positive literals whose conclusion is positive literal\n  - Horn clause: disjunction of literals where at most one is positive\n    - Closed under resolution\n    - Deciding entailment can be done in linear time wrt size of KB\n  - Forward chaining\n    - Data-driven reasoning\n    - Start with known data, add premise as new percepts come in, incrementally apply forward chaining\n  - Backward chaining\n    - Goal-directed reasoning\n    - Start with query, find implications in the KB whose conclusion is the query, if all the premises of one of those can eb proved to be true then the query is true\n\n\n\n\n## Module 7 Definitions\n* **Concept** - definition\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": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "58f6d839-832a-4593-e319-7864d69f939e"
      },
      "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?\nthe standard model is study and construction of agents that do the\nright thing.\n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n can machines really think? qualia: intrinsic nature of experiences\n\n## AIMA 2.1 Agents and Environments\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n In AI, we use consequentialism: evaluate an agent's behavior by its consequences.\nShould design performance measures based on what we want to be achieved in the\nenvironment rather than according to how we think the agent should behave\n\n## AIMA 2.3 The Nature of Environments\nRationality depends on four factors: (1) Performance measure\n(2) Agent's prior knowledge of the environment\n(3) Possible actions that the agent can perform\n(4) Percept sequence so far\n\nRationality is not the same thing as omniscience.\nRational agents need to be able to both gather information and learn from\nwhat it perceives, i.e. should be autonomous.\n\n Competitive vs. cooperative multiagent environments\nepisodic (current decisions don't affect next episode) vs. sequential\nstatic (env cannot change while agent is deliberating) vs. dynamic\n\n## AIMA 2.4 The Structure of Agents\nmodel-based agent: uses transition model & sensor\nutility function internalizes perfrmance measure\nsimple reflex agents respond directly (and only) to percepts\ngoal-based agents have a goal to achieve\nutility-based agents aim to maximize utility\n\n## Module 1 Lecture Notes\nAn agent is anything that:\nperceives its environment through sensors and\ncan act on its environment through actuators\n- Percept = agent’s perceptual inputs at any given instance\n- Agent function f: maps sequence of percept vectors P to an action a from a set A\n- Agent program: runs on the physical architecture to produce f\n\nRational agent:\n- For each possible percept sequence P\n- A rational agent selects an action a\n- To maximize expected value of its performance measure\n- (given perecept sequence and built-in knowledge)\n\nPerformance measure: objective criterion for success of an agent’s behavior\n\nTask environment: problem specification for which the agent is a solution (PEAS)\n- Performance measure\n- Environment\n- Actuators\n- Sensors\n\nReflex agent selects action based on current percept, ignores percept history. \n\nProblem-solving agent must plan ahead.\n\nRandomized behavior can be rational in some environments\n\n\n## Module 1 Definitions\n* **Deterministic** - next state determined by current state + action\n* **Stochastic** - nondeterministic with explicit probabilities\n* **Actuator** - the means by which the agent acts on its environment\n* **Percept sequence** - agen'ts complete history of everything it has ever perceived\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\n- All data treated as objects\n- Strong typing: every object has a fixed type\n--type(object)\n--isinstance(object, type)\n-Dynamic typing: variable comes into existence when first assigned. \nIf assigned again, type is updated. Functions have no type signatures.\n-Python uses dynamic typing.\n-No ++ or --\n-== checks objects of same value\n-is checks point to same object\n-Tuples and strings are immutable. Lists are mutable. Tuples and lists can have multiple types. You can slice all 3 types\nof sequences.\n- Keys in dict are immutable. .keys(), .values(), .items() [returns tuples]\n- Defaultdict imported from collections, initializes nonexistent dict values\n- No function overloading in Python\n- Keyword arguments can be used after other args\n- *args allows you to accept a variable number of non-kwargs\n- **kwargs allows the samne for kwargs. comes after *args\n- dynamic scope: functions see most current value of variables\n- functions are first-class\n- classes: __init__ instatiates. every method begins with (slf).\n- subclass: name of superclass as arg to class def'n\n- magic methods: init, len, copy, cmp, add, neg\n- list comprehension: [x for x in y if z]\n- set & dict comprehension\n- i = iter(k) creates iterator\n- yield: automatically return a generator when called. Crucial for processing infinite list\n- Will have key error if try to remove something not in the set\n- Cannot use + to concatenate dicts\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 Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n- Uniform-cost search is uninformed. Djikstra's \nis the same thing (no goal)\n- Bidirectonal search: searches forward from s_i and backwards from goal state(s).\nThere are many versions of this. Is complete and optimal, if applicable at all. \nTC = O(b^{d/2}), SC = O(b^{d/2})\n\n\n## Module 3 Lecture Notes\n\n### Search Problems\n- Agents that perform search are called “Problem-solving agents”\n    - Plan ahead: computational process is called search\n    - Consider sequence of actions (solution) that form path to goal state\n- Reflex agents: \n    - selects action only based on current percept\n    - Ignores rest of percept history\n- 8-Puzzle example: \n    - Puzzles are deterministic and known\n    - Formulate goal, search problem and solution\n    - Search problem:\n        - States: configurations of puzzle\n        - Actions: Move one of movable pieces\n        - Performance measure: Minimize total moves\n    - Solution: sequence of pieces moved\n- Holiday in Romania example:\n    - Goal: Be in Bucharest\n    - Search Problem:\n        - States: various cities\n        - Actions: drive between cities:\n        - Performance measure: minimize travel time/distance\n    - Solution: sequence of cities\n### Formulating search problem\n1. States: a set S\n2. Initial state: s_i\n3. Actions: a set A, for all s in Actions(s) = the set of actions that can be\nexecuted in s that are applicable in s\n4. Transition Model: Function that maps (s, a) --> s_r, where s_r is a \nsuccessor of s. {s_i} U Successors(s_i) = state space \n5. Path cost (performance measure): must be additive, c(x, a, y) is step cost\n6. Goal cost: Goal(s) is true if s is a goal state\n\nThink of it this way:\n- Which properties matter: initial state, goal state, intermediate states\n- Which actions are possible: operator set—actions & transition model\n- Which action is next: path cost\n\nUseful concepts:\n- State space: set of all states rechable from initial state by any sequence\n- Path: sequence of actions leading from one state s_j to another state s_k\n- Frontier: those states that are available for expanding (applying legal actions to)\n- Solution: path from initial states s_i to state s_f that satisfies goal test\n\n### Algos\nBFS: \n- Expand shallowest unexpanded node\n- Use a FIFO queue, put successors at the end of frontier successor list \n- Complete, optimal, TC: O(bd), SC: O(bd) [not good], where:\n    - B = max branching factor of search tree\n    - D = depth of least cost solution\n    - M = max depth of state space\n    - Use if possible infinite paths\n\nDFS:\n- Expand deepest unexpanded node\n- Frontier is LIFO queue\n- Not complete (bc infinite paths), Not optimal, TC: O(bm) [terrible], SC: O(b*m)\n- Use if space is restricted\n\nDepth-limited search:\n- DFS with depth limit l, where nodes at depth l have no successors\n- Complete if d<= l, optimal if d>= l, TC: O(bl), SC: O(bl)\n\nIterative deepening search:\n- Helps find best depth limit l\n- Use Depth-limited search as subroutine with increasing l\n- Complete, optimal if step/edge cost is 1 (finds goal at d), TC: O(bd), SC: O(bd)\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Path costs are monotonic. A* with consistent heuristic is optimally \nefficient. Prunes away nodes that are unnecessary.Beam search limits size of frontier or keeps nodes with scores \nwithin a delta to conseve memory usage. Can also use iterative-deepening A* search\nor recursive best-first search. Bidirectional search can be but is often not more efficient\nthan unidirectional search.\n\n## AIMA Chapter 3.6 Heuristic Functions\nEffective branching factor b* can represent quality of a heuristic, \nwhere b* is the branching factor that a uniform tree of depth d would need to contain\nN+1 nodes, and d is the depth of the solution. Good heuristic would have b* close to 1.\nDomination means more efficient. Cost of optimal sol'n to relaxed version of problem\nP or to subproblem is always admissible heuristic for P. Can use landmarks\nfor differential heuristic.\n\n## Module 4 Lecture Notes\n \n### Uniform Cost Search (also uninformed)\n- For weighted graphs\n- g(N): path cost function, adds cost of the path up to that node\n- Extension of BFS, expand node with lowest path cost\n- Frontier = priority queue ordered by g(n)\n- Tests if node is goal state when selected for expansion, not when added to frontier\n- Complete, optimal\n- Dijkstra’s algo is UCS without a goal\n### Heuristic Functions\n- Imagine we had a table of distances (that is an approximation, not the actual distance)\n- h(n) takes a state n and returns an estimate of the distance from n to the goal\n### Greedy best-first search\n- Select node for expansion with minimal evaluation function f(n)\n- f(n) = estimate heuristic h(n)\n- Do UCS with f(n) = h(n) instead of g(n)\n- Not optimal, doesn’t always find the shortest path\n- Not complete, can get stuck in loops\n\n`frontier = pq`\n`frontier.put(start, 0)`\n`came_from = {}`\n`came_from[start] = None`\n`while not frontier.empty(): get current; break if goal; for next in neighbors`\n`if next not in came_from: p = heurstic(goal, next); frontier.put(next, prority);\ncame_from[next] = current`\n\n### A* search\n- f(n) = g(n) + h(n)\n    - g(n) = actual cost (so far) to reach node\n    - h(n) = estimated cost to get from the node to the goal\n    - f(n) = estimated total cost of path through n to goal\n- h(n) needs to be admissible:\n    - Never overestimates the cost to reach the goal (optimistic)\n    - Heuristics slow down bad plans but never break optimality\n    - The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n- Dominance:\n    - If h2(n) \\geq h1(n) for all n (and both are admissible) then h2 dominates h1\n    - Best admissible heuristic is true, worst is 0 (teleportation)\n- Proof that A* is optimal\n- A* has space complexity O(b^d) [like BFS]\n    - Can be lower if has a better heuristic\n\n\n \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 Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Effectiveness of a-b pruning depends on order of examination.\nCan use iterative deepening, rank moves based on evaluations one ply at a time.\n\nType A strategy: wide but shallow\nType B strategy: deep but narrow \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \n- Can apply evaluation function to states\nand cut off search when appropriate. Eval function applies only\nto quiescent positions (no upcoming move will make a big difference \nin evaluation), may have to do quiescence search\n- Forward pruning: prunes moves that appear to be bad, can use beam search\n\n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n axioms of utility theory: orderability, transivity, continuity, substitutability,\nmonotonicity, decomposability (compound lotteries are reducible) \n\n## AIMA Chapter 16.3 Utility Functions\n Utility function is a map from a lottery to R. can be hard\nto figure out what people's preferences actually are. \n\n## Module 5 Lecture Notes\n \n### Game Formulatin, Game Trees\n- Simplest Game Environment:\n    - Multiagent\n    - Static: No change while agent is deliberating\n    - Discrete, Fully Observable Strategic\n- Our games:\n    - Two players alternate moves (max & min, max moves first)\n        - Root is labelled MAX\n    - Zero-sum\n    - Clear set of legal moves\n    - Well-defined outcomes\n- Game as search: \n    - Initial state: board configuration of chess\n    - Successor function: list of (move, state) pairs specifying legal moves\n    - Terminal test: is the game finished?\n    - Utility function: gives numerical value of terminal states\n    - MAX uses search tree to determine next move\n- Game Tree:\n    - Ply = tree level\n    - Nodes represent ‘board positions’: edges represent legal moves. Root node is first position in which decision must be made.\n    - Evaluation function f assigns real-number scores to `board positions’ w/o reference to path\n        - Based on static features of board alone\n        - f(n) > 0 if MAX winning in position n\n    - Terminal nodes labeled with desirability\n\n### Minimax and Alpha-Beta Pruning\n    - Procedure: until game is over\n    - Start with current position as a MAX node\n    - Expand game tree as a fixed number of ply\n    - Apply the evaluation function to the leaf positions\n    - Calculate back-up values bottom-up\n    - Pick the move assigned to MAX at the root\n    - Wait for MIN to respond\n\ndef max-value(state): if the state is a terminatal state, return\nutility; initalize v = -inf; for each successor: v = max(v, min-val(succ)); return v\n\nTwo additional values:\n- Alpha: max’s current lower bound on max’s outcome, aka max’s best already explored option on path to root\n- Beta: min’s current upper bound on min’s outcome, aka min’s best already explored option on path to root\n- Stop evaluating a branch whenever value greater than beta (for min) or less than alpha (for max) is found\n- Node values are passed back up the tree instead of values alpha and beta\n- Only pass alpha, beta values to child nodes\n- Alpha >= beta → prune (should always have alpha <= beta)\n\n### Expectimax:\nIf next agent is EXP: return def exp-value(state) where\n\ndef exp-value(state):\n  initialize v = 0; for each succ: p = probability(succ), v += p * value(succ); return v\n\n \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 \nCSP = (X, D, C) where X: set of variables, D: set of domains for each variable,\nC: set of constraints (scope, relation)\n- unary constraint: restricts single variable value\n- global constraint: arbitrary number of variables\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\n- Constraint propogation reduces number of values for variable using constraints\n- k-consistency: consistent value can be assigned to kth variable\n- strongly k-consistent: consistent for all j up to k\n- resource constraint: at most\n- bounds propagation\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Backtracking search\n- Minimum remaining values heuristic: choose var with fewest legal values\n- Degree heuristic: select variable with most constraints on other unassigned vars\n- Least-constraining value: value that rules out fewest choices for neighboring vars\nVariable selection is fail-first (backtrack less), but value selection is fail-last (only need one solutoin)\n\nInference:\n- Forward checking: when X is assigned a vlue, then for each unassigned var Y that X\nhas a constraint with, delete inconsistent values from Y\n- Maintaining arc consistency: after variable X_i is assigned a value, \ncall AC-3 for the arcs that contain X_i and its neighbors. assigns variables in backtracking search.\n\n- Backtrack to most recent preceding variable = chronological backtracking\n- backjumping is backtracing to most recent assignment in conflict set,\nwhich are the assignments that conflict with some value for SA\n- conflict-directed backjumping\n- constraing learning: find min set of vars from conflict set that causes problem\n\n\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Min-conflicts heuristic: pick what leads to fewest conflicts \nConstraint weighting \n\n## AIMA Chapter 6.5 The Structure of Problems\n \nIndependent subproblems are separate CC's\nCan use toposort on a tree constraint graph and choose\nany remaining value. (O(nd^2)), d is size of largest domain\n- cutset conditioning: assign value so that remaining vars are a tree, O(d^c (n-c)d^2)\n- tree decomposition: each node in tree contains set of nodes. O(nd^(w+1))\nwhere w is minimum width (one less than size of largest node) of tree components\n- Value symmetry: can intrduce symmetry-breaking conostraint, like NT <SA < WA\n\n\n\n\n## Module 6 Lecture Notes\n\n### CSP Overview\n- Finite set of variables, nonempty domain of possible values for each variable, finite set of constraints\n- Consistent = assignment does not violate the constraints\n- Complete = every variable is assigned a value\n- Solution = complete, consistent assignment\n- We use a general purpose algorithm, but can also have an objective function\n- Constraint graph: nodes are variables, arcs are (binary) constraints\n\n### Heuristics\n- Most constrained variable: minimum remaining values (MRV)\n- Most constraining (to remaining variables) variable [for tiebreakers]\n- Least constraining value: the one that rules out the fewest values in the remaining variables\n- Forward checking: Keep track of remaining legal values for unassigned variables. \nTerminate search when any unassigned variable has no remaining legal values. \n(But don't keep going), helps detect total failure early\n  - Propogates info from assigned to unassigned variables\n  - Basically maintain arc consistency for that variable after you assign to it\n\n### Arc Consistency\n- Constraint propagation (inference) = eliminates possible values for a variable if the value would violate local consistency\n- Arc consistency satisfies binary constraint\n- A directed arc represents a constraint\n- X → Y is consistent iff for every value x of X there is some allowed y\n- To make an arc (i,j) arc consistent, for each value v on Xi , if there is no label on Yj consistent with v then remove v from Xi\n- Given d values, checking arc (i,j) takes O(d2 ) time worst case\n- Waltz/Mackworth Constraint Propagation:\n  - Assign every node in constraint graph set of all possible values\n  - Repeat until there is no change in the set of values associated with any node:\n    - For each node i:\n      - For each neighboring node j:\n        - Remove any value from i which is not arc consistent with j\n- AC-3\n  - Add all arcs to a queue in the CSP\n  - while the queue is not empty, pop an arc (x, y) from the queue and remove inconsistent\n  values. For each neighbor n that you remove inconsistent values from x, add\n  (x, n) to the queue\n  - Remove inconsistent values (x, y) means for each value in x, if no value\n  in y allows (x, y) to be consistent, delete that value from x\n  - Complexity:\n    - Number of arcs is O(n^2)\n    - D values: checking single arc takes O(d^2)\n    - Each arc can only be inserted into the queue d times\n    - Worst case: O((n^2)(d^3))\n    - Planar graphs: # arcs can only be linear in N and time complexity is only O(nd^3)\n\n\n\n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Model-checking algos include backtrackng & local search (sound, not complete) \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Ystate estimation: maintain logcal sentence, describes set of possible states \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n\n### Knowledge-based Agents\n- So far, agents perform search over states that are atomic\n-  Knowledge base contains a set of sentences that are written in a knowledge representation language\n  - Two kinds of sentences:\n    - Axioms: a sentence that is given\n    - Derived sentences: new sentence derived from other sentences\n  - Process of derivation is called inference\n  - KB can initially contain background info, then agent adds to info through observations. Can also query or ask to derive new knowledge.\n  - KB false in models that contradict what the agent knows\n- Models: fixed set of truth values for each sentence\n  - M(a) = set of models of a sentence a\n  - Model checking is process of enumerating all possible models compatible with the KB\n- Logical entailment: sentence entails another sentence, can be applied to derive conclusions (logical inference)\n  - Inference algorithms enumerate sentences that are entailed\n  - Care about:\n    - Soundness: inference algo should only derive entailed sentences\n    - Complete: generate all valid entailments\n- Logical equivalence:\n  - If they are have the same models\n  - Iff a entails b and b entails a\n### Knowledge base\n- Construct sentences using propositional logic\n- Beta entails alpha iff m(beta) is a subset of m(alpha)\n- Monotonicity: if KB |= a then KB & B |= a\n- Inference rules:\n  - Modus ponens\n  - And elimination\n  - Biconditional elimination\n- Search for a proof:\n  - Initial state: initial knowledge base\n  - Actions: all inference rules applied to all sentences that match the top half of the inference rule\n  - Result: add sentence on bottom half to KB\n  - Goal: state that contains the sentence we are trying to prove\n- Monotonicity implies soundness\n- Resolution yields complete inference algo when coupled with any complete search algorithm\n  - If A or B, and not A, then B\n  - If l and m are complementary literals, then we can eliminate them via unit resolution\n- Conjunctive normal form: every sentence is a set of conjunctions of literals\n  - Use proof by contradiction\n  - Convert KB and \\lnot a into CNF\n  - Apply resolution rule to resulting clauses.\n  - Resolve every pair that contains complementary literals\n  - If that new clause isn’t already present, add it to the set\n  - Continue until either no new clauses can be added (KB does not entail a) or two clauses resolve to yield the empty clause (KB does entail a)\n- Practice using PL rules\n  - Eliminate ⇔ by replacing a ⇔ b with (a => b) && (b => a)\n  - Eliminate => by replacing a => b with (!a || b)\n  - Move ! inwards, eliminate double negation and apply De Morgan’s\n  - Apply distributive law to distribute || over && and && over ||: \n    - a || (b && c) = (a || b) && (a || c)\n    - a && (b || c) = (a && b) || (a && c)\n- Horn clauses and definite clauses\n  - Definite clauses: disjunction of literals where exactly one is positive\n    - Can be written as an implication whose premise is conjunction of positive literals whose conclusion is positive literal\n  - Horn clause: disjunction of literals where at most one is positive\n    - Closed under resolution\n    - Deciding entailment can be done in linear time wrt size of KB\n  - Forward chaining\n    - Data-driven reasoning\n    - Start with known data, add premise as new percepts come in, incrementally apply forward chaining\n  - Backward chaining\n    - Goal-directed reasoning\n    - Start with query, find implications in the KB whose conclusion is the query, if all the premises of one of those can eb proved to be true then the query is true\n\n\n\n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}