{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_midterm notes_Xinyuan.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "344222ad-a216-45e3-9726-b566dead59fe"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ef81cd11-e574-43c8-fb57-4c2e2e3d803c"
      },
      "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 = \"\"\"AI => Rationality. \\n\n",
        "Turing Test Approach: the machine needs: NLP, Knowledge Represent, Automated reasoning, ML \\n\n",
        "To pass total turing test, machine needs in addition: CV and Robotics \\n\n",
        "The cognitive modeling approach: Cognitive science. The “laws of thought” approach\"\"\" \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 = \"\"\" Weak AI: act as if they are intelligient, Strong AI: Actually thinking with consciousness \\n\n",
        "embodied cognition approach: Intelligience come from body as a whole. robotics, vision, and other sensors are central, not peripheral.\"\"\"\n",
        "chapter27_2 = \"\"\"strong AI is the issue of consciousness: awareness of the outside world, self, and subjective experience of living <= Qualia\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" agent function: action of agent in response to percept, agent program implements agent functions\"\"\"\n",
        "chapter2_2 = \"\"\" performance measure evaluates the behavior of the agent in an environment. \\n\n",
        "A rational agent acts to maximize the expected value of the performance measure, given the percept sequence and built in knowledge.\"\"\"\n",
        "chapter2_3 = \"\"\" task environment specification includes the performance measure, environment, the actuators, and the sensors. \\n\n",
        "specify the task environment the first thing when designing agents. Agents need to reflect uncertainty in task environment.\"\"\"\n",
        "chapter2_4 = \"\"\"Simple reflex agents respond directly to percepts \\n\n",
        "model-based reflex agents has internal state to track aspects of the world \\n\n",
        "Goal-based agents act to achieve their goals \\n\n",
        "utility-based agents try to maximize their own expected “happiness.”\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Task Environments: Fully vs. Partially Observable: whether sensor can detect whole environment \\n\n",
        "Deterministic: 1 outcome, Non-Deter: multiple outcomes possible, Stochastics: outcomes can be quantified by probabilities. \\n\n",
        "Episodic vs. Sequential, Static vs. Dynamic, Discrete States vs. Continuous\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"content an agent’s sensors are perceiving\",\n",
        "\"Rational Agent\" : \"Agents that act to achieve the best outcome\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 1,
      "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": 961
        },
        "outputId": "ee306291-ad53-41e0-c115-defa7d6d829c"
      },
      "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": 2,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nAI => Rationality. \n\nTuring Test Approach: the machine needs: NLP, Knowledge Represent, Automated reasoning, ML \n\nTo pass total turing test, machine needs in addition: CV and Robotics \n\nThe cognitive modeling approach: Cognitive science. The “laws of thought” approach\n\n## AIMA Chapter 27.1 The Limits of AI\n Weak AI: act as if they are intelligient, Strong AI: Actually thinking with consciousness \n\nembodied cognition approach: Intelligience come from body as a whole. robotics, vision, and other sensors are central, not peripheral.\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nstrong AI is the issue of consciousness: awareness of the outside world, self, and subjective experience of living <= Qualia\n\n## AIMA 2.1 Agents and Environments\n agent function: action of agent in response to percept, agent program implements agent functions\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n performance measure evaluates the behavior of the agent in an environment. \n\nA rational agent acts to maximize the expected value of the performance measure, given the percept sequence and built in knowledge.\n\n## AIMA 2.3 The Nature of Environments\n task environment specification includes the performance measure, environment, the actuators, and the sensors. \n\nspecify the task environment the first thing when designing agents. Agents need to reflect uncertainty in task environment.\n\n## AIMA 2.4 The Structure of Agents\nSimple reflex agents respond directly to percepts \n\nmodel-based reflex agents has internal state to track aspects of the world \n\nGoal-based agents act to achieve their goals \n\nutility-based agents try to maximize their own expected “happiness.”\n\n## Module 1 Lecture Notes\n Task Environments: Fully vs. Partially Observable: whether sensor can detect whole environment \n\nDeterministic: 1 outcome, Non-Deter: multiple outcomes possible, Stochastics: outcomes can be quantified by probabilities. \n\nEpisodic vs. Sequential, Static vs. Dynamic, Discrete States vs. Continuous\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - content an agent’s sensors are perceiving\n* **Rational agent** - Agents that act to achieve the best outcome\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" All data = objects. \\\n",
        "Strong Typing: Every object has a fixed type \\n\n",
        "Static Typing: Variables can only refer to objects of a declared type \\n\n",
        "Dynamic Typing: auto detect type, can be reassigned with diff type \\n\n",
        "Immutable: Tuple, String, keys of dict must be immutable \\n\n",
        "Mutable: Lists. \\\n",
        "No Function overloading \\n\n",
        "Generator: A iterator with next method, yield: Each time we call the __next__ method of the generator, the method runs until it \\\n",
        "encounters a yield statement, and then it stops and returns the value that was yielded. \\\n",
        "Next time, it resumes where it left off. \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"whether can be modified once created\",\n",
        "}"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 341
        },
        "outputId": "9d9a6445-cb8d-41c5-e3a1-6f4e2fd7adb0"
      },
      "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": 4,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n All data = objects. Strong Typing: Every object has a fixed type \n\nStatic Typing: Variables can only refer to objects of a declared type \n\nDynamic Typing: auto detect type, can be reassigned with diff type \n\nImmutable: Tuple, String, keys of dict must be immutable \n\nMutable: Lists. No Function overloading \n\nGenerator: A iterator with next method, yield: Each time we call the __next__ method of the generator, the method runs until it encounters a yield statement, and then it stops and returns the value that was yielded. Next time, it resumes where it left off. \n\n## Module 2 Definitions\n* **Mutability** - whether can be modified once created\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 = \"\"\" Search Problem Definition: the initial state, a set of actions, a transition model describing the results of those actions, a set of goal states, and an action cost function. \"\"\"\n",
        "chapter3_2 = \"\"\" Environment of the problem : represented by a state space graph. \\n \n",
        "Solution : A path through the state space (a sequence of actions) from the initial state to a goal state \\n\n",
        "Search algorithms generally treat states and actions as atomic, without any internal structure \"\"\"\n",
        "chapter3_3 = \"\"\"Graph search checks for redundant paths, tree-like search does not check. \\n\n",
        "The Best-First-Search algorithm is a graph search algorithm that selects nodes for expansion using to an evaluation function \\n \n",
        "tree-like search does not store visited nodes => uses less memory but run slower. \"\"\"\n",
        "chapter3_4 = \"\"\"Uninformed search have access only to the problem definition => build a search tree to find a solution \\n\n",
        "Uniform Cost Search : for paths with different path cost, expand the node with lowest path cost g(n). Dijkstra’s algorithm is a Uniform-cost Search without a goal. \\n\n",
        "Bi-directional Search : expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"A Node consists of: <state, parent-node, children, action, path-cost, depth> \\n\n",
        "Use DFS if: Restricted Space, Use BFS if: possible infinite paths.\"\"\"\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 all states reachable from the initial state by any sequence of actions\",\n",
        "\"Search Tree\" : \"paths that a search algorithm has explored in order to find a solution\",\n",
        "\"Frontier\" : \"Next states available for expanding\",\n",
        "\"Optimal Solution\" : \"Solution with lowest Path cost\"    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 720
        },
        "outputId": "1aac37dd-9fe6-4e48-98a5-1a755138f168"
      },
      "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": 6,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Search Problem Definition: the initial state, a set of actions, a transition model describing the results of those actions, a set of goal states, and an action cost function. \n\n## AIMA Chapter 3.2 Example Problems\n Environment of the problem : represented by a state space graph. \n \nSolution : A path through the state space (a sequence of actions) from the initial state to a goal state \n\nSearch algorithms generally treat states and actions as atomic, without any internal structure \n\n## AIMA Chapter 3.3 Search Algorithms\nGraph search checks for redundant paths, tree-like search does not check. \n\nThe Best-First-Search algorithm is a graph search algorithm that selects nodes for expansion using to an evaluation function \n \ntree-like search does not store visited nodes => uses less memory but run slower. \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\nUninformed search have access only to the problem definition => build a search tree to find a solution \n\nUniform Cost Search : for paths with different path cost, expand the node with lowest path cost g(n). Dijkstra’s algorithm is a Uniform-cost Search without a goal. \n\nBi-directional Search : expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet.\n\n## Module 3 Lecture Notes\nA Node consists of: <state, parent-node, children, action, path-cost, depth> \n\nUse DFS if: Restricted Space, Use BFS if: possible infinite paths.\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** - set of all states reachable from the initial state by any sequence of actions\n* **Search tree** - paths that a search algorithm has explored in order to find a solution\n* **Frontier** - Next states available for expanding\n* **Optimal solution** - Solution with lowest Path cost\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 = \"\"\"Informed Search : Access to problem definition and a heuristic h(n) \\n\n",
        "Heurisitc function h(n) gives estimate of the path cost from n to goal.\"\"\"\n",
        "chapter3_6 = \"\"\" Construct good heuristics by : Relax problem (reduce restrictions) \\n\n",
        "by storing precomputed solution costs for subproblems in a pattern database, by defining landmarks, or by learning from experience with the problem class. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"Greedy best first search : expand the node with lowest heuristic h(n). Not Optimal, Not Complete (May stuck in cycles) \\n\n",
        "A star search : expand node with lowest f(n) = h(n) + g(n). Complete, and Optimal if h(n) is admissible. \\n\n",
        "Admissible Heuristic : The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem \\n\n",
        "Dominance : if h1 and h2 are both admissible but h2(n) >= h1(n) for all n, then h2(n) dominates h1(n) because it is more accurate.\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"admissible\" : \"A heuristic is admissible or optimistic if it never overestimates the path cost to goal\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 456
        },
        "cellView": "form",
        "outputId": "0c83ef32-236e-4eb2-f7a2-ecdd43778fe8"
      },
      "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": 8,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nInformed Search : Access to problem definition and a heuristic h(n) \n\nHeurisitc function h(n) gives estimate of the path cost from n to goal.\n\n## AIMA Chapter 3.6 Heuristic Functions\n Construct good heuristics by : Relax problem (reduce restrictions) \n\nby storing precomputed solution costs for subproblems in a pattern database, by defining landmarks, or by learning from experience with the problem class. \n\n## Module 4 Lecture Notes\nGreedy best first search : expand the node with lowest heuristic h(n). Not Optimal, Not Complete (May stuck in cycles) \n\nA star search : expand node with lowest f(n) = h(n) + g(n). Complete, and Optimal if h(n) is admissible. \n\nAdmissible Heuristic : The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem \n\nDominance : if h1 and h2 are both admissible but h2(n) >= h1(n) for all n, then h2(n) dominates h1(n) because it is more accurate.\n\n## Module 4 Definitions\n* **Admissible** - A heuristic is admissible or optimistic if it never overestimates the path cost to goal\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 = \"\"\"A game can be defined by the initial state, \\\n",
        " the successor function (move, state) pairs for legal moves, \\\n",
        " a terminal test, and a utility function that applies to terminal states to say who won and what the final score is. \\n\n",
        " Environment : Static, Discrete, Multiagent, Fully Observable, strategic \\n\n",
        " Strategy : Next state depends on current state, action by agent and action by the other agent\"\"\"\n",
        "chapter5_2 = \"\"\" All plays are computed from MAX perspective, MAX determine the next move by a search tree \\n\n",
        "Ply : Alternate MAX/MIN labels at each successive tree level \\n\n",
        "The backed-up value : of each node in the tree is determined by the values of its children (MAX back up value = max of its children) \\n\n",
        "minimax value: the best achievable utility against a optimal adversary \"\"\"\n",
        "chapter5_3 = \"\"\" Heuristic alpha beta search : replace the Utility function with Eval(s,p) which estimates the expected utility of state s to player p for terminal or non-terminal states \\\n",
        "for terminal states : EVAL = Utility \\n\n",
        "Replace terminal test by a cutoff test. May cutoff at non-terminal states and apply Eval(s,p) to it.\"\"\"\n",
        "chapter5_5 = \"\"\" Game tree of stochastic games includes chance nodes in addition to MAX and MIN nodes \\n\n",
        "Value of a chance node = Weighted average of all possible children's values (Expected Utility) \\n\n",
        "expectiminimax value : the same as minimax value except that value for chance node is sum of outcome values weighted by their probability. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Probability theory describes what an agent should believe on the basis of evidence, utility theory describes what an agent wants, and decision theory puts the two together to describe what an agent should do. \"\"\"\n",
        "chapter16_2 = \"\"\" Utility theory shows that an agent whose preferences between lotteries are consistent with a set of simple axioms can be described as possessing a utility function; furthermore, the agent selects actions as if maximizing its expected utility. \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 926
        },
        "outputId": "dc8fb5db-e67a-401c-ff9f-0d476615b4ab"
      },
      "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": 10,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nA game can be defined by the initial state,  the successor function (move, state) pairs for legal moves,  a terminal test, and a utility function that applies to terminal states to say who won and what the final score is. \n\n Environment : Static, Discrete, Multiagent, Fully Observable, strategic \n\n Strategy : Next state depends on current state, action by agent and action by the other agent\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n All plays are computed from MAX perspective, MAX determine the next move by a search tree \n\nPly : Alternate MAX/MIN labels at each successive tree level \n\nThe backed-up value : of each node in the tree is determined by the values of its children (MAX back up value = max of its children) \n\nminimax value: the best achievable utility against a optimal adversary \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Heuristic alpha beta search : replace the Utility function with Eval(s,p) which estimates the expected utility of state s to player p for terminal or non-terminal states for terminal states : EVAL = Utility \n\nReplace terminal test by a cutoff test. May cutoff at non-terminal states and apply Eval(s,p) to it.\n\n## AIMA Chapter 5.5 Stochastic Games\n Game tree of stochastic games includes chance nodes in addition to MAX and MIN nodes \n\nValue of a chance node = Weighted average of all possible children's values (Expected Utility) \n\nexpectiminimax value : the same as minimax value except that value for chance node is sum of outcome values weighted by their probability. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Probability theory describes what an agent should believe on the basis of evidence, utility theory describes what an agent wants, and decision theory puts the two together to describe what an agent should do. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Utility theory shows that an agent whose preferences between lotteries are consistent with a set of simple axioms can be described as possessing a utility function; furthermore, the agent selects actions as if maximizing its expected utility. \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",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" CSP : Finite set of variables \\n\n",
        "Nonempty domain of possible values for each variable \\n\n",
        "Finite set of constraints \\n\n",
        "A state is defined as an assignment of values to some or all variables. \\n\n",
        "A consistent assignment does not violate the constraints \\n\n",
        "An assignment is complete when every variable is assigned a value. \\\n",
        "A solution to a CSP is a complete, consistent assignment\"\"\"\n",
        "chapter6_2 = \"\"\" constraint propagation: using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable.\"\"\"\n",
        "chapter6_3 = \"\"\" Backtracking Search : The minimum-remaining-values (Most Constrained) and degree (impose most constraints to other variables) heuristics are used to select the next variable, \\n\n",
        "least-constraining-value heuristic (cause least constraints for neighboring variables in the constraint graph) is used to assign value given the variable. \\n\n",
        "Inference by forward checking : Whenever X is assigned a value, we forward check X's neighbors to ensure Arc consistency of X.\"\"\"\n",
        "chapter6_4 = \"\"\" Local search : select the value that results in the minimum number of conflicts with other variables (Min conflict heuristic) \"\"\"\n",
        "chapter6_5 = \"\"\" CSP complexity : Tree-structured problems can be solved in linear time \\n\n",
        "Cutset conditioning : reduce a general CSP to a tree-structured one, Efficient (requiring only linear memory) if a small cutset can be found. \\n\n",
        "Tree decomposition : transform the CSP into a tree of subproblems, Efficient if the tree width of the constraint graph is small; need memory exponential in the tree width of the constraint graph \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Forward checking heuristic for backtrack search : Keep track of remaining legal values for unassigned variables. \\\n",
        "Terminate search when any unassigned variable has no remaining legal values. \\n\n",
        "Forward checking as part of Inference algorithm : only check X's neighbors for arc consistency\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"node-consistent\" : \"all the values in the variable’s domain satisfy the variable’s unary constraints\",\n",
        "\"arc-consistent\" : \"every value in the variable's domain satisfies the variable’s binary constraints\",\n",
        "\"K-consistent\" : \"a consistent value can always be assigned to any k-th variable.\",\n",
        "\"Strong K-consistent\" : \"if it is K-consistent also k-1-consistent and k-2...\"     \n",
        "}\n"
      ],
      "execution_count": 17,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 873
        },
        "outputId": "a9c7e0cb-adaf-4905-aecc-b27ac8a3608c"
      },
      "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": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSP : Finite set of variables \n\nNonempty domain of possible values for each variable \n\nFinite set of constraints \n\nA state is defined as an assignment of values to some or all variables. \n\nA consistent assignment does not violate the constraints \n\nAn assignment is complete when every variable is assigned a value. A solution to a CSP is a complete, consistent assignment\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n constraint propagation: using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable.\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Backtracking Search : The minimum-remaining-values (Most Constrained) and degree (impose most constraints to other variables) heuristics are used to select the next variable, \n\nleast-constraining-value heuristic (cause least constraints for neighboring variables in the constraint graph) is used to assign value given the variable. \n\nInference by forward checking : Whenever X is assigned a value, we forward check X's neighbors to ensure Arc consistency of X.\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search : select the value that results in the minimum number of conflicts with other variables (Min conflict heuristic) \n\n## AIMA Chapter 6.5 The Structure of Problems\n CSP complexity : Tree-structured problems can be solved in linear time \n\nCutset conditioning : reduce a general CSP to a tree-structured one, Efficient (requiring only linear memory) if a small cutset can be found. \n\nTree decomposition : transform the CSP into a tree of subproblems, Efficient if the tree width of the constraint graph is small; need memory exponential in the tree width of the constraint graph \n\n## Module 6 Lecture Notes\n Forward checking heuristic for backtrack search : Keep track of remaining legal values for unassigned variables. Terminate search when any unassigned variable has no remaining legal values. \n\nForward checking as part of Inference algorithm : only check X's neighbors for arc consistency\n\n## Module 6 Definitions\n* **Node-consistent** - all the values in the variable’s domain satisfy the variable’s unary constraints\n* **Arc-consistent** - every value in the variable's domain satisfies the variable’s binary constraints\n* **K-consistent** - a consistent value can always be assigned to any k-th variable.\n* **Strong k-consistent** - if it is K-consistent also k-1-consistent and k-2...\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" knowledge base : a set of sentences expressed in a language called a knowledge representation language and represents some assertion about the world. \\\n",
        " Axiom are sentenses given not derived. We use Inference to derive new sentenses from the old. \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" The semantics defines the truth of each sentence with respect to each possible world (Model)\\n\n",
        "Model : if a sentence alpha is true in Model M, then M satisfies alpha. We use M(alpha) for a set of all models for alpha. \\n\n",
        "Entailment : A entails B if and only if, in every model in which A is true, B is also true. Or M(A) is a subset of M(B) \\n\n",
        "Inference Algorithms derives new sentence A, then KB must entails A (M(KB) is subset of M(A)), then this algorithm is sound and truth preserving. \\n\n",
        "Inference Algorithm is complete if it can derive any sentence that is entailed\"\"\"\n",
        "chapter7_4 = \"\"\" Conjunction form : main connective is AND, Disjunction form: main connective is OR. \\n \"\"\"\n",
        "chapter7_5 = \"\"\" Definite clause : a disjunction of literals of which exactly one is positive (other variables must have a NOT sign) \\n\n",
        "Horn clause : a disjunction of literals of which at most one is positive. \\n\n",
        "The resolution rule yields a complete inference algorithm for knowledge bases that are expressed in conjunctive normal form. \\n\n",
        "Forward chaining and backward chaining are very natural reasoning algorithms for knowledge bases in Horn form\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"Monotonicity : the set of entailed sentence can only increase as information is added to the KB. \\\n",
        "If KB entails A, then KB AND B entails A \\n\n",
        "Resolution Algorithm : convert into CNF, Then apply the resolution rule to the resulting clauses. \\n\n",
        "• Resolve every pair that contains complementary literals to produce a new clause \\n\n",
        "• If that new clause isn’t already present, then add it to the set. \\n\n",
        "• Continue the process until one of two things happens: \\n\n",
        "1. There are no new clauses that can be added. In this case, the KB does not entail new sentence \\n\n",
        "2. Two clauses resolve to yield the empty clause (contradiction btw 2 clauses), in which case the KB does entail new sentence \\n\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 19,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 865
        },
        "outputId": "f715a50f-80d5-4500-e6fc-cbdd191a6518"
      },
      "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": 20,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n knowledge base : a set of sentences expressed in a language called a knowledge representation language and represents some assertion about the world.  Axiom are sentenses given not derived. We use Inference to derive new sentenses from the old. \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n The semantics defines the truth of each sentence with respect to each possible world (Model)\n\nModel : if a sentence alpha is true in Model M, then M satisfies alpha. We use M(alpha) for a set of all models for alpha. \n\nEntailment : A entails B if and only if, in every model in which A is true, B is also true. Or M(A) is a subset of M(B) \n\nInference Algorithms derives new sentence A, then KB must entails A (M(KB) is subset of M(A)), then this algorithm is sound and truth preserving. \n\nInference Algorithm is complete if it can derive any sentence that is entailed\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Conjunction form : main connective is AND, Disjunction form: main connective is OR. \n \n\n## AIMA 7.5 Propositional Theorem Proving\n Definite clause : a disjunction of literals of which exactly one is positive (other variables must have a NOT sign) \n\nHorn clause : a disjunction of literals of which at most one is positive. \n\nThe resolution rule yields a complete inference algorithm for knowledge bases that are expressed in conjunctive normal form. \n\nForward chaining and backward chaining are very natural reasoning algorithms for knowledge bases in Horn form\n\n## Module 7 Lecture Notes\nMonotonicity : the set of entailed sentence can only increase as information is added to the KB. If KB entails A, then KB AND B entails A \n\nResolution Algorithm : convert into CNF, Then apply the resolution rule to the resulting clauses. \n\n• Resolve every pair that contains complementary literals to produce a new clause \n\n• If that new clause isn’t already present, then add it to the set. \n\n• Continue the process until one of two things happens: \n\n1. There are no new clauses that can be added. In this case, the KB does not entail new sentence \n\n2. Two clauses resolve to yield the empty clause (contradiction btw 2 clauses), in which case the KB does entail new sentence \n\n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "79befc41-3197-493e-9e67-39ba5849096e"
      },
      "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": 21,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nAI => Rationality. \n\nTuring Test Approach: the machine needs: NLP, Knowledge Represent, Automated reasoning, ML \n\nTo pass total turing test, machine needs in addition: CV and Robotics \n\nThe cognitive modeling approach: Cognitive science. The “laws of thought” approach\n\n## AIMA Chapter 27.1 The Limits of AI\n Weak AI: act as if they are intelligient, Strong AI: Actually thinking with consciousness \n\nembodied cognition approach: Intelligience come from body as a whole. robotics, vision, and other sensors are central, not peripheral.\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nstrong AI is the issue of consciousness: awareness of the outside world, self, and subjective experience of living <= Qualia\n\n## AIMA 2.1 Agents and Environments\n agent function: action of agent in response to percept, agent program implements agent functions\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n performance measure evaluates the behavior of the agent in an environment. \n\nA rational agent acts to maximize the expected value of the performance measure, given the percept sequence and built in knowledge.\n\n## AIMA 2.3 The Nature of Environments\n task environment specification includes the performance measure, environment, the actuators, and the sensors. \n\nspecify the task environment the first thing when designing agents. Agents need to reflect uncertainty in task environment.\n\n## AIMA 2.4 The Structure of Agents\nSimple reflex agents respond directly to percepts \n\nmodel-based reflex agents has internal state to track aspects of the world \n\nGoal-based agents act to achieve their goals \n\nutility-based agents try to maximize their own expected “happiness.”\n\n## Module 1 Lecture Notes\n Task Environments: Fully vs. Partially Observable: whether sensor can detect whole environment \n\nDeterministic: 1 outcome, Non-Deter: multiple outcomes possible, Stochastics: outcomes can be quantified by probabilities. \n\nEpisodic vs. Sequential, Static vs. Dynamic, Discrete States vs. Continuous\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - content an agent’s sensors are perceiving\n* **Rational agent** - Agents that act to achieve the best outcome\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n All data = objects. Strong Typing: Every object has a fixed type \n\nStatic Typing: Variables can only refer to objects of a declared type \n\nDynamic Typing: auto detect type, can be reassigned with diff type \n\nImmutable: Tuple, String, keys of dict must be immutable \n\nMutable: Lists. No Function overloading \n\nGenerator: A iterator with next method, yield: Each time we call the __next__ method of the generator, the method runs until it encounters a yield statement, and then it stops and returns the value that was yielded. Next time, it resumes where it left off. \n\n## Module 2 Definitions\n* **Mutability** - whether can be modified once created\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Search Problem Definition: the initial state, a set of actions, a transition model describing the results of those actions, a set of goal states, and an action cost function. \n\n## AIMA Chapter 3.2 Example Problems\n Environment of the problem : represented by a state space graph. \n \nSolution : A path through the state space (a sequence of actions) from the initial state to a goal state \n\nSearch algorithms generally treat states and actions as atomic, without any internal structure \n\n## AIMA Chapter 3.3 Search Algorithms\nGraph search checks for redundant paths, tree-like search does not check. \n\nThe Best-First-Search algorithm is a graph search algorithm that selects nodes for expansion using to an evaluation function \n \ntree-like search does not store visited nodes => uses less memory but run slower. \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\nUninformed search have access only to the problem definition => build a search tree to find a solution \n\nUniform Cost Search : for paths with different path cost, expand the node with lowest path cost g(n). Dijkstra’s algorithm is a Uniform-cost Search without a goal. \n\nBi-directional Search : expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet.\n\n## Module 3 Lecture Notes\nA Node consists of: <state, parent-node, children, action, path-cost, depth> \n\nUse DFS if: Restricted Space, Use BFS if: possible infinite paths.\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** - set of all states reachable from the initial state by any sequence of actions\n* **Search tree** - paths that a search algorithm has explored in order to find a solution\n* **Frontier** - Next states available for expanding\n* **Optimal solution** - Solution with lowest Path cost\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nInformed Search : Access to problem definition and a heuristic h(n) \n\nHeurisitc function h(n) gives estimate of the path cost from n to goal.\n\n## AIMA Chapter 3.6 Heuristic Functions\n Construct good heuristics by : Relax problem (reduce restrictions) \n\nby storing precomputed solution costs for subproblems in a pattern database, by defining landmarks, or by learning from experience with the problem class. \n\n## Module 4 Lecture Notes\nGreedy best first search : expand the node with lowest heuristic h(n). Not Optimal, Not Complete (May stuck in cycles) \n\nA star search : expand node with lowest f(n) = h(n) + g(n). Complete, and Optimal if h(n) is admissible. \n\nAdmissible Heuristic : The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem \n\nDominance : if h1 and h2 are both admissible but h2(n) >= h1(n) for all n, then h2(n) dominates h1(n) because it is more accurate.\n\n## Module 4 Definitions\n* **Admissible** - A heuristic is admissible or optimistic if it never overestimates the path cost to goal\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nA game can be defined by the initial state,  the successor function (move, state) pairs for legal moves,  a terminal test, and a utility function that applies to terminal states to say who won and what the final score is. \n\n Environment : Static, Discrete, Multiagent, Fully Observable, strategic \n\n Strategy : Next state depends on current state, action by agent and action by the other agent\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n All plays are computed from MAX perspective, MAX determine the next move by a search tree \n\nPly : Alternate MAX/MIN labels at each successive tree level \n\nThe backed-up value : of each node in the tree is determined by the values of its children (MAX back up value = max of its children) \n\nminimax value: the best achievable utility against a optimal adversary \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Heuristic alpha beta search : replace the Utility function with Eval(s,p) which estimates the expected utility of state s to player p for terminal or non-terminal states for terminal states : EVAL = Utility \n\nReplace terminal test by a cutoff test. May cutoff at non-terminal states and apply Eval(s,p) to it.\n\n## AIMA Chapter 5.5 Stochastic Games\n Game tree of stochastic games includes chance nodes in addition to MAX and MIN nodes \n\nValue of a chance node = Weighted average of all possible children's values (Expected Utility) \n\nexpectiminimax value : the same as minimax value except that value for chance node is sum of outcome values weighted by their probability. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Probability theory describes what an agent should believe on the basis of evidence, utility theory describes what an agent wants, and decision theory puts the two together to describe what an agent should do. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Utility theory shows that an agent whose preferences between lotteries are consistent with a set of simple axioms can be described as possessing a utility function; furthermore, the agent selects actions as if maximizing its expected utility. \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 CSP : Finite set of variables \n\nNonempty domain of possible values for each variable \n\nFinite set of constraints \n\nA state is defined as an assignment of values to some or all variables. \n\nA consistent assignment does not violate the constraints \n\nAn assignment is complete when every variable is assigned a value. A solution to a CSP is a complete, consistent assignment\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n constraint propagation: using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable.\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Backtracking Search : The minimum-remaining-values (Most Constrained) and degree (impose most constraints to other variables) heuristics are used to select the next variable, \n\nleast-constraining-value heuristic (cause least constraints for neighboring variables in the constraint graph) is used to assign value given the variable. \n\nInference by forward checking : Whenever X is assigned a value, we forward check X's neighbors to ensure Arc consistency of X.\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search : select the value that results in the minimum number of conflicts with other variables (Min conflict heuristic) \n\n## AIMA Chapter 6.5 The Structure of Problems\n CSP complexity : Tree-structured problems can be solved in linear time \n\nCutset conditioning : reduce a general CSP to a tree-structured one, Efficient (requiring only linear memory) if a small cutset can be found. \n\nTree decomposition : transform the CSP into a tree of subproblems, Efficient if the tree width of the constraint graph is small; need memory exponential in the tree width of the constraint graph \n\n## Module 6 Lecture Notes\n Forward checking heuristic for backtrack search : Keep track of remaining legal values for unassigned variables. Terminate search when any unassigned variable has no remaining legal values. \n\nForward checking as part of Inference algorithm : only check X's neighbors for arc consistency\n\n## Module 6 Definitions\n* **Node-consistent** - all the values in the variable’s domain satisfy the variable’s unary constraints\n* **Arc-consistent** - every value in the variable's domain satisfies the variable’s binary constraints\n* **K-consistent** - a consistent value can always be assigned to any k-th variable.\n* **Strong k-consistent** - if it is K-consistent also k-1-consistent and k-2...\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n knowledge base : a set of sentences expressed in a language called a knowledge representation language and represents some assertion about the world.  Axiom are sentenses given not derived. We use Inference to derive new sentenses from the old. \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n The semantics defines the truth of each sentence with respect to each possible world (Model)\n\nModel : if a sentence alpha is true in Model M, then M satisfies alpha. We use M(alpha) for a set of all models for alpha. \n\nEntailment : A entails B if and only if, in every model in which A is true, B is also true. Or M(A) is a subset of M(B) \n\nInference Algorithms derives new sentence A, then KB must entails A (M(KB) is subset of M(A)), then this algorithm is sound and truth preserving. \n\nInference Algorithm is complete if it can derive any sentence that is entailed\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Conjunction form : main connective is AND, Disjunction form: main connective is OR. \n \n\n## AIMA 7.5 Propositional Theorem Proving\n Definite clause : a disjunction of literals of which exactly one is positive (other variables must have a NOT sign) \n\nHorn clause : a disjunction of literals of which at most one is positive. \n\nThe resolution rule yields a complete inference algorithm for knowledge bases that are expressed in conjunctive normal form. \n\nForward chaining and backward chaining are very natural reasoning algorithms for knowledge bases in Horn form\n\n## Module 7 Lecture Notes\nMonotonicity : the set of entailed sentence can only increase as information is added to the KB. If KB entails A, then KB AND B entails A \n\nResolution Algorithm : convert into CNF, Then apply the resolution rule to the resulting clauses. \n\n• Resolve every pair that contains complementary literals to produce a new clause \n\n• If that new clause isn’t already present, then add it to the set. \n\n• Continue the process until one of two things happens: \n\n1. There are no new clauses that can be added. In this case, the KB does not entail new sentence \n\n2. Two clauses resolve to yield the empty clause (contradiction btw 2 clauses), in which case the KB does entail new sentence \n\n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}