{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other materials 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": "a528c840-5f2d-4bc0-dafd-02d887d41eb0"
      },
      "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": 4,
      "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": "af8a2e37-d130-40c2-dd6d-428954612e52"
      },
      "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": 5,
      "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": 6,
      "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",
        "chapter1_1 = \"\"\" Chapter 1.1 summary. \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" descartes and dualism. turning + immitation game. \\n\n",
        "searle and chinese room. eliza (early nlp program) eliza simulated conversation through\n",
        "\"pattern matching\" and substitution to give an illusion of \n",
        "understanding, but had no framework for contextualization. \\n\n",
        "dennet - brain in a vat. \\n\n",
        "Agent program runs on physical architecture to produce f \n",
        "agent = architecture + program \\n\n",
        "PEAS: specify a task environment (Performance measure, Environment, Actuator, Sensor) \\n\n",
        "Given a PEAS task environment, construct agent function f that\n",
        "maximizes performance measure, and design an agent program that implements. \\n\n",
        "Fully Observable (chess) v. Partially Observable (self driving), Deterministic (chess) v. Nondeterministic v. Stochastic \n",
        "(slot machine), Episodic () v. Sequential (driving), Static (sudoku) v. Dynamic (driving), \n",
        "Discrete v. Continuous, Single Agent (crossword) v. Multi Agent (pacman) \\n\n",
        "The hardest case is Continuous, Partially Observable, Stochastic and Multiagent. \\n\n",
        "Simple reflex agent selects  action based on the current percept, and\n",
        "ignores percept history.\n",
        "Problem-solving agent will consider sequence of actions (path) to goal state. \n",
        "Finding the path is is called search. \\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"agent function\": \"maps sequence of percept vectors to action a from set A\",\n",
        "\"performance measure\" : \"objective criterion to measure success of agent's behavior through percept sequence\",\n",
        "\"ration agent\" : \"agent that makes decisions/ actions to maximize its performance measure\",\n",
        "\"simple reflex agent\" : \"agent decides on basis of current percept not rest of history\",\n",
        "\"model based agent\" : \"agent keeps track of what it has seen so far to decide actions\",\n",
        "\"goal based agent\" : \"agent has goal to achieve\",\n",
        "\"utility based agent\" : \"max/min utility\"\n",
        "}"
      ],
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "faa7006b-3f82-4f0a-9548-7dc58d9b1ea0"
      },
      "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": 8,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n descartes and dualism. turning + immitation game. \n\nsearle and chinese room. eliza (early nlp program) eliza simulated conversation through\n\"pattern matching\" and substitution to give an illusion of \nunderstanding, but had no framework for contextualization. \n\ndennet - brain in a vat. \n\nAgent program runs on physical architecture to produce f \nagent = architecture + program \n\nPEAS: specify a task environment (Performance measure, Environment, Actuator, Sensor) \n\nGiven a PEAS task environment, construct agent function f that\nmaximizes performance measure, and design an agent program that implements. \n\nFully Observable (chess) v. Partially Observable (self driving), Deterministic (chess) v. Nondeterministic v. Stochastic \n(slot machine), Episodic () v. Sequential (driving), Static (sudoku) v. Dynamic (driving), \nDiscrete v. Continuous, Single Agent (crossword) v. Multi Agent (pacman) \n\nThe hardest case is Continuous, Partially Observable, Stochastic and Multiagent. \n\nSimple reflex agent selects  action based on the current percept, and\nignores percept history.\nProblem-solving agent will consider sequence of actions (path) to goal state. \nFinding the path is is called search. \n\n\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* **Agent function** - maps sequence of percept vectors to action a from set A\n* **Performance measure** - objective criterion to measure success of agent's behavior through percept sequence\n* **Ration agent** - agent that makes decisions/ actions to maximize its performance measure\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": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 210
        },
        "outputId": "40fe2f95-5134-4642-bf9e-870201ea4a08"
      },
      "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": 10,
      "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 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" branching factor: closer to 1, more optimal. \\n\n",
        "- If #nodes in  A∗ = N and solution depth = d, then b∗ = branching factor \n",
        "that a uniform tree of depth d would have to have in order\n",
        "to contain N + 1 nodes. $N +1 = 1+ b∗ + (b∗)^2 + ··· + (b∗)^d .$ \\n\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "If environment is Fully observable, Deterministic and Known then solution is fixed sequence of actions. \\n\n",
        "Search problem: \\n\n",
        "1. Set of States: a set S \\n\n",
        "2. Initial state s \\n \n",
        "3. Set of Actions: a set A; Actions(s) = set of actions that can be executed for s. \\n\n",
        "4. Transition Model: Result(s, a) → sr (sr is successor of s) \\n\n",
        "5. Path cost (Performance Measure): Must be additive, e.g. sum of distances, number of\n",
        "actions, … c(x,a,y) is the step cost, assumed ≥ 0 \\n\n",
        "6. Goal test: Goal(s) \\n\n",
        "Basic Search Algorithms \\n\n",
        "1. Tree Search: enumerate all possible paths from initial state.  \\n\n",
        "state is representation of physical configuration. Node is  part of a search tree\n",
        "• node = <state, parent-node, children, action, path-cost, depth> \\n\n",
        "2. Graph search: same as tree except, keep track of visited states/ explored nodes/ check for redundant paths. \\n\n",
        "Uninformed search strategies: every node looks good. \\n\n",
        "Evaluating search strategies: completeness, optimality, time / space complexity. \\n\n",
        "Time/space complexity variables: \n",
        "• b, maximum branching factor, \n",
        "• d, depth of the shallowest goal node,\n",
        "• m, maximum length of path in state space \\n\n",
        "BFS - frontier first, fifo queue. If b is finite, bfs is Complete. is optimal, if cost = 1 per step,\n",
        "Time Complexity?  $ 1+b+b^2+b^3+… +b^d = O(b^d) $\n",
        "Space Complexity? $ O(b^d) $ \\n\n",
        "DFS - lifo queue. not Complete (fails in infinite-depth space/ loops / can be modified to avoid repeats), \n",
        "not optimal. Time = $O(b^m) $. bad if m lot > d; but for dense solutions, faster; \n",
        "Space?  linear $O(b*m)$ \\n\n",
        "Depth-limited search: dfs with limited depth. If l = d, then optimal. If l < d - incomplete ; l > d - not optimal; \n",
        "Time complexity: $O ( b^1)$ Space complexity: $O(b * l)$ \\n\n",
        "Iterative deepening search: dfs with increasing depth at each step. will stop when l = d. complete and optimal.\n",
        "Time: $O(b^d) $ Space complexity: $O ( b * d) $\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",  \n",
        "\"State space\" : \" set of states reachable from  initial state\",\n",
        "\"path\": \"equence of actions leading from one state sj to another state sk\",\n",
        "\"search tree\": \"representation of paths that search algorithm has explored\",\n",
        "\"frontier\" : \"states available for expansion\",\n",
        "\"relaxed problem\" : \"problem with relaxed constraints on actions\"\n",
        "}"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "9783a208-3964-4410-97b2-e3382c74f9f5"
      },
      "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": 12,
      "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\nIf environment is Fully observable, Deterministic and Known then solution is fixed sequence of actions. \n\nSearch problem: \n\n1. Set of States: a set S \n\n2. Initial state s \n \n3. Set of Actions: a set A; Actions(s) = set of actions that can be executed for s. \n\n4. Transition Model: Result(s, a) → sr (sr is successor of s) \n\n5. Path cost (Performance Measure): Must be additive, e.g. sum of distances, number of\nactions, … c(x,a,y) is the step cost, assumed ≥ 0 \n\n6. Goal test: Goal(s) \n\nBasic Search Algorithms \n\n1. Tree Search: enumerate all possible paths from initial state.  \n\nstate is representation of physical configuration. Node is  part of a search tree\n• node = <state, parent-node, children, action, path-cost, depth> \n\n2. Graph search: same as tree except, keep track of visited states/ explored nodes/ check for redundant paths. \n\nUninformed search strategies: every node looks good. \n\nEvaluating search strategies: completeness, optimality, time / space complexity. \n\nTime/space complexity variables: \n• b, maximum branching factor, \n• d, depth of the shallowest goal node,\n• m, maximum length of path in state space \n\nBFS - frontier first, fifo queue. If b is finite, bfs is Complete. is optimal, if cost = 1 per step,\nTime Complexity?  $ 1+b+b^2+b^3+… +b^d = O(b^d) $\nSpace Complexity? $ O(b^d) $ \n\nDFS - lifo queue. not Complete (fails in infinite-depth space/ loops / can be modified to avoid repeats), \nnot optimal. Time = $O(b^m) $. bad if m lot > d; but for dense solutions, faster; \nSpace?  linear $O(b*m)$ \n\nDepth-limited search: dfs with limited depth. If l = d, then optimal. If l < d - incomplete ; l > d - not optimal; \nTime complexity: $O ( b^1)$ Space complexity: $O(b * l)$ \n\nIterative deepening search: dfs with increasing depth at each step. will stop when l = d. complete and optimal.\nTime: $O(b^d) $ Space complexity: $O ( b * d) $\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** -  set of states reachable from  initial state\n* **Path** - equence of actions leading from one state sj to another state sk\n* **Search tree** - representation of paths that search algorithm has explored\n* **Frontier** - states available for expansion\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Uniform cost search: BFS + Expand node with lowest path cost. “cost\n",
        "contours” \\n\n",
        "- Tests if node = goal state when node is selected for expansion, not when added to the frontier. \\n\n",
        "- Updates node on frontier if better path to same state is found. \\n\n",
        "- Always enqueues node before checking node = goal. \\n\n",
        "Informed search: Node expansion based on estimate (distance to goal). Best-first search: node selected for expansion\n",
        "based on evaluation function f(n). (sort frontier by f(n)) \\n\n",
        "Greedy Best first search: expand node with minimal f(n) (= h(n)) / node that is estimated to be closest to goal.\n",
        "ignores g(n) cost to get to goal. not optimal and not complete (loops) \\n\n",
        "A* search: avoid expanding paths that are expensive, but expand most promising first. is optimal \\n\n",
        "- g(n) = actual cost (so far) to reach node\n",
        "- h(n) = estimated cost to get from node to  goal\n",
        "- f(n) = estimated total cost of path through n to goal  = g(n) + h(n) \\n\n",
        "dominance: If h2(n) ≥ h1(n) for all n (both admissible), then h2 dominates h1.\n",
        "- h2 is optimistic and more accurate than h1\n",
        "- hmd dominates hoop \\n\n",
        "can use ma* and sma* to improve a*\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",  \n",
        "\"heuristic function\" :  \"h(n) takes state n and returns an estimate of the distance from n to goal.\",\n",
        "\"admissible heuristic\" : \"heuristic is admissible if it does not overestimate cost to reach the goal (optimistic)\",\n",
        "\"relaxed problem\" : \"problem with fewer restrictions on the actions than the original\"\n",
        "}"
      ],
      "execution_count": 13,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 693
        },
        "cellView": "form",
        "outputId": "651e0352-bd42-4fdb-a4d6-36c2f5fe43f5"
      },
      "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": 14,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# 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 Uniform cost search: BFS + Expand node with lowest path cost. “cost\ncontours” \n\n- Tests if node = goal state when node is selected for expansion, not when added to the frontier. \n\n- Updates node on frontier if better path to same state is found. \n\n- Always enqueues node before checking node = goal. \n\nInformed search: Node expansion based on estimate (distance to goal). Best-first search: node selected for expansion\nbased on evaluation function f(n). (sort frontier by f(n)) \n\nGreedy Best first search: expand node with minimal f(n) (= h(n)) / node that is estimated to be closest to goal.\nignores g(n) cost to get to goal. not optimal and not complete (loops) \n\nA* search: avoid expanding paths that are expensive, but expand most promising first. is optimal \n\n- g(n) = actual cost (so far) to reach node\n- h(n) = estimated cost to get from node to  goal\n- f(n) = estimated total cost of path through n to goal  = g(n) + h(n) \n\ndominance: If h2(n) ≥ h1(n) for all n (both admissible), then h2 dominates h1.\n- h2 is optimistic and more accurate than h1\n- hmd dominates hoop \n\n \n\n## Module 4 Definitions\n* **Concept** - definition\n* **Heuristic function** - h(n) takes state n and returns an estimate of the distance from n to goal.\n* **Admissible heuristic** - heuristic is admissible if it does not overestimate cost to reach the goal (optimistic)\n* **Relaxed problem** - problem with fewer restrictions on the actions than the original\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Game environment:\n",
        "-  Multiagent\n",
        "- Static:\n",
        "- Discrete: finite set of percepts and actions.\n",
        "- Fully observable: \n",
        "- Strategic: next state is determined by current state and action executed by agents. \\n\n",
        "Games as search:\n",
        "- Initial state, Successor function: (move,state) pairs, Terminal test, \n",
        "Utility function: numerical value of terminal states. \\n\n",
        "MAX & MIN Nodes: MAX tries to MAXimize MAX’s outcome. MAX’s opponent MINimizes MAX’s outcome. \\n\n",
        "MAX node - maximum of its children ; MIN node - min of its children \\n\n",
        "init values - max: -infty min +infty \\n\n",
        "Alpha-beta pruning: \\n\n",
        "- α: MAX’s current lower bound on MAX’s outcome / β: MIN’s current upper bound on MIN’s outcome\n",
        "prune when: \n",
        "- for MAX node: a value v >= β is backed-up \n",
        "- for MIN node: a value v <= α  is found \\n\n",
        "Expectimax search: average score under optimal play (max and chance nodes) \\n\n",
        "chance nodes have probability associated with moves\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"Evaluation function f\": \"real-number scores to `board positions’ w/o path\",    \n",
        "}"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 969
        },
        "outputId": "7fccb7e8-4cb6-494e-e2f1-c7dc092bd4a0"
      },
      "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": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Game environment:\n-  Multiagent\n- Static:\n- Discrete: finite set of percepts and actions.\n- Fully observable: \n- Strategic: next state is determined by current state and action executed by agents. \n\nGames as search:\n- Initial state, Successor function: (move,state) pairs, Terminal test, \nUtility function: numerical value of terminal states. \n\nMAX & MIN Nodes: MAX tries to MAXimize MAX’s outcome. MAX’s opponent MINimizes MAX’s outcome. \n\nMAX node - maximum of its children ; MIN node - min of its children \n\ninit values - max: -infty min +infty \n\nAlpha-beta pruning: \n\n- α: MAX’s current lower bound on MAX’s outcome / β: MIN’s current upper bound on MIN’s outcome\nprune when: \n- for MAX node: a value v >= β is backed-up \n- for MIN node: a value v <= α  is found \n\n\n \n\n## Module 5 Definitions\n* **Evaluation function f** - real-number scores to `board positions’ w/o path\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_2 = \"\"\" graph is strongly k-consistent if it is k-consistent and is also (k − 1)-consistent, STRONGLY\n",
        "(k−2)-consistent, . . . to 1-consistent. \\n\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_4 = \"\"\" cycle cutset / cutset conditioning  \\n\n",
        "CSPs with constraint graphs of bounded tree width can be solvable in poly time. \\n\n",
        "\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" CSP: (sudoku)\n",
        "- finite set of variables\n",
        "- Nonempty domain of values for each variable \n",
        "- set of constraints (limits values for var) \\n\n",
        "solution to a CSP is a complete, consistent assignment. (every var has assignment) \\n\n",
        "\n",
        "CSP representation: \n",
        "- constraint graph (nodes =var, arc = binary constraint), representation pattern \\n\n",
        "var can be continous or discrete (finite domains: n variables, domain size d = $O(d^n)$ complete assignment) \\n\n",
        "improving backtracking Heuristics: \\n\n",
        "- assign to most constrained var at each step\n",
        "- (if ties:) Most constraining variable\n",
        "- In what order should that variable’s values be tried?  Least constraining value \\n\n",
        "1. Most constrained variable Heuristic - Choose variable with fewest legal values - minimum remaining values (MRV) heuristic \\n\n",
        "2. Most constraining variable Heuristic - most constraining and most constrained \\n\n",
        "3. Least constraining value Heuristic \\n\n",
        "\n",
        "Arc Consistency: \\n\n",
        "Node consistency: satisfies unary constraints k = 1 ;\n",
        "Arc consistency: satisfies binary constraints k = 2 ; \n",
        "(Xi is arc-consistent w.r.t. Xj if for every value v in Di, there is some value w in\n",
        "Dj that satisfies the binary constraint on the arc between Xi and Xj)\n",
        "path consistency: k = 3 \\n\n",
        "constraint graph: directed edges between node x and y represent constraint. (so we have pair of arcs) \\n\n",
        "X -> Y is consistent iff for every value x of X there is some allowed y. \\n\n",
        "to make an (i,j) arc consistent, for each val in X: we remove value x from X for which there are no y values.  \\n\n",
        "Given d values, checking arc (i,j) takes $O(d^2)$ time worst case \\n \n",
        "\n",
        "AC 3: \\n\n",
        "At each iteration, only need to check Xi where >= one neighbor of Xi has lost a value in the previous iteration.\n",
        "If Xi loses value only because of arc inconsistencies with Yj, don’t need to check Yj on next iteration. \n",
        "only need to check (j,i). \\n\n",
        "Complexity: All nodes connected to every node, total # of arcs is 2*n*(n-1) = $O(n^2)$ \\n\n",
        "with d values, need to check arc (i,j) takes $O(d^2)$ \\n\n",
        "Each arc (i,j) can only be inserted into the queue d times; Worst case complexity: $O(n^2d^3 )$ \\n\n",
        "time complexity is  $O(nd^3 )$ if graph is planar - num of arcs are linear in N.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}"
      ],
      "execution_count": 27,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 914
        },
        "outputId": "427aaa68-5162-4235-887b-d66964e32b30"
      },
      "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": 28,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n CSP: (sudoku)\n- finite set of variables\n- Nonempty domain of values for each variable \n- set of constraints (limits values for var) \n\nsolution to a CSP is a complete, consistent assignment. (every var has assignment) \n\n\nCSP representation: \n- constraint graph (nodes =var, arc = binary constraint), representation pattern \n\nvar can be continous or discrete (finite domains: n variables, domain size d = $O(d^n)$ complete assignment) \n\nimproving backtracking Heuristics: \n\n- assign to most constrained var at each step\n- (if ties:) Most constraining variable\n- In what order should that variable’s values be tried?  Least constraining value \n\n1. Most constrained variable Heuristic - Choose variable with fewest legal values - minimum remaining values (MRV) heuristic \n\n2. Most constraining variable Heuristic - most constraining and most constrained \n\n3. Least constraining value Heuristic \n\n\nArc Consistency and AC3: \n\nNode consistency: satisfies unary constraints k = 1 ;\nArc consistency: satisfies binary constraints k = 2 ;\npath consistency: k = 3 \n\n\n\n## Module 6 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" wampa world; goal - get luke, exit. environment:grid ; performance measure (pts).\n",
        "actuators (possible actions). sensors. sentence is true in a model m iff m satisfies sentence or m is a model of sentecne.\n",
        "M(alpha) = set of models of alpha. \\n\n",
        "logical entailment: sentence follows another logically (alpha |= beta). \\n\n",
        "model checking: process of enumerating models compatible with KB.  \\n\n",
        "• logic: the semantics of sentences, (meaning) \\n\n",
        "• Semantics: truth of sentence w.r.t world, (model)\n",
        "beta entails alpha iff every model in which beta is true, alpha is also true”\n",
        "KB |=alpha iff  M(KB) ⊆ M(KB alpha) \\n\n",
        "(alpha ⟹ beta) ≡ (¬β ⟹ ¬alpha) Contraposition \\n\n",
        "(alpha ⟹ β) ≡ (¬alpha ⋁ β) Implication elimination \\n\n",
        "(alpha ⇔ β) ≡ ((alpha ⟹ β) ⋀ (β ⟹alpha)) Biconditional elimination \\n\n",
        "¬(alpha ⋀ β) ≡ (¬alpha ⋁ ¬β) De Morgan \\n\n",
        "¬(alpha ⋁ β) ≡ (¬alpha ⋀ ¬β) De Morgan \\n\n",
        "((alpha ⋀ β) ⋁ ɣ) ≡ ((alpha ⋀ β) ⋁ (alpha ⋀ ɣ))) Distributivity of ⋀ over ⋁ \\n\n",
        "((alpha ⋁ β) ⋀ ɣ) ≡ ((alpha ⋁ β) ⋀ (alpha ⋁ ɣ))) Distributivity of ⋁ over ⋀ \\n\n",
        "CNF: Clauses are disjunctions of literals. \\n\n",
        "1. Eliminate ⇔ : alpha ⇔ β with (alpha ⟹ β) ⋀ (β ⟹alpha ) \\n \n",
        "2. Eliminate ⟹ : alpha ⟹ β with ¬alpha ⋁ β \\n\n",
        "3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s \\n\n",
        "4. Apply distributivity law to distribute ⋁ over ⋀.  \\n\n",
        "resolution algorithm: uses contradiction to show that kb entails alpha. convert kb to cnf form.\n",
        "apply resolution rule to get new clause (removing contradictory clauses). end result: either empty (contradiction)\n",
        "or no new clauses added. \\n\n",
        "Deciding entailment with Horn clauses can be done in linear time wrt size of KB. \\n\n",
        "Forward Chaining (data-driven reasoning). Agent starts with known\n",
        "data, adding premises as new percepts enter, then applies forward chaining algo\n",
        "to derive new conclusions. No specific query needed. \\n\n",
        "Backward chaining (goal-directed reasoning) works backwards from a query. If query is true,\n",
        "then done. Else, algo finds implications in KB which lead to query. \n",
        "If all the premises of one of those are true (via backward chaining), then query=true.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge based agent\" : \"use reason+knowledge to determine action\",    \n",
        "\"knowledge base\" : \"set of sentences in knowledge representation language (axioms/atomic + derived sentences)\",\n",
        "\"model\" : \"abstractions w truth values for each sentence\",\n",
        "\"modus ponens\": \"if a -> b + given a, then b applies\",\n",
        "\"and elimination\": \"if a and b + given a, then b is implied\",\n",
        "\"CNF\" : \"sentence rep as conjuction of disjunctions. eg: ( a or b ) and (c or d)\",\n",
        "\"Definite clause\" : \"disjunction of literals where exactly one is positive\",\n",
        "\"Horn clause\" : \"disjunction of literals with <=1 positive (definite + clauses with no positive literals) (closed under resolution)\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "d265ac45-2e57-41de-d9c5-dd7668ada977"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \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 Your summary here \n\n## Module 7 Lecture Notes\n wampa world; goal - get luke, exit. environment:grid ; performance measure (pts).\nactuators (possible actions). sensors. sentence is true in a model m iff m satisfies sentence or m is a model of sentecne.\nM(alpha) = set of models of alpha. \n\nlogical entailment: sentence follows another logically (alpha |= beta). \n\nmodel checking: process of enumerating models compatible with KB.  \n\n• logic: the semantics of sentences, (meaning) \n\n• Semantics: truth of sentence w.r.t world, (model)\nbeta entails alpha iff every model in which beta is true, alpha is also true”\nKB |=alpha iff  M(KB) ⊆ M(KB alpha) \n\n(alpha ⟹ beta) ≡ (¬β ⟹ ¬alpha) Contraposition \n\n(alpha ⟹ β) ≡ (¬alpha ⋁ β) Implication elimination \n\n(alpha ⇔ β) ≡ ((alpha ⟹ β) ⋀ (β ⟹alpha)) Biconditional elimination \n\n¬(alpha ⋀ β) ≡ (¬alpha ⋁ ¬β) De Morgan \n\n¬(alpha ⋁ β) ≡ (¬alpha ⋀ ¬β) De Morgan \n\n((alpha ⋀ β) ⋁ ɣ) ≡ ((alpha ⋀ β) ⋁ (alpha ⋀ ɣ))) Distributivity of ⋀ over ⋁ \n\n((alpha ⋁ β) ⋀ ɣ) ≡ ((alpha ⋁ β) ⋀ (alpha ⋁ ɣ))) Distributivity of ⋁ over ⋀ \n\nCNF: Clauses are disjunctions of literals. \n\n1. Eliminate ⇔ : alpha ⇔ β with (alpha ⟹ β) ⋀ (β ⟹alpha ) \n \n2. Eliminate ⟹ : alpha ⟹ β with ¬alpha ⋁ β \n\n3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s \n\n4. Apply distributivity law to distribute ⋁ over ⋀.  \n\nresolution algorithm: uses contradiction to show that kb entails alpha. convert kb to cnf form.\napply resolution rule to get new clause (removing contradictory clauses). end result: either empty (contradiction)\nor no new clauses added. \n\nDeciding entailment with Horn clauses can be done in linear time wrt size of KB. \n\nForward Chaining (data-driven reasoning). Agent starts with known\ndata, adding premises as new percepts enter, then applies forward chaining algo\nto derive new conclusions. No specific query needed. \n\nBackward chaining (goal-directed reasoning) works backwards from a query. If query is true,\nthen done. Else, algo finds implications in KB which lead to query. \nIf all the premises of one of those are true (via backward chaining), then query=true.\n\n\n## Module 7 Definitions\n* **Knowledge based agent** - use reason+knowledge to determine action\n* **Knowledge base** - set of sentences in knowledge representation language (axioms/atomic + derived sentences)\n* **Model** - abstractions w truth values for each sentence\n* **Definite clause** - disjunction of literals where exactly one is positive\n* **Horn clause** - disjunction of literals with <=1 positive (definite + clauses with no positive literals) (closed under resolution)\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/"
        },
        "id": "T3cm1WV542_a",
        "outputId": "1e35f8dc-8712-4aad-fced-e8d79768a61b"
      },
      "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 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 Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \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 Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}