{
  "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": "b4b721d2-9d3a-41a6-86a9-4515c7b68420"
      },
      "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": 49,
      "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": "13d26624-cfc0-45f1-dd1c-0726f5fc9423"
      },
      "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": 50,
      "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": 51,
      "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 = \"\"\" Chapter 1.1 summary. \"\"\" \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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 52,
      "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": 725
        },
        "cellView": "form",
        "outputId": "a936c485-08bc-47b0-8907-0943d9fdc55a"
      },
      "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": 53,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \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 Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 54,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "outputId": "da7fc083-c3cb-4b94-8e85-0717864d78ef"
      },
      "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": 55,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \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 = \"\"\" An agent can follow a four phase problem solving process : Goal formulation; Problem formulation (define states and actions);\\\n",
        " Search (stimulate various sequence of actions until solution is found) and Execution. The solution is a fixed sequence of actions if the \\\n",
        " environment is fully-observable, deterministic and known. The agent can then execute the solution blindly, ignoring its percepts (open loop). \\\n",
        " If the environment is non-deterministic then agent has to monitor its percepts (closed loop). In this case, where the environment is partially \\\n",
        " observable and non-deterministic, we follow a branching strategy of solution which recommends actions based on the percepts that arrive. \\n\n",
        "Search problem definition : Set of states (state space); Initial state; Set of goal states; Actions; Transition model; Action cost function. \\\n",
        "Actions(s) is a finite set of actions that are applicable in state s. Result(s, a) returns the state that results from performing action a on state s.\\\n",
        " Action-Cost(s, a, s’) is the cost of applying a to go from state s to s’. Cost function can b e used as performance measure. A graph (vertices are states\\\n",
        "  and edges are actions) can be used to represent the state space. The right level of abstraction is crucial - removing as much detail as possible and\\\n",
        "   ensuring that the abstracted actions are easy to perform.  \"\"\"\n",
        "\n",
        "chapter3_2 = \"\"\" Standardized vs Real-world problems. Standardized problems are used as a benchmark to compare the performance of algorithms. \\\n",
        "Real-world problems vary from situation to situation. \\n\n",
        "Standardized problems examples : Grid Navigation (ex : Vacuum Cleaner prob); Sokoban Puzzle (Goal is to push boxes scattered around grid to \\\n",
        "storage locations); Sliding tile puzzle; Donald Knuth puzzle (start with 4 and apply square root, factorial and floor in any sequence to get\\\n",
        " a particular number - this prob has infinite state space). Infinite state spaces are common for problems involving mathematical expressions, \\\n",
        " circuits, proofs, programs and other objects that are recursively defined. \\n\n",
        "Real-World problems examples : Route-finding (Routing video streams in computer networks, military operations planning, airline-planning systems)\\\n",
        "; Touring problems (Traveling salesperson); VLSI layout; Robot navigation; Automatic assembly sequencing (Protein Design). In robot navigation,\\\n",
        " robot can make its own path and state-space can be multi-dimensional. In assembly sequencing, deciding the legal actions is the most expensive part. \"\"\"\n",
        "chapter3_3 = \"\"\" In a search tree, every node corresponds to a state in the state space, the edges correspond to the actions and the root node\\\n",
        " corresponds to the initial state. The state space consists of all the possible states and actions. The search tree consists of paths between \\\n",
        " states to reach the goal. There can be multiple paths to a state in a search tree but each node has a unique path back to the root. A state is \\\n",
        " considered to be reached if it has a node corresponding to it and expanded if it has child nodes. The frontier divides the state space into \\\n",
        " 2 regions : Interior (every state has been expanded) and exterior (states that have not yet been reached).\\n\n",
        "Best-First Search : From the frontier, the node with the lowest value of some evaluation function f(n) is chosen to be expanded next. If this \\\n",
        "is the goal state, we return. To the frontier, each child node is added if it hasn’t been reached before or is being reached with a lower path \\\n",
        "cost than before.\\n\n",
        "Search Data-Structures : node.STATE; node.ACTION; node.PARENT; node.PATH-COST [g(n)]. For the frontier, we use a queue (either priority queue, \\\n",
        "FIFO or LIFO[stack]). The operations that can be performed on a frontier are : Is-Empty, Pop (removes node on top) , Top (returns node on top), \\\n",
        "Add. A look up table can be used to store the reached states where the state is the key and the node for that state is the value.\\n\n",
        "Avoiding redundant paths makes an algorithm much faster. Three approaches to avoid redundant paths : Store all reached states and only the best \\\n",
        "path to reach that state ; Not worrying about repeated states in large state space problems (ex : assembly problem); Check for cycles but not \\\n",
        "redundant paths in general. The first approach can be used if the reached states can fit in the memory.  In the third approach, some algorithms \\\n",
        "check all the way up and eliminate all cycles whereas some check only a few links up and remove short cycles. Other algorithms have to be used in \\\n",
        "this case to remove long cycles. \\n\n",
        "Best First Search is a graph search algorithm. Tree search is slower than n graph search but uses less memory.\\n\n",
        "Evaluating algorithms : Completeness (must be systematic in exploring infinite state space); Cost Optimality; Time complexity; Space complexity. \\\n",
        "T and S complexity are considered with respect to difficulty of the problem. Ex: for explicit search graphs, space = |V| + |E| but for implicit it \\\n",
        "is measured in terms of d, m, b. \"\"\"\n",
        "chapter3_4 = \"\"\" \n",
        "BFS : All actions have the same cost. Complete (on infinite search spaces as well) and optimal(when all actions have same cost). f(n) is the number \\\n",
        "of actions it takes to reach the node, i.e, the depth. FIFO Queue is used. ‘Reached’ can be a set of states and not a mapping from state to node. \\\n",
        "Early goal test is done. Time and space complexity are O(b^d).\\n\n",
        "Djikstra’s or Uniform-Cost search : Actions have different cost. f(n) is cost of path from root to node n. Expands nodes with uniform path cost. \\\n",
        "Late goal test is done. Complete and Optimal.\\n\n",
        "DFS : Deepest node expanded. BFS with f(n) as negative of depth. Tree-like search, not graph. Does not keep track of reached states. Not optimal. \\\n",
        "Complete if state space is finite and acyclic. In cyclic, it can get stick in infinite loop so some DFS check each new node for cycles. Not complete \\\n",
        "in infinite spaces. Less need for memory.\\n\n",
        "Backtracking : DFS variant which uses lesser memory. Only one successor is generated instead of all bye modifying current state instead of generating\\\n",
        " brand new state. Critical when state space is large.\\n\n",
        "Depth limited : Treat all nodes at depth ml as leaf nodes. Incomplete if l not chosen correctly. Diameter of state space gives efficient value for l.\\n\n",
        "Iterative deepening : l is increased till solution is found or failure rather this cutoff value. Optimal if all actions have same cost. Complete for \\\n",
        "finite acyclic and for cyclic if we check for cycles all the way up. Preferred when state space is large and cannot fit in memory and depth of solution\\\n",
        " is not known.\\n\n",
        "Bidirectional : Forward from initial state and backward from goal state. Two frontiers and tables of reached states. Solution found when the two \\\n",
        "frontiers collide. When f(n) is path cost then it becomes bidirectional uniform cost search. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"Problem-Solving agent\" : \"an agent that can formulate a plan via search and uses atomic structures\",\n",
        "\"Planning agents\" : \"Agents that use factored or structured representation of states\",\n",
        "\"Path\" : \"Sequence of actions\",\n",
        "\"Solution\" : \"Path from initial to goal state\",\n",
        "\"Optimal solution\" : \"Solution with lowest path cost\",\n",
        "\"Abstraction\" : \"Removal of detail from representation\",\n",
        "\"Search Problem\" : \"Input is a search problem and output is a solution or reports a failure if there is none\",\n",
        "\"Frontier\" : \"A set of nodes that have been reached but not expanded yet\",\n",
        "\"Redundant Paths\" : \"A path that results in a repeated state\",\n",
        "\"Cycle or Loopy paths\" : \"Special case of redundant paths A-B and B-A\",\n",
        "\"Graph Search/ Tree Search\" : \"Search algorithm that checks for redundant paths/ Does not check for redundant paths\",\n",
        "\"Completeness\" : \"Return a solution if there is one and report failure if no solution\",\n",
        "\"Cost Optimality\" : \"Finds a solution with the lowest path cost\",\n",
        "\"Depth (d)\" : \"Number of actions in an optimal solution\",\n",
        "\"Branching Factor (b)\" : \"The total number of child nodes of a node that need to be considered\",\n",
        "\"(m)\" : \"Maximum number of actions in any path of the tree\",\n",
        "\"Uninformed Search\" : \"Access to only the prolem definition. No heuristic.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 56,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "7badee51-6993-42e4-ff65-c06d9cc38511"
      },
      "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": 57,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n An agent can follow a four phase problem solving process : Goal formulation; Problem formulation (define states and actions); Search (stimulate various sequence of actions until solution is found) and Execution. The solution is a fixed sequence of actions if the  environment is fully-observable, deterministic and known. The agent can then execute the solution blindly, ignoring its percepts (open loop).  If the environment is non-deterministic then agent has to monitor its percepts (closed loop). In this case, where the environment is partially  observable and non-deterministic, we follow a branching strategy of solution which recommends actions based on the percepts that arrive. \n\nSearch problem definition : Set of states (state space); Initial state; Set of goal states; Actions; Transition model; Action cost function. Actions(s) is a finite set of actions that are applicable in state s. Result(s, a) returns the state that results from performing action a on state s. Action-Cost(s, a, s’) is the cost of applying a to go from state s to s’. Cost function can b e used as performance measure. A graph (vertices are states  and edges are actions) can be used to represent the state space. The right level of abstraction is crucial - removing as much detail as possible and   ensuring that the abstracted actions are easy to perform.  \n\n## AIMA Chapter 3.2 Example Problems\n Standardized vs Real-world problems. Standardized problems are used as a benchmark to compare the performance of algorithms. Real-world problems vary from situation to situation. \n\nStandardized problems examples : Grid Navigation (ex : Vacuum Cleaner prob); Sokoban Puzzle (Goal is to push boxes scattered around grid to storage locations); Sliding tile puzzle; Donald Knuth puzzle (start with 4 and apply square root, factorial and floor in any sequence to get a particular number - this prob has infinite state space). Infinite state spaces are common for problems involving mathematical expressions,  circuits, proofs, programs and other objects that are recursively defined. \n\nReal-World problems examples : Route-finding (Routing video streams in computer networks, military operations planning, airline-planning systems); Touring problems (Traveling salesperson); VLSI layout; Robot navigation; Automatic assembly sequencing (Protein Design). In robot navigation, robot can make its own path and state-space can be multi-dimensional. In assembly sequencing, deciding the legal actions is the most expensive part. \n\n## AIMA Chapter 3.3 Search Algorithms\n In a search tree, every node corresponds to a state in the state space, the edges correspond to the actions and the root node corresponds to the initial state. The state space consists of all the possible states and actions. The search tree consists of paths between  states to reach the goal. There can be multiple paths to a state in a search tree but each node has a unique path back to the root. A state is  considered to be reached if it has a node corresponding to it and expanded if it has child nodes. The frontier divides the state space into  2 regions : Interior (every state has been expanded) and exterior (states that have not yet been reached).\n\nBest-First Search : From the frontier, the node with the lowest value of some evaluation function f(n) is chosen to be expanded next. If this is the goal state, we return. To the frontier, each child node is added if it hasn’t been reached before or is being reached with a lower path cost than before.\n\nSearch Data-Structures : node.STATE; node.ACTION; node.PARENT; node.PATH-COST [g(n)]. For the frontier, we use a queue (either priority queue, FIFO or LIFO[stack]). The operations that can be performed on a frontier are : Is-Empty, Pop (removes node on top) , Top (returns node on top), Add. A look up table can be used to store the reached states where the state is the key and the node for that state is the value.\n\nAvoiding redundant paths makes an algorithm much faster. Three approaches to avoid redundant paths : Store all reached states and only the best path to reach that state ; Not worrying about repeated states in large state space problems (ex : assembly problem); Check for cycles but not redundant paths in general. The first approach can be used if the reached states can fit in the memory.  In the third approach, some algorithms check all the way up and eliminate all cycles whereas some check only a few links up and remove short cycles. Other algorithms have to be used in this case to remove long cycles. \n\nBest First Search is a graph search algorithm. Tree search is slower than n graph search but uses less memory.\n\nEvaluating algorithms : Completeness (must be systematic in exploring infinite state space); Cost Optimality; Time complexity; Space complexity. T and S complexity are considered with respect to difficulty of the problem. Ex: for explicit search graphs, space = |V| + |E| but for implicit it is measured in terms of d, m, b. \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \nBFS : All actions have the same cost. Complete (on infinite search spaces as well) and optimal(when all actions have same cost). f(n) is the number of actions it takes to reach the node, i.e, the depth. FIFO Queue is used. ‘Reached’ can be a set of states and not a mapping from state to node. Early goal test is done. Time and space complexity are O(b^d).\n\nDjikstra’s or Uniform-Cost search : Actions have different cost. f(n) is cost of path from root to node n. Expands nodes with uniform path cost. Late goal test is done. Complete and Optimal.\n\nDFS : Deepest node expanded. BFS with f(n) as negative of depth. Tree-like search, not graph. Does not keep track of reached states. Not optimal. Complete if state space is finite and acyclic. In cyclic, it can get stick in infinite loop so some DFS check each new node for cycles. Not complete in infinite spaces. Less need for memory.\n\nBacktracking : DFS variant which uses lesser memory. Only one successor is generated instead of all bye modifying current state instead of generating brand new state. Critical when state space is large.\n\nDepth limited : Treat all nodes at depth ml as leaf nodes. Incomplete if l not chosen correctly. Diameter of state space gives efficient value for l.\n\nIterative deepening : l is increased till solution is found or failure rather this cutoff value. Optimal if all actions have same cost. Complete for finite acyclic and for cyclic if we check for cycles all the way up. Preferred when state space is large and cannot fit in memory and depth of solution is not known.\n\nBidirectional : Forward from initial state and backward from goal state. Two frontiers and tables of reached states. Solution found when the two frontiers collide. When f(n) is path cost then it becomes bidirectional uniform cost search. \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search and uses atomic structures\n* **Planning agents** - Agents that use factored or structured representation of states\n* **Path** - Sequence of actions\n* **Solution** - Path from initial to goal state\n* **Optimal solution** - Solution with lowest path cost\n* **Abstraction** - Removal of detail from representation\n* **Search problem** - Input is a search problem and output is a solution or reports a failure if there is none\n* **Frontier** - A set of nodes that have been reached but not expanded yet\n* **Redundant paths** - A path that results in a repeated state\n* **Cycle or loopy paths** - Special case of redundant paths A-B and B-A\n* **Graph search/ tree search** - Search algorithm that checks for redundant paths/ Does not check for redundant paths\n* **Completeness** - Return a solution if there is one and report failure if no solution\n* **Cost optimality** - Finds a solution with the lowest path cost\n* **Depth (d)** - Number of actions in an optimal solution\n* **Branching factor (b)** - The total number of child nodes of a node that need to be considered\n* **(m)** - Maximum number of actions in any path of the tree\n* **Uninformed search** - Access to only the prolem definition. No heuristic.\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 = \"\"\" Greedy Best-First : Expands nodes with lowest h(n). bNot optimal. Complete in finite spaces. \\n\n",
        "A* : f(n) = g(n) + h(n). Complete. Optimal if h(n) is admissible or consistent. Every consistent heuristic is admissible. With consistent h,\\\n",
        " the first found path not a node is optimal so no need to re-add it to the frontier. It prunes that are not necessary to find optimal solution. \\\n",
        " Optimally efficient. But it expands a lot of nodes.\\n\n",
        "Search Contours : All nodes in a contour have f(n) <= some X. Contours of uniform cost search are circles and that of A* stitch out towards the \\\n",
        "goal and become narrowly focused on optimal path. g(n) is monotonic, i.e, it always increases because path costs are positive. f(n) may increase \\\n",
        "or be equal only if h(n) is consistent.\\n\n",
        "Weighted A* : f = g + W * h for some W >1. Somewhat like greedy search.\\n\n",
        "Bounded suboptimal search : Look for a solution that is within a constant factor W off optimal cost. Weighted A*b is an example.\\n\n",
        "Bounded-cost search : Look for solution whose cost is less than some constant C.\\n\n",
        "Unbounded-cost search : Solution of any cosy accepted as long as it can be found quickly. Example is speedy search which is similar to greedy best \\\n",
        "first where h is number of actions to goal state irrespective of their cost.\\n\n",
        "To reduce memory needs, we can eliminate the use of reached states DS by using the separation property not frontiers and the prohibition of U-turn \\\n",
        "actions to make sure that all actions move outwards or onto another frontier state. We can also remove nodes from reached state DS using reference counts.\\n\n",
        "Beam-Search : Frontier size limited by seeing k nodes with the best f-cost. Can be suboptimal and incomplete. Another way is to keep nodes that are \\\n",
        "within a certain limit of the best fscore.\\n\n",
        "IDA* : at each iteration f-contour is increased. If each new node has new f cost then might not be useful.\\n\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" Common heuristics for n-puzzle problem : number of misplaced tiles ; Sum of distances of tiles from their goal position (Manhattan \\\n",
        "Distance). b* close to 1 for good heuristic.\\n\n",
        "If h2(n)>=h1(n) for any node n then h2 dominates h1.\\n\n",
        "State space of relaxed problem is supergraph of original problem. Cost of optimal solution in relaxed is an admissible heuristic in original. We must\\\n",
        " be able to save relaxed problems without search algorithms. h(n) = max {h1,…hn}. h dominates all in the set but takes longer to compute.\\n\n",
        "Admissible heuristics can also be derived from solution cost of subproblem. Cost of optimal solution in such a subproblem is a lower bound on the cost\\\n",
        " of complete problem. Each pattern database gives an admissible heuristic. In disjoint pattern databases, we record the number of moves for each \\\n",
        " subproblem and not the cost. Then the cost of two subproblems can be added to get an admissible heuristic.\\n\n",
        "For very large spaces, precomputation of optimal path cost can help. Instead of paths between all vertices, we can choose landmarks and find cost \\\n",
        "from all vertices to those landmarks. If optimal path does not go through landmark then h is inadmissible. Shortcuts are efficient but inadmissible.\\n \n",
        "Choosing landmarks : Random; Choose first one at random then iterate and choose one that is farthest from the previous one; For differential, choose \\\n",
        "ones that are on perimeter; Frequently requested landmarks.\\n\n",
        "Can an agent learn to search better? Yes using metalevel state space.\\n\n",
        "Heuristics can be learnt from experience.Some ML techniques work better with features that are relevant to the prediction. Linear combination\\\n",
        " of features can be used to predict the heuristic.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Informed search\" : \"Access to problem definition and heuristic\",    \n",
        "\"Admissible heuristic\" : \"Never overestimates the cost of reaching a goal. Optimistic.\",\n",
        "\"Satisficing Solutios\" : \"Good enough and suboptimal solutions\",\n",
        "\"Detour Index\" : \"Multiplier that is added to straight line index\",\n",
        "\"Relaxed Problem\" : \"Problem with fewer restrictions on actions\",\n",
        "\"Shortcuts\" : \"Added artificial edges that define optimal paths that are multi-action\",\n",
        "\"Metalevel state space\" : \"Each action is a computational step that alters the state\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 58,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1f136350-f2d8-4bae-ccff-8285bb45cad7"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 59,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Greedy Best-First : Expands nodes with lowest h(n). bNot optimal. Complete in finite spaces. \n\nA* : f(n) = g(n) + h(n). Complete. Optimal if h(n) is admissible or consistent. Every consistent heuristic is admissible. With consistent h, the first found path not a node is optimal so no need to re-add it to the frontier. It prunes that are not necessary to find optimal solution.  Optimally efficient. But it expands a lot of nodes.\n\nSearch Contours : All nodes in a contour have f(n) <= some X. Contours of uniform cost search are circles and that of A* stitch out towards the goal and become narrowly focused on optimal path. g(n) is monotonic, i.e, it always increases because path costs are positive. f(n) may increase or be equal only if h(n) is consistent.\n\nWeighted A* : f = g + W * h for some W >1. Somewhat like greedy search.\n\nBounded suboptimal search : Look for a solution that is within a constant factor W off optimal cost. Weighted A*b is an example.\n\nBounded-cost search : Look for solution whose cost is less than some constant C.\n\nUnbounded-cost search : Solution of any cosy accepted as long as it can be found quickly. Example is speedy search which is similar to greedy best first where h is number of actions to goal state irrespective of their cost.\n\nTo reduce memory needs, we can eliminate the use of reached states DS by using the separation property not frontiers and the prohibition of U-turn actions to make sure that all actions move outwards or onto another frontier state. We can also remove nodes from reached state DS using reference counts.\n\nBeam-Search : Frontier size limited by seeing k nodes with the best f-cost. Can be suboptimal and incomplete. Another way is to keep nodes that are within a certain limit of the best fscore.\n\nIDA* : at each iteration f-contour is increased. If each new node has new f cost then might not be useful.\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n Common heuristics for n-puzzle problem : number of misplaced tiles ; Sum of distances of tiles from their goal position (Manhattan Distance). b* close to 1 for good heuristic.\n\nIf h2(n)>=h1(n) for any node n then h2 dominates h1.\n\nState space of relaxed problem is supergraph of original problem. Cost of optimal solution in relaxed is an admissible heuristic in original. We must be able to save relaxed problems without search algorithms. h(n) = max {h1,…hn}. h dominates all in the set but takes longer to compute.\n\nAdmissible heuristics can also be derived from solution cost of subproblem. Cost of optimal solution in such a subproblem is a lower bound on the cost of complete problem. Each pattern database gives an admissible heuristic. In disjoint pattern databases, we record the number of moves for each  subproblem and not the cost. Then the cost of two subproblems can be added to get an admissible heuristic.\n\nFor very large spaces, precomputation of optimal path cost can help. Instead of paths between all vertices, we can choose landmarks and find cost from all vertices to those landmarks. If optimal path does not go through landmark then h is inadmissible. Shortcuts are efficient but inadmissible.\n \nChoosing landmarks : Random; Choose first one at random then iterate and choose one that is farthest from the previous one; For differential, choose ones that are on perimeter; Frequently requested landmarks.\n\nCan an agent learn to search better? Yes using metalevel state space.\n\nHeuristics can be learnt from experience.Some ML techniques work better with features that are relevant to the prediction. Linear combination of features can be used to predict the heuristic.\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Informed search** - Access to problem definition and heuristic\n* **Admissible heuristic** - Never overestimates the cost of reaching a goal. Optimistic.\n* **Satisficing solutios** - Good enough and suboptimal solutions\n* **Detour index** - Multiplier that is added to straight line index\n* **Relaxed problem** - Problem with fewer restrictions on actions\n* **Shortcuts** - Added artificial edges that define optimal paths that are multi-action\n* **Metalevel state space** - Each action is a computational step that alters the state\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_3 = \"\"\" Your summary here \"\"\"\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"Zero-sum\" : \"What is good for one player is just as bad for another player\",  \n",
        "\"Terminal state\" : \"State where game ends\",\n",
        "\"Utility Function\" : \"Calculates payoff for each player in terminal state s\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 60,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 708
        },
        "outputId": "7e305760-6cac-4a53-be7d-a1d00ac0e80b"
      },
      "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": 61,
      "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 Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \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 Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Zero-sum** - What is good for one player is just as bad for another player\n* **Terminal state** - State where game ends\n* **Utility function** - Calculates payoff for each player in terminal state s\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 = \"\"\" CSP is NP-complete. CSPs use general heuristics instead of domain specific ones AND factored representation (set of variables, each with a value). \\\n",
        "Three components of a CSP : Set of variables ( X : {X1,…,Xn}) ; Set of Domains (D : {D1,…,Dn}) ; Set of Constraints (C) that mention all allowed \\\n",
        "value combinations. Each constraint Cj  can be represented as <scope, rel>. Scope is a tuple of variables involved in the Constraint. Rel is the \\\n",
        "relationship that can be represented as an explicit set of tuples that stays the constraint or as a mathematical function like X < Y.\\n\n",
        "CSPs assign values to variable. An assignment is consistent if it does not violate any constraint and complete (/partial) if all (/some) variables\\\n",
        " are assigned (/unassigned) a value. A solution (/partial solution) to a CSP is complete (/partial assignment) and consistent. Why CSP? Easy to formulate;\\\n",
        "  fast and efficient; can quickly prune large parts of the search space that a search algorithm cannot. If we find that a partial assignment is not \\\n",
        "  consistent, we can rule out further assignments and find out why the assignment was inconsistent.\\n\n",
        "Simplest CSPs have discrete, finite domains. Discrete domains can also be infinite like the set of integers. Linear constraints have solution algorithms\\\n",
        " whereas none exist for nonlinear constraints. Linear programming is an example of CSP with continuous domain. Constraints can be unary(restricts single variable assignment)\\\n",
        " , binary(relationship between two variables) or higher \\\n",
        " order like ternary. A global constraint need not involve all the variables in a CSP. Most common global constraint is Alldiff which says that all the\\\n",
        "  variables involved in the constraint must have different values. All finite domain CSPs can be reduced to binary CSPs with the introduction of \\\n",
        "  sufficient auxiliary variables. Another way is a dual graph. However, Alldiff is more easier and less prone to errors.\\n\n",
        "Preference Constraints are generally encoded as costs on variable assignments and result in Constrained Optimization Problems (COP).  \"\"\"\n",
        "chapter6_2 = \"\"\" Constraint Propagation uses constraints to eliminate illegal values for a variable, which intern reduces the domain of another \\\n",
        "variable and so on. This can be done before search or can be mixed with it. Doing it before sometime may also solve a problem completely. The idea \\\n",
        "behind this is local consistency - enforcing local consistent in the constraints graph eliminates values for variables throughout the graph. Types of\\\n",
        " local consistency :\\n\n",
        "Node-consistency (k=1) : A variable is node consistent if all the values in its domain satisfy its unary constraints. A graph is node consistent if all\\\n",
        " its variables are node consistent.\\n\n",
        "Arc-consistency (k=2): A variable is arc consistent if all its domain values satisfy its binary constraints. Xi is arc consistent wrt Xj if for every \\\n",
        "value in Di there is some value in Dj that is consistent with the binary constraints in Xi and Xj. An algorithm for enforcing this is AC-3. Complexity \\\n",
        "of AC-3 is O(c * d ^3). Checking consistency of an arc can be done in O(d^2). C is the number of arcs and d is at most domain size of each variable.\\n\n",
        "Path-consistency (k=3) : Infers implicit constraints by looking at triples of variables and tightens the binary constraints. {Xi, Xj} are path consistent\\\n",
        " wrt Xm if for every {Xi = a, Xj = b} consistent with {Xi, Xj} there is some assignment for Xm that is consistent with {Xi, Xm} and {Xm, Xj}.\\n\n",
        "A CSP is strongly k-consistent if it is k consistent, k-1 consistent, …, 1 consistent. Total runtime of such a CSP is O(d * n^2). In the worst case, \\\n",
        "an algorithm that establishes n-consistency takes time and space exponential in n.\\n\n",
        "For Alldiff, if m variables and n possible distinct values, and m>n then the constraint cannot be satisfied. So, remove variables with only single\\\n",
        " possible values, then remove that value from domain and repeat till single variable left. If empty domain or m>n still then inconsistent and no solution.\\n\n",
        "Resource Constraint to Atmost constraint. Example is Atmost(10,P1,P2,…Pn). Inconsistency can be found by checking the sum of minimum possible value for\\\n",
        " each variable. \\n\n",
        "If domain is large, it is represented by upper and lower bounds and undergoes bound propagation. CSP is bound consistent if for every variable X \\\n",
        "(and every upper and lower bound of X) there exists some value of Y that is consistent , for every variable Y.\\n\n",
        "Sudoku has 81 variables, 27 Alldiff, domain is 1 to 9. Naked triples is another strategy is solve. \"\"\"\n",
        "chapter6_3 = \"\"\" If prev step leaves some variables with multiple values, we use backtracking that works on partial assignments. A tree with n nodes\\\n",
        " and d domain values has n! * d^n leaves and d^n possible complete assignments. Using the commutativity property of CSPs, the number of leaves is reduced\\\n",
        "  d^n.\\n\n",
        "In backtracking algorithm, we repeatedly choose unassigned variables and assign it all values in its domain via a recursive call trying to reach the\\\n",
        " solution. If solution found, it is returned; else backtracked to the previous state and the next value is tried. If nothing works then failure returned. \\n\n",
        "Which variable should be assigned next and in what order? Random and static ordering are inefficient. Choosing the most constrained variable is efficient \\\n",
        "and is called minimum-remaining-values (MRV) or fail-first heuristic. For tie-braking, we use degree heuristic, i.e, we choose the variable that is \\\n",
        "involved in the maximum number of constraints. The order of choosing values for the selected variable can be done by least-constraining-heuristic that \\\n",
        "chooses the value that eliminates the fewest number of choices for its neighbors.\\n\n",
        "What inferences to perform at each step? Forward checking intertwines search and inference. When X is chosen, we establish arc consistency for it by \\\n",
        "deleting any value from Y’s domain that is inconsistent with the X’s chosen value. MRV combined with FC is more effective. Maintaining Arc consistency\\\n",
        " checks further ahead than FC. When Xi is assigned a value, AC-3 is called for {Xj,Xi}. If empty set encountered, then we backtrack immediately. Unlike \\\n",
        " FC, MAC recursively propagates constraints when domain changes are made.\\n\n",
        "Can more than one step be backtracked if appropriate? We keep track of a conflict set that are inconsistent with values of X, then we backjump to the \\\n",
        "most recent assignment in the conflict set. This is used if no legal values for X are possible in the backtracking algorithm. FC can be used to create \\\n",
        "this set but it would be redundant to use buckjumping when FC or MAC are used. Conflict-directed backjumping uses conflict set along with any subsequent\\\n",
        " variables that result in inconsistent solutions. This is calculated by cs(Xi) <- cs(Xi) U cs(Xj) - {Xi} where Xi is the value we buckjump to.\\n\n",
        "Can partial states be saved and reused? The no-good are recorded by adding them as new constraints or by keeping them in a separate cache. No-goods can \\\n",
        "be used by FC or backjumping. \"\"\"\n",
        "chapter6_4 = \"\"\" Many CSPs can be solved by local search algorithms that are effective. Complete-state formulation is used where in every state, all the \\\n",
        "variables are assigned values and then value of one variable is changed at a time. It is changed to a value that causes the least number of conflicts by \\\n",
        "using min-conflicts heuristic. For n-queens, if initial placement of queens is ignored, runtime is approximately independent of problem size. It works \\\n",
        "effectively because the solutions are densely distributed in the state space. However, plateaus may be encountered which can be overcome by plateau search\\\n",
        " (sideway moves which result in a state with the same score as current state). Tabu search can direct this by keeping a list of visited states and\\\n",
        "  restricting the search from visiting them again. We can also move away from plateaus using simulated annealing.\\n\n",
        "In constraint weighing, each C is initially given weight 1. At each stage, the variable/value is changed such that the change will result in lowest\\\n",
        " total constraint weight. This add learning overtime by assigning higher weights to more difficult constraints and makes sure by ensuring that we move\\\n",
        "  to a better state by adding topography to the plateaus.\\n\n",
        "Local search is also useful in online environments when the problem changes. Example is flight scheduling and when an airport has to be ruled out due\\\n",
        " to weather changes. \"\"\"\n",
        "chapter6_5 = \"\"\" The approaches described in this section can also be used to solve problems such as probabilistic reasoning. Dividing the problem into\\\n",
        " independent subproblems can prove to be helpful.\\n \n",
        "Each connected component in a CSP corresponds to a subproblem CSPi. If Si is a solution of CSPi then UiSi is a solution of UiCSPi. With this, the total\\\n",
        " work is O((d^c)*(n/c)) where c is the number of variables in every subproblem. Without this the work is O(d^n).\\n\n",
        "Any CSP that is tree-structured has time complexity that is linear in number of variables.\\n\n",
        "Topological sort  with arc consistency can be done in O(n*d^2) complexity. Then we sign values to nodes as we go down the tree. We don’t need to backtrack. \\\n",
        "Two ways to convert graphs to trees:\\n\n",
        "Cutset Conditioning (Removing nodes) : Assign values to some variables whose removal forms a tree. Choose a subset S (cycle cutset) of such variables. \\\n",
        "For each possible consistent assignment in S, remove those values from the remaining variables’ domains and return solution + S if there is one for the \\\n",
        "remaining CSP. Total runtime is O((d^c) * (n-c)*(d^2)) where c is the size of cycle cutset. The smaller c is, the better.\\n\n",
        "Tree decomposition (Collapsing nodes together) : Each node consists of a set of variables. Every variable of original graph must be in at-least one node.\\\n",
        " If two variables are connected by a constraint, they must appear tog6her in at least one node along with the constraint. If a variable is in two nodes,\\\n",
        "  then it must appear in every node that connects those two nodes and the value of this variable is the same in all nodes. Complexity to solve this tree\\\n",
        "   is O((n)*d^2). Here the domain is the set of tuples of values. d has to be as small as possible. Tree width (w) = (Size of largest node) - 1. Tree width\\\n",
        "    of a graph is the minimum width among all its tree decompositions. Then, complexity is O((n)*d^(w+1)).\\n\n",
        "Timewise, tree decomposition is better because w<c+1. But cutset can be solved using linear memory whereas tree decomposition uses memory exponential\\\n",
        " in w.\\n\n",
        "Value Symmetry can be broken by symmetry breaking constraints. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"Constraint Graph\" : \"Graph with variables as nodes and constraints as edges\",\n",
        "\"n-ary Constraints\" : \"Constraints involving n variables\",\n",
        "\"Constraint hypergraph\" : \"Nodes are variables and hypernodes are n-ary constraints\",\n",
        "\"Dual Graph\" : \"Variables are constraints in the original graph and one binary constraints for each pair of variables\",\n",
        "\"Preference Constraints\" : \"Indicate a preferred solution\",\n",
        "\"Precedence Constraints\" : \"Define some order of succesion among operations\",\n",
        "\"Disjunctive Constraints\" : \"Constraints realted by OR\",\n",
        "\"Binary CSP\" : \"CSP with only unary or binary constraints and can be represented as a Constraint Graph\",\n",
        "\"k-Consistency\" : \"If for set of k-1 variables (each with consistent assignments), there is a consistent value for kth variable\",\n",
        "\"Chronological Backtracking\" : \"We backtrack to the most recent decision\",\n",
        "\"Constraint Learning\" : \"Identfying the minimum number of variables from conflict set that cause inconsistency\",\n",
        "\"No-good\" : \"The above set of variables and their values\",\n",
        "\"Constraint Weighing\" : \"Search is directed towards important constraints\",\n",
        "\"Constraint tree\" : \"Only one path connects two variables\",\n",
        "\"Directional Arc Consistency\" : \"A CSP is DAC for an order X1,...,Xn if every Xi is arc-consistent with Xj(j>i)\",\n",
        "\"Topological Sort\" : \"An ordering of variables such that each variables occurs after its parent in a tree\",\n",
        "\"Value Symmetry\" : \"Occurs when values to variables can be uniformly interchanged. (d! possibilities).\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 62,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "745d4cba-7589-4ea1-aa88-5875c7117936"
      },
      "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": 63,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP is NP-complete. CSPs use general heuristics instead of domain specific ones AND factored representation (set of variables, each with a value). Three components of a CSP : Set of variables ( X : {X1,…,Xn}) ; Set of Domains (D : {D1,…,Dn}) ; Set of Constraints (C) that mention all allowed value combinations. Each constraint Cj  can be represented as <scope, rel>. Scope is a tuple of variables involved in the Constraint. Rel is the relationship that can be represented as an explicit set of tuples that stays the constraint or as a mathematical function like X < Y.\n\nCSPs assign values to variable. An assignment is consistent if it does not violate any constraint and complete (/partial) if all (/some) variables are assigned (/unassigned) a value. A solution (/partial solution) to a CSP is complete (/partial assignment) and consistent. Why CSP? Easy to formulate;  fast and efficient; can quickly prune large parts of the search space that a search algorithm cannot. If we find that a partial assignment is not   consistent, we can rule out further assignments and find out why the assignment was inconsistent.\n\nSimplest CSPs have discrete, finite domains. Discrete domains can also be infinite like the set of integers. Linear constraints have solution algorithms whereas none exist for nonlinear constraints. Linear programming is an example of CSP with continuous domain. Constraints can be unary(restricts single variable assignment) , binary(relationship between two variables) or higher  order like ternary. A global constraint need not involve all the variables in a CSP. Most common global constraint is Alldiff which says that all the  variables involved in the constraint must have different values. All finite domain CSPs can be reduced to binary CSPs with the introduction of   sufficient auxiliary variables. Another way is a dual graph. However, Alldiff is more easier and less prone to errors.\n\nPreference Constraints are generally encoded as costs on variable assignments and result in Constrained Optimization Problems (COP).  \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Constraint Propagation uses constraints to eliminate illegal values for a variable, which intern reduces the domain of another variable and so on. This can be done before search or can be mixed with it. Doing it before sometime may also solve a problem completely. The idea behind this is local consistency - enforcing local consistent in the constraints graph eliminates values for variables throughout the graph. Types of local consistency :\n\nNode-consistency (k=1) : A variable is node consistent if all the values in its domain satisfy its unary constraints. A graph is node consistent if all its variables are node consistent.\n\nArc-consistency (k=2): A variable is arc consistent if all its domain values satisfy its binary constraints. Xi is arc consistent wrt Xj if for every value in Di there is some value in Dj that is consistent with the binary constraints in Xi and Xj. An algorithm for enforcing this is AC-3. Complexity of AC-3 is O(c * d ^3). Checking consistency of an arc can be done in O(d^2). C is the number of arcs and d is at most domain size of each variable.\n\nPath-consistency (k=3) : Infers implicit constraints by looking at triples of variables and tightens the binary constraints. {Xi, Xj} are path consistent wrt Xm if for every {Xi = a, Xj = b} consistent with {Xi, Xj} there is some assignment for Xm that is consistent with {Xi, Xm} and {Xm, Xj}.\n\nA CSP is strongly k-consistent if it is k consistent, k-1 consistent, …, 1 consistent. Total runtime of such a CSP is O(d * n^2). In the worst case, an algorithm that establishes n-consistency takes time and space exponential in n.\n\nFor Alldiff, if m variables and n possible distinct values, and m>n then the constraint cannot be satisfied. So, remove variables with only single possible values, then remove that value from domain and repeat till single variable left. If empty domain or m>n still then inconsistent and no solution.\n\nResource Constraint to Atmost constraint. Example is Atmost(10,P1,P2,…Pn). Inconsistency can be found by checking the sum of minimum possible value for each variable. \n\nIf domain is large, it is represented by upper and lower bounds and undergoes bound propagation. CSP is bound consistent if for every variable X (and every upper and lower bound of X) there exists some value of Y that is consistent , for every variable Y.\n\nSudoku has 81 variables, 27 Alldiff, domain is 1 to 9. Naked triples is another strategy is solve. \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n If prev step leaves some variables with multiple values, we use backtracking that works on partial assignments. A tree with n nodes and d domain values has n! * d^n leaves and d^n possible complete assignments. Using the commutativity property of CSPs, the number of leaves is reduced  d^n.\n\nIn backtracking algorithm, we repeatedly choose unassigned variables and assign it all values in its domain via a recursive call trying to reach the solution. If solution found, it is returned; else backtracked to the previous state and the next value is tried. If nothing works then failure returned. \n\nWhich variable should be assigned next and in what order? Random and static ordering are inefficient. Choosing the most constrained variable is efficient and is called minimum-remaining-values (MRV) or fail-first heuristic. For tie-braking, we use degree heuristic, i.e, we choose the variable that is involved in the maximum number of constraints. The order of choosing values for the selected variable can be done by least-constraining-heuristic that chooses the value that eliminates the fewest number of choices for its neighbors.\n\nWhat inferences to perform at each step? Forward checking intertwines search and inference. When X is chosen, we establish arc consistency for it by deleting any value from Y’s domain that is inconsistent with the X’s chosen value. MRV combined with FC is more effective. Maintaining Arc consistency checks further ahead than FC. When Xi is assigned a value, AC-3 is called for {Xj,Xi}. If empty set encountered, then we backtrack immediately. Unlike  FC, MAC recursively propagates constraints when domain changes are made.\n\nCan more than one step be backtracked if appropriate? We keep track of a conflict set that are inconsistent with values of X, then we backjump to the most recent assignment in the conflict set. This is used if no legal values for X are possible in the backtracking algorithm. FC can be used to create this set but it would be redundant to use buckjumping when FC or MAC are used. Conflict-directed backjumping uses conflict set along with any subsequent variables that result in inconsistent solutions. This is calculated by cs(Xi) <- cs(Xi) U cs(Xj) - {Xi} where Xi is the value we buckjump to.\n\nCan partial states be saved and reused? The no-good are recorded by adding them as new constraints or by keeping them in a separate cache. No-goods can be used by FC or backjumping. \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Many CSPs can be solved by local search algorithms that are effective. Complete-state formulation is used where in every state, all the variables are assigned values and then value of one variable is changed at a time. It is changed to a value that causes the least number of conflicts by using min-conflicts heuristic. For n-queens, if initial placement of queens is ignored, runtime is approximately independent of problem size. It works effectively because the solutions are densely distributed in the state space. However, plateaus may be encountered which can be overcome by plateau search (sideway moves which result in a state with the same score as current state). Tabu search can direct this by keeping a list of visited states and  restricting the search from visiting them again. We can also move away from plateaus using simulated annealing.\n\nIn constraint weighing, each C is initially given weight 1. At each stage, the variable/value is changed such that the change will result in lowest total constraint weight. This add learning overtime by assigning higher weights to more difficult constraints and makes sure by ensuring that we move  to a better state by adding topography to the plateaus.\n\nLocal search is also useful in online environments when the problem changes. Example is flight scheduling and when an airport has to be ruled out due to weather changes. \n\n## AIMA Chapter 6.5 The Structure of Problems\n The approaches described in this section can also be used to solve problems such as probabilistic reasoning. Dividing the problem into independent subproblems can prove to be helpful.\n \nEach connected component in a CSP corresponds to a subproblem CSPi. If Si is a solution of CSPi then UiSi is a solution of UiCSPi. With this, the total work is O((d^c)*(n/c)) where c is the number of variables in every subproblem. Without this the work is O(d^n).\n\nAny CSP that is tree-structured has time complexity that is linear in number of variables.\n\nTopological sort  with arc consistency can be done in O(n*d^2) complexity. Then we sign values to nodes as we go down the tree. We don’t need to backtrack. Two ways to convert graphs to trees:\n\nCutset Conditioning (Removing nodes) : Assign values to some variables whose removal forms a tree. Choose a subset S (cycle cutset) of such variables. For each possible consistent assignment in S, remove those values from the remaining variables’ domains and return solution + S if there is one for the remaining CSP. Total runtime is O((d^c) * (n-c)*(d^2)) where c is the size of cycle cutset. The smaller c is, the better.\n\nTree decomposition (Collapsing nodes together) : Each node consists of a set of variables. Every variable of original graph must be in at-least one node. If two variables are connected by a constraint, they must appear tog6her in at least one node along with the constraint. If a variable is in two nodes,  then it must appear in every node that connects those two nodes and the value of this variable is the same in all nodes. Complexity to solve this tree   is O((n)*d^2). Here the domain is the set of tuples of values. d has to be as small as possible. Tree width (w) = (Size of largest node) - 1. Tree width    of a graph is the minimum width among all its tree decompositions. Then, complexity is O((n)*d^(w+1)).\n\nTimewise, tree decomposition is better because w<c+1. But cutset can be solved using linear memory whereas tree decomposition uses memory exponential in w.\n\nValue Symmetry can be broken by symmetry breaking constraints. \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Constraint graph** - Graph with variables as nodes and constraints as edges\n* **N-ary constraints** - Constraints involving n variables\n* **Constraint hypergraph** - Nodes are variables and hypernodes are n-ary constraints\n* **Dual graph** - Variables are constraints in the original graph and one binary constraints for each pair of variables\n* **Preference constraints** - Indicate a preferred solution\n* **Precedence constraints** - Define some order of succesion among operations\n* **Disjunctive constraints** - Constraints realted by OR\n* **Binary csp** - CSP with only unary or binary constraints and can be represented as a Constraint Graph\n* **K-consistency** - If for set of k-1 variables (each with consistent assignments), there is a consistent value for kth variable\n* **Chronological backtracking** - We backtrack to the most recent decision\n* **Constraint learning** - Identfying the minimum number of variables from conflict set that cause inconsistency\n* **No-good** - The above set of variables and their values\n* **Constraint weighing** - Search is directed towards important constraints\n* **Constraint tree** - Only one path connects two variables\n* **Directional arc consistency** - A CSP is DAC for an order X1,...,Xn if every Xi is arc-consistent with Xj(j>i)\n* **Topological sort** - An ordering of variables such that each variables occurs after its parent in a tree\n* **Value symmetry** - Occurs when values to variables can be uniformly interchanged. (d! possibilities).\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 = \"\"\" The key component of a knowledge based agent is its knowledge base. A KBA’s inputs are its percepts and outputs are actions.\\\n",
        " Two standard operations are TELL and ASK. They may involve inference. TELL adds new sentences to the KB. ASK queries what is known. Initially,\\\n",
        "  a KB contains background knowledge. Three things that happen overtime the agent gram is called :\\n\n",
        "TELLS the KB what is perceived\\n\n",
        "ASKS what action to take. Involves reasoning.\\n\n",
        "TELLS the KB which action is selected and returns that action.\\n\n",
        "Three functions that act as the interface between sensors - actuators and core representation - reasoning :\\n\n",
        "MAKE-PERCEPT-SENTENCE : Makes a sentence out of the given percent at the given time\\n\n",
        "MAKE-ACTION-QUERY :  Makes a sentence that asks which action is to be taken\\n\n",
        "MAKE-ACTION-SENTENCE : Makes a sentence that asserts which action is taken \\n\n",
        "Details of representation language are hidden behind these 3 functions and the details of inference mechanisms are hidden behind TELL and ASK.\\\n",
        "There are different levels the KBA can be viewed at. With the knowledge level, we can fix its behavior. Two approaches to design a KBA’s behavior :\\n\n",
        "Declarative : Beginning from an empty KB, a KBA TELLS sentences one after another until it knows how to work with its environment. \\n\n",
        "Procedural : This converts the required behaviors directly into program code in an empty KB. \\n\n",
        "A successful agent often combines both. \"\"\"\n",
        "chapter7_2 = \"\"\" PEAS Environment : Performance Measure, Environment, Actuators, Sensors. The Wumpus environment is Deterministic, Discrete, \\\n",
        "Static, Single-Agent, Sequential (rewards are gained only after a sequence of actions are taken), Partially Observable (the agent’s location, \\\n",
        "availability of arrow and wumpus’s health are not directly observable).  \"\"\"\n",
        "chapter7_3 = \"\"\" The syntax of a representation language is used to express a sentence. M(\\u0391) is the set of models where \\u0391 is true or m satisfies \\\n",
        "\\u0391.\\n\n",
        "Entailment : If \\u0391 entails \\u0392 then \\u0391 is a stronger assertion and it eliminates more possible models.\\n\n",
        "Inference algorithms can derive a sentence \\u0391 from \\u0392 by inference i.\\n\n",
        "Unsound inference makes up things as it goes so it is not desirable. Model checking is sound and works when the space of the models is finite.\\n\n",
        "If KB is true in the real world then \\u0391 that is derived from KB by a sound inference is also true in the real world. \\n\n",
        "An agents sensors create a connection between the logical KB and the real world. Learning is fallible so KB need not necessarily be \\\n",
        "true in the real world but good learning procedures can optimize this. \"\"\"\n",
        "chapter7_4 = \"\"\" Syntax : Atomic sentences have a single proposition symbol that stands for a proposition and can be T or F. Two fixed\\\n",
        " proposition symbols are ‘True’ which is the always-true proposition and ‘False’ which is the always-false proposition. Complex sentences \\\n",
        " are constructed from simple sentences and logical connectives. The five common connectives are (in their order of precedence) : Negation, \\\n",
        " AND (Conjunction), OR (Disjunction), Implies (implication or conditional), If and only if (biconditional).\\n\n",
        "A positive(/negative) literal is an (/negated) atomic sentence. Parts of the conjunction (/disjunction) are called conjuncts (/disjuncts).\\n\n",
        "In A -> B, A is the premise or antecedent and B is its conclusion or consequent. Im-plications are also called rules or if-then statements.\\n \n",
        "Semantics : A set of rules that determine the truth of a sentence in a model. If 3 proposition symbols are present, then 2^3 = 8 models are \\\n",
        "possible. P -> Q is false only when P is true and Q is false. Truth tables specify the truth value of a sentence. Exclusive OR (XOR) returns \\\n",
        "false when both P and Q are true (OR does not do this). There need not be any relevance or causation between P and Q in propositional logic. \\\n",
        "P<->Q is true if P->Q and Q->P are both true.\\n\n",
        "TT-Entails algorithm is sound (implements the definition of entailment directly) and complete (works for any KB and alpha and terminates) because\\\n",
        " there are finite models.\\n\n",
        "If n symbols in all in KB and alpha then 2^n models. Time c complexity is O(2^n) and space complexity is O(n) because it is depth-first. Every known\\\n",
        " inference algorithm has time complexity that is exponential in input size. \"\"\"\n",
        "chapter7_5 = \"\"\" If the number of models is large then using theorem proving for entailment can be more efficient than model checking. P AND Q, Q \\\n",
        "AND P and logically equivalent., i.e, they are true in the same set of models. P OR (NOT P) is valid. Every tautology is logically Equivalent to the \\\n",
        "sentence ‘True’. Deduction theorem states that A entails B if and only if A ->B is valid. Every valid implication is a legitimate inference. Satisfiability can be checked by enumerating the possible models. SAT problem is NP-Complete. Ex: CSP. \n",
        "P is valid if and only if NOT P is unsatisfiable. P is satisfiable if and only if NOT P is not valid. A entails B if and only if A AND (NOT B) is \\\n",
        "unsatisfiable. This can be proved by proof by contradiction by first assuming B is False. This leads to contraction to known axiom A. Inference \\\n",
        "rules (All are sound):\\n\n",
        "Modus Ponens - When A and A->B are given,  can be inferred.\\n\n",
        "And-Elimination - Any of the conjuncts from a conduction can be inferred. (A AND B )/ A\\n\n",
        "All logical equivalences can be used as inference rules. Example : From A<->B, A->B AND B->A can be inferred and vice versa.\\n\n",
        "Proof by resolution : Resolution is an inference rule that when combined with any complete search algorithm yields a complete inference algorithm. \\\n",
        "Only one pair of complementary literals can be resolved at a time. For any sentences A and B, a resolution based theorem prover can decide whether \\\n",
        "A entails B.\\n\n",
        "In propositional logic, every sentence is logically equivalent to a conjunction of clauses. A CNF can be used as input to a resolution procedure.\\n\n",
        "In resolution algorithms, if no clauses can be added then KB does not entail A. If two clauses resolve into an empty clause then KB entails A. An \\\n",
        "empty clause is equivalent to False. In such an algorithm, we first convert KB AND NOT A into a CNF.\\n\n",
        "If a set of clauses are unsatisfiable then the resolution closure of those clauses is an empty clause.\\n\n",
        "Horn Clauses are closed under resolution. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Knowledge-based Agents\" : \"Maintain internal state of knowledge, reason over it, update it  and perform actions accordingly\", \n",
        "\"Knowledge Base\" : \"Set of sentences which are explained in a knowledge representation language\",\n",
        "\"Sentence\": \"Represent facts/assertions of the environment/world\",\n",
        "\"Axiom\" : \"A declaration that is not derived from other sentences\",\n",
        "\"Inference\" : \"Derie new sentences from what is known\",\n",
        "\"Knowledge Level\" : \"First and most abstract level of a KBA where we describe what the agent knows and its goals\",\n",
        "\"Logical Level\" : \"The level of a KBA at  which knowledge is encoded in sentences\",\n",
        "\"Implementation Level\" : \"The level that runs on the agent's architecture\",\n",
        "\"Learning Agent\" : \"A KBA that can learn for itself and from its past experiences\",\n",
        "\"Semantics of a sentence\" : \"Meaning of a sentence that determines the truth of it in each possible model\",\n",
        "\"Models\" : \"Mathematical abstracts that have a truth value for every sentence in them\",\n",
        "\"Entailment\" : \"One sentence is logically implied from another\",\n",
        "\"Logical Inference\" : \"When entailment is used to derive conclusions\",\n",
        "\"Model Checking\" : \"Enumerating all models to check if \\u0391 entails \\u0392\",\n",
        "\"Sound or Truth-Preserving\" : \"An inference that derives only entailed sentences\",\n",
        "\"Completeness\" : \"An inference algorithm is complete if it derives all entailed sentence\",\n",
        "\"Grounding\" : \"The relationship or connection between the real world and logical reasoning\",\n",
        "\"Learning\" : \"Sentence constructions that produce general rules\",\n",
        "\"Theorem Proving\" : \"Applying inference rules and proving a sentence without using models\",\n",
        "\"logical Equivalence\" : \"A and B are L.E if and only if they entail one another\",\n",
        "\"Validity (Tautologies)\" : \"A sentence \\u0391 is valid if it is true in ALL models\",\n",
        "\"Satisfiability\" : \"If there is some model m that the sentence is true in\",\n",
        "\"SAT problem\" : \"To determine the satisfiability of a sentence in propositional logic\",\n",
        "\"Reductio ad absurdum\" : \"Proof by refutation or proof by contradiction\",\n",
        "\"Modus Ponens\" : \"An inference rule ((Alpha -> Beta), Alpha) / Beta\",\n",
        "\"Monotonicity\" : \"As information is added to the KB, the set of entailed sentences increases\",\n",
        "\"Clause\" : \"Disjunction of literals\",\n",
        "\"Factoring\" : \"Removing multiple occurances of a literal from a sentence\",\n",
        "\"Conjunctive Normal Form\" : \"Sentence that is represented as a conjunction of clauses\",\n",
        "\"Ground Resolution Theorem\" : \"Completeness theorem for propositional logic resolution\",\n",
        "\"Definite Clause\" : \"Disjunction of literals that has only one positive clause\",\n",
        "\"Goal Clauses\" : \"Disjunction of literals with no positive clauses\",\n",
        "\"Horn Clauses\" : \"Disjunction of literals with atmost one positive clause\",\n",
        "\"k-CNF\" :\"A CNF with atomost k literals\"\n",
        "}\n",
        "\n",
        "\n"
      ],
      "execution_count": 64,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "23476e3a-005b-4cf4-a0aa-5cfc552dff8c"
      },
      "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": 65,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n The key component of a knowledge based agent is its knowledge base. A KBA’s inputs are its percepts and outputs are actions. Two standard operations are TELL and ASK. They may involve inference. TELL adds new sentences to the KB. ASK queries what is known. Initially,  a KB contains background knowledge. Three things that happen overtime the agent gram is called :\n\nTELLS the KB what is perceived\n\nASKS what action to take. Involves reasoning.\n\nTELLS the KB which action is selected and returns that action.\n\nThree functions that act as the interface between sensors - actuators and core representation - reasoning :\n\nMAKE-PERCEPT-SENTENCE : Makes a sentence out of the given percent at the given time\n\nMAKE-ACTION-QUERY :  Makes a sentence that asks which action is to be taken\n\nMAKE-ACTION-SENTENCE : Makes a sentence that asserts which action is taken \n\nDetails of representation language are hidden behind these 3 functions and the details of inference mechanisms are hidden behind TELL and ASK.There are different levels the KBA can be viewed at. With the knowledge level, we can fix its behavior. Two approaches to design a KBA’s behavior :\n\nDeclarative : Beginning from an empty KB, a KBA TELLS sentences one after another until it knows how to work with its environment. \n\nProcedural : This converts the required behaviors directly into program code in an empty KB. \n\nA successful agent often combines both. \n\n## AIMA Chapter 7.2 The Wumpus World\n PEAS Environment : Performance Measure, Environment, Actuators, Sensors. The Wumpus environment is Deterministic, Discrete, Static, Single-Agent, Sequential (rewards are gained only after a sequence of actions are taken), Partially Observable (the agent’s location, availability of arrow and wumpus’s health are not directly observable).  \n\n## AIMA Chapter 7.3 Logic\n The syntax of a representation language is used to express a sentence. M(Α) is the set of models where Α is true or m satisfies Α.\n\nEntailment : If Α entails Β then Α is a stronger assertion and it eliminates more possible models.\n\nInference algorithms can derive a sentence Α from Β by inference i.\n\nUnsound inference makes up things as it goes so it is not desirable. Model checking is sound and works when the space of the models is finite.\n\nIf KB is true in the real world then Α that is derived from KB by a sound inference is also true in the real world. \n\nAn agents sensors create a connection between the logical KB and the real world. Learning is fallible so KB need not necessarily be true in the real world but good learning procedures can optimize this. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Syntax : Atomic sentences have a single proposition symbol that stands for a proposition and can be T or F. Two fixed proposition symbols are ‘True’ which is the always-true proposition and ‘False’ which is the always-false proposition. Complex sentences  are constructed from simple sentences and logical connectives. The five common connectives are (in their order of precedence) : Negation,  AND (Conjunction), OR (Disjunction), Implies (implication or conditional), If and only if (biconditional).\n\nA positive(/negative) literal is an (/negated) atomic sentence. Parts of the conjunction (/disjunction) are called conjuncts (/disjuncts).\n\nIn A -> B, A is the premise or antecedent and B is its conclusion or consequent. Im-plications are also called rules or if-then statements.\n \nSemantics : A set of rules that determine the truth of a sentence in a model. If 3 proposition symbols are present, then 2^3 = 8 models are possible. P -> Q is false only when P is true and Q is false. Truth tables specify the truth value of a sentence. Exclusive OR (XOR) returns false when both P and Q are true (OR does not do this). There need not be any relevance or causation between P and Q in propositional logic. P<->Q is true if P->Q and Q->P are both true.\n\nTT-Entails algorithm is sound (implements the definition of entailment directly) and complete (works for any KB and alpha and terminates) because there are finite models.\n\nIf n symbols in all in KB and alpha then 2^n models. Time c complexity is O(2^n) and space complexity is O(n) because it is depth-first. Every known inference algorithm has time complexity that is exponential in input size. \n\n## AIMA 7.5 Propositional Theorem Proving\n If the number of models is large then using theorem proving for entailment can be more efficient than model checking. P AND Q, Q AND P and logically equivalent., i.e, they are true in the same set of models. P OR (NOT P) is valid. Every tautology is logically Equivalent to the sentence ‘True’. Deduction theorem states that A entails B if and only if A ->B is valid. Every valid implication is a legitimate inference. Satisfiability can be checked by enumerating the possible models. SAT problem is NP-Complete. Ex: CSP. \nP is valid if and only if NOT P is unsatisfiable. P is satisfiable if and only if NOT P is not valid. A entails B if and only if A AND (NOT B) is unsatisfiable. This can be proved by proof by contradiction by first assuming B is False. This leads to contraction to known axiom A. Inference rules (All are sound):\n\nModus Ponens - When A and A->B are given,  can be inferred.\n\nAnd-Elimination - Any of the conjuncts from a conduction can be inferred. (A AND B )/ A\n\nAll logical equivalences can be used as inference rules. Example : From A<->B, A->B AND B->A can be inferred and vice versa.\n\nProof by resolution : Resolution is an inference rule that when combined with any complete search algorithm yields a complete inference algorithm. Only one pair of complementary literals can be resolved at a time. For any sentences A and B, a resolution based theorem prover can decide whether A entails B.\n\nIn propositional logic, every sentence is logically equivalent to a conjunction of clauses. A CNF can be used as input to a resolution procedure.\n\nIn resolution algorithms, if no clauses can be added then KB does not entail A. If two clauses resolve into an empty clause then KB entails A. An empty clause is equivalent to False. In such an algorithm, we first convert KB AND NOT A into a CNF.\n\nIf a set of clauses are unsatisfiable then the resolution closure of those clauses is an empty clause.\n\nHorn Clauses are closed under resolution. \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge-based agents** - Maintain internal state of knowledge, reason over it, update it  and perform actions accordingly\n* **Knowledge base** - Set of sentences which are explained in a knowledge representation language\n* **Sentence** - Represent facts/assertions of the environment/world\n* **Axiom** - A declaration that is not derived from other sentences\n* **Inference** - Derie new sentences from what is known\n* **Knowledge level** - First and most abstract level of a KBA where we describe what the agent knows and its goals\n* **Logical level** - The level of a KBA at  which knowledge is encoded in sentences\n* **Implementation level** - The level that runs on the agent's architecture\n* **Learning agent** - A KBA that can learn for itself and from its past experiences\n* **Semantics of a sentence** - Meaning of a sentence that determines the truth of it in each possible model\n* **Models** - Mathematical abstracts that have a truth value for every sentence in them\n* **Entailment** - One sentence is logically implied from another\n* **Logical inference** - When entailment is used to derive conclusions\n* **Model checking** - Enumerating all models to check if Α entails Β\n* **Sound or truth-preserving** - An inference that derives only entailed sentences\n* **Completeness** - An inference algorithm is complete if it derives all entailed sentence\n* **Grounding** - The relationship or connection between the real world and logical reasoning\n* **Learning** - Sentence constructions that produce general rules\n* **Theorem proving** - Applying inference rules and proving a sentence without using models\n* **Logical equivalence** - A and B are L.E if and only if they entail one another\n* **Validity (tautologies)** - A sentence Α is valid if it is true in ALL models\n* **Satisfiability** - If there is some model m that the sentence is true in\n* **Sat problem** - To determine the satisfiability of a sentence in propositional logic\n* **Reductio ad absurdum** - Proof by refutation or proof by contradiction\n* **Modus ponens** - An inference rule ((Alpha -> Beta), Alpha) / Beta\n* **Monotonicity** - As information is added to the KB, the set of entailed sentences increases\n* **Clause** - Disjunction of literals\n* **Factoring** - Removing multiple occurances of a literal from a sentence\n* **Conjunctive normal form** - Sentence that is represented as a conjunction of clauses\n* **Ground resolution theorem** - Completeness theorem for propositional logic resolution\n* **Definite clause** - Disjunction of literals that has only one positive clause\n* **Goal clauses** - Disjunction of literals with no positive clauses\n* **Horn clauses** - Disjunction of literals with atmost one positive clause\n* **K-cnf** - A CNF with atomost k literals\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": "9839f6c4-9984-44ca-d3fd-afdfef95211d"
      },
      "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": 66,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \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 Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \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 An agent can follow a four phase problem solving process : Goal formulation; Problem formulation (define states and actions); Search (stimulate various sequence of actions until solution is found) and Execution. The solution is a fixed sequence of actions if the  environment is fully-observable, deterministic and known. The agent can then execute the solution blindly, ignoring its percepts (open loop).  If the environment is non-deterministic then agent has to monitor its percepts (closed loop). In this case, where the environment is partially  observable and non-deterministic, we follow a branching strategy of solution which recommends actions based on the percepts that arrive. \n\nSearch problem definition : Set of states (state space); Initial state; Set of goal states; Actions; Transition model; Action cost function. Actions(s) is a finite set of actions that are applicable in state s. Result(s, a) returns the state that results from performing action a on state s. Action-Cost(s, a, s’) is the cost of applying a to go from state s to s’. Cost function can b e used as performance measure. A graph (vertices are states  and edges are actions) can be used to represent the state space. The right level of abstraction is crucial - removing as much detail as possible and   ensuring that the abstracted actions are easy to perform.  \n\n## AIMA Chapter 3.2 Example Problems\n Standardized vs Real-world problems. Standardized problems are used as a benchmark to compare the performance of algorithms. Real-world problems vary from situation to situation. \n\nStandardized problems examples : Grid Navigation (ex : Vacuum Cleaner prob); Sokoban Puzzle (Goal is to push boxes scattered around grid to storage locations); Sliding tile puzzle; Donald Knuth puzzle (start with 4 and apply square root, factorial and floor in any sequence to get a particular number - this prob has infinite state space). Infinite state spaces are common for problems involving mathematical expressions,  circuits, proofs, programs and other objects that are recursively defined. \n\nReal-World problems examples : Route-finding (Routing video streams in computer networks, military operations planning, airline-planning systems); Touring problems (Traveling salesperson); VLSI layout; Robot navigation; Automatic assembly sequencing (Protein Design). In robot navigation, robot can make its own path and state-space can be multi-dimensional. In assembly sequencing, deciding the legal actions is the most expensive part. \n\n## AIMA Chapter 3.3 Search Algorithms\n In a search tree, every node corresponds to a state in the state space, the edges correspond to the actions and the root node corresponds to the initial state. The state space consists of all the possible states and actions. The search tree consists of paths between  states to reach the goal. There can be multiple paths to a state in a search tree but each node has a unique path back to the root. A state is  considered to be reached if it has a node corresponding to it and expanded if it has child nodes. The frontier divides the state space into  2 regions : Interior (every state has been expanded) and exterior (states that have not yet been reached).\n\nBest-First Search : From the frontier, the node with the lowest value of some evaluation function f(n) is chosen to be expanded next. If this is the goal state, we return. To the frontier, each child node is added if it hasn’t been reached before or is being reached with a lower path cost than before.\n\nSearch Data-Structures : node.STATE; node.ACTION; node.PARENT; node.PATH-COST [g(n)]. For the frontier, we use a queue (either priority queue, FIFO or LIFO[stack]). The operations that can be performed on a frontier are : Is-Empty, Pop (removes node on top) , Top (returns node on top), Add. A look up table can be used to store the reached states where the state is the key and the node for that state is the value.\n\nAvoiding redundant paths makes an algorithm much faster. Three approaches to avoid redundant paths : Store all reached states and only the best path to reach that state ; Not worrying about repeated states in large state space problems (ex : assembly problem); Check for cycles but not redundant paths in general. The first approach can be used if the reached states can fit in the memory.  In the third approach, some algorithms check all the way up and eliminate all cycles whereas some check only a few links up and remove short cycles. Other algorithms have to be used in this case to remove long cycles. \n\nBest First Search is a graph search algorithm. Tree search is slower than n graph search but uses less memory.\n\nEvaluating algorithms : Completeness (must be systematic in exploring infinite state space); Cost Optimality; Time complexity; Space complexity. T and S complexity are considered with respect to difficulty of the problem. Ex: for explicit search graphs, space = |V| + |E| but for implicit it is measured in terms of d, m, b. \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \nBFS : All actions have the same cost. Complete (on infinite search spaces as well) and optimal(when all actions have same cost). f(n) is the number of actions it takes to reach the node, i.e, the depth. FIFO Queue is used. ‘Reached’ can be a set of states and not a mapping from state to node. Early goal test is done. Time and space complexity are O(b^d).\n\nDjikstra’s or Uniform-Cost search : Actions have different cost. f(n) is cost of path from root to node n. Expands nodes with uniform path cost. Late goal test is done. Complete and Optimal.\n\nDFS : Deepest node expanded. BFS with f(n) as negative of depth. Tree-like search, not graph. Does not keep track of reached states. Not optimal. Complete if state space is finite and acyclic. In cyclic, it can get stick in infinite loop so some DFS check each new node for cycles. Not complete in infinite spaces. Less need for memory.\n\nBacktracking : DFS variant which uses lesser memory. Only one successor is generated instead of all bye modifying current state instead of generating brand new state. Critical when state space is large.\n\nDepth limited : Treat all nodes at depth ml as leaf nodes. Incomplete if l not chosen correctly. Diameter of state space gives efficient value for l.\n\nIterative deepening : l is increased till solution is found or failure rather this cutoff value. Optimal if all actions have same cost. Complete for finite acyclic and for cyclic if we check for cycles all the way up. Preferred when state space is large and cannot fit in memory and depth of solution is not known.\n\nBidirectional : Forward from initial state and backward from goal state. Two frontiers and tables of reached states. Solution found when the two frontiers collide. When f(n) is path cost then it becomes bidirectional uniform cost search. \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search and uses atomic structures\n* **Planning agents** - Agents that use factored or structured representation of states\n* **Path** - Sequence of actions\n* **Solution** - Path from initial to goal state\n* **Optimal solution** - Solution with lowest path cost\n* **Abstraction** - Removal of detail from representation\n* **Search problem** - Input is a search problem and output is a solution or reports a failure if there is none\n* **Frontier** - A set of nodes that have been reached but not expanded yet\n* **Redundant paths** - A path that results in a repeated state\n* **Cycle or loopy paths** - Special case of redundant paths A-B and B-A\n* **Graph search/ tree search** - Search algorithm that checks for redundant paths/ Does not check for redundant paths\n* **Completeness** - Return a solution if there is one and report failure if no solution\n* **Cost optimality** - Finds a solution with the lowest path cost\n* **Depth (d)** - Number of actions in an optimal solution\n* **Branching factor (b)** - The total number of child nodes of a node that need to be considered\n* **(m)** - Maximum number of actions in any path of the tree\n* **Uninformed search** - Access to only the prolem definition. No heuristic.\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Greedy Best-First : Expands nodes with lowest h(n). bNot optimal. Complete in finite spaces. \n\nA* : f(n) = g(n) + h(n). Complete. Optimal if h(n) is admissible or consistent. Every consistent heuristic is admissible. With consistent h, the first found path not a node is optimal so no need to re-add it to the frontier. It prunes that are not necessary to find optimal solution.  Optimally efficient. But it expands a lot of nodes.\n\nSearch Contours : All nodes in a contour have f(n) <= some X. Contours of uniform cost search are circles and that of A* stitch out towards the goal and become narrowly focused on optimal path. g(n) is monotonic, i.e, it always increases because path costs are positive. f(n) may increase or be equal only if h(n) is consistent.\n\nWeighted A* : f = g + W * h for some W >1. Somewhat like greedy search.\n\nBounded suboptimal search : Look for a solution that is within a constant factor W off optimal cost. Weighted A*b is an example.\n\nBounded-cost search : Look for solution whose cost is less than some constant C.\n\nUnbounded-cost search : Solution of any cosy accepted as long as it can be found quickly. Example is speedy search which is similar to greedy best first where h is number of actions to goal state irrespective of their cost.\n\nTo reduce memory needs, we can eliminate the use of reached states DS by using the separation property not frontiers and the prohibition of U-turn actions to make sure that all actions move outwards or onto another frontier state. We can also remove nodes from reached state DS using reference counts.\n\nBeam-Search : Frontier size limited by seeing k nodes with the best f-cost. Can be suboptimal and incomplete. Another way is to keep nodes that are within a certain limit of the best fscore.\n\nIDA* : at each iteration f-contour is increased. If each new node has new f cost then might not be useful.\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n Common heuristics for n-puzzle problem : number of misplaced tiles ; Sum of distances of tiles from their goal position (Manhattan Distance). b* close to 1 for good heuristic.\n\nIf h2(n)>=h1(n) for any node n then h2 dominates h1.\n\nState space of relaxed problem is supergraph of original problem. Cost of optimal solution in relaxed is an admissible heuristic in original. We must be able to save relaxed problems without search algorithms. h(n) = max {h1,…hn}. h dominates all in the set but takes longer to compute.\n\nAdmissible heuristics can also be derived from solution cost of subproblem. Cost of optimal solution in such a subproblem is a lower bound on the cost of complete problem. Each pattern database gives an admissible heuristic. In disjoint pattern databases, we record the number of moves for each  subproblem and not the cost. Then the cost of two subproblems can be added to get an admissible heuristic.\n\nFor very large spaces, precomputation of optimal path cost can help. Instead of paths between all vertices, we can choose landmarks and find cost from all vertices to those landmarks. If optimal path does not go through landmark then h is inadmissible. Shortcuts are efficient but inadmissible.\n \nChoosing landmarks : Random; Choose first one at random then iterate and choose one that is farthest from the previous one; For differential, choose ones that are on perimeter; Frequently requested landmarks.\n\nCan an agent learn to search better? Yes using metalevel state space.\n\nHeuristics can be learnt from experience.Some ML techniques work better with features that are relevant to the prediction. Linear combination of features can be used to predict the heuristic.\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Informed search** - Access to problem definition and heuristic\n* **Admissible heuristic** - Never overestimates the cost of reaching a goal. Optimistic.\n* **Satisficing solutios** - Good enough and suboptimal solutions\n* **Detour index** - Multiplier that is added to straight line index\n* **Relaxed problem** - Problem with fewer restrictions on actions\n* **Shortcuts** - Added artificial edges that define optimal paths that are multi-action\n* **Metalevel state space** - Each action is a computational step that alters the state\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 Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \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 Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Zero-sum** - What is good for one player is just as bad for another player\n* **Terminal state** - State where game ends\n* **Utility function** - Calculates payoff for each player in terminal state s\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP is NP-complete. CSPs use general heuristics instead of domain specific ones AND factored representation (set of variables, each with a value). Three components of a CSP : Set of variables ( X : {X1,…,Xn}) ; Set of Domains (D : {D1,…,Dn}) ; Set of Constraints (C) that mention all allowed value combinations. Each constraint Cj  can be represented as <scope, rel>. Scope is a tuple of variables involved in the Constraint. Rel is the relationship that can be represented as an explicit set of tuples that stays the constraint or as a mathematical function like X < Y.\n\nCSPs assign values to variable. An assignment is consistent if it does not violate any constraint and complete (/partial) if all (/some) variables are assigned (/unassigned) a value. A solution (/partial solution) to a CSP is complete (/partial assignment) and consistent. Why CSP? Easy to formulate;  fast and efficient; can quickly prune large parts of the search space that a search algorithm cannot. If we find that a partial assignment is not   consistent, we can rule out further assignments and find out why the assignment was inconsistent.\n\nSimplest CSPs have discrete, finite domains. Discrete domains can also be infinite like the set of integers. Linear constraints have solution algorithms whereas none exist for nonlinear constraints. Linear programming is an example of CSP with continuous domain. Constraints can be unary(restricts single variable assignment) , binary(relationship between two variables) or higher  order like ternary. A global constraint need not involve all the variables in a CSP. Most common global constraint is Alldiff which says that all the  variables involved in the constraint must have different values. All finite domain CSPs can be reduced to binary CSPs with the introduction of   sufficient auxiliary variables. Another way is a dual graph. However, Alldiff is more easier and less prone to errors.\n\nPreference Constraints are generally encoded as costs on variable assignments and result in Constrained Optimization Problems (COP).  \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Constraint Propagation uses constraints to eliminate illegal values for a variable, which intern reduces the domain of another variable and so on. This can be done before search or can be mixed with it. Doing it before sometime may also solve a problem completely. The idea behind this is local consistency - enforcing local consistent in the constraints graph eliminates values for variables throughout the graph. Types of local consistency :\n\nNode-consistency (k=1) : A variable is node consistent if all the values in its domain satisfy its unary constraints. A graph is node consistent if all its variables are node consistent.\n\nArc-consistency (k=2): A variable is arc consistent if all its domain values satisfy its binary constraints. Xi is arc consistent wrt Xj if for every value in Di there is some value in Dj that is consistent with the binary constraints in Xi and Xj. An algorithm for enforcing this is AC-3. Complexity of AC-3 is O(c * d ^3). Checking consistency of an arc can be done in O(d^2). C is the number of arcs and d is at most domain size of each variable.\n\nPath-consistency (k=3) : Infers implicit constraints by looking at triples of variables and tightens the binary constraints. {Xi, Xj} are path consistent wrt Xm if for every {Xi = a, Xj = b} consistent with {Xi, Xj} there is some assignment for Xm that is consistent with {Xi, Xm} and {Xm, Xj}.\n\nA CSP is strongly k-consistent if it is k consistent, k-1 consistent, …, 1 consistent. Total runtime of such a CSP is O(d * n^2). In the worst case, an algorithm that establishes n-consistency takes time and space exponential in n.\n\nFor Alldiff, if m variables and n possible distinct values, and m>n then the constraint cannot be satisfied. So, remove variables with only single possible values, then remove that value from domain and repeat till single variable left. If empty domain or m>n still then inconsistent and no solution.\n\nResource Constraint to Atmost constraint. Example is Atmost(10,P1,P2,…Pn). Inconsistency can be found by checking the sum of minimum possible value for each variable. \n\nIf domain is large, it is represented by upper and lower bounds and undergoes bound propagation. CSP is bound consistent if for every variable X (and every upper and lower bound of X) there exists some value of Y that is consistent , for every variable Y.\n\nSudoku has 81 variables, 27 Alldiff, domain is 1 to 9. Naked triples is another strategy is solve. \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n If prev step leaves some variables with multiple values, we use backtracking that works on partial assignments. A tree with n nodes and d domain values has n! * d^n leaves and d^n possible complete assignments. Using the commutativity property of CSPs, the number of leaves is reduced  d^n.\n\nIn backtracking algorithm, we repeatedly choose unassigned variables and assign it all values in its domain via a recursive call trying to reach the solution. If solution found, it is returned; else backtracked to the previous state and the next value is tried. If nothing works then failure returned. \n\nWhich variable should be assigned next and in what order? Random and static ordering are inefficient. Choosing the most constrained variable is efficient and is called minimum-remaining-values (MRV) or fail-first heuristic. For tie-braking, we use degree heuristic, i.e, we choose the variable that is involved in the maximum number of constraints. The order of choosing values for the selected variable can be done by least-constraining-heuristic that chooses the value that eliminates the fewest number of choices for its neighbors.\n\nWhat inferences to perform at each step? Forward checking intertwines search and inference. When X is chosen, we establish arc consistency for it by deleting any value from Y’s domain that is inconsistent with the X’s chosen value. MRV combined with FC is more effective. Maintaining Arc consistency checks further ahead than FC. When Xi is assigned a value, AC-3 is called for {Xj,Xi}. If empty set encountered, then we backtrack immediately. Unlike  FC, MAC recursively propagates constraints when domain changes are made.\n\nCan more than one step be backtracked if appropriate? We keep track of a conflict set that are inconsistent with values of X, then we backjump to the most recent assignment in the conflict set. This is used if no legal values for X are possible in the backtracking algorithm. FC can be used to create this set but it would be redundant to use buckjumping when FC or MAC are used. Conflict-directed backjumping uses conflict set along with any subsequent variables that result in inconsistent solutions. This is calculated by cs(Xi) <- cs(Xi) U cs(Xj) - {Xi} where Xi is the value we buckjump to.\n\nCan partial states be saved and reused? The no-good are recorded by adding them as new constraints or by keeping them in a separate cache. No-goods can be used by FC or backjumping. \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Many CSPs can be solved by local search algorithms that are effective. Complete-state formulation is used where in every state, all the variables are assigned values and then value of one variable is changed at a time. It is changed to a value that causes the least number of conflicts by using min-conflicts heuristic. For n-queens, if initial placement of queens is ignored, runtime is approximately independent of problem size. It works effectively because the solutions are densely distributed in the state space. However, plateaus may be encountered which can be overcome by plateau search (sideway moves which result in a state with the same score as current state). Tabu search can direct this by keeping a list of visited states and  restricting the search from visiting them again. We can also move away from plateaus using simulated annealing.\n\nIn constraint weighing, each C is initially given weight 1. At each stage, the variable/value is changed such that the change will result in lowest total constraint weight. This add learning overtime by assigning higher weights to more difficult constraints and makes sure by ensuring that we move  to a better state by adding topography to the plateaus.\n\nLocal search is also useful in online environments when the problem changes. Example is flight scheduling and when an airport has to be ruled out due to weather changes. \n\n## AIMA Chapter 6.5 The Structure of Problems\n The approaches described in this section can also be used to solve problems such as probabilistic reasoning. Dividing the problem into independent subproblems can prove to be helpful.\n \nEach connected component in a CSP corresponds to a subproblem CSPi. If Si is a solution of CSPi then UiSi is a solution of UiCSPi. With this, the total work is O((d^c)*(n/c)) where c is the number of variables in every subproblem. Without this the work is O(d^n).\n\nAny CSP that is tree-structured has time complexity that is linear in number of variables.\n\nTopological sort  with arc consistency can be done in O(n*d^2) complexity. Then we sign values to nodes as we go down the tree. We don’t need to backtrack. Two ways to convert graphs to trees:\n\nCutset Conditioning (Removing nodes) : Assign values to some variables whose removal forms a tree. Choose a subset S (cycle cutset) of such variables. For each possible consistent assignment in S, remove those values from the remaining variables’ domains and return solution + S if there is one for the remaining CSP. Total runtime is O((d^c) * (n-c)*(d^2)) where c is the size of cycle cutset. The smaller c is, the better.\n\nTree decomposition (Collapsing nodes together) : Each node consists of a set of variables. Every variable of original graph must be in at-least one node. If two variables are connected by a constraint, they must appear tog6her in at least one node along with the constraint. If a variable is in two nodes,  then it must appear in every node that connects those two nodes and the value of this variable is the same in all nodes. Complexity to solve this tree   is O((n)*d^2). Here the domain is the set of tuples of values. d has to be as small as possible. Tree width (w) = (Size of largest node) - 1. Tree width    of a graph is the minimum width among all its tree decompositions. Then, complexity is O((n)*d^(w+1)).\n\nTimewise, tree decomposition is better because w<c+1. But cutset can be solved using linear memory whereas tree decomposition uses memory exponential in w.\n\nValue Symmetry can be broken by symmetry breaking constraints. \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Constraint graph** - Graph with variables as nodes and constraints as edges\n* **N-ary constraints** - Constraints involving n variables\n* **Constraint hypergraph** - Nodes are variables and hypernodes are n-ary constraints\n* **Dual graph** - Variables are constraints in the original graph and one binary constraints for each pair of variables\n* **Preference constraints** - Indicate a preferred solution\n* **Precedence constraints** - Define some order of succesion among operations\n* **Disjunctive constraints** - Constraints realted by OR\n* **Binary csp** - CSP with only unary or binary constraints and can be represented as a Constraint Graph\n* **K-consistency** - If for set of k-1 variables (each with consistent assignments), there is a consistent value for kth variable\n* **Chronological backtracking** - We backtrack to the most recent decision\n* **Constraint learning** - Identfying the minimum number of variables from conflict set that cause inconsistency\n* **No-good** - The above set of variables and their values\n* **Constraint weighing** - Search is directed towards important constraints\n* **Constraint tree** - Only one path connects two variables\n* **Directional arc consistency** - A CSP is DAC for an order X1,...,Xn if every Xi is arc-consistent with Xj(j>i)\n* **Topological sort** - An ordering of variables such that each variables occurs after its parent in a tree\n* **Value symmetry** - Occurs when values to variables can be uniformly interchanged. (d! possibilities).\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n The key component of a knowledge based agent is its knowledge base. A KBA’s inputs are its percepts and outputs are actions. Two standard operations are TELL and ASK. They may involve inference. TELL adds new sentences to the KB. ASK queries what is known. Initially,  a KB contains background knowledge. Three things that happen overtime the agent gram is called :\n\nTELLS the KB what is perceived\n\nASKS what action to take. Involves reasoning.\n\nTELLS the KB which action is selected and returns that action.\n\nThree functions that act as the interface between sensors - actuators and core representation - reasoning :\n\nMAKE-PERCEPT-SENTENCE : Makes a sentence out of the given percent at the given time\n\nMAKE-ACTION-QUERY :  Makes a sentence that asks which action is to be taken\n\nMAKE-ACTION-SENTENCE : Makes a sentence that asserts which action is taken \n\nDetails of representation language are hidden behind these 3 functions and the details of inference mechanisms are hidden behind TELL and ASK.There are different levels the KBA can be viewed at. With the knowledge level, we can fix its behavior. Two approaches to design a KBA’s behavior :\n\nDeclarative : Beginning from an empty KB, a KBA TELLS sentences one after another until it knows how to work with its environment. \n\nProcedural : This converts the required behaviors directly into program code in an empty KB. \n\nA successful agent often combines both. \n\n## AIMA Chapter 7.2 The Wumpus World\n PEAS Environment : Performance Measure, Environment, Actuators, Sensors. The Wumpus environment is Deterministic, Discrete, Static, Single-Agent, Sequential (rewards are gained only after a sequence of actions are taken), Partially Observable (the agent’s location, availability of arrow and wumpus’s health are not directly observable).  \n\n## AIMA Chapter 7.3 Logic\n The syntax of a representation language is used to express a sentence. M(Α) is the set of models where Α is true or m satisfies Α.\n\nEntailment : If Α entails Β then Α is a stronger assertion and it eliminates more possible models.\n\nInference algorithms can derive a sentence Α from Β by inference i.\n\nUnsound inference makes up things as it goes so it is not desirable. Model checking is sound and works when the space of the models is finite.\n\nIf KB is true in the real world then Α that is derived from KB by a sound inference is also true in the real world. \n\nAn agents sensors create a connection between the logical KB and the real world. Learning is fallible so KB need not necessarily be true in the real world but good learning procedures can optimize this. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Syntax : Atomic sentences have a single proposition symbol that stands for a proposition and can be T or F. Two fixed proposition symbols are ‘True’ which is the always-true proposition and ‘False’ which is the always-false proposition. Complex sentences  are constructed from simple sentences and logical connectives. The five common connectives are (in their order of precedence) : Negation,  AND (Conjunction), OR (Disjunction), Implies (implication or conditional), If and only if (biconditional).\n\nA positive(/negative) literal is an (/negated) atomic sentence. Parts of the conjunction (/disjunction) are called conjuncts (/disjuncts).\n\nIn A -> B, A is the premise or antecedent and B is its conclusion or consequent. Im-plications are also called rules or if-then statements.\n \nSemantics : A set of rules that determine the truth of a sentence in a model. If 3 proposition symbols are present, then 2^3 = 8 models are possible. P -> Q is false only when P is true and Q is false. Truth tables specify the truth value of a sentence. Exclusive OR (XOR) returns false when both P and Q are true (OR does not do this). There need not be any relevance or causation between P and Q in propositional logic. P<->Q is true if P->Q and Q->P are both true.\n\nTT-Entails algorithm is sound (implements the definition of entailment directly) and complete (works for any KB and alpha and terminates) because there are finite models.\n\nIf n symbols in all in KB and alpha then 2^n models. Time c complexity is O(2^n) and space complexity is O(n) because it is depth-first. Every known inference algorithm has time complexity that is exponential in input size. \n\n## AIMA 7.5 Propositional Theorem Proving\n If the number of models is large then using theorem proving for entailment can be more efficient than model checking. P AND Q, Q AND P and logically equivalent., i.e, they are true in the same set of models. P OR (NOT P) is valid. Every tautology is logically Equivalent to the sentence ‘True’. Deduction theorem states that A entails B if and only if A ->B is valid. Every valid implication is a legitimate inference. Satisfiability can be checked by enumerating the possible models. SAT problem is NP-Complete. Ex: CSP. \nP is valid if and only if NOT P is unsatisfiable. P is satisfiable if and only if NOT P is not valid. A entails B if and only if A AND (NOT B) is unsatisfiable. This can be proved by proof by contradiction by first assuming B is False. This leads to contraction to known axiom A. Inference rules (All are sound):\n\nModus Ponens - When A and A->B are given,  can be inferred.\n\nAnd-Elimination - Any of the conjuncts from a conduction can be inferred. (A AND B )/ A\n\nAll logical equivalences can be used as inference rules. Example : From A<->B, A->B AND B->A can be inferred and vice versa.\n\nProof by resolution : Resolution is an inference rule that when combined with any complete search algorithm yields a complete inference algorithm. Only one pair of complementary literals can be resolved at a time. For any sentences A and B, a resolution based theorem prover can decide whether A entails B.\n\nIn propositional logic, every sentence is logically equivalent to a conjunction of clauses. A CNF can be used as input to a resolution procedure.\n\nIn resolution algorithms, if no clauses can be added then KB does not entail A. If two clauses resolve into an empty clause then KB entails A. An empty clause is equivalent to False. In such an algorithm, we first convert KB AND NOT A into a CNF.\n\nIf a set of clauses are unsatisfiable then the resolution closure of those clauses is an empty clause.\n\nHorn Clauses are closed under resolution. \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge-based agents** - Maintain internal state of knowledge, reason over it, update it  and perform actions accordingly\n* **Knowledge base** - Set of sentences which are explained in a knowledge representation language\n* **Sentence** - Represent facts/assertions of the environment/world\n* **Axiom** - A declaration that is not derived from other sentences\n* **Inference** - Derie new sentences from what is known\n* **Knowledge level** - First and most abstract level of a KBA where we describe what the agent knows and its goals\n* **Logical level** - The level of a KBA at  which knowledge is encoded in sentences\n* **Implementation level** - The level that runs on the agent's architecture\n* **Learning agent** - A KBA that can learn for itself and from its past experiences\n* **Semantics of a sentence** - Meaning of a sentence that determines the truth of it in each possible model\n* **Models** - Mathematical abstracts that have a truth value for every sentence in them\n* **Entailment** - One sentence is logically implied from another\n* **Logical inference** - When entailment is used to derive conclusions\n* **Model checking** - Enumerating all models to check if Α entails Β\n* **Sound or truth-preserving** - An inference that derives only entailed sentences\n* **Completeness** - An inference algorithm is complete if it derives all entailed sentence\n* **Grounding** - The relationship or connection between the real world and logical reasoning\n* **Learning** - Sentence constructions that produce general rules\n* **Theorem proving** - Applying inference rules and proving a sentence without using models\n* **Logical equivalence** - A and B are L.E if and only if they entail one another\n* **Validity (tautologies)** - A sentence Α is valid if it is true in ALL models\n* **Satisfiability** - If there is some model m that the sentence is true in\n* **Sat problem** - To determine the satisfiability of a sentence in propositional logic\n* **Reductio ad absurdum** - Proof by refutation or proof by contradiction\n* **Modus ponens** - An inference rule ((Alpha -> Beta), Alpha) / Beta\n* **Monotonicity** - As information is added to the KB, the set of entailed sentences increases\n* **Clause** - Disjunction of literals\n* **Factoring** - Removing multiple occurances of a literal from a sentence\n* **Conjunctive normal form** - Sentence that is represented as a conjunction of clauses\n* **Ground resolution theorem** - Completeness theorem for propositional logic resolution\n* **Definite clause** - Disjunction of literals that has only one positive clause\n* **Goal clauses** - Disjunction of literals with no positive clauses\n* **Horn clauses** - Disjunction of literals with atmost one positive clause\n* **K-cnf** - A CNF with atomost k literals\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}