{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "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": "344222ad-a216-45e3-9726-b566dead59fe"
      },
      "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/",
          "height": 0
        },
        "outputId": "8f33ea8f-1a76-4c8d-99a8-be6ae855baa8"
      },
      "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": 6,
      "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 = \"Egret Jin\"\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 = \"hello\" \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 = \"\"\" A rational agent is not guaranteed to find optimal solutions., Touchless faucets can also be viewed as agents., A rational agent selects an action that maximizes the expected value of its performance measure. \n",
        "Agent function is abstract, agent program is concrete implementation.\"\"\"\n",
        "chapter2_2 = \"\"\" Rational agent selects best action expected to maximize its performance measure given evidence from percept sequence and whatever else knowledge it has \"\"\"\n",
        "chapter2_3 = \"\"\" Fully observable  - can see all aspects relevant to action, partially observable if not. \n",
        "\n",
        "Hardest set of descriptors is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown, like taxi driving.\"\"\"\n",
        "chapter2_4 = \"\"\" SImple reflex agent select actions based on current senses (percept), not history. Internal state depends on percept history and reflects\n",
        "at least some unobserved aspects of current state. Utility function is internalization of performance measure. \"\"\"\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\" : \"content sensors perceive, stimulus\",\n",
        "\"deterministic\" : \"next state of environment is completely determined by current state and action executed by the agent\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 9,
      "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": 757
        },
        "outputId": "c595d36b-014e-4099-cf03-b3654acadb62"
      },
      "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": 10,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nhello\n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" all data is treated as an object, strongly typed (fixed). int, float, str, tuple, dict, list, bool, None, generator, function\n",
        "\n",
        "dynamic typing, where variables come into existence when first assigned. Type(var) is automatically determined and reassigned, so type errors only caught at runtime.\n",
        "\n",
        "strings are immutable, concat with + operator. ==  checks if variables point to objects of the same value, is checks whether they point to the same object. \n",
        "split, join, capitalize, upper, strip\n",
        "\n",
        "list are mutable, use y=x[:] to get a shallow copy of any sequence. Can use slicing !\n",
        "append, insert, index, count, remove (first occurences), reverse, sort (in place)\n",
        "\n",
        "dictionaries are unordered and work by hashing so keys must be immutable, with constant average add, lookup, update\n",
        "keys, values, items\n",
        "\n",
        "functions can return multiple values as tuple, but no function overloading. can also provide default args, *args, and **kwargs.\n",
        "can pass functions to one another, \"first-class\" objects\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"the ability of objects to change their values\",\n",
        "\"tuple\" : \"simple immutable ordered sequence of items of mixed types. has t[x] and negative lookup (from right)\",\n",
        "\"strings\" : \"immutable, unicode with 2-byte characters\",\n",
        "\"list\" : \"mutable ordered sequence of items of mixed types\"\n",
        "}"
      ],
      "execution_count": 86,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 493
        },
        "outputId": "bbeb616c-bcbc-4858-8eb4-322260679abf"
      },
      "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": 87,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n all data is treated as an object, strongly typed (fixed). int, float, str, tuple, dict, list, bool, None, generator, function\n\ndynamic typing, where variables come into existence when first assigned. Type(var) is automatically determined and reassigned, so type errors only caught at runtime.\n\nstrings are immutable, concat with + operator. ==  checks if variables point to objects of the same value, is checks whether they point to the same object. \nsplit, join, capitalize, upper, strip\n\nlist are mutable, use y=x[:] to get a shallow copy of any sequence. Can use slicing !\nappend, insert, index, count, remove (first occurences), reverse, sort (in place)\n\ndictionaries are unordered and work by hashing so keys must be immutable, with constant average add, lookup, update\nkeys, values, items\n\nfunctions can return multiple values as tuple, but no function overloading. can also provide default args, *args, and **kwargs.\ncan pass functions to one another, \"first-class\" objects\n\n \n\n## Module 2 Definitions\n* **Mutability** - the ability of objects to change their values\n* **Tuple** - simple immutable ordered sequence of items of mixed types. has t[x] and negative lookup (from right)\n* **Strings** - immutable, unicode with 2-byte characters\n* **List** - mutable ordered sequence of items of mixed types\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Reflex Agents - ignore history and only selects action based on current state.\n",
        "\n",
        "Full observable, deterministic, known environments have fixed sequence of actions as solutions.\n",
        "\n",
        "For repeated states, check if visited before adding to search queue. This turns tree search into a graph search,\n",
        "but removes exponential time to linear time. In code, before loop set explored set to empty, before expanding child node add to explored set, then add child nodes to set if not in explored.\n",
        "\n",
        "b - maximum branching factor of search tree\n",
        "\n",
        "d - depth of shallowest goal node\n",
        "\n",
        "m - maximum length of any path in the state space (could be infinity)\n",
        "\n",
        "BFS - FIFO, expands shallowest node. Complete if b is finite, optimal is cost = 1 per step (not in general). Time complexitiy is $O(b^d)$. Space complexitiy if $O(b^d)$\n",
        "\n",
        "DFS - LIFO, expands deepest unexpanded node. Not complete or optimal. Time complexity $O(b^m)$. Space complexity $O(b*m)$. \n",
        "\n",
        "Use DFS if space restricted, many possible solutions with wrong/long paths that are short, search can be fine turned.\n",
        "Use BFS if possible infinite paths, some solutions have short paths, and we can quickly discard unlikely paths.\n",
        "\n",
        "Depth limited search: Time $O(b^l)$, Space $O(bl)$\n",
        "\n",
        "Iterative deepening search: complete if no infinite paths and optimal if step cost is 1. Time $O(b^d)$, Space $O(b*d)$\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 80,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 850
        },
        "outputId": "74d606f6-d11a-46be-bbfb-c9ff162b8d01"
      },
      "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": 81,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n Reflex Agents - ignore history and only selects action based on current state.\n\nFull observable, deterministic, known environments have fixed sequence of actions as solutions.\n\nFor repeated states, check if visited before adding to search queue. This turns tree search into a graph search,\nbut removes exponential time to linear time. In code, before loop set explored set to empty, before expanding child node add to explored set, then add child nodes to set if not in explored.\n\nb - maximum branching factor of search tree\n\nd - depth of shallowest goal node\n\nm - maximum length of any path in the state space (could be infinity)\n\nBFS - FIFO, expands shallowest node. Complete if b is finite, optimal is cost = 1 per step (not in general). Time complexitiy is $O(b^d)$. Space complexitiy if $O(b^d)$\n\nDFS - LIFO, expands deepest unexpanded node. Not complete or optimal. Time complexity $O(b^m)$. Space complexity $O(b*m)$. \n\nUse DFS if space restricted, many possible solutions with wrong/long paths that are short, search can be fine turned.\nUse BFS if possible infinite paths, some solutions have short paths, and we can quickly discard unlikely paths.\n\nDepth limited search: Time $O(b^l)$, Space $O(bl)$\n\nIterative deepening search: complete if no infinite paths and optimal if step cost is 1. Time $O(b^d)$, Space $O(b*d)$\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"  \"\"\"\n",
        "chapter3_6 = \"\"\"  \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "\n",
        "Uniform Cost search - tree search algorithm for a weighted tree. expands nodes with lowest path cost, bfs, tests for goal state\n",
        "when selected for expansion, not when added to fronter. updates a node on the frontier if a better path to the same state is found. always \n",
        "enqueues a node before checking if it is a goal. favors lower cost paths.\n",
        "\n",
        "Heuristic function h(n) takes a state n and estimates distance from n to the goal\n",
        "\n",
        "Greedy Best-First Search - uses f(n) = h(n). not optimal or complete\n",
        "\n",
        "A* search - f(n) = g(n) + h(n). admissible + optimal if never overestimates cost to reach goal. dominant (greater than) is more accurate.\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"search problem\" : \"states, initial state, actions, transition model, path cost, goal test\",\n",
        "\"\" : \"\",     \n",
        "}\n",
        "\n"
      ],
      "execution_count": 78,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 448
        },
        "cellView": "form",
        "outputId": "4e62274c-ab7e-40c0-96d8-df5247040945"
      },
      "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": 79,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n  \n\n## AIMA Chapter 3.6 Heuristic Functions\n  \n\n## Module 4 Lecture Notes\n \n\nUniform Cost search - tree search algorithm for a weighted tree. expands nodes with lowest path cost, bfs, tests for goal state\nwhen selected for expansion, not when added to fronter. updates a node on the frontier if a better path to the same state is found. always \nenqueues a node before checking if it is a goal. favors lower cost paths.\n\nHeuristic function h(n) takes a state n and estimates distance from n to the goal\n\nGreedy Best-First Search - uses f(n) = h(n). not optimal or complete\n\nA* search - f(n) = g(n) + h(n). admissible + optimal if never overestimates cost to reach goal. dominant (greater than) is more accurate.\n\n## Module 4 Definitions\n* **Search problem** - states, initial state, actions, transition model, path cost, goal test\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 = \"\"\" Common games are perfect information, zero-sum. A game is formally defined\n",
        "by initial state, actions, transition model(s, a) (defines state resulting from taking action a in state s),\n",
        "terminal test, utility function(s, p) (determines value for player p for state s)\"\"\"\n",
        "chapter5_2 = \"\"\" Minimax - max's strategy is conditional and contingent on what min does. It\n",
        "does a DFS search for the optimal minimax value for each node.\n",
        "\n",
        "Minimax\n",
        "\n",
        "Time complexity: $O(b^m)$ \n",
        "\n",
        "Space complexity: $O(bm)$\n",
        "\n",
        "Alpha-Beta Pruning - don't explore nodes that are not useful. Refer to written notes for\n",
        "a walkthrough example with 4 levels. Effectiveness depends on order in which states are examined.\n",
        "Perfect ordering gives $O(b^{m/2})$, random gives $O(b^{3m/4})$\n",
        "\n",
        "Type A is wide but shallow and evaluates all possible moves to a certain depth (chess)\n",
        "\n",
        "Type B is deep but narrow and followings promising paths as far as possible  (go)\"\"\"\n",
        "chapter5_3 = \"\"\" We replace our utility function with an evaluation function, which estimate's utility. We \n",
        "also replace the terminal test with a cutoff test, which works the same but allows us to cut off search\n",
        "whenever. Eval is always between a loss and a win for s, p.\n",
        "\n",
        "Forward pruning removes bad appearing moves even if better later on.\n",
        "Beam search considers beams of n best moves but can accidentally prune the actual best move.\n",
        "Late move reduction assumes move orderings has been done well.\n",
        "\n",
        "For games with moves well known (chess openings), we can use table lookup instead of \n",
        "manually searching. Same goes for ends, with fewer moves, but computers are better at this. \"\"\"\n",
        "chapter5_5 = \"\"\" Stochastic games contain random elements, like throwing dice. Game trees include \n",
        "chance nodes in addition to max/min nodes. We have expectiminimax value for games with chance nodes,\n",
        "where the value is the expected value computed using probability.\n",
        "\n",
        "This takes O(b^mn^m) where n is # of distinct dice rolls\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Orderability, Transitivity, Continuity, Substitutability, Monotonicity, Decomposability. \"\"\"\n",
        "chapter16_2 = \"\"\"  \"\"\"\n",
        "chapter16_3 = \"\"\"  \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"minimax search\" : \"max and min opponents, game wtih multiple outcome scores\",\n",
        "\"alpha-beta pruning\" : \"getting rid of parts of tree that have no difference in outcome\",\n",
        "\"transpositions\" : \"different move sequences ending in same positions, can be addressed with a transposition table that caches state h(n) values\",\n",
        "\"perference elicitation\" : \"presenting choices to the human and using that to understand the underlying utility function\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 64,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "73d5713f-a74e-4316-d779-f3471a18b5d9"
      },
      "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": 65,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Common games are perfect information, zero-sum. A game is formally defined\nby initial state, actions, transition model(s, a) (defines state resulting from taking action a in state s),\nterminal test, utility function(s, p) (determines value for player p for state s)\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Minimax - max's strategy is conditional and contingent on what min does. It\ndoes a DFS search for the optimal minimax value for each node.\n\nMinimax\n\nTime complexity: $O(b^m)$ \n\nSpace complexity: $O(bm)$\n\nAlpha-Beta Pruning - don't explore nodes that are not useful. Refer to written notes for\na walkthrough example with 4 levels. Effectiveness depends on order in which states are examined.\nPerfect ordering gives $O(b^{m/2})$, random gives $O(b^{3m/4})$\n\nType A is wide but shallow and evaluates all possible moves to a certain depth (chess)\n\nType B is deep but narrow and followings promising paths as far as possible  (go)\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n We replace our utility function with an evaluation function, which estimate's utility. We \nalso replace the terminal test with a cutoff test, which works the same but allows us to cut off search\nwhenever. Eval is always between a loss and a win for s, p.\n\nForward pruning removes bad appearing moves even if better later on.\nBeam search considers beams of n best moves but can accidentally prune the actual best move.\nLate move reduction assumes move orderings has been done well.\n\nFor games with moves well known (chess openings), we can use table lookup instead of \nmanually searching. Same goes for ends, with fewer moves, but computers are better at this. \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games contain random elements, like throwing dice. Game trees include \nchance nodes in addition to max/min nodes. We have expectiminimax value for games with chance nodes,\nwhere the value is the expected value computed using probability.\n\nThis takes O(b^mn^m) where n is # of distinct dice rolls\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Orderability, Transitivity, Continuity, Substitutability, Monotonicity, Decomposability. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n  \n\n## AIMA Chapter 16.3 Utility Functions\n  \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Minimax search** - max and min opponents, game wtih multiple outcome scores\n* **Alpha-beta pruning** - getting rid of parts of tree that have no difference in outcome\n* **Transpositions** - different move sequences ending in same positions, can be addressed with a transposition table that caches state h(n) values\n* **Perference elicitation** - presenting choices to the human and using that to understand the underlying utility function\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 has three components: a set of variables, a set of domains, and a set of contraints\n",
        "that specify allowable combinations of values. A domain contains the set of allowable values for a variable.\n",
        "They can have different size domains. Each constraint has a pair (scope, ref) where scope contains the variables\n",
        "in the constraint and rel is the relation that defines the values those variabels can have. \n",
        "\n",
        "Consistent - assignment does not violate any constraints\n",
        "\n",
        "Complete - every variable has a value\n",
        "\n",
        "Solution is consistent and complete. Partial assignment has some variables unassigned, partial\n",
        "solution has partial assignment that is consistent. Once we find a partial assignment violates a constraint,\n",
        "we can discard further refinements of the partial assignment. Faster than atomic state problems.\n",
        "\n",
        "CSPS used for linear programming, with linear constraints.\n",
        "\n",
        "Unary Constraint - A != red\n",
        "\n",
        "Binary Constraint - A != B\n",
        "\n",
        "Global Constraint - arbitrary number of variables, sudoku\n",
        "\n",
        "Preference Constraints - not necessary, like scheduling preferences, often encoded as costs on individual variable assignments \"\"\"\n",
        "chapter6_2 = \"\"\" Local consistency. In one part of the graph can spread throughout the graph.\n",
        "\n",
        "Node consistency: all values in a variable's domain satisfy its unary constraints. A graph is \n",
        "node consistent if all vairables in the graph are node consistent.\n",
        "\n",
        "Arc consistency: all values in a variable's domain satisfy its binary constraints. A graph is \n",
        "arc consistent if every variable is arc consistent with every other variable. This doesn't work for map\n",
        "coloring because there exist different color pairs.\n",
        "\n",
        "AC-3 is the most popular algorithm for enforcing arc consistency. It maintains a queue of arcs, then pops off\n",
        "an arbitary one, makes it arc-consistent. If this makes the domain smaller, we add all neighbors of the node whose\n",
        "domain changed. Move through all arcs. If a domain = 0 we have no solution. We end up with\n",
        "an arc consistent CSP, which is faster to search because it has a smaller domain.\n",
        "\n",
        "For n variables with domain size at most d and c binary constraints, each arc is inserted into the queue at most\n",
        "d times, checking consistency takes $O(d^2)$ time, so we get O(cd^3) total worst case time. \n",
        "\n",
        "Path consistency: Use implicit constraints to tighten binary constraints, inferring from variable triplets.\n",
        "Basically, for A, B, C check A, B and B, C pairs.\n",
        "\n",
        "K consistency: If for any set of k-1 variables a consistent value can be assigned to any kth variable. Strongly \n",
        "k-consistent is for all k, k-1...1 are consistent. \"\"\"\n",
        "chapter6_3 = \"\"\" We have to search for a solution if CSP leaves behind more than 1 possible value for a variable. \n",
        "\n",
        "Backtracking repeatedly chooses an unassigned variable, tries all values in the domain of that variable and extending it into a solution\n",
        "via recursion. If it fails, we go to a previous state, otherwise we return the solution. We keep a single representation of a state instead of \n",
        "creating new ones. This can be improved using domain independent heuristics.\n",
        "\n",
        "Forward checking establishes arc consistency whenever a variable is assigned. It deletes any variable from neighboring domains\n",
        "that is inconsistent. Doesn't look far ahead enough though, so can't detect all inconsistencies.\n",
        "\n",
        "MAC - maintaining arc consistency detects things forward checking misses. It calls AC-3 but starts with only arcs that are unassigned\n",
        "neighbors of the initial node. It recursively propagates constraints when changes are made to the domains of variables. \n",
        "\n",
        "Conflict-directed backjumping - using conflict sets and backtracking to the most recent assignment in the conflict set, which is\n",
        "computed using forward checking. At each backjump, absorb conflict sets.\"\"\"\n",
        "chapter6_4 = \"\"\"Min-conflicts heuristic: select value that results in the minimum number of conflicts with other \n",
        "variables. All local search techniques are candidates for application to CSPs.\n",
        "\n",
        "Tabu search: keeping a small list of recently visited states and not returning to those states to escape plateaus.\n",
        "\n",
        "Constraint weighting: concentrating search on important constraints, giving them a number weight and incrementing all that are violated by a current\n",
        "assignment. Adds topography to plateaus and adds learning. Possible to improve from current state and over time difficult constraints have higher weights. \"\"\"\n",
        "chapter6_5 = \"\"\" Breaking into independent subproblems is linear in n. For n/c subproblems, each CSP has c variables from total n variables with c as constant.\n",
        "Each subproblem takes $d^c$ work to solve, where d is size of domain. Total work is then $O(d^c n/c)$ compared to $O(d^n)$. One is linear, other is exponential.\n",
        "\n",
        "Constraint graph is a tree when any two variables are connected by at most one path. Using DAC, directional arc consistency we can solve in linear time bc tree-structured. \n",
        "We use topological sort. We can make directed arc consistent in $O(n)$ steps for $d$ domains, total time $O(nd^2)$. Then we can go down list and choose any remaining value,\n",
        "since arc-consistent, parent to child will always have valid value. No need for backtracking!\n",
        "\n",
        "Cutset conditioning: Choose a subset s of the CSP's variables so that we get a tree after the removal of s (cycle cutset).\n",
        "For each possible assignment to variables in s that satisfy all constraints on s, remove any inconsistent values for other domains and if the CSP remaining is a solution\n",
        "return it with s. $O(d^c*(n-c)d^2)$ If nearly a tree it saves a lot of time !!!\n",
        "\n",
        "Tree decomposition: Transform original graph into a tree where each node consists of a set of variables. Works if every variable appears in at least one of tree nodes, if two variables connected by constraint, they must appear together\n",
        "in at least one of tree nodes, if a variable appears in two nodes in the tree, it must also appear in every node along path connected nodes. Basically ensure\n",
        "all variables and constrainted are represented and any variable from original problem have the same value wherever they appear. $O(nd^2)$ time, where $n$ is number of tree\n",
        "nodes and $d$ is size of largest domain (set of tuples of values). Tree width of a tree decomposition is one less than size of the largest node: min width among all its tree decompositions.\n",
        "If tree width w then solvable in $O(nd^{w+1})$. CSPS with constraint graphs of bounded tree width are solvable in polynomial time.\n",
        "\n",
        "Time favors tree, cycle-cutset memory (linear vs exponential in w)\n",
        "\n",
        "Also elimate permutation solutions using symmetry-breaking constraint, like ordering colors by preference.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"constraint propagation\" : \"using constraints to reduce the number of possible values for a variable\",    \n",
        "\"commutativity\" : \"order of actions does not matter\",\n",
        "\"minimum remaining values\" : \"most contrained, fail first, picks variabel most likely to cause a failure (fewest legal values) soon to cause pruning\",\n",
        "\"degree heuristic\" : \"attempts to reduce the branching factor of future choices, selects variable with largest number of constraints on other unassigned variables\",\n",
        "\"least constraining value\" : \"useful for deciding order of examination, prefers value that rules out the least choices for neighboring variables\",\n",
        "\"directional arc consistent\" : \"ordering of variables $X_1, X_2... X_n$ iff every $X_i$ is arc consistent with each $X_j, j>i$\"\n",
        "}\n"
      ],
      "execution_count": 75,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6202ebdb-0361-4429-dbd4-0bdd1a3da80d"
      },
      "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": 76,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP has three components: a set of variables, a set of domains, and a set of contraints\nthat specify allowable combinations of values. A domain contains the set of allowable values for a variable.\nThey can have different size domains. Each constraint has a pair (scope, ref) where scope contains the variables\nin the constraint and rel is the relation that defines the values those variabels can have. \n\nConsistent - assignment does not violate any constraints\n\nComplete - every variable has a value\n\nSolution is consistent and complete. Partial assignment has some variables unassigned, partial\nsolution has partial assignment that is consistent. Once we find a partial assignment violates a constraint,\nwe can discard further refinements of the partial assignment. Faster than atomic state problems.\n\nCSPS used for linear programming, with linear constraints.\n\nUnary Constraint - A != red\n\nBinary Constraint - A != B\n\nGlobal Constraint - arbitrary number of variables, sudoku\n\nPreference Constraints - not necessary, like scheduling preferences, often encoded as costs on individual variable assignments \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Local consistency. In one part of the graph can spread throughout the graph.\n\nNode consistency: all values in a variable's domain satisfy its unary constraints. A graph is \nnode consistent if all vairables in the graph are node consistent.\n\nArc consistency: all values in a variable's domain satisfy its binary constraints. A graph is \narc consistent if every variable is arc consistent with every other variable. This doesn't work for map\ncoloring because there exist different color pairs.\n\nAC-3 is the most popular algorithm for enforcing arc consistency. It maintains a queue of arcs, then pops off\nan arbitary one, makes it arc-consistent. If this makes the domain smaller, we add all neighbors of the node whose\ndomain changed. Move through all arcs. If a domain = 0 we have no solution. We end up with\nan arc consistent CSP, which is faster to search because it has a smaller domain.\n\nFor n variables with domain size at most d and c binary constraints, each arc is inserted into the queue at most\nd times, checking consistency takes $O(d^2)$ time, so we get O(cd^3) total worst case time. \n\nPath consistency: Use implicit constraints to tighten binary constraints, inferring from variable triplets.\nBasically, for A, B, C check A, B and B, C pairs.\n\nK consistency: If for any set of k-1 variables a consistent value can be assigned to any kth variable. Strongly \nk-consistent is for all k, k-1...1 are consistent. \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n We have to search for a solution if CSP leaves behind more than 1 possible value for a variable. \n\nBacktracking repeatedly chooses an unassigned variable, tries all values in the domain of that variable and extending it into a solution\nvia recursion. If it fails, we go to a previous state, otherwise we return the solution. We keep a single representation of a state instead of \ncreating new ones. This can be improved using domain independent heuristics.\n\nForward checking establishes arc consistency whenever a variable is assigned. It deletes any variable from neighboring domains\nthat is inconsistent. Doesn't look far ahead enough though, so can't detect all inconsistencies.\n\nMAC - maintaining arc consistency detects things forward checking misses. It calls AC-3 but starts with only arcs that are unassigned\nneighbors of the initial node. It recursively propagates constraints when changes are made to the domains of variables. \n\nConflict-directed backjumping - using conflict sets and backtracking to the most recent assignment in the conflict set, which is\ncomputed using forward checking. At each backjump, absorb conflict sets.\n\n## AIMA Chapter 6.4 Local Search for CSPs\nMin-conflicts heuristic: select value that results in the minimum number of conflicts with other \nvariables. All local search techniques are candidates for application to CSPs.\n\nTabu search: keeping a small list of recently visited states and not returning to those states to escape plateaus.\n\nConstraint weighting: concentrating search on important constraints, giving them a number weight and incrementing all that are violated by a current\nassignment. Adds topography to plateaus and adds learning. Possible to improve from current state and over time difficult constraints have higher weights. \n\n## AIMA Chapter 6.5 The Structure of Problems\n Breaking into independent subproblems is linear in n. For n/c subproblems, each CSP has c variables from total n variables with c as constant.\nEach subproblem takes $d^c$ work to solve, where d is size of domain. Total work is then $O(d^c n/c)$ compared to $O(d^n)$. One is linear, other is exponential.\n\nConstraint graph is a tree when any two variables are connected by at most one path. Using DAC, directional arc consistency we can solve in linear time bc tree-structured. \nWe use topological sort. We can make directed arc consistent in $O(n)$ steps for $d$ domains, total time $O(nd^2)$. Then we can go down list and choose any remaining value,\nsince arc-consistent, parent to child will always have valid value. No need for backtracking!\n\nCutset conditioning: Choose a subset s of the CSP's variables so that we get a tree after the removal of s (cycle cutset).\nFor each possible assignment to variables in s that satisfy all constraints on s, remove any inconsistent values for other domains and if the CSP remaining is a solution\nreturn it with s. $O(d^c*(n-c)d^2)$ If nearly a tree it saves a lot of time !!!\n\nTree decomposition: Transform original graph into a tree where each node consists of a set of variables. Works if every variable appears in at least one of tree nodes, if two variables connected by constraint, they must appear together\nin at least one of tree nodes, if a variable appears in two nodes in the tree, it must also appear in every node along path connected nodes. Basically ensure\nall variables and constrainted are represented and any variable from original problem have the same value wherever they appear. $O(nd^2)$ time, where $n$ is number of tree\nnodes and $d$ is size of largest domain (set of tuples of values). Tree width of a tree decomposition is one less than size of the largest node: min width among all its tree decompositions.\nIf tree width w then solvable in $O(nd^{w+1})$. CSPS with constraint graphs of bounded tree width are solvable in polynomial time.\n\nTime favors tree, cycle-cutset memory (linear vs exponential in w)\n\nAlso elimate permutation solutions using symmetry-breaking constraint, like ordering colors by preference.\n\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Constraint propagation** - using constraints to reduce the number of possible values for a variable\n* **Commutativity** - order of actions does not matter\n* **Minimum remaining values** - most contrained, fail first, picks variabel most likely to cause a failure (fewest legal values) soon to cause pruning\n* **Degree heuristic** - attempts to reduce the branching factor of future choices, selects variable with largest number of constraints on other unassigned variables\n* **Least constraining value** - useful for deciding order of examination, prefers value that rules out the least choices for neighboring variables\n* **Directional arc consistent** - ordering of variables $X_1, X_2... X_n$ iff every $X_i$ is arc consistent with each $X_j, j>i$\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 = \"\"\" Knowledge-based agents use a process of reasoning to come to a conclusion, \n",
        "or develop logic to support themselves. They use inference to \"tell\" and \"ask\" to the knowledge base.\n",
        "The agent program tells knowledge base what is perceives and asks what should be done. The program then \n",
        "tells the knowledge base what action was chosen and returns the action to be executed. Analysis is \n",
        "independent of the implementation level, and can be built declaratively or procedurally. \"\"\"\n",
        "chapter7_2 = \"\"\" Wumpus world example, of rescuing something while avoiding pits and wumpus. There\n",
        "are performance measures for success, failure, and actions being taken. The environment is\n",
        "created according to a set of specifications (deterministic, discrete, static, single agent, sequential,\n",
        "partially observable, transition model unknown). Actuators exist for movement/actions and their \n",
        "results. Sensors are also used to determine wumpus, pits, the thing we're rescuing, etc.\n",
        "\n",
        "The difficulty lies in logically reasoning the layout of the room. Through actuators and sensors we can\n",
        "figure out the layout and our actions. Refer to visuals for an example. \"\"\"\n",
        "chapter7_3 = \"\"\" Entailment carries out logical inference. An inference algorithm deriving only \n",
        "entailed sentences is sound/truth preserving. It's complete if it can derive any sentence entailed. \"\"\"\n",
        "chapter7_4 = \"\"\" logical connective - refer to written notes for symbols. every known inference algorithm for \n",
        "propositional logical has a worst-case complexity that is exponential in the size of the input \"\"\"\n",
        "chapter7_5 = \"\"\" a is valid iff not a is unsatisfiable, a is satisfiable iff not a is not valid. \n",
        "\n",
        "a |= b if and only if the sentence (a ^ not b) is unsatisfiable\n",
        "\n",
        "refer to written notes for proof method\n",
        "\n",
        "biconditional elimination\n",
        "\n",
        "and elimination\n",
        "\n",
        "logical equivalence for contrapositive\n",
        "\n",
        "modus ponens\n",
        "\n",
        "de morgan's rule \n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"  \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agents\" : \"agents capable of maintaining an internal state of knowledge\",\n",
        "\"propositional logic\" : \"branch of logic that studies ways of combining or altering statements/propositions to form other statements/propisitions\",\n",
        "\"knowledge base\" : \"set of statements we start with, axioms\",\n",
        "\"axiom\" : \"statemenet we take as a given without being derived\",\n",
        "\"inference\" : \"deriving new statements from old ones, following knowledge base\",\n",
        "\"declarative approach\" : \"telling the empty knowledge base statements one by one\",\n",
        "\"procedural\" : \"encoding deserived behaviors directly in the code -- I assume starting out with some knowledge\",\n",
        "\"entailment\" : \"a |= b, b follows logically from a; M(a), M(b) also true. (a is a subset of b)\",\n",
        "\"deduction theorem\" : \"for any sentences a and b, a |= b iff sence a => b is valid\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 73,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 981
        },
        "outputId": "3db3a59c-1203-4e86-e7e1-aa6c06590286"
      },
      "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": 49,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Knowledge-based agents use a process of reasoning to come to a conclusion, \nor develop logic to support themselves. They use inference to \"tell\" and \"ask\" to the knowledge base.\nThe agent program tells knowledge base what is perceives and asks what should be done. The program then \ntells the knowledge base what action was chosen and returns the action to be executed. Analysis is \nindependent of the implementation level, and can be built declaratively or procedurally. \n\n## AIMA Chapter 7.2 The Wumpus World\n Wumpus world example, of rescuing something while avoiding pits and wumpus. There\nare performance measures for success, failure, and actions being taken. The environment is\ncreated according to a set of specifications (deterministic, discrete, static, single agent, sequential,\npartially observable, transition model unknown). Actuators exist for movement/actions and their \nresults. Sensors are also used to determine wumpus, pits, the thing we're rescuing, etc.\n\nThe difficulty lies in logically reasoning the layout of the room. Through actuators and sensors we can\nfigure out the layout and our actions. Refer to visuals for an example. \n\n## AIMA Chapter 7.3 Logic\n Entailment carries out logical inference. An inference algorithm deriving only \nentailed sentences is sound/truth preserving. It's complete if it can derive any sentence entailed. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n logical connective - refer to written notes for symbols. every known inference algorithm for \npropositional logical has a worst-case complexity that is exponential in the size of the input \n\n## AIMA 7.5 Propositional Theorem Proving\n a is valid iff not a is unsatisfiable, a is satisfiable iff not a is not valid. \n\na |= b if and only if the sentence (a ^ not b) is unsatisfiable\n\nrefer to written notes for proof method\n\nbiconditional elimitation\nand elimination\nlogical equivalence for contrapositive\nmodus ponens\nde morgan's rule \n\n## Module 7 Lecture Notes\n  \n\n## Module 7 Definitions\n* **Knowledge-based agents** - agents capable of maintaining an internal state of knowledge\n* **Propositional logic** - branch of logic that studies ways of combining or altering statements/propositions to form other statements/propisitions\n* **Knowledge base** - set of statements we start with, axioms\n* **Axiom** - statemenet we take as a given without being derived\n* **Inference** - deriving new statements from old ones, following knowledge base\n* **Declarative approach** - telling the empty knowledge base statements one by one\n* **Procedural** - encoding deserived behaviors directly in the code -- I assume starting out with some knowledge\n* **Entailment** - a |= b, b follows logically from a; M(a), M(b) also true. (a is a subset of b)\n* **Deduction theorem** - for any sentences a and b, a |= b iff sence a => b is valid\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": "f032b30c-4695-4967-d441-ce8b886a2dbb"
      },
      "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": 77,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nhello\n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Common games are perfect information, zero-sum. A game is formally defined\nby initial state, actions, transition model(s, a) (defines state resulting from taking action a in state s),\nterminal test, utility function(s, p) (determines value for player p for state s)\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Minimax - max's strategy is conditional and contingent on what min does. It\ndoes a DFS search for the optimal minimax value for each node.\n\nMinimax\n\nTime complexity: $O(b^m)$ \n\nSpace complexity: $O(bm)$\n\nAlpha-Beta Pruning - don't explore nodes that are not useful. Refer to written notes for\na walkthrough example with 4 levels. Effectiveness depends on order in which states are examined.\nPerfect ordering gives $O(b^{m/2})$, random gives $O(b^{3m/4})$\n\nType A is wide but shallow and evaluates all possible moves to a certain depth (chess)\n\nType B is deep but narrow and followings promising paths as far as possible  (go)\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n We replace our utility function with an evaluation function, which estimate's utility. We \nalso replace the terminal test with a cutoff test, which works the same but allows us to cut off search\nwhenever. Eval is always between a loss and a win for s, p.\n\nForward pruning removes bad appearing moves even if better later on.\nBeam search considers beams of n best moves but can accidentally prune the actual best move.\nLate move reduction assumes move orderings has been done well.\n\nFor games with moves well known (chess openings), we can use table lookup instead of \nmanually searching. Same goes for ends, with fewer moves, but computers are better at this. \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games contain random elements, like throwing dice. Game trees include \nchance nodes in addition to max/min nodes. We have expectiminimax value for games with chance nodes,\nwhere the value is the expected value computed using probability.\n\nThis takes O(b^mn^m) where n is # of distinct dice rolls\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Orderability, Transitivity, Continuity, Substitutability, Monotonicity, Decomposability. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n  \n\n## AIMA Chapter 16.3 Utility Functions\n  \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Minimax search** - max and min opponents, game wtih multiple outcome scores\n* **Alpha-beta pruning** - getting rid of parts of tree that have no difference in outcome\n* **Transpositions** - different move sequences ending in same positions, can be addressed with a transposition table that caches state h(n) values\n* **Perference elicitation** - presenting choices to the human and using that to understand the underlying utility function\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP has three components: a set of variables, a set of domains, and a set of contraints\nthat specify allowable combinations of values. A domain contains the set of allowable values for a variable.\nThey can have different size domains. Each constraint has a pair (scope, ref) where scope contains the variables\nin the constraint and rel is the relation that defines the values those variabels can have. \n\nConsistent - assignment does not violate any constraints\n\nComplete - every variable has a value\n\nSolution is consistent and complete. Partial assignment has some variables unassigned, partial\nsolution has partial assignment that is consistent. Once we find a partial assignment violates a constraint,\nwe can discard further refinements of the partial assignment. Faster than atomic state problems.\n\nCSPS used for linear programming, with linear constraints.\n\nUnary Constraint - A != red\n\nBinary Constraint - A != B\n\nGlobal Constraint - arbitrary number of variables, sudoku\n\nPreference Constraints - not necessary, like scheduling preferences, often encoded as costs on individual variable assignments \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Local consistency. In one part of the graph can spread throughout the graph.\n\nNode consistency: all values in a variable's domain satisfy its unary constraints. A graph is \nnode consistent if all vairables in the graph are node consistent.\n\nArc consistency: all values in a variable's domain satisfy its binary constraints. A graph is \narc consistent if every variable is arc consistent with every other variable. This doesn't work for map\ncoloring because there exist different color pairs.\n\nAC-3 is the most popular algorithm for enforcing arc consistency. It maintains a queue of arcs, then pops off\nan arbitary one, makes it arc-consistent. If this makes the domain smaller, we add all neighbors of the node whose\ndomain changed. Move through all arcs. If a domain = 0 we have no solution. We end up with\nan arc consistent CSP, which is faster to search because it has a smaller domain.\n\nFor n variables with domain size at most d and c binary constraints, each arc is inserted into the queue at most\nd times, checking consistency takes $O(d^2)$ time, so we get O(cd^3) total worst case time. \n\nPath consistency: Use implicit constraints to tighten binary constraints, inferring from variable triplets.\nBasically, for A, B, C check A, B and B, C pairs.\n\nK consistency: If for any set of k-1 variables a consistent value can be assigned to any kth variable. Strongly \nk-consistent is for all k, k-1...1 are consistent. \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n We have to search for a solution if CSP leaves behind more than 1 possible value for a variable. \n\nBacktracking repeatedly chooses an unassigned variable, tries all values in the domain of that variable and extending it into a solution\nvia recursion. If it fails, we go to a previous state, otherwise we return the solution. We keep a single representation of a state instead of \ncreating new ones. This can be improved using domain independent heuristics.\n\nForward checking establishes arc consistency whenever a variable is assigned. It deletes any variable from neighboring domains\nthat is inconsistent. Doesn't look far ahead enough though, so can't detect all inconsistencies.\n\nMAC - maintaining arc consistency detects things forward checking misses. It calls AC-3 but starts with only arcs that are unassigned\nneighbors of the initial node. It recursively propagates constraints when changes are made to the domains of variables. \n\nConflict-directed backjumping - using conflict sets and backtracking to the most recent assignment in the conflict set, which is\ncomputed using forward checking. At each backjump, absorb conflict sets.\n\n## AIMA Chapter 6.4 Local Search for CSPs\nMin-conflicts heuristic: select value that results in the minimum number of conflicts with other \nvariables. All local search techniques are candidates for application to CSPs.\n\nTabu search: keeping a small list of recently visited states and not returning to those states to escape plateaus.\n\nConstraint weighting: concentrating search on important constraints, giving them a number weight and incrementing all that are violated by a current\nassignment. Adds topography to plateaus and adds learning. Possible to improve from current state and over time difficult constraints have higher weights. \n\n## AIMA Chapter 6.5 The Structure of Problems\n Breaking into independent subproblems is linear in n. For n/c subproblems, each CSP has c variables from total n variables with c as constant.\nEach subproblem takes $d^c$ work to solve, where d is size of domain. Total work is then $O(d^c n/c)$ compared to $O(d^n)$. One is linear, other is exponential.\n\nConstraint graph is a tree when any two variables are connected by at most one path. Using DAC, directional arc consistency we can solve in linear time bc tree-structured. \nWe use topological sort. We can make directed arc consistent in $O(n)$ steps for $d$ domains, total time $O(nd^2)$. Then we can go down list and choose any remaining value,\nsince arc-consistent, parent to child will always have valid value. No need for backtracking!\n\nCutset conditioning: Choose a subset s of the CSP's variables so that we get a tree after the removal of s (cycle cutset).\nFor each possible assignment to variables in s that satisfy all constraints on s, remove any inconsistent values for other domains and if the CSP remaining is a solution\nreturn it with s. $O(d^c*(n-c)d^2)$ If nearly a tree it saves a lot of time !!!\n\nTree decomposition: Transform original graph into a tree where each node consists of a set of variables. Works if every variable appears in at least one of tree nodes, if two variables connected by constraint, they must appear together\nin at least one of tree nodes, if a variable appears in two nodes in the tree, it must also appear in every node along path connected nodes. Basically ensure\nall variables and constrainted are represented and any variable from original problem have the same value wherever they appear. $O(nd^2)$ time, where $n$ is number of tree\nnodes and $d$ is size of largest domain (set of tuples of values). Tree width of a tree decomposition is one less than size of the largest node: min width among all its tree decompositions.\nIf tree width w then solvable in $O(nd^{w+1})$. CSPS with constraint graphs of bounded tree width are solvable in polynomial time.\n\nTime favors tree, cycle-cutset memory (linear vs exponential in w)\n\nAlso elimate permutation solutions using symmetry-breaking constraint, like ordering colors by preference.\n\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Constraint propagation** - using constraints to reduce the number of possible values for a variable\n* **Commutativity** - order of actions does not matter\n* **Minimum remaining values** - most contrained, fail first, picks variabel most likely to cause a failure (fewest legal values) soon to cause pruning\n* **Degree heuristic** - attempts to reduce the branching factor of future choices, selects variable with largest number of constraints on other unassigned variables\n* **Least constraining value** - useful for deciding order of examination, prefers value that rules out the least choices for neighboring variables\n* **Directional arc consistent** - ordering of variables $X_1, X_2... X_n$ iff every $X_i$ is arc consistent with each $X_j, j>i$\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Knowledge-based agents use a process of reasoning to come to a conclusion, \nor develop logic to support themselves. They use inference to \"tell\" and \"ask\" to the knowledge base.\nThe agent program tells knowledge base what is perceives and asks what should be done. The program then \ntells the knowledge base what action was chosen and returns the action to be executed. Analysis is \nindependent of the implementation level, and can be built declaratively or procedurally. \n\n## AIMA Chapter 7.2 The Wumpus World\n Wumpus world example, of rescuing something while avoiding pits and wumpus. There\nare performance measures for success, failure, and actions being taken. The environment is\ncreated according to a set of specifications (deterministic, discrete, static, single agent, sequential,\npartially observable, transition model unknown). Actuators exist for movement/actions and their \nresults. Sensors are also used to determine wumpus, pits, the thing we're rescuing, etc.\n\nThe difficulty lies in logically reasoning the layout of the room. Through actuators and sensors we can\nfigure out the layout and our actions. Refer to visuals for an example. \n\n## AIMA Chapter 7.3 Logic\n Entailment carries out logical inference. An inference algorithm deriving only \nentailed sentences is sound/truth preserving. It's complete if it can derive any sentence entailed. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n logical connective - refer to written notes for symbols. every known inference algorithm for \npropositional logical has a worst-case complexity that is exponential in the size of the input \n\n## AIMA 7.5 Propositional Theorem Proving\n a is valid iff not a is unsatisfiable, a is satisfiable iff not a is not valid. \n\na |= b if and only if the sentence (a ^ not b) is unsatisfiable\n\nrefer to written notes for proof method\n\nbiconditional elimitation\nand elimination\nlogical equivalence for contrapositive\nmodus ponens\nde morgan's rule \n\n## Module 7 Lecture Notes\n  \n\n## Module 7 Definitions\n* **Knowledge-based agents** - agents capable of maintaining an internal state of knowledge\n* **Propositional logic** - branch of logic that studies ways of combining or altering statements/propositions to form other statements/propisitions\n* **Knowledge base** - set of statements we start with, axioms\n* **Axiom** - statemenet we take as a given without being derived\n* **Inference** - deriving new statements from old ones, following knowledge base\n* **Declarative approach** - telling the empty knowledge base statements one by one\n* **Procedural** - encoding deserived behaviors directly in the code -- I assume starting out with some knowledge\n* **Entailment** - a |= b, b follows logically from a; M(a), M(b) also true. (a is a subset of b)\n* **Deduction theorem** - for any sentences a and b, a |= b iff sence a => b is valid\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}