{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "M_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": "dba836ae-b92b-4165-d3a5-670f50c79a45"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c5f60bea-4249-4ad5-924f-d3fe81baebe9"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" 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 = \"\"\" An agent is anything that perceives its environment through sensors and can act on its environment through actuators. <br> A percept is the agent’s perceptual\n",
        "inputs at any given instance. <br>\n",
        "Environments: <br>\n",
        "Fully observable, Deterministic, Known environment <br>\n",
        "Solution: fixed sequence of actions <br>\n",
        "Partially observable or Nondeterministic <br>\n",
        "Solution: Recommends different future actions depending on the what percepts it receives - Branching strategy. <br>\"\"\"\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",
        "\"reflex agent\": \"action based on current percept, ignores percept history\",\n",
        "\"problem solving agent\": \"Plans ahead, process is called SEARCH. Sequence of actions - path - to goal state. Solution is such a sequence\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 946
        },
        "cellView": "form",
        "outputId": "ed30428d-44c0-4be3-f0ca-b14b2df453f9"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n 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 An agent is anything that perceives its environment through sensors and can act on its environment through actuators. <br> A percept is the agent’s perceptual\ninputs at any given instance. <br>\nEnvironments: <br>\nFully observable, Deterministic, Known environment <br>\nSolution: fixed sequence of actions <br>\nPartially observable or Nondeterministic <br>\nSolution: Recommends different future actions depending on the what percepts it receives - Branching strategy. <br>\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* **Reflex agent** - action based on current percept, ignores percept history\n* **Problem solving agent** - Plans ahead, process is called SEARCH. Sequence of actions - path - to goal state. Solution is such a sequence\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": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "outputId": "c2604d55-b9d6-426c-dcf9-b680ea3c6528"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n 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 = \"\"\"1. States: a set S <br>\n",
        "2. An initial state <br>\n",
        "3. Actions: a set A ∀ s Actions(s) = the set of actions that can be executed in s. <br>\n",
        "4. Transition Model to get successors <br>\n",
        "5. Path cost (Performance Measure): Must be additive <br>\n",
        "6. Goal test: Goal(s) <br>\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" Frontier <b>separates</b> 2 regions of the state-space graph: an interior region: expanded, and an exterior region:not yet been reached. <br>\n",
        "Binary Search:<br>\n",
        "Best-First Search: To find the next best node to expand, use  minimum value of evaluation function, f(n) uses <b>late goal</b>   test<br>\n",
        "Redundant Paths: Cycle (special case)<br>\n",
        "Solution 1: Keep track of all past paths, to not repeat the same path again. <br>\n",
        "Solution 2: Graph checks for redundant paths, Tree search does not (less space) <br> \n",
        "Tree Search: Enumerate all possible paths from the initial state. Here: search through explicit tree generation\n",
        "ROOT= initial state.\n",
        "Nodes in search tree generated through transition model\n",
        "Tree search treats different paths to the same node as distinct<br>\n",
        "Solution 3: Check for cycles explicitly (no extra memory, but slower) using parent pointers <br>\n",
        "\n",
        "Problem Solving Performance: <br>\n",
        "1. <b>Completeness</b>: Guaranteed to find a solution when there is one and correctly identify if there is no solution <br>\n",
        "2. Cost optimality: Find optimal solution <br>\n",
        "3. Time complexity: Number of states/actions created <br>\n",
        "4. Space complexity: <br>\n",
        "Parameters: <br>\n",
        "m: maximum length of a path <br>\n",
        "b: branching factor <br>\n",
        "d: depth of the tree <br>\n",
        "Infinite paths: Algo should be <b> systematic </b> <br> \n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\" \n",
        "1. BREADTH FIRST: All non-goal nodes equally good<br> \n",
        "Node inserted into queue only after testing to see if it is a goal state <br>\n",
        "Properties:\n",
        "a) Complete if b is finite <br>\n",
        "b) Optimal if cost of step = 1/equal <br>\n",
        "c) Time complexity: b^d <br>\n",
        "d) Space complexity: b^d <br>\n",
        "\n",
        "Use when: Infinite paths, solns have short paths, \n",
        "CONS: Exponential space <br> \n",
        "\n",
        "2. DEPTH FIRST SEARCH: <br>\n",
        "Properties: <br>\n",
        "a) Not Complete: No. It fails in infinite-depth spaces, spaces with loops <br>\n",
        "Complete in finite spaces: Modify to avoid repeated states along path <br>\n",
        "b) Optimal: No <br>\n",
        "c) Time: O(b^m) worse than BFS if m >> d, faster in dense spaces <br>\n",
        "d) Space: O(b*m) Linear space <br>\n",
        "Use when: space is finite, many possible solns with long paths & wrong paths are terminated quicky, search can be fine tuned, <br> \n",
        "\n",
        "3. DEPTH LIMITED SEARCH: Depth first with limited depth l<br>\n",
        "If l < d, not complete, complete otherwise. Time: O(b^l) Space: O(b*l) <br> \n",
        "\n",
        "4. ITERATIVE DEEPENING: Complete and optimal (goal found at l = d (depth of shallowest goal)) <br>\n",
        "Time: O(b^d) (same as BFS) Space: O(b*d) Optimal: If cost = 1 <br>\n",
        "\n",
        "5. UNIFORM COST/DIJKSTRA's SEARCH: Best first search, with path-cost as the evaluation function <br>\n",
        "\n",
        "6. BIDIRECTIONAL: From the initial state and also from the goal state. 2* b^d/2 << b^d <br>\n",
        "Optimal and Complete: if both directions are BFS and uniform cost. Also is state space has a solution or finite space<br>\n",
        "\"\"\"\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",
        "\"state space\": \"The set of all states reachable from the initial state by any sequence of actions\",\n",
        "\"Search tree\": \"a way of representing the paths that a search algorithm has explored. Root:initial state, leaves: successor states.\",\n",
        "\"Frontier\": \"those states that are available for expanding (for applying legal actions to)\",\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",  \n",
        "\"admissibility\": \"A key property is admissibility: an admissible heuristic is one that never overestimates the cost to reach a goal. (An admissible heuristic is therefore optimistic.) \"  \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "92bf160c-9627-4922-ceaf-7a81f7fe4f83"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'admissibility' is too long!\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n1. States: a set S <br>\n2. An initial state <br>\n3. Actions: a set A ∀ s Actions(s) = the set of actions that can be executed in s. <br>\n4. Transition Model to get successors <br>\n5. Path cost (Performance Measure): Must be additive <br>\n6. Goal test: Goal(s) <br>\n\n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Frontier <b>separates</b> 2 regions of the state-space graph: an interior region: expanded, and an exterior region:not yet been reached. <br>\nBinary Search:<br>\nBest-First Search: To find the next best node to expand, use  minimum value of evaluation function, f(n) uses <b>late goal</b>   test<br>\nRedundant Paths: Cycle (special case)<br>\nSolution 1: Keep track of all past paths, to not repeat the same path again. <br>\nSolution 2: Graph checks for redundant paths, Tree search does not (less space) <br> \nTree Search: Enumerate all possible paths from the initial state. Here: search through explicit tree generation\nROOT= initial state.\nNodes in search tree generated through transition model\nTree search treats different paths to the same node as distinct<br>\nSolution 3: Check for cycles explicitly (no extra memory, but slower) using parent pointers <br>\n\nProblem Solving Performance: <br>\n1. <b>Completeness</b>: Guaranteed to find a solution when there is one and correctly identify if there is no solution <br>\n2. Cost optimality: Find optimal solution <br>\n3. Time complexity: Number of states/actions created <br>\n4. Space complexity: <br>\nParameters: <br>\nm: maximum length of a path <br>\nb: branching factor <br>\nd: depth of the tree <br>\nInfinite paths: Algo should be <b> systematic </b> <br> \n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n1. BREADTH FIRST: All non-goal nodes equally good<br> \nNode inserted into queue only after testing to see if it is a goal state <br>\nProperties:\na) Complete if b is finite <br>\nb) Optimal if cost of step = 1/equal <br>\nc) Time complexity: b^d <br>\nd) Space complexity: b^d <br>\n\nUse when: Infinite paths, solns have short paths, \nCONS: Exponential space <br> \n\n2. DEPTH FIRST SEARCH: <br>\nProperties: <br>\na) Not Complete: No. It fails in infinite-depth spaces, spaces with loops <br>\nComplete in finite spaces: Modify to avoid repeated states along path <br>\nb) Optimal: No <br>\nc) Time: O(b^m) worse than BFS if m >> d, faster in dense spaces <br>\nd) Space: O(b*m) Linear space <br>\nUse when: space is finite, many possible solns with long paths & wrong paths are terminated quicky, search can be fine tuned, <br> \n\n3. DEPTH LIMITED SEARCH: Depth first with limited depth l<br>\nIf l < d, not complete, complete otherwise. Time: O(b^l) Space: O(b*l) <br> \n\n4. ITERATIVE DEEPENING: Complete and optimal (goal found at l = d (depth of shallowest goal)) <br>\nTime: O(b^d) (same as BFS) Space: O(b*d) Optimal: If cost = 1 <br>\n\n5. UNIFORM COST/DIJKSTRA's SEARCH: Best first search, with path-cost as the evaluation function <br>\n\n6. BIDIRECTIONAL: From the initial state and also from the goal state. 2* b^d/2 << b^d <br>\nOptimal and Complete: if both directions are BFS and uniform cost. Also is state space has a solution or finite space<br>\n\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **State space** - The set of all states reachable from the initial state by any sequence of actions\n* **Search tree** - a way of representing the paths that a search algorithm has explored. Root:initial state, leaves: successor states.\n* **Frontier** - those states that are available for expanding (for applying legal actions to)\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Admissibility** - A key property is admissibility: an admissible heuristic is one that never overestimates the cost to reach a goal. (An admissible heuristic is therefore optimistic.) \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 = \"\"\" Uses domain-specific information about the location of the goals. h(n) heuristic.Estimate using some evaluation function. <br>\n",
        "1. Greedy Best-First Search: f(n) = h(n) Expands the node that is estimated to be closest to goal. Same as UCS with f(n) replaceing g(n). Completely ignores g(n): the cost to get to n. <br>  \n",
        "Not Optimal, not complete: can get stuck in loops <br>\n",
        "2. A* : f(n) = g(n) + h(n). g(n) = actual cost to reach so far, h(n): estimated cost to reach goal from n <br>\n",
        "If h(n) is admissible, A* is optimal using Tree Search <br>\n",
        "Optimally efficient with consisten heurestics, efficient as prunes away nodes that are not necessary for finding the optimal soln. <br>\n",
        "3.  Satisficing search: Inadmissible heuristics and weighted A∗ - suboptimal solutions called satisficing <br>\n",
        "3.1 bounded suboptimal search:solution that is guaranteed to be within a constant factor W of the optimal cost.\n",
        "Weighted A∗ Bounded-cost search provides this guarantee. Bounded-cost search: look for solution whose cost is less than some constant C. <br>\n",
        "And in unbounded-cost search, we accept a solution of any cost, as Unbounded-cost search long as we can find it quickly. <br>\n",
        "Speedy search An example of an unbounded-cost search algorithm is speedy search\n",
        "4. Memory bounded: <br>\n",
        "5. Beam search limits the size of the frontier. <br>\n",
        "6. Iterative-deepening A∗search (IDA∗): Benefits of A∗ without the requirement to keep all reached states in memory, at a cost of visiting some states multiple times.\n",
        "For problems that do not fit in memory. <br>\n",
        "7. Recursive best-first search: Best-first search, but using only linear space. More efficient than IDA*, but has more excessive node generation. <br>\n",
        "8.  Bidirectional heuristic search: \n",
        "\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" \n",
        "1. Effective branching factor: b* <br>\n",
        "2. h2 dominates h1: h2(n) >= h1(n), h2 is  more efficient than h1 <br>\n",
        "3. Relaxed Problem: Problem with a fewer restrictions, the state space graph of the relaxed problem is subgraph of the original one. <br>\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" .. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"admissible heuristic\" : \"If it never overestimates the cost to reach the goal\",   \n",
        "\"consistence\": \"If for every node n and it's successor n' generated by action s h(n) <= h(n') + C(n,a,n').\" \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 890
        },
        "cellView": "form",
        "outputId": "c6b70803-d0d7-45bb-c14e-212671efd0b6"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Uses domain-specific information about the location of the goals. h(n) heuristic.Estimate using some evaluation function. <br>\n1. Greedy Best-First Search: f(n) = h(n) Expands the node that is estimated to be closest to goal. Same as UCS with f(n) replaceing g(n). Completely ignores g(n): the cost to get to n. <br>  \nNot Optimal, not complete: can get stuck in loops <br>\n2. A* : f(n) = g(n) + h(n). g(n) = actual cost to reach so far, h(n): estimated cost to reach goal from n <br>\nIf h(n) is admissible, A* is optimal using Tree Search <br>\nOptimally efficient with consisten heurestics, efficient as prunes away nodes that are not necessary for finding the optimal soln. <br>\n3.  Satisficing search: Inadmissible heuristics and weighted A∗ - suboptimal solutions called satisficing <br>\n3.1 bounded suboptimal search:solution that is guaranteed to be within a constant factor W of the optimal cost.\nWeighted A∗ Bounded-cost search provides this guarantee. Bounded-cost search: look for solution whose cost is less than some constant C. <br>\nAnd in unbounded-cost search, we accept a solution of any cost, as Unbounded-cost search long as we can find it quickly. <br>\nSpeedy search An example of an unbounded-cost search algorithm is speedy search\n4. Memory bounded: <br>\n5. Beam search limits the size of the frontier. <br>\n6. Iterative-deepening A∗search (IDA∗): Benefits of A∗ without the requirement to keep all reached states in memory, at a cost of visiting some states multiple times.\nFor problems that do not fit in memory. <br>\n7. Recursive best-first search: Best-first search, but using only linear space. More efficient than IDA*, but has more excessive node generation. <br>\n8.  Bidirectional heuristic search: \n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \n1. Effective branching factor: b* <br>\n2. h2 dominates h1: h2(n) >= h1(n), h2 is  more efficient than h1 <br>\n3. Relaxed Problem: Problem with a fewer restrictions, the state space graph of the relaxed problem is subgraph of the original one. <br>\n\n## Module 4 Lecture Notes\n .. \n\n## Module 4 Definitions\n* **Admissible heuristic** - If it never overestimates the cost to reach the goal\n* **Consistence** - If for every node n and it's successor n' generated by action s h(n) <= h(n') + C(n,a,n').\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 = \"\"\" .. \"\"\"\n",
        "chapter5_2 = \"\"\" <b>Minimax Algo</b>:  complete depth-first exploration of the game tree. <br>\n",
        "maximum depth m, b legal moves: time complexity O(bm), space complexity is O(bm) (all actions), O(m) action generated one at a time <br>\n",
        "<b> AlphaBeta Pruning </b> α = the value of the best (i.e., highest-value) choice we have found so far at any choice point\n",
        "along the path for MAX. Think: α = “at least.” <br>\n",
        "β = the value of the best (i.e., lowest-value) choice we have found so far at any choice point\n",
        "along the path for MIN. Think: β = “at most. <br>\n",
        "<b> Move ordering </b>: If the ordering is done properly, alpha–beta would need to examine only O(b^m/2) nodes to instead of O(b^m). Effetive branching factor will be b^0.5. <br>\n",
        "<b> Transposition table </b> caches the heuristic value of states. <br>\n",
        "<b>Type A</b>: considers all possible moves to a certain depth in the search tree, uses a heuristic evaluation function to estimate the utility of states at that depth. It explores\n",
        "a wide but shallow portion of the tree. <br>\n",
        "Type B: ignores moves that look bad, and follows promising lines “as far as possible.” Explores a deep, narrow portion of the tree. <br>\n",
        "\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" .. \"\"\"\n",
        "chapter5_5 = \"\"\" Have a random element <br>\n",
        "Expected value of a position: the average over all Expected value possible outcomes of the chance nodes. <br>\n",
        "Expectiminimax value <br>\n",
        "Evaluation function must return values that area positive linear transformation of the probability of winning <br>\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" ... \"\"\"\n",
        "chapter16_2 = \"\"\" Deterministic environment, agent needs only a preference ranking on states(score does not matter) - called a value function or ordinal utility function.<br>\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" \n",
        "Preference elicitation: involves presenting choices to the human and using the observed preferences to find the underlying utility function. <br> \n",
        "1. framing effect: the exact wording of a decision problem can have a big impact on the agent’s choices<br>\n",
        "2. anchoring effect:  relative utility judgments rather than absolute ones <br>\n",
        "3. ambiguity aversion: people elect the known probability rather than the unknown unknowns. <br>\n",
        "4. Decision theory: A normative theory, describes how a rational agent should act. <br>\n",
        "5. Descriptive theory: describes how actual agents—for example, humans— really do act. <br>\n",
        "6. Estimated expected utility of the best choice to be too high is called the optimizer’s curse <br>\n",
        "7. Certainty effect: People are strongly attracted to gains that are certain. <br>\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "63d2d02a-4b04-48de-cb5d-62c65ab27292"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n .. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n <b>Minimax Algo</b>:  complete depth-first exploration of the game tree. <br>\nmaximum depth m, b legal moves: time complexity O(bm), space complexity is O(bm) (all actions), O(m) action generated one at a time <br>\n<b> AlphaBeta Pruning </b> α = the value of the best (i.e., highest-value) choice we have found so far at any choice point\nalong the path for MAX. Think: α = “at least.” <br>\nβ = the value of the best (i.e., lowest-value) choice we have found so far at any choice point\nalong the path for MIN. Think: β = “at most. <br>\n<b> Move ordering </b>: If the ordering is done properly, alpha–beta would need to examine only O(b^m/2) nodes to instead of O(b^m). Effetive branching factor will be b^0.5. <br>\n<b> Transposition table </b> caches the heuristic value of states. <br>\n<b>Type A</b>: considers all possible moves to a certain depth in the search tree, uses a heuristic evaluation function to estimate the utility of states at that depth. It explores\na wide but shallow portion of the tree. <br>\nType B: ignores moves that look bad, and follows promising lines “as far as possible.” Explores a deep, narrow portion of the tree. <br>\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n .. \n\n## AIMA Chapter 5.5 Stochastic Games\n Have a random element <br>\nExpected value of a position: the average over all Expected value possible outcomes of the chance nodes. <br>\nExpectiminimax value <br>\nEvaluation function must return values that area positive linear transformation of the probability of winning <br>\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n ... \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Deterministic environment, agent needs only a preference ranking on states(score does not matter) - called a value function or ordinal utility function.<br>\n\n\n## AIMA Chapter 16.3 Utility Functions\n \nPreference elicitation: involves presenting choices to the human and using the observed preferences to find the underlying utility function. <br> \n1. framing effect: the exact wording of a decision problem can have a big impact on the agent’s choices<br>\n2. anchoring effect:  relative utility judgments rather than absolute ones <br>\n3. ambiguity aversion: people elect the known probability rather than the unknown unknowns. <br>\n4. Decision theory: A normative theory, describes how a rational agent should act. <br>\n5. Descriptive theory: describes how actual agents—for example, humans— really do act. <br>\n6. Estimated expected utility of the best choice to be too high is called the optimizer’s curse <br>\n7. Certainty effect: People are strongly attracted to gains that are certain. <br>\n\n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" CSP vs Search: In search problems, states are black boxes with a transition model to move between boxes. In CSPs, the agent can see inside the states and move between states accordingly.\n",
        "  \"forward checking\": \"Assign value to X and establishes arc consistency for it, remove invalid values for variables with arcs with X. Performs arc consistency only on the initial set of arcs\", <br>\n",
        "\" Maintaining Arc Consistency Algo\": \"Detect inconsistencies, call AC3 on only the arcs (x_j, X_i) for all neighbors of X_i. Recurively propagate arc consistency.\", <br>\n",
        "\"chronological backtracking\": \"When search fails: back up to the preceding variable and try a different value for it.\", <br>\n",
        "\"backjumping\": \"Revisit node that is most likely to fix the problem, maintain conflict set. Algo backtracks to the most recent assignment in the conflict set.\", <br>\n",
        "\"Constraint learning\": \"The idea of finding a minimum set of variables from the conflict set that causes the problem. Set of such values is called no-good and can be used by backtracking/forwardchecking/backjumping algos.\", <br>\n",
        "\"min-conflicts heuristic\": \"Chose value that will lead to minimum number of conflicts. Runtime is independent of problem size.\", <br>\n",
        "\"tabu search\": \"keeping a small list of recently visited states and forbidding the algorithm to return to those states.\", <br>\n",
        "\"Tree width of a tree decomposition of a graph\": \"one less than the size of the largest node\", <br>\n",
        "\"symmetry-breaking constraint\": \"Adding a constraint to break value symmetry.\" <br>\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\" Two ways to rule out variable assignments:search or inference. <br>\n",
        " Inference techniques: use constraints to rule out variable assignment <br>\n",
        " The key idea behind inference in CSPs is k-consistency, arc k = 2, node k = 1, path k = 3 <br>\n",
        "AC3: Algo to enforce arc consistence <br>\n",
        "Bactracking Search: A form of DFS <br>\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"  Constraint Learning: records the conflicts as they are encountered in the search to avoid the same conflict later. <br>\n",
        "MAC is a way of interleaving search and inference. AC-3 is pure inference. MAC runs while assigning variables in backtracking search. Instead of queueing all arcs, MAC only queues arcs incident on the assigned variable. Then, it runs identically to AC-3. <br>\"\"\"\n",
        "chapter6_4 = \"\"\" Constraint Weighting: Concentrate the search on the important constraints. <br>\n",
        "Each constraint is given a numeric weight(all 1 initially). At each step of the search, choose a variable to change that will result in the lowest total weight of all violated constraints. \n",
        "The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment. \n",
        "This has two benefits: it adds topography to plateaus, making sure that it is possible to improve from the current state, and it also adds learning: over time the difficult constraints are assigned higher weights.\n",
        "k-consistency: \"for any set of k − 1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.\"\"\"\n",
        "chapter6_5 = \"\"\" \n",
        "1. Find independent subproblems, by finding connected components  <br>\n",
        "2.  Note: any tree-structured CSP can be solved in time linear in the number of variables <br>\n",
        "3. directional arc consistency: Solutions is to find topological sorting of the CSP graph. O(n) steps, each of which must compare up to d possible domain values for two variables, for a total time of O(nd2) <br>\n",
        "4. Cutset conditioning: Reduce a constraint graph to a tree involves assigning values to some variables so that the remaining variables form a tree. \n",
        "5. Cutset conditioning: Cycle cutset S is called a cycle cutset is by removing S, graph becomes tree. <br>\n",
        "6. Tree Decomposition: A way to reduce CSP graph to a tree, each node in the tree consists of multiple nodes of the graph <br>\n",
        "6.1. Conditions: Every variable appears in at least one of the tree nodes. <br>\n",
        "If two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes. <br>\n",
        "If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes. <br>\n",
        "6.2. Tree decomposition subproblems are efficient if the tree width of the constraint graph is small <br>\n",
        "6.3.  Whenever you have a cycle-cutset of size c there is also a tree of width w<c+1, and it may be far smaller in some cases. <br>\n",
        "6.4. Cutset conditioning more space efficient as can be executed in linear memory, while tree decomposition requries memory exponential in the tree width w.\n",
        "\n",
        "bounds-consistent: if for every variable X , and for both the lower-bound and upper-bound values of X , there exists some value of Y that satisfies the constraint between X and Y for every variable Y.\n",
        "least-constraining-value heurestic: to decide the order in which the values should be examined, prefers the value that rules out the fewest choices for the neighboring variables\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" <br> <br> <br> <br> <br> <br>\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"Node Consistency\" : \"If all the values in the variable’s domain satisfy the variable’s unary constraints.\",    \n",
        "\"Arc Consistent\": \"if every value in its domain satisfies the variable’s binary constraints.\",\n",
        "\"Path Consistency\": \"Tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables\",\n",
        "\"strongly k-consistent\": \"A CSP is strongly k-consistent if it is k-consistent and is also (k − 1)-consistent, (k − 2)...\",\n",
        "\"global constraint \": \"Involving arbitary number of variables (not necessarily all)\",\n",
        "\"Resource constraint\": \"Atmost - \",\n",
        "\"Bound propagation\": \"Represent domains with lower and upper bound.\",\n",
        "\"Cummulative CSPs\": \"Order of actions does not matter\",\n",
        "\"minimum-remaining-values (MRV) heuristic\": \"Choosing the variable with lowest legal values, does not help in first assignment, more powerful\",\n",
        "\"degree-heurestic\": \"Choose variable with maximum number of constraints, tie breaker\",\n",
        "\n",
        "\n",
        "\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "24c001da-6e50-4af6-b496-eeb515a0dcd2"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP vs Search: In search problems, states are black boxes with a transition model to move between boxes. In CSPs, the agent can see inside the states and move between states accordingly.\n  \"forward checking\": \"Assign value to X and establishes arc consistency for it, remove invalid values for variables with arcs with X. Performs arc consistency only on the initial set of arcs\", <br>\n\" Maintaining Arc Consistency Algo\": \"Detect inconsistencies, call AC3 on only the arcs (x_j, X_i) for all neighbors of X_i. Recurively propagate arc consistency.\", <br>\n\"chronological backtracking\": \"When search fails: back up to the preceding variable and try a different value for it.\", <br>\n\"backjumping\": \"Revisit node that is most likely to fix the problem, maintain conflict set. Algo backtracks to the most recent assignment in the conflict set.\", <br>\n\"Constraint learning\": \"The idea of finding a minimum set of variables from the conflict set that causes the problem. Set of such values is called no-good and can be used by backtracking/forwardchecking/backjumping algos.\", <br>\n\"min-conflicts heuristic\": \"Chose value that will lead to minimum number of conflicts. Runtime is independent of problem size.\", <br>\n\"tabu search\": \"keeping a small list of recently visited states and forbidding the algorithm to return to those states.\", <br>\n\"Tree width of a tree decomposition of a graph\": \"one less than the size of the largest node\", <br>\n\"symmetry-breaking constraint\": \"Adding a constraint to break value symmetry.\" <br>\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Two ways to rule out variable assignments:search or inference. <br>\n Inference techniques: use constraints to rule out variable assignment <br>\n The key idea behind inference in CSPs is k-consistency, arc k = 2, node k = 1, path k = 3 <br>\nAC3: Algo to enforce arc consistence <br>\nBactracking Search: A form of DFS <br>\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n  Constraint Learning: records the conflicts as they are encountered in the search to avoid the same conflict later. <br>\nMAC is a way of interleaving search and inference. AC-3 is pure inference. MAC runs while assigning variables in backtracking search. Instead of queueing all arcs, MAC only queues arcs incident on the assigned variable. Then, it runs identically to AC-3. <br>\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Constraint Weighting: Concentrate the search on the important constraints. <br>\nEach constraint is given a numeric weight(all 1 initially). At each step of the search, choose a variable to change that will result in the lowest total weight of all violated constraints. \nThe weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment. \nThis has two benefits: it adds topography to plateaus, making sure that it is possible to improve from the current state, and it also adds learning: over time the difficult constraints are assigned higher weights.\nk-consistency: \"for any set of k − 1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.\n\n## AIMA Chapter 6.5 The Structure of Problems\n \n1. Find independent subproblems, by finding connected components  <br>\n2.  Note: any tree-structured CSP can be solved in time linear in the number of variables <br>\n3. directional arc consistency: Solutions is to find topological sorting of the CSP graph. O(n) steps, each of which must compare up to d possible domain values for two variables, for a total time of O(nd2) <br>\n4. Cutset conditioning: Reduce a constraint graph to a tree involves assigning values to some variables so that the remaining variables form a tree. \n5. Cutset conditioning: Cycle cutset S is called a cycle cutset is by removing S, graph becomes tree. <br>\n6. Tree Decomposition: A way to reduce CSP graph to a tree, each node in the tree consists of multiple nodes of the graph <br>\n6.1. Conditions: Every variable appears in at least one of the tree nodes. <br>\nIf two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes. <br>\nIf a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes. <br>\n6.2. Tree decomposition subproblems are efficient if the tree width of the constraint graph is small <br>\n6.3.  Whenever you have a cycle-cutset of size c there is also a tree of width w<c+1, and it may be far smaller in some cases. <br>\n6.4. Cutset conditioning more space efficient as can be executed in linear memory, while tree decomposition requries memory exponential in the tree width w.\n\nbounds-consistent: if for every variable X , and for both the lower-bound and upper-bound values of X , there exists some value of Y that satisfies the constraint between X and Y for every variable Y.\nleast-constraining-value heurestic: to decide the order in which the values should be examined, prefers the value that rules out the fewest choices for the neighboring variables\n\n\n\n## Module 6 Lecture Notes\n <br> <br> <br> <br> <br> <br>\n\n## Module 6 Definitions\n* **Node consistency** - If all the values in the variable’s domain satisfy the variable’s unary constraints.\n* **Arc consistent** - if every value in its domain satisfies the variable’s binary constraints.\n* **Path consistency** - Tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables\n* **Strongly k-consistent** - A CSP is strongly k-consistent if it is k-consistent and is also (k − 1)-consistent, (k − 2)...\n* **Global constraint ** - Involving arbitary number of variables (not necessarily all)\n* **Resource constraint** - Atmost - \n* **Bound propagation** - Represent domains with lower and upper bound.\n* **Cummulative csps** - Order of actions does not matter\n* **Minimum-remaining-values (mrv) heuristic** - Choosing the variable with lowest legal values, does not help in first assignment, more powerful\n* **Degree-heurestic** - Choose variable with maximum number of constraints, tie breaker\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 = \"\"\" Reasoning over internal representation of knowledge to decide the action to be taken. <br>\n",
        "For problem solving agents, we represented the world using multiple states. But this kind of representation is limiting. Becomes difficult to define the goal state/s that are more complex. <br>\n",
        "Knowledge Base: A set of sentence weitten inknowledge representation language. Sentence contains some assertion about the world <br>\n",
        "KB agents can add info to the knowledge base. <Tell> action to assert info to KB and <Ask> action to ask info from the KB. <br>\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" Performance measure: Add penalty for takng time, for falling in the pit, for being eaten by the Wampa etc.<br>\n",
        "<b>Actuators</b>: Move forward, left, right <br>\n",
        "If moves into pit/wampa, die <br>\n",
        "Grab to pick up Luke <br>\n",
        "Shoot fires in straight line <br>\n",
        "If hits the wall, stays there <br>\n",
        "Percept\n",
        "\n",
        "<b>Environment</b>: Deterministic, descrete, static, single agent <br>\n",
        "<b>Sequential</b>: Because a lot of steps have to be taken before reaching the goal. <br>\n",
        "<b>Partially Observable</b>: Some parts of the board are not directly perceivable.<br>\n",
        "\n",
        "<b> Walktrough: </b>\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\" General class of representations for kb agents <br> \n",
        "1. Consists of sentences in the representation language. <br>\n",
        "2. RL has a syntax <br> \n",
        "3. A logic defines the semantics (meaning) of the sentences <br>\n",
        "4. Semantics defines the truth for each sentence wrt a possible world, often called a model. <br>\n",
        "m: model alpha = true in model m, then m satisifies model OR m is a model of alpha <br>\n",
        "M(alpha): set of all models of alpha <br>\n",
        "\n",
        "Logical Entailment: if a follows logically from b, a|= b. <br>\n",
        "a |b iff M(a) is a subset of M(b) [a is a more specific sentence] <br> <br>\n",
        "Logical Inference: Deriving conclusions from existing logical sentences. <br> <br> <br> <br> <br> <br>\n",
        "  \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "chapter7_5 = \"\"\" Logically equivalent: If alpha and beta are true in the same set of models. <br>\n",
        "If  <br> \n",
        "Initial State <br>\n",
        "Actions: All inference rules applied to all sentences that match the top half of the inference rule. <br>\n",
        "Result: Add the sentence on the bottom half of the KB <br>\n",
        "Goal: The goal is a state that contains the sentence that we are trying to prove <br>\n",
        "Clauses: Disjunctions of literals. <br>\n",
        "Resolution rule only applies to clauses. (Every sentence in propositional logic is a conjuntion of clauses)<br>\n",
        "\n",
        "Resolution Algorithm: Proof by contradiction. <br>\n",
        "To show KB |= a, prove (KB ^ not a) is unsatisfiable. <br>\n",
        "1. First convert (KB ^ not a) to CNF. <br>\n",
        "2. Apply resolution rule to the clauses. <br>\n",
        "3. If the new clause is not already present, add it to the set. <br>\n",
        "4. Continue until: <br>\n",
        "4.1 There are no new clauses that can be added, KB does not entail alpha <br>\n",
        "4.3 Two clauses resolve to yield the empty clause, then KB does entail alpha <br>\n",
        "<br>\n",
        "<br>\n",
        "<br>\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \"Axiom\" : \"A sentence that is given\", <br>\n",
        "\"Derived Sentence\": \"A new sentence derived from other sentences\", <br>\n",
        "\"Sound\": \"The inference algorithm should only derive entailed sentences\", <br>\n",
        "\"Complete\": \"If inference algorithm can derive all sentences that are entailed\", <br>\n",
        "\"Resulution\": \"The single inference rule, which yields a complete inference algo when coupled with the algo.\", <br> \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "2a2b7bd2-6308-4d32-d492-04ebc3589673"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Reasoning over internal representation of knowledge to decide the action to be taken. <br>\nFor problem solving agents, we represented the world using multiple states. But this kind of representation is limiting. Becomes difficult to define the goal state/s that are more complex. <br>\nKnowledge Base: A set of sentence weitten inknowledge representation language. Sentence contains some assertion about the world <br>\nKB agents can add info to the knowledge base. <Tell> action to assert info to KB and <Ask> action to ask info from the KB. <br>\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Performance measure: Add penalty for takng time, for falling in the pit, for being eaten by the Wampa etc.<br>\n<b>Actuators</b>: Move forward, left, right <br>\nIf moves into pit/wampa, die <br>\nGrab to pick up Luke <br>\nShoot fires in straight line <br>\nIf hits the wall, stays there <br>\nPercept\n\n<b>Environment</b>: Deterministic, descrete, static, single agent <br>\n<b>Sequential</b>: Because a lot of steps have to be taken before reaching the goal. <br>\n<b>Partially Observable</b>: Some parts of the board are not directly perceivable.<br>\n\n<b> Walktrough: </b>\n\n\n## AIMA Chapter 7.3 Logic\n General class of representations for kb agents <br> \n1. Consists of sentences in the representation language. <br>\n2. RL has a syntax <br> \n3. A logic defines the semantics (meaning) of the sentences <br>\n4. Semantics defines the truth for each sentence wrt a possible world, often called a model. <br>\nm: model alpha = true in model m, then m satisifies model OR m is a model of alpha <br>\nM(alpha): set of all models of alpha <br>\n\nLogical Entailment: if a follows logically from b, a|= b. <br>\na |b iff M(a) is a subset of M(b) [a is a more specific sentence] <br> <br>\nLogical Inference: Deriving conclusions from existing logical sentences. <br> <br> <br> <br> <br> <br>\n  \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Logically equivalent: If alpha and beta are true in the same set of models. <br>\nIf  <br> \nInitial State <br>\nActions: All inference rules applied to all sentences that match the top half of the inference rule. <br>\nResult: Add the sentence on the bottom half of the KB <br>\nGoal: The goal is a state that contains the sentence that we are trying to prove <br>\nClauses: Disjunctions of literals. <br>\nResolution rule only applies to clauses. (Every sentence in propositional logic is a conjuntion of clauses)<br>\n\nResolution Algorithm: Proof by contradiction. <br>\nTo show KB |= a, prove (KB ^ not a) is unsatisfiable. <br>\n1. First convert (KB ^ not a) to CNF. <br>\n2. Apply resolution rule to the clauses. <br>\n3. If the new clause is not already present, add it to the set. <br>\n4. Continue until: <br>\n4.1 There are no new clauses that can be added, KB does not entail alpha <br>\n4.3 Two clauses resolve to yield the empty clause, then KB does entail alpha <br>\n<br>\n<br>\n<br>\n\n\n## Module 7 Lecture Notes\n \"Axiom\" : \"A sentence that is given\", <br>\n\"Derived Sentence\": \"A new sentence derived from other sentences\", <br>\n\"Sound\": \"The inference algorithm should only derive entailed sentences\", <br>\n\"Complete\": \"If inference algorithm can derive all sentences that are entailed\", <br>\n\"Resulution\": \"The single inference rule, which yields a complete inference algo when coupled with the algo.\", <br> \n\n## Module 7 Definitions\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": "f7c70144-0b2d-4ca6-daed-39a086bc5a90"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n 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 An agent is anything that perceives its environment through sensors and can act on its environment through actuators. <br> A percept is the agent’s perceptual\ninputs at any given instance. <br>\nEnvironments: <br>\nFully observable, Deterministic, Known environment <br>\nSolution: fixed sequence of actions <br>\nPartially observable or Nondeterministic <br>\nSolution: Recommends different future actions depending on the what percepts it receives - Branching strategy. <br>\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* **Reflex agent** - action based on current percept, ignores percept history\n* **Problem solving agent** - Plans ahead, process is called SEARCH. Sequence of actions - path - to goal state. Solution is such a sequence\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## WARNING: Your definition of 'admissibility' is too long!\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n1. States: a set S <br>\n2. An initial state <br>\n3. Actions: a set A ∀ s Actions(s) = the set of actions that can be executed in s. <br>\n4. Transition Model to get successors <br>\n5. Path cost (Performance Measure): Must be additive <br>\n6. Goal test: Goal(s) <br>\n\n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Frontier <b>separates</b> 2 regions of the state-space graph: an interior region: expanded, and an exterior region:not yet been reached. <br>\nBinary Search:<br>\nBest-First Search: To find the next best node to expand, use  minimum value of evaluation function, f(n) uses <b>late goal</b>   test<br>\nRedundant Paths: Cycle (special case)<br>\nSolution 1: Keep track of all past paths, to not repeat the same path again. <br>\nSolution 2: Graph checks for redundant paths, Tree search does not (less space) <br> \nTree Search: Enumerate all possible paths from the initial state. Here: search through explicit tree generation\nROOT= initial state.\nNodes in search tree generated through transition model\nTree search treats different paths to the same node as distinct<br>\nSolution 3: Check for cycles explicitly (no extra memory, but slower) using parent pointers <br>\n\nProblem Solving Performance: <br>\n1. <b>Completeness</b>: Guaranteed to find a solution when there is one and correctly identify if there is no solution <br>\n2. Cost optimality: Find optimal solution <br>\n3. Time complexity: Number of states/actions created <br>\n4. Space complexity: <br>\nParameters: <br>\nm: maximum length of a path <br>\nb: branching factor <br>\nd: depth of the tree <br>\nInfinite paths: Algo should be <b> systematic </b> <br> \n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n1. BREADTH FIRST: All non-goal nodes equally good<br> \nNode inserted into queue only after testing to see if it is a goal state <br>\nProperties:\na) Complete if b is finite <br>\nb) Optimal if cost of step = 1/equal <br>\nc) Time complexity: b^d <br>\nd) Space complexity: b^d <br>\n\nUse when: Infinite paths, solns have short paths, \nCONS: Exponential space <br> \n\n2. DEPTH FIRST SEARCH: <br>\nProperties: <br>\na) Not Complete: No. It fails in infinite-depth spaces, spaces with loops <br>\nComplete in finite spaces: Modify to avoid repeated states along path <br>\nb) Optimal: No <br>\nc) Time: O(b^m) worse than BFS if m >> d, faster in dense spaces <br>\nd) Space: O(b*m) Linear space <br>\nUse when: space is finite, many possible solns with long paths & wrong paths are terminated quicky, search can be fine tuned, <br> \n\n3. DEPTH LIMITED SEARCH: Depth first with limited depth l<br>\nIf l < d, not complete, complete otherwise. Time: O(b^l) Space: O(b*l) <br> \n\n4. ITERATIVE DEEPENING: Complete and optimal (goal found at l = d (depth of shallowest goal)) <br>\nTime: O(b^d) (same as BFS) Space: O(b*d) Optimal: If cost = 1 <br>\n\n5. UNIFORM COST/DIJKSTRA's SEARCH: Best first search, with path-cost as the evaluation function <br>\n\n6. BIDIRECTIONAL: From the initial state and also from the goal state. 2* b^d/2 << b^d <br>\nOptimal and Complete: if both directions are BFS and uniform cost. Also is state space has a solution or finite space<br>\n\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **State space** - The set of all states reachable from the initial state by any sequence of actions\n* **Search tree** - a way of representing the paths that a search algorithm has explored. Root:initial state, leaves: successor states.\n* **Frontier** - those states that are available for expanding (for applying legal actions to)\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Admissibility** - A key property is admissibility: an admissible heuristic is one that never overestimates the cost to reach a goal. (An admissible heuristic is therefore optimistic.) \n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Uses domain-specific information about the location of the goals. h(n) heuristic.Estimate using some evaluation function. <br>\n1. Greedy Best-First Search: f(n) = h(n) Expands the node that is estimated to be closest to goal. Same as UCS with f(n) replaceing g(n). Completely ignores g(n): the cost to get to n. <br>  \nNot Optimal, not complete: can get stuck in loops <br>\n2. A* : f(n) = g(n) + h(n). g(n) = actual cost to reach so far, h(n): estimated cost to reach goal from n <br>\nIf h(n) is admissible, A* is optimal using Tree Search <br>\nOptimally efficient with consisten heurestics, efficient as prunes away nodes that are not necessary for finding the optimal soln. <br>\n3.  Satisficing search: Inadmissible heuristics and weighted A∗ - suboptimal solutions called satisficing <br>\n3.1 bounded suboptimal search:solution that is guaranteed to be within a constant factor W of the optimal cost.\nWeighted A∗ Bounded-cost search provides this guarantee. Bounded-cost search: look for solution whose cost is less than some constant C. <br>\nAnd in unbounded-cost search, we accept a solution of any cost, as Unbounded-cost search long as we can find it quickly. <br>\nSpeedy search An example of an unbounded-cost search algorithm is speedy search\n4. Memory bounded: <br>\n5. Beam search limits the size of the frontier. <br>\n6. Iterative-deepening A∗search (IDA∗): Benefits of A∗ without the requirement to keep all reached states in memory, at a cost of visiting some states multiple times.\nFor problems that do not fit in memory. <br>\n7. Recursive best-first search: Best-first search, but using only linear space. More efficient than IDA*, but has more excessive node generation. <br>\n8.  Bidirectional heuristic search: \n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \n1. Effective branching factor: b* <br>\n2. h2 dominates h1: h2(n) >= h1(n), h2 is  more efficient than h1 <br>\n3. Relaxed Problem: Problem with a fewer restrictions, the state space graph of the relaxed problem is subgraph of the original one. <br>\n\n## Module 4 Lecture Notes\n .. \n\n## Module 4 Definitions\n* **Admissible heuristic** - If it never overestimates the cost to reach the goal\n* **Consistence** - If for every node n and it's successor n' generated by action s h(n) <= h(n') + C(n,a,n').\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n .. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n <b>Minimax Algo</b>:  complete depth-first exploration of the game tree. <br>\nmaximum depth m, b legal moves: time complexity O(bm), space complexity is O(bm) (all actions), O(m) action generated one at a time <br>\n<b> AlphaBeta Pruning </b> α = the value of the best (i.e., highest-value) choice we have found so far at any choice point\nalong the path for MAX. Think: α = “at least.” <br>\nβ = the value of the best (i.e., lowest-value) choice we have found so far at any choice point\nalong the path for MIN. Think: β = “at most. <br>\n<b> Move ordering </b>: If the ordering is done properly, alpha–beta would need to examine only O(b^m/2) nodes to instead of O(b^m). Effetive branching factor will be b^0.5. <br>\n<b> Transposition table </b> caches the heuristic value of states. <br>\n<b>Type A</b>: considers all possible moves to a certain depth in the search tree, uses a heuristic evaluation function to estimate the utility of states at that depth. It explores\na wide but shallow portion of the tree. <br>\nType B: ignores moves that look bad, and follows promising lines “as far as possible.” Explores a deep, narrow portion of the tree. <br>\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n .. \n\n## AIMA Chapter 5.5 Stochastic Games\n Have a random element <br>\nExpected value of a position: the average over all Expected value possible outcomes of the chance nodes. <br>\nExpectiminimax value <br>\nEvaluation function must return values that area positive linear transformation of the probability of winning <br>\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n ... \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Deterministic environment, agent needs only a preference ranking on states(score does not matter) - called a value function or ordinal utility function.<br>\n\n\n## AIMA Chapter 16.3 Utility Functions\n \nPreference elicitation: involves presenting choices to the human and using the observed preferences to find the underlying utility function. <br> \n1. framing effect: the exact wording of a decision problem can have a big impact on the agent’s choices<br>\n2. anchoring effect:  relative utility judgments rather than absolute ones <br>\n3. ambiguity aversion: people elect the known probability rather than the unknown unknowns. <br>\n4. Decision theory: A normative theory, describes how a rational agent should act. <br>\n5. Descriptive theory: describes how actual agents—for example, humans— really do act. <br>\n6. Estimated expected utility of the best choice to be too high is called the optimizer’s curse <br>\n7. Certainty effect: People are strongly attracted to gains that are certain. <br>\n\n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP vs Search: In search problems, states are black boxes with a transition model to move between boxes. In CSPs, the agent can see inside the states and move between states accordingly.\n  \"forward checking\": \"Assign value to X and establishes arc consistency for it, remove invalid values for variables with arcs with X. Performs arc consistency only on the initial set of arcs\", <br>\n\" Maintaining Arc Consistency Algo\": \"Detect inconsistencies, call AC3 on only the arcs (x_j, X_i) for all neighbors of X_i. Recurively propagate arc consistency.\", <br>\n\"chronological backtracking\": \"When search fails: back up to the preceding variable and try a different value for it.\", <br>\n\"backjumping\": \"Revisit node that is most likely to fix the problem, maintain conflict set. Algo backtracks to the most recent assignment in the conflict set.\", <br>\n\"Constraint learning\": \"The idea of finding a minimum set of variables from the conflict set that causes the problem. Set of such values is called no-good and can be used by backtracking/forwardchecking/backjumping algos.\", <br>\n\"min-conflicts heuristic\": \"Chose value that will lead to minimum number of conflicts. Runtime is independent of problem size.\", <br>\n\"tabu search\": \"keeping a small list of recently visited states and forbidding the algorithm to return to those states.\", <br>\n\"Tree width of a tree decomposition of a graph\": \"one less than the size of the largest node\", <br>\n\"symmetry-breaking constraint\": \"Adding a constraint to break value symmetry.\" <br>\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Two ways to rule out variable assignments:search or inference. <br>\n Inference techniques: use constraints to rule out variable assignment <br>\n The key idea behind inference in CSPs is k-consistency, arc k = 2, node k = 1, path k = 3 <br>\nAC3: Algo to enforce arc consistence <br>\nBactracking Search: A form of DFS <br>\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n  Constraint Learning: records the conflicts as they are encountered in the search to avoid the same conflict later. <br>\nMAC is a way of interleaving search and inference. AC-3 is pure inference. MAC runs while assigning variables in backtracking search. Instead of queueing all arcs, MAC only queues arcs incident on the assigned variable. Then, it runs identically to AC-3. <br>\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Constraint Weighting: Concentrate the search on the important constraints. <br>\nEach constraint is given a numeric weight(all 1 initially). At each step of the search, choose a variable to change that will result in the lowest total weight of all violated constraints. \nThe weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment. \nThis has two benefits: it adds topography to plateaus, making sure that it is possible to improve from the current state, and it also adds learning: over time the difficult constraints are assigned higher weights.\nk-consistency: \"for any set of k − 1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.\n\n## AIMA Chapter 6.5 The Structure of Problems\n \n1. Find independent subproblems, by finding connected components  <br>\n2.  Note: any tree-structured CSP can be solved in time linear in the number of variables <br>\n3. directional arc consistency: Solutions is to find topological sorting of the CSP graph. O(n) steps, each of which must compare up to d possible domain values for two variables, for a total time of O(nd2) <br>\n4. Cutset conditioning: Reduce a constraint graph to a tree involves assigning values to some variables so that the remaining variables form a tree. \n5. Cutset conditioning: Cycle cutset S is called a cycle cutset is by removing S, graph becomes tree. <br>\n6. Tree Decomposition: A way to reduce CSP graph to a tree, each node in the tree consists of multiple nodes of the graph <br>\n6.1. Conditions: Every variable appears in at least one of the tree nodes. <br>\nIf two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes. <br>\nIf a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes. <br>\n6.2. Tree decomposition subproblems are efficient if the tree width of the constraint graph is small <br>\n6.3.  Whenever you have a cycle-cutset of size c there is also a tree of width w<c+1, and it may be far smaller in some cases. <br>\n6.4. Cutset conditioning more space efficient as can be executed in linear memory, while tree decomposition requries memory exponential in the tree width w.\n\nbounds-consistent: if for every variable X , and for both the lower-bound and upper-bound values of X , there exists some value of Y that satisfies the constraint between X and Y for every variable Y.\nleast-constraining-value heurestic: to decide the order in which the values should be examined, prefers the value that rules out the fewest choices for the neighboring variables\n\n\n\n## Module 6 Lecture Notes\n <br> <br> <br> <br> <br> <br>\n\n## Module 6 Definitions\n* **Node consistency** - If all the values in the variable’s domain satisfy the variable’s unary constraints.\n* **Arc consistent** - if every value in its domain satisfies the variable’s binary constraints.\n* **Path consistency** - Tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables\n* **Strongly k-consistent** - A CSP is strongly k-consistent if it is k-consistent and is also (k − 1)-consistent, (k − 2)...\n* **Global constraint ** - Involving arbitary number of variables (not necessarily all)\n* **Resource constraint** - Atmost - \n* **Bound propagation** - Represent domains with lower and upper bound.\n* **Cummulative csps** - Order of actions does not matter\n* **Minimum-remaining-values (mrv) heuristic** - Choosing the variable with lowest legal values, does not help in first assignment, more powerful\n* **Degree-heurestic** - Choose variable with maximum number of constraints, tie breaker\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Reasoning over internal representation of knowledge to decide the action to be taken. <br>\nFor problem solving agents, we represented the world using multiple states. But this kind of representation is limiting. Becomes difficult to define the goal state/s that are more complex. <br>\nKnowledge Base: A set of sentence weitten inknowledge representation language. Sentence contains some assertion about the world <br>\nKB agents can add info to the knowledge base. <Tell> action to assert info to KB and <Ask> action to ask info from the KB. <br>\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Performance measure: Add penalty for takng time, for falling in the pit, for being eaten by the Wampa etc.<br>\n<b>Actuators</b>: Move forward, left, right <br>\nIf moves into pit/wampa, die <br>\nGrab to pick up Luke <br>\nShoot fires in straight line <br>\nIf hits the wall, stays there <br>\nPercept\n\n<b>Environment</b>: Deterministic, descrete, static, single agent <br>\n<b>Sequential</b>: Because a lot of steps have to be taken before reaching the goal. <br>\n<b>Partially Observable</b>: Some parts of the board are not directly perceivable.<br>\n\n<b> Walktrough: </b>\n\n\n## AIMA Chapter 7.3 Logic\n General class of representations for kb agents <br> \n1. Consists of sentences in the representation language. <br>\n2. RL has a syntax <br> \n3. A logic defines the semantics (meaning) of the sentences <br>\n4. Semantics defines the truth for each sentence wrt a possible world, often called a model. <br>\nm: model alpha = true in model m, then m satisifies model OR m is a model of alpha <br>\nM(alpha): set of all models of alpha <br>\n\nLogical Entailment: if a follows logically from b, a|= b. <br>\na |b iff M(a) is a subset of M(b) [a is a more specific sentence] <br> <br>\nLogical Inference: Deriving conclusions from existing logical sentences. <br> <br> <br> <br> <br> <br>\n  \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Logically equivalent: If alpha and beta are true in the same set of models. <br>\nIf  <br> \nInitial State <br>\nActions: All inference rules applied to all sentences that match the top half of the inference rule. <br>\nResult: Add the sentence on the bottom half of the KB <br>\nGoal: The goal is a state that contains the sentence that we are trying to prove <br>\nClauses: Disjunctions of literals. <br>\nResolution rule only applies to clauses. (Every sentence in propositional logic is a conjuntion of clauses)<br>\n\nResolution Algorithm: Proof by contradiction. <br>\nTo show KB |= a, prove (KB ^ not a) is unsatisfiable. <br>\n1. First convert (KB ^ not a) to CNF. <br>\n2. Apply resolution rule to the clauses. <br>\n3. If the new clause is not already present, add it to the set. <br>\n4. Continue until: <br>\n4.1 There are no new clauses that can be added, KB does not entail alpha <br>\n4.3 Two clauses resolve to yield the empty clause, then KB does entail alpha <br>\n<br>\n<br>\n<br>\n\n\n## Module 7 Lecture Notes\n \"Axiom\" : \"A sentence that is given\", <br>\n\"Derived Sentence\": \"A new sentence derived from other sentences\", <br>\n\"Sound\": \"The inference algorithm should only derive entailed sentences\", <br>\n\"Complete\": \"If inference algorithm can derive all sentences that are entailed\", <br>\n\"Resulution\": \"The single inference rule, which yields a complete inference algo when coupled with the algo.\", <br> \n\n## Module 7 Definitions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}