{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "“FINAL Template_for CIS521_midterm notes.ipynb”的副本",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "7c5cdea4-fab7-49d0-daab-45049c3068af"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "0fba2813-5f70-45b4-a740-0e496effad3c"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "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 = \"\"\" To past turing, computer need: NLP, Knowledge representation, automated reasoning, machine learning. \\n\n",
        "To pass total turing test, need: computer vision, robotics.\n",
        " \"\"\" \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 = \"\"\" The environment is deterministic if the next stated is completely determined by the present state and actions conduct by the agent. Otherwise, it's nondeterministic. \"\"\"\n",
        "chapter2_4 = \"\"\" A task environment includes performance measure, external environment, actuators and the sensors. Needs to be specified fully when designing an agent,task environment can be fully or partially observable, single or multi-agent \\n\n",
        "deterministic or nondeterministic, episodic or sequential, static or dynamic, discrete or continuous, known or unknown. The agent program implements the agent function. Agents can improve their performance by learning. \"\"\"\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",
        "\"rational agent\" : \"a agent that acts to achieve best expected outcome given the evidence provided by percept sequence and own knowledge\",\n",
        "\"value alignment problem\" : \"problem of achieving agreement between true preference and objective we put into machine\",\n",
        "\"percept\" : \"anything the agent's sensors are perceiving\",\n",
        "\"percept sequence\" : \"history of agent percept\",\n",
        "\"information gathering\" : \"acts to modify future percepts\",\n",
        "\"Simple reflex agent\" : \"agents that respond directly to percept.\",\n",
        "\"model-based reflex agent\" : \"keep a internal state to track the world that are not evident in current percept.\",\n",
        "\"Goal-based agent\" : \"act to achieve goals\",\n",
        "\"utility based agent\" : \"act to maximize utility\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "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": 907
        },
        "cellView": "form",
        "outputId": "b89c62d8-5dfd-4ac5-93a0-ab13531fe530"
      },
      "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": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n To past turing, computer need: NLP, Knowledge representation, automated reasoning, machine learning. \n\nTo pass total turing test, need: computer vision, robotics.\n \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 The environment is deterministic if the next stated is completely determined by the present state and actions conduct by the agent. Otherwise, it's nondeterministic. \n\n## AIMA 2.4 The Structure of Agents\n A task environment includes performance measure, external environment, actuators and the sensors. Needs to be specified fully when designing an agent,task environment can be fully or partially observable, single or multi-agent \n\ndeterministic or nondeterministic, episodic or sequential, static or dynamic, discrete or continuous, known or unknown. The agent program implements the agent function. Agents can improve their performance by learning. \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* **Rational agent** - a agent that acts to achieve best expected outcome given the evidence provided by percept sequence and own knowledge\n* **Value alignment problem** - problem of achieving agreement between true preference and objective we put into machine\n* **Percept** - anything the agent's sensors are perceiving\n* **Percept sequence** - history of agent percept\n* **Information gathering** - acts to modify future percepts\n* **Simple reflex agent** - agents that respond directly to percept.\n* **Model-based reflex agent** - keep a internal state to track the world that are not evident in current percept.\n* **Goal-based agent** - act to achieve goals\n* **Utility based agent** - act to maximize utility\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 = \"\"\" strings are immutable. list.remove() removes the first occurrence. string.captialize() upper first character. string.strip(). '_'.join(words). \\n\n",
        "To define a subclass, put the superclass name in parentheses\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"immutable\" : \"cannot be modified once created.\",\n",
        "\"first class object\" : \"entity that can be dynamically created or destroyed. pass to function, reutrn as value.\",\n",
        "}"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 249
        },
        "outputId": "03b76d37-7e7b-4cdc-e558-41b59b2477f9"
      },
      "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": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n strings are immutable. list.remove() removes the first occurrence. string.captialize() upper first character. string.strip(). '_'.join(words). \n\nTo define a subclass, put the superclass name in parentheses\n\n## Module 2 Definitions\n* **Immutable** - cannot be modified once created.\n* **First class object** - entity that can be dynamically created or destroyed. pass to function, reutrn as value.\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 = \"\"\" In a fully observable, deterministic and known environment the solution to any problem is a fixed sequence of actions \\n\n",
        " We need the initial state and goal state to define a search problem. \\n\n",
        " To fully define a search problem we need State space, Initial state, Goal states, Actions, Transition model, Action cost function. \\n\n",
        " Graph search is faster than tree search because it does not examing redundant paths. \\n\n",
        " Graph search uses more space (memory) than tree search because it stores what states are reached and what paths are redundant. \\n\n",
        " Search problem criteria : completeness, cost optimality, time complexity, space complexity. \\n\n",
        " Best-first search expands nodes according to an evaluation function. \\n\n",
        " Breath-first search expands node which is shallowest. \\n\n",
        " BFS is complete, optimal for unit action cost. \\n\n",
        " Uniform-cost search expands the node with lowest path cost. \\n\n",
        " Uniform-cost search is optimal and complete \\n\n",
        " DFS is not complete nor optimal. \\n\n",
        " Deep-limited search is not complete nor optimal. \\n\n",
        " Iterative deepening search expands the node according to deep-limited search with increasing depth bounds. \\n\n",
        " Iterative deepening search is complete is all depths are checked. optimal for unit actions costs. \\n\n",
        " Bidirectional search expands nodes around the initial and goal states. stops when two frontier meet. \\n\n",
        " BFS: Time: O(b^d) Space: O(b^d). \\n\n",
        " DFS: Time: O(b^m) Space: O(b*m), m is much larger than d. \\n\n",
        " IDS: O(b^d) O(bd)\n",
        " DLS: O(b^l) O(bl)\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\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 possible states of the environment\",\n",
        "\"solution to search problem\" : \"path through the state space from initial state to goal state\",\n",
        "\"optimal solution\" : \"solution with lowest path cost\",     \n",
        "\"graph search\" : \"checks for redundant paths\",  \n",
        "\"tree search\" : \"does not check for redundant paths\",  \n",
        "\"complete\" : \"guaranteed to find a solution if there is one, report failure if there is not\", \n",
        "\"cost optimal\" : \"guaranteed to find the solution with lowest path cost\",\n",
        "\"uninformed\" : \"only has access to problem definition\",\n",
        "\"complete algorithm\" : \"BFS, UCS, IDS, Bidirectional\",   \n",
        "\"optimal algorithm\" : \"BFS, UCS, IDS, Bidrectional\",   \n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "37dde484-6de7-44c4-9dc5-03d602334fa3"
      },
      "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": 15,
      "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 In a fully observable, deterministic and known environment the solution to any problem is a fixed sequence of actions \n\n We need the initial state and goal state to define a search problem. \n\n To fully define a search problem we need State space, Initial state, Goal states, Actions, Transition model, Action cost function. \n\n Graph search is faster than tree search because it does not examing redundant paths. \n\n Graph search uses more space (memory) than tree search because it stores what states are reached and what paths are redundant. \n\n Search problem criteria : completeness, cost optimality, time complexity, space complexity. \n\n Best-first search expands nodes according to an evaluation function. \n\n Breath-first search expands node which is shallowest. \n\n BFS is complete, optimal for unit action cost. \n\n Uniform-cost search expands the node with lowest path cost. \n\n Uniform-cost search is optimal and complete \n\n DFS is not complete nor optimal. \n\n Deep-limited search is not complete nor optimal. \n\n Iterative deepening search expands the node according to deep-limited search with increasing depth bounds. \n\n Iterative deepening search is complete is all depths are checked. optimal for unit actions costs. \n\n Bidirectional search expands nodes around the initial and goal states. stops when two frontier meet. \n\n BFS: Time: O(b^d) Space: O(b^d). \n\n DFS: Time: O(b^m) Space: O(b*m), m is much larger than d. \n\n IDS: O(b^d) O(bd)\n DLS: O(b^l) O(bl)\n\n\n\n\n\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** - set of possible states of the environment\n* **Solution to search problem** - path through the state space from initial state to goal state\n* **Optimal solution** - solution with lowest path cost\n* **Graph search** - checks for redundant paths\n* **Tree search** - does not check for redundant paths\n* **Complete** - guaranteed to find a solution if there is one, report failure if there is not\n* **Cost optimal** - guaranteed to find the solution with lowest path cost\n* **Uninformed** - only has access to problem definition\n* **Complete algorithm** - BFS, UCS, IDS, Bidirectional\n* **Optimal algorithm** - BFS, UCS, IDS, Bidrectional\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 = \"\"\" Greedy best-first search expands nodes with minimal h(n) \\n\n",
        "A* search expands nodes with minimal f(n) = g(n) + h(n) \\n\n",
        "A* search has high space complexity \\n\n",
        "A* is complete. optimal is h(n) is admissible. \\n\n",
        "Beam search limites the size of the frontier. \\n\n",
        "Beam search is not optimal nor complete \\n\n",
        "Beam search runs faster than complete searches \\n\n",
        "Weighted A* expands for f(n) = g(n) + W * h(n). not optimal. is complete. expands fewer nodes. \\n\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed\" : \"has access to the problem definition and heuristic function h(n)\",\n",
        "\"heuristic function\" : \"estimates the cost of a solution from a node n\",\n",
        "\"admissible\" : \"never overestimates the cost to reach a goal, also called optimistic\",   \n",
        "\"IDA*\" : \"Iterative Deepening A*\",\n",
        "\"RBFS\" : \"recursive best first search\",\n",
        "\"SMA*\" : \"simplified memory-bounded A*\",         \n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 587
        },
        "cellView": "form",
        "outputId": "3e108cc2-1ff7-4ad3-9864-601fbcbd5385"
      },
      "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": 17,
      "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 Greedy best-first search expands nodes with minimal h(n) \n\nA* search expands nodes with minimal f(n) = g(n) + h(n) \n\nA* search has high space complexity \n\nA* is complete. optimal is h(n) is admissible. \n\nBeam search limites the size of the frontier. \n\nBeam search is not optimal nor complete \n\nBeam search runs faster than complete searches \n\nWeighted A* expands for f(n) = g(n) + W * h(n). not optimal. is complete. expands fewer nodes. \n\n\n\n \n\n## Module 4 Definitions\n* **Informed** - has access to the problem definition and heuristic function h(n)\n* **Heuristic function** - estimates the cost of a solution from a node n\n* **Admissible** - never overestimates the cost to reach a goal, also called optimistic\n* **Ida*** - Iterative Deepening A*\n* **Rbfs** - recursive best first search\n* **Sma*** - simplified memory-bounded A*\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 = \"\"\" Games have multiple agents (not search problem) \\n\n",
        " minimax search solves perfect information zero-sum games, evaluates as DFS \\n\n",
        " minimax: the value at the node is the value of the best terminal sate reach by both player optimally \\n\n",
        " minimax has time complexity O(b^m), b is the number of legal moves at each node. m is the max depth of tree \\n\n",
        " In minimax, the value of the node is the optimal value of its children. \\n\n",
        " Alpha-beta pruning eliminates provably irrelevant subtrees. \\n\n",
        " beta is the value of the best choice for MIN \\n\n",
        " Alpha-beta optimal running time O(b^(m/2)). worst same as minimax. \\n\n",
        " Type A B strategy is useful because it's not feasible to search the whole tree for large game. \\n\n",
        " Heuristic alpha-beta search replaces the utility function with a evaluation function. terminal test replaced with cutoff test \\n\n",
        " evaluation function only apply to positions that are quiescent. \\n\n",
        " handle games of chance using expectiminimax. \\n\n",
        " To define a game we need: initial state, terminal states, set of legal moves, utility functions. \\n\n",
        " minimax assumes opponent plays perfectly. \\n\n",
        " α: MAX’s current lower bound on MAX’s outcome \\n\n",
        " β: MIN’s current upper bound on MIN’s outcome \\n\n",
        " Therefore, stop evaluating a branch whenever:\n",
        " When evaluating a MAX node: a value v ≥ β is backed-up \\n\n",
        " When evaluating a MIN node: a value v ≤ α is found \\n\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"perfect information\" : \"fully observable\",\n",
        "\"zero-sum\" : \"what's good for one player is as bad for the other\",   \n",
        "\"terminal state\" : \"A state where a game ends\",\n",
        "\"utility function U(s)\" : \" gives the payoff for each player in terminal state s\",\n",
        "\"Type A Strategy\" : \"explores a wide but shallow portion of the tree\",\n",
        "\"Type B Strategy\" : \"explores a deep but narrow portion of the tree\",\n",
        "\"evaluation function\" : \"estimates the value of non-terminal nodes\",\n",
        "\"quiescient\" : \"no pending move that would wildly swing the valuation.\",   \n",
        "\"horizon effect\" : \"when an agent try to erroneously delay the inevitable\",            \n",
        "\"forward pruning\" : \"prunes moves that appear to be bad moves, example of Type B strategy. e.g. Beam search\",\n",
        "\"MCTS\" : \"Monte Carlo tree search, play the game to the end while randomly selecting moves, repeatedly play the game from the state and take average.\",      \n",
        "}\n",
        "\n"
      ],
      "execution_count": 18,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "4e1c5bf7-0763-4de4-ffda-cca6b211b239"
      },
      "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": 19,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'MCTS' is too long!\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 Games have multiple agents (not search problem) \n\n minimax search solves perfect information zero-sum games, evaluates as DFS \n\n minimax: the value at the node is the value of the best terminal sate reach by both player optimally \n\n minimax has time complexity O(b^m), b is the number of legal moves at each node. m is the max depth of tree \n\n In minimax, the value of the node is the optimal value of its children. \n\n Alpha-beta pruning eliminates provably irrelevant subtrees. \n\n beta is the value of the best choice for MIN \n\n Alpha-beta optimal running time O(b^(m/2)). worst same as minimax. \n\n Type A B strategy is useful because it's not feasible to search the whole tree for large game. \n\n Heuristic alpha-beta search replaces the utility function with a evaluation function. terminal test replaced with cutoff test \n\n evaluation function only apply to positions that are quiescent. \n\n handle games of chance using expectiminimax. \n\n To define a game we need: initial state, terminal states, set of legal moves, utility functions. \n\n minimax assumes opponent plays perfectly. \n\n α: MAX’s current lower bound on MAX’s outcome \n\n β: MIN’s current upper bound on MIN’s outcome \n\n Therefore, stop evaluating a branch whenever:\n When evaluating a MAX node: a value v ≥ β is backed-up \n\n When evaluating a MIN node: a value v ≤ α is found \n\n\n\n \n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n* **Zero-sum** - what's good for one player is as bad for the other\n* **Terminal state** - A state where a game ends\n* **Utility function u(s)** -  gives the payoff for each player in terminal state s\n* **Type a strategy** - explores a wide but shallow portion of the tree\n* **Type b strategy** - explores a deep but narrow portion of the tree\n* **Evaluation function** - estimates the value of non-terminal nodes\n* **Quiescient** - no pending move that would wildly swing the valuation.\n* **Horizon effect** - when an agent try to erroneously delay the inevitable\n* **Forward pruning** - prunes moves that appear to be bad moves, example of Type B strategy. e.g. Beam search\n* **Mcts** - Monte Carlo tree search, play the game to the end while randomly selecting moves, repeatedly play the game from the state and take average.\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" csp represent state with set of variable/value pairs \\n\n",
        "csp represent the conditions for a solution with a set of constraints on the variables \\n\n",
        "in search problems states are black boxes, while in CSP agent can see inside state and move between them accordingly \\n\n",
        "2 ways of ruling out variable assignment in CSP : search or inference \\n\n",
        "inference use constraints to rule out variable assignment, enforcing k-consistency \\n\n",
        "CSP is k-consistent is for any set of k-1 variables and for any consistent assignment to those vars, a consistent var can always be assigned to any kth var. \\n\n",
        "Node consistency is k-consistency with k=1 \\n\n",
        "Arc consistency : k = 2 \\n\n",
        "path consistency : k = 3 \\n\n",
        "AC3 enforces arc consistency \\n\n",
        "backtracking search is a form of DFS used for CSPs \\n\n",
        "backtracking occurs when no legal assignment can be found for a var. \\n\n",
        "MRV heuristic stands for Minimum remaining value, chooses the variable with fewest legal values \\n\n",
        "degree heuristic chooses the variable with largest number of constraints \\n\n",
        "least constaining value heuristic chooses the value that rules out fewest values for neighboring varibales \\n\n",
        "constraint learning records the conflicts as they are encountered in order to avoid same later \\n\n",
        "solving CSP takes exponential time in number of varibales \\n\n",
        "tree-structured CSP takes linear time. \\n\n",
        "cutset conditioning is used to reduce a CSP to a tree-structured CSP, most space efficient \\n\n",
        "Tree decomposition techniques transform the CSP into a tree of subproblems, efficient if the tree width of the constraint graph is small, more efficient than cutset \\n\n",
        "AC-3 place all arcs in a queue, pop arcs, for each arc, remove inconsistent values. if we change the value of a node, add its arcs to the queue, terminates when queue empty \\n\n",
        "Forward checking eastablish arc consistency for X when X is assigned. For each unassigned var Y that is connected to X, delete from Y's domain any value that is inconsistent with X \\n\n",
        "MAC is a way of interleaving seach and inference. AC-3 is pure inference. \\n\n",
        "Assumption: single agent, deterministic actions, fully observable, discrete state space \\n\n",
        "CSP consists of finite set of variables, nonempty domain of possible values, finite set of constraints. \\n\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"strongly k-consistent\" : \"k,k-1....1 consistent\",   \n",
        "\"MAC\" : \"Maintaining Arc Consistency\",   \n",
        "}\n"
      ],
      "execution_count": 20,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "4219e2c3-ad42-4524-8b49-51d1487f59f3"
      },
      "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": 21,
      "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 represent state with set of variable/value pairs \n\ncsp represent the conditions for a solution with a set of constraints on the variables \n\nin search problems states are black boxes, while in CSP agent can see inside state and move between them accordingly \n\n2 ways of ruling out variable assignment in CSP : search or inference \n\ninference use constraints to rule out variable assignment, enforcing k-consistency \n\nCSP is k-consistent is for any set of k-1 variables and for any consistent assignment to those vars, a consistent var can always be assigned to any kth var. \n\nNode consistency is k-consistency with k=1 \n\nArc consistency : k = 2 \n\npath consistency : k = 3 \n\nAC3 enforces arc consistency \n\nbacktracking search is a form of DFS used for CSPs \n\nbacktracking occurs when no legal assignment can be found for a var. \n\nMRV heuristic stands for Minimum remaining value, chooses the variable with fewest legal values \n\ndegree heuristic chooses the variable with largest number of constraints \n\nleast constaining value heuristic chooses the value that rules out fewest values for neighboring varibales \n\nconstraint learning records the conflicts as they are encountered in order to avoid same later \n\nsolving CSP takes exponential time in number of varibales \n\ntree-structured CSP takes linear time. \n\ncutset conditioning is used to reduce a CSP to a tree-structured CSP, most space efficient \n\nTree decomposition techniques transform the CSP into a tree of subproblems, efficient if the tree width of the constraint graph is small, more efficient than cutset \n\nAC-3 place all arcs in a queue, pop arcs, for each arc, remove inconsistent values. if we change the value of a node, add its arcs to the queue, terminates when queue empty \n\nForward checking eastablish arc consistency for X when X is assigned. For each unassigned var Y that is connected to X, delete from Y's domain any value that is inconsistent with X \n\nMAC is a way of interleaving seach and inference. AC-3 is pure inference. \n\nAssumption: single agent, deterministic actions, fully observable, discrete state space \n\nCSP consists of finite set of variables, nonempty domain of possible values, finite set of constraints. \n\n\n\n\n\n## Module 6 Definitions\n* **Strongly k-consistent** - k,k-1....1 consistent\n* **Mac** - Maintaining Arc Consistency\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" knowledge based agents use reasoning over an internal representation of knowledge to decide actions. \\n\n",
        "KB contains a set of sentence that are written in knowledge representation language. \\n\n",
        "β entails α if and only if every model in which β is true, α is also true \\n\n",
        "(α ⟹ β) ≡ (¬β ⟹ ¬α) \\n\n",
        "(α ⟹ β) ≡ (¬α ⋁ β) Implication elimination \\n\n",
        "(α ⇔ β) ≡ ((α ⟹ β) ⋀ (β ⟹α)) Biconditional Elimination \\n\n",
        "¬(α ⋀ β) ≡ (¬α ⋁ ¬β) De Morgan \\n\n",
        "¬(α ⋁ β) ≡ (¬α ⋀ ¬β) De Morgan \\n\n",
        "(α ⋀ (β ⋁ ɣ)) ≡ ((α ⋀ β) ⋁ (α ⋀ ɣ)) Distributivity of ⋀ over ⋁ \\n\n",
        "(α ⋁ (β ⋀ ɣ)) ≡ ((α ⋁ β) ⋀ (α ⋁ ɣ)) Distributivity of ⋁ over ⋀ \\n\n",
        "forward chaining is data-driven reasoning\n",
        "backward chaining is goal-directed reasoning\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Axioms\" : \"a sentence that is given\",\n",
        "\"Derived sentences\" : \"new sentence that is derived from other sentences\",\n",
        "\"inference\" : \"process of deriving new sentences from old sentences\",\n",
        "\"models\" : \"mathematical abstractions that have a fixed set of truth values\",\n",
        "\"M(a)\" : \"set of all models of a\",    \n",
        "\"propositional symbols\" : \"statement that can be true or false\",\n",
        "\"sound\" : \"the inference algorithm should only derive entailed sentences\",\n",
        "\"complete\" : \"an inference algorithm is complete if it can derive all sentences that are entailed\",\n",
        "\"conjunctive normal form\" : \"conjunction of clauses, only contain ⋀ and ⋁ \",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 25,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 867
        },
        "outputId": "cce903be-7ce1-4321-d882-3ef7220b5a45"
      },
      "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": 26,
      "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 knowledge based agents use reasoning over an internal representation of knowledge to decide actions. \n\nKB contains a set of sentence that are written in knowledge representation language. \n\nβ entails α if and only if every model in which β is true, α is also true \n\n(α ⟹ β) ≡ (¬β ⟹ ¬α) \n\n(α ⟹ β) ≡ (¬α ⋁ β) Implication elimination \n\n(α ⇔ β) ≡ ((α ⟹ β) ⋀ (β ⟹α)) Biconditional Elimination \n\n¬(α ⋀ β) ≡ (¬α ⋁ ¬β) De Morgan \n\n¬(α ⋁ β) ≡ (¬α ⋀ ¬β) De Morgan \n\n(α ⋀ (β ⋁ ɣ)) ≡ ((α ⋀ β) ⋁ (α ⋀ ɣ)) Distributivity of ⋀ over ⋁ \n\n(α ⋁ (β ⋀ ɣ)) ≡ ((α ⋁ β) ⋀ (α ⋁ ɣ)) Distributivity of ⋁ over ⋀ \n\n\n \n\n## Module 7 Definitions\n* **Axioms** - a sentence that is given\n* **Derived sentences** - new sentence that is derived from other sentences\n* **Inference** - process of deriving new sentences from old sentences\n* **Models** - mathematical abstractions that have a fixed set of truth values\n* **M(a)** - set of all models of a\n* **Propositional symbols** - statement that can be true or false\n* **Sound** - the inference algorithm should only derive entailed sentences\n* **Complete** - an inference algorithm is complete if it can derive all sentences that are entailed\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": 3366
        },
        "id": "T3cm1WV542_a",
        "outputId": "a929c6c6-b72b-4fd8-bd35-a014674c9230"
      },
      "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": {}
        }
      ]
    }
  ]
}