{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other 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": "4980d5f7-346d-4574-e51d-f7ad8452d2e6"
      },
      "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": 1,
      "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": "5d2b8a25-e07a-4c8b-df47-8902619c58cc"
      },
      "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": 2,
      "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": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Chapter 1.1 summary. \"\"\" \n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Agent: anything that perceives its environment through sensors and acts on its environment through actuators \n",
        "Rational agent: behaves rationally \n",
        "We define a performance measure to test whether an agent acts rationally \n",
        "\n",
        "Percept: agent’s perceptual inputs at any given instance\n",
        "\n",
        "Agent function: maps a sequence of percept vectors P to an action a from a set A\n",
        "\n",
        "For each possible percept sequence P • a rational agent selects an action a • to maximize its performance measure\n",
        "\n",
        "Task environment: a problem specification for which the agent is a solution \n",
        "To specify a task environment: \n",
        "P - performance measure\n",
        "E - environment\n",
        "A - actuators\n",
        "S - sensors\n",
        "\n",
        "When is something an agent vs a part of the environment: \n",
        "When something’s behavior can be described as having its own performance measure \n",
        "\n",
        "Fully observable: has access to all required information to complete target task (chess) \n",
        "Partially observable: partial information in order to solve AI problems (self driving → don’t know what’s around the corner) \n",
        "\n",
        "Deterministic: always give the same outcome given the same input\n",
        "Nondeterministic: may give different outcomes for the same input\n",
        "Stochastic: uncertainty associated with the outcome\n",
        "\n",
        "Episodic: environment where each state is independent of each other\n",
        "Sequential: environment where the next state is dependent on the current action\n",
        "\n",
        "Static: model trained once on data offline to be used for an extended period\n",
        "Dynamic: new data is continuously coming into the model and is incorporated with smaller updates\n",
        "\n",
        "Single Agent: only one agent is involved in an environment and operating by itself \n",
        "Multi Agent: multiple agents are operating in an environment\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n",
        "\n"
      ],
      "execution_count": 17,
      "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": 626
        },
        "outputId": "bbb98cfa-c80f-4350-a18d-3b8275c3a7c1"
      },
      "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",
        "  (\"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": 23,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## Module 1 Lecture Notes\n Agent: anything that perceives its environment through sensors and acts on its environment through actuators \nRational agent: behaves rationally \nWe define a performance measure to test whether an agent acts rationally \n\nPercept: agent’s perceptual inputs at any given instance\n\nAgent function: maps a sequence of percept vectors P to an action a from a set A\n\nFor each possible percept sequence P • a rational agent selects an action a • to maximize its performance measure\n\nTask environment: a problem specification for which the agent is a solution \nTo specify a task environment: \nP - performance measure\nE - environment\nA - actuators\nS - sensors\n\nWhen is something an agent vs a part of the environment: \nWhen something’s behavior can be described as having its own performance measure \n\nFully observable: has access to all required information to complete target task (chess) \nPartially observable: partial information in order to solve AI problems (self driving → don’t know what’s around the corner) \n\nDeterministic: always give the same outcome given the same input\nNondeterministic: may give different outcomes for the same input\nStochastic: uncertainty associated with the outcome\n\nEpisodic: environment where each state is independent of each other\nSequential: environment where the next state is dependent on the current action\n\nStatic: model trained once on data offline to be used for an extended period\nDynamic: new data is continuously coming into the model and is incorporated with smaller updates\n\nSingle Agent: only one agent is involved in an environment and operating by itself \nMulti Agent: multiple agents are operating in an environment\n \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "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 = \"\"\" \n",
        "Reflex Agent:  selects an action based only on the current percept → ignores rest of percept history\n",
        "Problem solving agent: plans ahead (process is called search) → considers a sequence of actions to form a path to a goal state \n",
        "\n",
        "Transition Model: description of what each action does \n",
        "A successor is any state reachable from a given state by applying a single action \n",
        "State space: set of all states reachable from the initial state by a sequence of actions \n",
        "Path: a sequence of actions leading from one state to another \n",
        "Solution: a path from initial state to final state that satisfies the goal \n",
        "Optimal solution: if no solution has a lower path cost \n",
        "Search tree: represents the path that a search algorithm has explored \n",
        "root = initial state \n",
        "Leaves = successor states \n",
        "Frontier: states that are available for expanding → NEXT NODES IN LINE \n",
        "\n",
        "Basic search algorithms: \n",
        "Tree Search: enumerate in some order all possible paths from initial state \n",
        "Search through explicit tree generation \n",
        "Nodes in search tree are generated through transition model \n",
        "Tree search treats different paths to the same node as distinct \n",
        "\n",
        "STEPS TO TREE SEARCH \n",
        "Initialize frontier to the initial state of the problem \n",
        "Do \n",
        "If the frontier is empty → return failure \n",
        "Else → choose leaf node for expansion according to strategy & remove from frontier \n",
        "If node is goal state → return solution \n",
        "Else → expand the node and add resulting nodes to the frontier \n",
        "\n",
        "Node vs state \n",
        "\n",
        "State → represents physical configuration (DO NOT HAVE parents, children, depth, path cost) \n",
        "Node → data structure constituting part of search tree (includes state, parent node, children, action, path cost, depth) \n",
        "\n",
        "How to fix repeated search → USE GRAPH SEARCH \n",
        "Check to see if a node has been added before adding to a search queue (maintain an explored set) \n",
        "\n",
        "Uninformed search strategies: only uses information available in problem definition \n",
        "All non goal nodes in the frontier look equally good \n",
        "Informed search (HEURISTIC SEARCH STRATEGIES) \n",
        "Some non goal nodes can be ranked above others \n",
        "\n",
        "Search strategies: details the order of tree expansion (implemented by different queue structures -- LIFO, FIFO, priority) \n",
        "\n",
        "How to evaluate search strategies: \n",
        "Completeness: does it always find the solution, if a solution exists? \n",
        "Optimality: finds the lowest path cost \n",
        "Time complexity: # of nodes generated in the worst case \n",
        "Space complexity: # of nodes simultaneously in memory in the worst case \n",
        "\n",
        "What affects time, space complexity \n",
        "B → maximum branching factor (branching factor = # of successors generated by a given node)\n",
        "D → depth of the shallowest goal node → easiest goal node to reach \n",
        "M → maximum length of any path in the state space \n",
        "\n",
        "BFS: expand shallowest unexpanded node \n",
        "Implementation: frontier is FIFO \n",
        "\n",
        "Properties BFS: \n",
        "Complete: Yes, if b is finite \n",
        "Optimal: Yes, if all step costs are the same (WHY: the shallowest goal node need not necessarily be the optimal goal node) \n",
        "Time complexity: b + b^2 + b+3 + … + b^d = O(b^d) \n",
        "Space complexity: b + b^2 + b^3 + … + b^d = O(b^d) → all states must be remembered to avoid redundant paths\n",
        "\n",
        "Depth first search: expand deepest unexpanded node \n",
        "Implementation: LIFO (Last in First out) \n",
        "Properties of DFS: \n",
        "Complete: fails on infinite depth spaces or spaces with loops\n",
        "Optimal: No \n",
        "Time: O(b^m) where b = branching factor and m = maximum depth of search tree \n",
        "Space: O(bm) → only need to store the nodes which are present in the path from root to current node \n",
        "\n",
        "When to use DFS vs BFS \n",
        "Use dfs: \n",
        "When space is restricted \n",
        "There are many possible solutions with long paths and wrong paths are terminated quickly \n",
        "Search can be fine-tuned quickly \n",
        "Use bfs: \n",
        "Possible infinite paths \n",
        "Some solutions have short paths \n",
        "Can quickly discard unlikely paths \n",
        "\n",
        "BFS is complete, optimal, but uses a lot of space. DFS is NOT complete, NOT optimal but uses linear space \n",
        "\n",
        "TO GET THE BEST OF BOTH WORLDS → depth limited search \n",
        "Do DFS but with depth limit l → nodes at depth l have no successors \n",
        "If l = d → optimal (d = depth of the least cost solution) \n",
        "If l < d then incomplete \n",
        "If l > d then not optimal \n",
        "Properties of depth limited search \n",
        "Time complexity: O(b^l) \n",
        "Space complexity: O(bl) \n",
        "\n",
        "How to find best depth limit: use iterative deepening search → use depth limitations search with an increasing limit \n",
        "\n",
        "ITERATIVE DEEPENING IS ALWAYS COMPLETE & OPTIMAL \n",
        "\n",
        "Iterative deepening Properties \n",
        "Complete: YES\n",
        "Time complexity: O(b^d)\n",
        "Space complexity: O(bd) \n",
        "Optimal: YES \n",
        "\n",
        "Uniform cost search: tree search algorithm used for traversing or searching weight tree \n",
        "CORE IDEA: expand node with lowest path cost \n",
        "Implementation: frontier is a priority queue ordered by g(n) to prioritize which paths to explore (based on path cost NO HEURISTIC) \n",
        "Uninformed search → It expands the least cost node and does so in every direction \n",
        "\n",
        "*** IN BFS, we first check if a node is in the goal state before adding to the frontier. \n",
        "*** IN UCS, we check if a node is in the goal state when it is selected for expansion (always enques a node to the frontier before checking whether it is a goal) \n",
        "g(N): the path cost function \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",
        "}\n",
        "\n"
      ],
      "execution_count": 18,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "32a9dac2-5380-4429-b2d7-b92da7c7148c"
      },
      "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": 19,
      "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 \nReflex Agent:  selects an action based only on the current percept → ignores rest of percept history\nProblem solving agent: plans ahead (process is called search) → considers a sequence of actions to form a path to a goal state \n\nTransition Model: description of what each action does \nA successor is any state reachable from a given state by applying a single action \nState space: set of all states reachable from the initial state by a sequence of actions \nPath: a sequence of actions leading from one state to another \nSolution: a path from initial state to final state that satisfies the goal \nOptimal solution: if no solution has a lower path cost \nSearch tree: represents the path that a search algorithm has explored \nroot = initial state \nLeaves = successor states \nFrontier: states that are available for expanding → NEXT NODES IN LINE \n\nBasic search algorithms: \nTree Search: enumerate in some order all possible paths from initial state \nSearch through explicit tree generation \nNodes in search tree are generated through transition model \nTree search treats different paths to the same node as distinct \n\nSTEPS TO TREE SEARCH \nInitialize frontier to the initial state of the problem \nDo \nIf the frontier is empty → return failure \nElse → choose leaf node for expansion according to strategy & remove from frontier \nIf node is goal state → return solution \nElse → expand the node and add resulting nodes to the frontier \n\nNode vs state \n\nState → represents physical configuration (DO NOT HAVE parents, children, depth, path cost) \nNode → data structure constituting part of search tree (includes state, parent node, children, action, path cost, depth) \n\nHow to fix repeated search → USE GRAPH SEARCH \nCheck to see if a node has been added before adding to a search queue (maintain an explored set) \n\nUninformed search strategies: only uses information available in problem definition \nAll non goal nodes in the frontier look equally good \nInformed search (HEURISTIC SEARCH STRATEGIES) \nSome non goal nodes can be ranked above others \n\nSearch strategies: details the order of tree expansion (implemented by different queue structures -- LIFO, FIFO, priority) \n\nHow to evaluate search strategies: \nCompleteness: does it always find the solution, if a solution exists? \nOptimality: finds the lowest path cost \nTime complexity: # of nodes generated in the worst case \nSpace complexity: # of nodes simultaneously in memory in the worst case \n\nWhat affects time, space complexity \nB → maximum branching factor (branching factor = # of successors generated by a given node)\nD → depth of the shallowest goal node → easiest goal node to reach \nM → maximum length of any path in the state space \n\nBFS: expand shallowest unexpanded node \nImplementation: frontier is FIFO \n\nProperties BFS: \nComplete: Yes, if b is finite \nOptimal: Yes, if all step costs are the same (WHY: the shallowest goal node need not necessarily be the optimal goal node) \nTime complexity: b + b^2 + b+3 + … + b^d = O(b^d) \nSpace complexity: b + b^2 + b^3 + … + b^d = O(b^d) → all states must be remembered to avoid redundant paths\n\nDepth first search: expand deepest unexpanded node \nImplementation: LIFO (Last in First out) \nProperties of DFS: \nComplete: fails on infinite depth spaces or spaces with loops\nOptimal: No \nTime: O(b^m) where b = branching factor and m = maximum depth of search tree \nSpace: O(bm) → only need to store the nodes which are present in the path from root to current node \n\nWhen to use DFS vs BFS \nUse dfs: \nWhen space is restricted \nThere are many possible solutions with long paths and wrong paths are terminated quickly \nSearch can be fine-tuned quickly \nUse bfs: \nPossible infinite paths \nSome solutions have short paths \nCan quickly discard unlikely paths \n\nBFS is complete, optimal, but uses a lot of space. DFS is NOT complete, NOT optimal but uses linear space \n\nTO GET THE BEST OF BOTH WORLDS → depth limited search \nDo DFS but with depth limit l → nodes at depth l have no successors \nIf l = d → optimal (d = depth of the least cost solution) \nIf l < d then incomplete \nIf l > d then not optimal \nProperties of depth limited search \nTime complexity: O(b^l) \nSpace complexity: O(bl) \n\nHow to find best depth limit: use iterative deepening search → use depth limitations search with an increasing limit \n\nITERATIVE DEEPENING IS ALWAYS COMPLETE & OPTIMAL \n\nIterative deepening Properties \nComplete: YES\nTime complexity: O(b^d)\nSpace complexity: O(bd) \nOptimal: YES \n\nUniform cost search: tree search algorithm used for traversing or searching weight tree \nCORE IDEA: expand node with lowest path cost \nImplementation: frontier is a priority queue ordered by g(n) to prioritize which paths to explore (based on path cost NO HEURISTIC) \nUninformed search → It expands the least cost node and does so in every direction \n\n*** IN BFS, we first check if a node is in the goal state before adding to the frontier. \n*** IN UCS, we check if a node is in the goal state when it is selected for expansion (always enques a node to the frontier before checking whether it is a goal) \ng(N): the path cost function \n\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "Best first search (informed search): node selected for expansion based on evaluation function f(n) \n",
        "f(n) is estimate of distance to goal \n",
        "Special cases: greedy search, A* search \n",
        "\n",
        "Heuristic functions: rule of thumb, simplification, educated guess that reduces or limits the search for solutions in domains that are poorly understood \n",
        "\n",
        "Greedy Best First Search: form of best first search \n",
        "Evaluation function is f(n) = h(n) \n",
        "First expands the node whose estimated distance to the goal is the smallest → DOES NOT USE PAST KNOWLEDGE \n",
        "HENCE, NOT complete → there is risk to take a path that does not bring you to the goal \n",
        "All nodes on frontier are kept in memory → nodes that are already expanded are not started in memory (SPACE COMPLEXITY: proportional to # of nodes on frontier and length of found path) \n",
        "NOT OPTIMAL, path found may not be optimal \n",
        "TIME Complexity: O(b^m) where b is maximum branching factor, m is max depth \n",
        "A* Algorithm: best known form of best first search \n",
        "Key idea: avoid expanding paths that are already expensive, but expand most promising first \n",
        "Heuristics: f(n) = g(n) + h(n) \n",
        "g(n) = actual cost so far to reach the node \n",
        "h(n) = estimated cost to get from node to goal \n",
        "f(n) = estimated total cost of path through n to goal  \n",
        "ALGORITHM DOESN’T END UNTIL WE “EXPAND” THE GOAL NODE → goal node must be at the top of the frontier queue (Meaning it is lowest cost) → keep expanding lowest cost node (as on pq) until goal node is on top of queue\n",
        "\n",
        "Admissible heuristic: if it never overestimates cost to reach goal (optimistic) \n",
        "If h(n) is admissible, A* using tree search is optimal \n",
        "\n",
        "Relaxed problems: problem with fewer restrictions on the actions than the original \n",
        "Cost of an optimal solution to a relaxed problem is an admissible heuristic to the original problem\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 20,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 654
        },
        "cellView": "form",
        "outputId": "1fdf2d9b-12b5-4cb7-cfb0-d7d940c09a79"
      },
      "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": 21,
      "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 \nBest first search (informed search): node selected for expansion based on evaluation function f(n) \nf(n) is estimate of distance to goal \nSpecial cases: greedy search, A* search \n\nHeuristic functions: rule of thumb, simplification, educated guess that reduces or limits the search for solutions in domains that are poorly understood \n\nGreedy Best First Search: form of best first search \nEvaluation function is f(n) = h(n) \nFirst expands the node whose estimated distance to the goal is the smallest → DOES NOT USE PAST KNOWLEDGE \nHENCE, NOT complete → there is risk to take a path that does not bring you to the goal \nAll nodes on frontier are kept in memory → nodes that are already expanded are not started in memory (SPACE COMPLEXITY: proportional to # of nodes on frontier and length of found path) \nNOT OPTIMAL, path found may not be optimal \nTIME Complexity: O(b^m) where b is maximum branching factor, m is max depth \nA* Algorithm: best known form of best first search \nKey idea: avoid expanding paths that are already expensive, but expand most promising first \nHeuristics: f(n) = g(n) + h(n) \ng(n) = actual cost so far to reach the node \nh(n) = estimated cost to get from node to goal \nf(n) = estimated total cost of path through n to goal  \nALGORITHM DOESN’T END UNTIL WE “EXPAND” THE GOAL NODE → goal node must be at the top of the frontier queue (Meaning it is lowest cost) → keep expanding lowest cost node (as on pq) until goal node is on top of queue\n\nAdmissible heuristic: if it never overestimates cost to reach goal (optimistic) \nIf h(n) is admissible, A* using tree search is optimal \n\nRelaxed problems: problem with fewer restrictions on the actions than the original \nCost of an optimal solution to a relaxed problem is an admissible heuristic to the original problem\n \n\n## Module 4 Definitions\n* **Concept** - definition\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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "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",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "A constraint satisfaction problem consists of three components, X, D, and C : \n",
        "\\n \\t X is a set of variables, {X1,...,Xn}.\n",
        "\\n \\t D is a set of domains, {D1, . . . , Dn}, one for each variable.\n",
        "\\n \\t C is a set of constraints that specify allowable combinations of values. \n",
        "\n",
        "\\n \\n Solutions to CSPs can be found by a completely general\n",
        "purpose algorithm, given only the formal specification of\n",
        "the CSP.\n",
        "\n",
        "\\n Benefits of CSP: \n",
        "\\n \\t Clean specification of many problems, generic goal, successor function & heuristics\n",
        "\\n \\t CSP “knows” which variables violate a constraint and hence where to focus the search\n",
        "\\n \\t CSPs: Automatically prune off all branches that violate constraints\n",
        "\n",
        "\\n CSP Representation on graph:\n",
        "\\n \\t nodes are variables \n",
        "\\n \\t arcs are binary constraints \n",
        "\n",
        "\\n Varietes of CSPs: \n",
        "\\n \\t Discrete Variables: n variables with domain size d --> O(d^n) complete assignments\n",
        "\\n \\t Continous Variables: linear constraints solvable in polynomial time by linear programming\n",
        "\n",
        "\\n A CSP is expressed as a search problem: \n",
        "\\n \\t Initial State: the empty assignment {}\n",
        "\\n \\t Successor Function: Assign value to any unassigned variable provided no constraint conflict\n",
        "\\n \\t Goal Test: current assignment is complete \n",
        "\\n \\t Path cost: a constant cost for every step\n",
        "\n",
        "\\n Search & Branching Factor \n",
        "\\n \\t n variables of domain size d \n",
        "\\n \\t Branching factor at the root is n*d \n",
        "\\n \\t Branching factor at next level is (n-1)*d\n",
        "\\n \\t Tree has n!*d^n leaves\n",
        "\n",
        "\\n CSP = tree search\n",
        "\n",
        "\\n Backtracking search: used for DFS  that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign (basic uninformed algorithm for CSPs)\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"consistent assignment\" : \"assignment that does not violate any constraints\",\n",
        "\"complete assignment\" : \" every variable is assigned, and a solution to a CSP is a consistent, complete assignment\", \n",
        "\"partial assignment\" : \"assigns values to only some of the variables\", \n",
        "\"binary CSP\" : \"each constraint relates two variables\", \n",
        "\"higher-order constraints: constraints involved 3+ variables\",\n",
        "\"Backtracking search\" : \"Depth-first search for CSPs with single-variable assignments\"   \n",
        "}\n"
      ],
      "execution_count": 42,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 494
        },
        "outputId": "351413f9-d748-4291-ba24-872cb31be943"
      },
      "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",
        "  (\"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": 43,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## Module 6 Lecture Notes\n \nA constraint satisfaction problem consists of three components, X, D, and C : \n\n \t X is a set of variables, {X1,...,Xn}.\n\n \t D is a set of domains, {D1, . . . , Dn}, one for each variable.\n\n \t C is a set of constraints that specify allowable combinations of values. \n\n\n \n Solutions to CSPs can be found by a completely general\npurpose algorithm, given only the formal specification of\nthe CSP.\n\n\n Benefits of CSP: \n\n \t Clean specification of many problems, generic goal, successor function & heuristics\n\n \t CSP “knows” which variables violate a constraint and hence where to focus the search\n\n \t CSPs: Automatically prune off all branches that violate constraints\n\n\n CSP Representation: \n\n## Module 6 Definitions\n* **Consistent assignment** - assignment that does not violate any constraints\n* **Complete assignment** -  every variable is assigned, and a solution to a CSP is a consistent, complete assignment\n* **Partial assignment** - assigns values to only some of the variables\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 = \"\"\" When to use KBA over rational agent: To create an agent that is not purely reactionary and that maintains an internal state of knowledge, reasons over that knowledge, and updates its knowledge as it makes observations and takes actions \n",
        "                  \\n How KBA works: Each time the agent program is called, it does three things. First, it TELLs the KB what it perceives. Second, it ASKs the KB what action it should perform. In the process of answering this query, extensive reasoning may be done about the current state of the world, about the outcomes of possible action sequences, and so on. Third, the agent program TELLs the KB which action was chosen, and the agent executes the action.\n",
        "                  \\n alpha could be a sentence that means “there is no pit in [2,2]”. In that case, M(alpha) would be all instances of Wampa World where [2,2] doesn’t have a pit.\n",
        "                  \\n WE ONLY NEED TO SPECIFY what the agent knows and what its goals are --> decision is independent of how agent works on the implementation level\"\"\"\n",
        "chapter7_2 = \"\"\" Fundamental Property of logical reasoning: conclusion is guaranteed to be correct if the available information is correct \"\"\"\n",
        "chapter7_3 = \"\"\" Difference between Possible World & Model: Informally, we may think of a possible world as, for example, having x men and y women sitting at a table playing bridge, and the sentence x + y = 4 is true when there are four people in total. Formally, the possible models are just all possible assignments of real numbers to the variables x and y. Each such assignment fixes the truth of any sentence of arithmetic whose variables are x and y. \n",
        "                 \\n If a sentence α is true in model m, we say that m satisfies α or sometimes m is a model of α. \n",
        "                 \\n α represents some assignement --> in the above example, α could be 2 men and 2 women which satisfies the model\n",
        "                 \\n LOGICAL ENTAILMENT: (NOTE) If α enatils β, then α is a stronger assertion than β, meaning α rules out more possible worlds\n",
        "                 \\n We have described a reasoning process whose conclusions are guaranteed to be true in any world in which the premises are true; in particular, if KB is true in the real world, then any sentence α derived from KB by a sound inference procedure is also true in the real world. \n",
        "                 \\n how do we know that KB is true in the real world: the agent’s sensors create the connection. For example, our wumpus-world agent has a smell sensor. The agent program creates a suitable sentence whenever there is a smell. Then, whenever that sentence is in the knowledge base, it is true in the real world. Thus, the meaning and truth of percept sentences are defined by the processes of sensing and sentence construction that produce them. \"\"\"\n",
        "chapter7_4 = \"\"\" Syntax: defines the allowable sentences\n",
        "                  \\n Types of logical connectivities: \n",
        "                  \\n ¬ (not). A sentence such as ¬W1,3 is called the negation of W1,3. A literal is either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal)\n",
        "                  \\n ∧ (and). A sentence whose main connective is ∧, such as W1,3 ∧ P3,1, is called a con- junction; its parts are the conjuncts\n",
        "                  \\n ∨ (or). A sentence using ∨, such as (W1,3 ∧P3,1)∨W2,2, is a disjunction of the disjuncts (W1,3 ∧ P3,1) and W2,2\n",
        "                  \\n ⇒ (implies). A sentence such as (W1,3 ∧P3,1) ⇒ ¬W2,2 is called an implication (or con- ditional). Its premise or antecedent is (W1,3 ∧P3,1), and its conclusion or consequent is ¬W2,2. Implications are also known as rules or if–then statements\n",
        "                  \\n ⇔ (if and only if). The sentence W1,3 ⇔ ¬W2,2 is a biconditional\n",
        "                  \\n (xor) XOR represents the inequality function, i.e., the output is true if the inputs are not alike otherwise the output is false.\n",
        "                  \\n\n",
        "                  \\n\n",
        "                  Operator Precedence: ¬,∧,∨,⇒,⇔ \n",
        "                  \\n \n",
        "                  \\n Semantics: defines the rules for determining the truth of a sentence with respect to a particular model\n",
        "                  \\n\n",
        "                  \\n The semantics for propositional logic must specify how to compute the truth value of any sentence, given a model. This is done recursively. All sentences are constructed from atomic sentences and the five connectives; therefore, we need to specify how to compute the truth of atomic sentences and how to compute the truth of sentences formed with each of the five connectives. \n",
        "                  \\n For complex sentences --> we have five rules: \n",
        "                  \\n \n",
        "                  \\n ¬P is true iff P is false in m\n",
        "                  \\n P ∧ Q is true iff both P and Q are true in m\n",
        "                  \\n P ∨ Q is true iff either P or Q is true in m\n",
        "                  \\n P ⇒ Q is true unless P is true and Q is false in m\n",
        "                  \\n P ⇔ Q is true iff P and Q are both true or both false in m.\n",
        "                  \\n \n",
        "                  \\n Explanation of implication: propositional logic does not require any relation of causation or relevance between P and Q. The sentence “5 is odd implies Tokyo is the capital of Japan” is a true sentence of propositional logic. any implication is true whenever its antecedent is false. For example, “5 is even implies Sam is smart” is true, regardless of whether Sam is smart which makes sense if you think of “P ⇒ Q” as saying, “If P is true, then I am claiming that Q is true. Otherwise I am making no claim.” The only way for this sentence to be false is if P is true but Q is false.\"\"\"\n",
        "chapter7_5 = \"\"\" To decide if α |= β --> check that (α ⇒ β) is true in every model (inference algorithm) or by proving that (α ⇒ β) is equivalent to True \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\", \n",
        "\"Knowledge base\" : \"organized set of knowledge (sentences) about a particular subject that contains facts and judgmental knowledge\",\n",
        "\"Sentence\" : \"expressed in a language called a knowledge representation language and represents some assertion about the world\",\n",
        "\"Inference Engine\" : \"set of rules on which to make decisions (reasoning by manipulating knowledge base)\",  \n",
        "\"Tell\" : \"writing knowledge to KB\",\n",
        "\"Ask\" : \"Query what is in KB\",\n",
        "\"Background knowledge\" : \"Knowledge already contained in KB\", \n",
        "\"MAKE-PERCEPT-SENTENCE\" : \"constructs a sentence asserting that the agent perceived the given percept at the given time\", \n",
        "\"MAKE-ACTION-QUERY\" : \"constructs a sentence that asks what action should be done at the current time\", \n",
        "\"MAKE-ACTION-SENTENCE\" : \"constructs a sentence asserting that the chosen action was executed\", \n",
        "\"Declarative approach to system building\" : \"agent designer can TELL sentences one by one until the agent knows how to operate in its environment\", \n",
        "\"procedural approach\" : \"encodes desired behaviors directly as program code\", \n",
        "\"Syntax of a sentence\" : \"specifies all the sentences that are well formed --> ordinary arthimetic works fine\", \n",
        "\"Semantics of a sentence\" : \"truth of each sentence with respect to each possible world --> must be either True or False\", \n",
        "\"Possible World\" : \"(potentially) real environments that the agent might or might not be in\", \n",
        "\"Model\" : \"mathematical abstractions, each of which simply fixes the truth or falsehood of every relevant sentence\", \n",
        "\"Logical entailment in words\" : \"the idea that a sentence fol- lows logically from another sentence\",\n",
        "\"Logical entailment between sentences formula\" : \"α |= β if and only if, in every model in which α is true, β is also true\",\n",
        "\"Model checking\" : \"algorithm that enumerates all possible models to check that α is true in all models in which KB is true, that is, that M(KB) ⊆ M(α)\", \n",
        "\"Logical inference (in math)\" : \"if an inference algorithm i can derive α from KB, we write KB ⊢i α\", \n",
        "\"Logical inference (in words)\" : \"α is derived from KB by i or i derives α from KB\", \n",
        "\"Sound/Truth Preserving\" : \"An inference algorithm that derives only entailed sentences\", \n",
        "\"Completeness\" : \"an inference algorithm is complete if it can derive any sentence that is entailed\", \n",
        "\"Grounding\" : \"connection between logical reasoning processes and the real environment in which the agent exists\",\n",
        "\"Grounding in practical terms\" : \" how do we know that KB is true in the real world?\",\n",
        "\"Learning\" : \"General rules (ex: wumpuses cause smells)\", \n",
        "\"Propositional Logic\" : \"simplest form of logic where all the statements are made by propositions\", \n",
        "\"Atomic Sentence\" : \"declarative sentence which is either T/F and which cannot be broken down into other simpler sentences\", \n",
        "\"Complex Sentences\" : \"constructed from simpler sentences, using parentheses and logical connectives\", \n",
        "\"Literal\" : \"an assignment of a value to a Boolean variable\", \n",
        "\"BNF Grammar\" : \"context-free grammar commonly used by developers of programming languages to specify the syntax rules of a language\", \n",
        "\"theorem proving\" : \"applying rules of inference directly to the sentences in our knowledge base to construct a proof of the desired sentence without consulting models\",\n",
        "\"logical equivalence\" : \"two sen- tences α and β are logically equivalent if they are true in the same set of models\", \n",
        "\"logical equivalence\" : \"any two sentences α and β are equivalent only if each of them entails the other\",\n",
        "\"valid sentences/tautology\" : \"A sentence is valid if it is true in all models\", \n",
        "\"deduction theorem\" : \"For any sentences α and β, α |= β if and only if the sentence (α ⇒ β) is valid.\",\n",
        "\"satisfiability\" : \"A sentence is satisfiable if it is true in, or satisfied by, some model\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 24,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "d55db9cf-236a-48b5-d223-de84885e3c40"
      },
      "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": 25,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your summary of 'AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic' is too long!\n## WARNING: Your definition of 'Model checking' is too long!\nWARNING: Your definition of 'theorem proving' is too long!\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n When to use KBA over rational agent: To create an agent that is not purely reactionary and that maintains an internal state of knowledge, reasons over that knowledge, and updates its knowledge as it makes observations and takes actions \n                  \n How KBA works: Each time the agent program is called, it does three things. First, it TELLs the KB what it perceives. Second, it ASKs the KB what action it should perform. In the process of answering this query, extensive reasoning may be done about the current state of the world, about the outcomes of possible action sequences, and so on. Third, the agent program TELLs the KB which action was chosen, and the agent executes the action.\n                  \n alpha could be a sentence that means “there is no pit in [2,2]”. In that case, M(alpha) would be all instances of Wampa World where [2,2] doesn’t have a pit.\n                  \n WE ONLY NEED TO SPECIFY what the agent knows and what its goals are --> decision is independent of how agent works on the implementation level\n\n## AIMA Chapter 7.2 The Wumpus World\n Fundamental Property of logical reasoning: conclusion is guaranteed to be correct if the available information is correct \n\n## AIMA Chapter 7.3 Logic\n Difference between Possible World & Model: Informally, we may think of a possible world as, for example, having x men and y women sitting at a table playing bridge, and the sentence x + y = 4 is true when there are four people in total. Formally, the possible models are just all possible assignments of real numbers to the variables x and y. Each such assignment fixes the truth of any sentence of arithmetic whose variables are x and y. \n                 \n If a sentence α is true in model m, we say that m satisfies α or sometimes m is a model of α. \n                 \n α represents some assignement --> in the above example, α could be 2 men and 2 women which satisfies the model\n                 \n LOGICAL ENTAILMENT: (NOTE) If α enatils β, then α is a stronger assertion than β, meaning α rules out more possible worlds\n                 \n We have described a reasoning process whose conclusions are guaranteed to be true in any world in which the premises are true; in particular, if KB is true in the real world, then any sentence α derived from KB by a sound inference procedure is also true in the real world. \n                 \n how do we know that KB is true in the real world: the agent’s sensors create the connection. For example, our wumpus-world agent has a smell sensor. The agent program creates a suitable sentence whenever there is a smell. Then, whenever that sentence is in the knowledge base, it is true in the real world. Thus, the meaning and truth of percept sentences are defined by the processes of sensing and sentence construction that produce them. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Syntax: defines the allowable sentences\n                  \n Types of logical connectivities: \n                  \n ¬ (not). A sentence such as ¬W1,3 is called the negation of W1,3. A literal is either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal)\n                  \n ∧ (and). A sentence whose main connective is ∧, such as W1,3 ∧ P3,1, is called a con- junction; its parts are the conjuncts\n                  \n ∨ (or). A sentence using ∨, such as (W1,3 ∧P3,1)∨W2,2, is a disjunction of the disjuncts (W1,3 ∧ P3,1) and W2,2\n                  \n ⇒ (implies). A sentence such as (W1,3 ∧P3,1) ⇒ ¬W2,2 is called an implication (or con- ditional). Its premise or antecedent is (W1,3 ∧P3,1), and its conclusion or consequent is ¬W2,2. Implications are also known as rules or if–then statements\n                  \n ⇔ (if and only if). The sentence W1,3 ⇔ ¬W2,2 is a biconditional\n                  \n (xor) XOR represents the inequality function, i.e., the output is true if the inputs are not alike otherwise the output is false.\n                  \n\n                  \n\n                  Operator Precedence: ¬,∧,∨,⇒,⇔ \n                  \n \n                  \n Semantics: defines the rules for determining the truth of a sentence with respect to a particular model\n                  \n\n                  \n The semantics for propositional logic must specify how to compute the truth value of any sentence, given a model. This is done recursively. All sentences are constructed from atomic sentences and the five connectives; therefore, we need to specify how to compute the truth of atomic sentences and how to compute the truth of sentences formed with each of the five connectives. \n                  \n For complex sentences --> we have five rules: \n                  \n \n                  \n ¬P is true iff P is false in m\n                  \n P ∧ Q is true iff both P and Q are true in m\n                  \n P ∨ Q is true iff either P or Q is true in m\n                  \n P ⇒ Q is true unless P is true and Q is false in m\n                  \n P ⇔ Q is true iff P and Q are both true or both false in m.\n                  \n \n                  \n Explanation of implication: propositional logic does not require any relation of causation or relevance between P and Q. The sentence “5 is odd implies Tokyo is the capital of Japan” is a true sentence of propositional logic. any implication is true whenever its antecedent is false. For example, “5 is even implies Sam is smart” is true, regardless of whether Sam is smart which makes sense if you think of “P ⇒ Q” as saying, “If P is true, then I am claiming that Q is true. Otherwise I am making no claim.” The only way for this sentence to be false is if P is true but Q is false.\n\n## AIMA 7.5 Propositional Theorem Proving\n To decide if α |= β --> check that (α ⇒ β) is true in every model (inference algorithm) or by proving that (α ⇒ β) is equivalent to True \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n* **Knowledge base** - organized set of knowledge (sentences) about a particular subject that contains facts and judgmental knowledge\n* **Sentence** - expressed in a language called a knowledge representation language and represents some assertion about the world\n* **Inference engine** - set of rules on which to make decisions (reasoning by manipulating knowledge base)\n* **Tell** - writing knowledge to KB\n* **Ask** - Query what is in KB\n* **Background knowledge** - Knowledge already contained in KB\n* **Make-percept-sentence** - constructs a sentence asserting that the agent perceived the given percept at the given time\n* **Make-action-query** - constructs a sentence that asks what action should be done at the current time\n* **Make-action-sentence** - constructs a sentence asserting that the chosen action was executed\n* **Declarative approach to system building** - agent designer can TELL sentences one by one until the agent knows how to operate in its environment\n* **Procedural approach** - encodes desired behaviors directly as program code\n* **Syntax of a sentence** - specifies all the sentences that are well formed --> ordinary arthimetic works fine\n* **Semantics of a sentence** - truth of each sentence with respect to each possible world --> must be either True or False\n* **Possible world** - (potentially) real environments that the agent might or might not be in\n* **Model** - mathematical abstractions, each of which simply fixes the truth or falsehood of every relevant sentence\n* **Logical entailment in words** - the idea that a sentence fol- lows logically from another sentence\n* **Logical entailment between sentences formula** - α |= β if and only if, in every model in which α is true, β is also true\n* **Model checking** - algorithm that enumerates all possible models to check that α is true in all models in which KB is true, that is, that M(KB) ⊆ M(α)\n* **Logical inference (in math)** - if an inference algorithm i can derive α from KB, we write KB ⊢i α\n* **Logical inference (in words)** - α is derived from KB by i or i derives α from KB\n* **Sound/truth preserving** - An inference algorithm that derives only entailed sentences\n* **Completeness** - an inference algorithm is complete if it can derive any sentence that is entailed\n* **Grounding** - connection between logical reasoning processes and the real environment in which the agent exists\n* **Grounding in practical terms** -  how do we know that KB is true in the real world?\n* **Learning** - General rules (ex: wumpuses cause smells)\n* **Propositional logic** - simplest form of logic where all the statements are made by propositions\n* **Atomic sentence** - declarative sentence which is either T/F and which cannot be broken down into other simpler sentences\n* **Complex sentences** - constructed from simpler sentences, using parentheses and logical connectives\n* **Literal** - an assignment of a value to a Boolean variable\n* **Bnf grammar** - context-free grammar commonly used by developers of programming languages to specify the syntax rules of a language\n* **Theorem proving** - applying rules of inference directly to the sentences in our knowledge base to construct a proof of the desired sentence without consulting models\n* **Logical equivalence** - any two sentences α and β are equivalent only if each of them entails the other\n* **Valid sentences/tautology** - A sentence is valid if it is true in all models\n* **Deduction theorem** - For any sentences α and β, α |= β if and only if the sentence (α ⇒ β) is valid.\n* **Satisfiability** - A sentence is satisfiable if it is true in, or satisfied by, some model\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": {
        "id": "T3cm1WV542_a"
      },
      "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": []
    }
  ]
}