{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "brNDGX-kvzds",
        "aPtM8g7R0Pds",
        "cw5IpDLCZa4W",
        "s3Uk9gQTevcj",
        "5yG3-YncJfTB",
        "elCCgY64spuq",
        "9xRbdqDox2zD",
        "vX7lbnJd4sT5"
      ],
      "toc_visible": true
    },
    "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": "4185914b-f630-463c-9856-99e80a562e46"
      },
      "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": "3bb3d652-8b38-446e-c564-eb2be48cf6bc"
      },
      "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 = \"\"\"There are four categories of AI: thinking humanly, represented by \\\n",
        "the Turing Test approach, requires user to have ability in NLP, knowledge representation, \\\n",
        "automated reasoning and ML; thinking humnaly, resides in the realm of cognitive science; \\\n",
        "thinking rationally, the law of thought approach, related to logic; acting rationally refers \\\n",
        "to rationaly agent that acts to achieve best expected outcome.\"\"\" \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 = \"\"\"The weak AI assumption is machines can act as if there were intelligent. \\\n",
        "Objections include arguments from disability in that there are things a machine cannot do, and \\\n",
        "the mathematical objection which remains unproved. There's also argument from informality, \\\n",
        "described by Turing as rules that machine can follow cannot capture complex human behavior.\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"The strong AI assumption is machines are actually thinking. This relates to the \\\n",
        "mind-body issue that falls under two philosophical school, dualist and monist theory, characterized \\\n",
        "by whether mind and body are separate being.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"An agent uses sensors for percept (perceptual inputs) and actuators \\\n",
        "to carry out actions. \"\"\"\n",
        "chapter2_2 = \"\"\"Rationality does not equal omniscience, instead it requires agent \\\n",
        "to gather information and learn from what it perceives.\"\"\"\n",
        "chapter2_3 = \"\"\"Task environment can be described using PEAS(performance, environment, actuators, sensors). \\\n",
        "Different property of environemnt includes fully vs. partially observable, single vs. multiagent, \\\n",
        "deterministic vs. stochastic, episodic vs. sequential, discrete vs. continuous, known vs. unknown\"\"\"\n",
        "chapter2_4 = \"\"\"Types of agents: simple-reflex agent, model-based agent(agent that maintain \\\n",
        "internal state that depends on percept history and extend beyond the current observation), \\\n",
        "goal-based agent(uses search and planning), utility-based agent(based on utility function, \\\n",
        "an internalization of performance measure), learning agent.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"known environment\": \"the outcome or outcome probabilities for all actions are given.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "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": 827
        },
        "cellView": "form",
        "outputId": "b4fdd00e-bb6b-49d6-b033-ce48316f01dd"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nThere are four categories of AI: thinking humanly, represented by the Turing Test approach, requires user to have ability in NLP, knowledge representation, automated reasoning and ML; thinking humnaly, resides in the realm of cognitive science; thinking rationally, the law of thought approach, related to logic; acting rationally refers to rationaly agent that acts to achieve best expected outcome.\n\n## AIMA Chapter 27.1 The Limits of AI\nThe weak AI assumption is machines can act as if there were intelligent. Objections include arguments from disability in that there are things a machine cannot do, and the mathematical objection which remains unproved. There's also argument from informality, described by Turing as rules that machine can follow cannot capture complex human behavior.\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nThe strong AI assumption is machines are actually thinking. This relates to the mind-body issue that falls under two philosophical school, dualist and monist theory, characterized by whether mind and body are separate being.\n\n## AIMA 2.1 Agents and Environments\nAn agent uses sensors for percept (perceptual inputs) and actuators to carry out actions. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nRationality does not equal omniscience, instead it requires agent to gather information and learn from what it perceives.\n\n## AIMA 2.3 The Nature of Environments\nTask environment can be described using PEAS(performance, environment, actuators, sensors). Different property of environemnt includes fully vs. partially observable, single vs. multiagent, deterministic vs. stochastic, episodic vs. sequential, discrete vs. continuous, known vs. unknown\n\n## AIMA 2.4 The Structure of Agents\nTypes of agents: simple-reflex agent, model-based agent(agent that maintain internal state that depends on percept history and extend beyond the current observation), goal-based agent(uses search and planning), utility-based agent(based on utility function, an internalization of performance measure), learning agent.\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Known environment** - the outcome or outcome probabilities for all actions are given.\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",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "outputId": "4b6becda-5840-4dd5-a917-92a246de78f2"
      },
      "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": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"Problem-solving agent is a type of goal-based agent. A problem can be \\\n",
        "defined as follows: initial state, actions, transition model, goal state, path cost. \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\"Tree search doesn't check for visited node while graph-search does. \\\n",
        "Search algorithm can be measure using the following criteria: completeness, optimality, time and \\\n",
        "space complexity. Complexity is expressed with b(branching factor), d(depth of the shallowest goal \\\n",
        "node, m(maximum length of any path in the state space).\"\"\"\n",
        "chapter3_4 = \"\"\"Uninformed search means we only know the problem definition. **BFS** uses a \\\n",
        "FIFO queue; it's complete if the shallowest goal node is at finite depth d. BFS is optimal if \\\n",
        "the path cost is a nondecreasing function of depth (or cost = 1). Time and space complexity are both O(b^d). \\\n",
        "Uniform cost expands the node with the lowest path cost; it is optimal and complete \\\n",
        "if each step has a positive cost. **DFS** uses LIFO queue, and is usually implemented with a \\\n",
        "recursive call to itself; it is not optimal and of time complexity O(b^m), space complexity O(bm). \\\n",
        "Depth-limited search and iterative deepening DFS are variations of DFS. Bidirectional search runs two \\\n",
        "simulataneous search from intial and goal states, and of O(b^(d/2)). It checks if the frontier \\\n",
        "of two searches overlap. \n",
        "Search algorithm are typically judged by 4 criteria: time complexity, space complexity, \\\n",
        "completeness, optimality\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"**Tree search** enumerates through all possible paths in some order, \\\n",
        "and it doesn't check for visited states. **Node** differs from **States** in that it's part \\\n",
        "of the search tree and thus have parents, children, depth and path cost. **DFS** is preferred \\\n",
        "over **BFS** is space is limited; the reverse is true if there's possible inifinite 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",
        "\"search\": \"the process fo looking for a sequence of actions that reaches the goal\",\n",
        "\"leaf node\": \"node with no children\",\n",
        "\"frontier\": \"set of leaf nodes available for expansion at any given point\",\n",
        "\"completeness\": \"the algorithm is guaranteed to find a solution when there is one\",\n",
        "\"branching factor\": \"b, the maximum number of successors of any node\",\n",
        "\"optimal solution\": \"a solution is optimal if no other solution has lower path cost\"   \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 644
        },
        "outputId": "3b37b059-c939-4953-856b-b252882fd0be"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\nProblem-solving agent is a type of goal-based agent. A problem can be defined as follows: initial state, actions, transition model, goal state, path cost. \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\nTree search doesn't check for visited node while graph-search does. Search algorithm can be measure using the following criteria: completeness, optimality, time and space complexity. Complexity is expressed with b(branching factor), d(depth of the shallowest goal node, m(maximum length of any path in the state space).\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\nUninformed search means we only know the problem definition. BFS uses a FIFO queue; it's complete if the shallowest goal node is at finite depth d. BFS is optimal if the path cost is a nondecreasing function of depth. Time and space complexity are both O(b^d). Uniform cost expands the node with the lowest path cost; it is optimal and complete if each step has a positive cost. DFS uses LIFO queue, and is usually implemented with a recursive call to itself; it is not optimal and of time complexity O(b^m), space complexity O(bm). Depth-limited search and iterative deepening DFS are variations of DFS. Bidirectional search runs two simulataneous search from intial and goal states, and of O(b^(d/2)). It checks if the frontier of two searches overlap.\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Search** - the process fo looking for a sequence of actions that reaches the goal\n* **Leaf node** - node with no children\n* **Rontier** - set of leaf nodes available for expansion at any given point\n* **Completeness** - the algorithm is guaranteed to find a solution when there is one\n* **Branching factor** - b, the maximum number of successors of any node\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**. **Greedy best-first search** evaluates nodes based on \\\n",
        "only heuristic function; it's neither optimal nor complete. **A\\* search** uses the sum of path cost \\\n",
        "and heuristic function; it's both complete and optimal given admissable and complete (in graph serach) h(n). \\\n",
        "This is identical to uniform-cost-search by substituing the cost function. Since A\\* search keeps all generated \\\n",
        "node in memory, it runs out of memory easily. There are several **memory-bounded heuristic search**: \n",
        "1. ierative-deepening A\\*\n",
        "2. recursive best-first search (RBFS): similar to recursive DFS, except it keeps track of the lowest cost \\\n",
        "to the current node and terminates if the value is exceeded. It's optimal if h(n) is admissable.\n",
        "3. Memoery-bounded A\\* (MA\\*), simplifed MA\\*\"\"\"\n",
        "chapter3_6 = \"\"\"One heuristic funcion dominates another when A\\* will never expand more node \\\n",
        "using the former function than using the latter. Quality of heuristic function can be \\\n",
        "measured by **effective branching factor** b\\*. The closer b\\* is to 1, the better designed \\\n",
        "is the heutistic. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"**Uniform search** assumes all moves are equal in cost, and \\\n",
        "it expands node with lowest path cost. It tests if a state is goals state when it's \\\n",
        "selected for expansion, as opposed to when it's added to frontier like BFS. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"best-first search\": \"instance of tree-search or graph-search where the best node \\\n",
        "is selected for expansion based on some evaluation function, f(n)\",\n",
        "\"heuristic function\": \"estimated cost of the cheapest path from the state at node n to a goal state\",\n",
        "\"admissable heuristic\": \"heuristic function that never overestimates the cost to reach goal\",\n",
        "\"consistent heuristic\": \"$h(n) \\leq c(n, a, n') + h(n')$, where n' denotes successor of n\",\n",
        "\"Manhattan distance\": \"sum of distances of tiles from their goal positions\"    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 529
        },
        "cellView": "form",
        "outputId": "992a744a-d7d4-46cc-930e-e39b9ff6cc8b"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n**Informed search**. **Greedy best-first search** evaluates nodes based on only heuristic function; it's neither optimal nor complete. **A\\* search** uses the sum of path cost and heuristic function; it's both complete and optimal given admissable and complete (in graph serach) h(n). This is identical to uniform-cost-search by substituing the cost function. Since A\\* search keeps all generated node in memory, it runs out of memory easily. There are several **memory-bounded heuristic search**: \n1. ierative-deepening A\\*\n2. recursive best-first search (RBFS): similar to recursive DFS, except it keeps track of the lowest cost to the current node and terminates if the value is exceeded. It's optimal if h(n) is admissable.\n3. Memoery-bounded A\\* (MA\\*), simplifed MA\\*\n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Best-first search** - instance of tree-search or graph-search where the best node is selected for expansion based on some evaluation function, f(n)\n* **Heuristic function** - estimated cost of the cheapest path from the state at node n to a goal state\n* **Admissable heuristic** - heuristic function that never overestimates the cost to reach goal\n* **Consistent heuristic** - $h(n) \\leq c(n, a, n') + h(n')$, where n' denotes successor of n\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"Games, or adversarial searches are multiagent. Game tree is defined by \\\n",
        "tge initlal state, actions functions, and transitions.\"\"\"\n",
        "chapter5_2 = \"\"\"Calculating minimax value assumes both players play optimally. Minimax algorithm \\\n",
        "performs complete DFS of game tree. Time complexity is O(b^m) and space complexity is O(bm) if \\\n",
        "all actions are generated at once, or O(m) if actions generated one at a time. \"\"\"\n",
        "chapter5_3 = \"\"\"In alpha-beta pruning, alpha/beta are the best value we've found for either \\\n",
        "MAX or MIN. Branches are pruned once it's known that it's worst than alpha or beta value. \\\n",
        "Time complexity is O(b^(m/2)) if we can identify the best successor. The algorithm calls max-value \\\n",
        "and min-value function interchangeably and recursively.\"\"\"\n",
        "chapter5_5 = \"\"\"Gmaes are stochastic when randomness is introduced. Minimax value can be \\\n",
        "generalized to expecti-minimax value based on expected value, average over all possible outcomes \\\n",
        "of chance nodes. Time complexity of these games are O(b^m n^m) where n is number of random outcomes (e.g. dice roll). \\\n",
        "We can also use Monte Carlo simulation to evalaute a position, by having the algorithm play against itself \\\n",
        "using random dice rolls. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"According to MEU(maximum expected utility), rational agent should choose \\\n",
        "action that maximizes expected utility.\"\"\"\n",
        "chapter16_2 = \"\"\"Rules of preferences for rational agent: 1. orderability, agent can't avoid deciding \\\n",
        "and has to choose either prefer one or be indifferent; 2. transitivity, if A>B and B>C, then A>C; \\\n",
        "3. continuity, if A>B>C, then for some p, [p, A; 1-p, C] ~ B; 4. substitutability, A ~ B, then \\\n",
        "[p, A; 1-p, C]~[p,B; 1-p,C]; 5. monotonicity, if A>B, then agent prefers lottery with higher probability of A; \\\n",
        "6. decomposability, compound lotteries can be decomposed to simpler forms. \"\"\"\n",
        "chapter16_3 = \"\"\"Human behaviors are subject to irrationality: for example, the existence of certainty effect, \\\n",
        "ambiguity aversion, framing effect(different wordings of a factual statement could have different impacts), \\\n",
        "anchoring effect.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"back-up value\": \"optimal value of a node's children\",\n",
        "\"preference elicitation\": \"the process of working out an agent's utility function\",\n",
        "\"certainty equivalent\": \"the value an agent accepts in certainty instead of lottery\",\n",
        "\"normative theory\": \"describes how a rational agent should act\",\n",
        "\"descriptive theory\": \"describes how an agent actually acts\"    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 861
        },
        "outputId": "5fe95e45-b53e-4256-e82b-6cbe2672d73a"
      },
      "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": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nGames, or adversarial searches are multiagent. Game tree is defined by tge initlal state, actions functions, and transitions.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nCalculating minimax value assumes both players play optimally. Minimax algorithm performs complete DFS of game tree. Time complexity is O(b^m) and space complexity is O(bm) if all actions are generated at once, or O(m) if actions generated one at a time. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nIn alpha-beta pruning, alpha/beta are the best value we've found for either MAX or MIN. Branches are pruned once it's known that it's worst than alpha or beta value. Time complexity is O(b^(m/2)) if we can identify the best successor. The algorithm calls max-value and min-value function interchangeably and recursively.\n\n## AIMA Chapter 5.5 Stochastic Games\nGmaes are stochastic when randomness is introduced. Minimax value can be generalized to expecti-minimax value based on expected value, average over all possible outcomes of chance nodes. Time complexity of these games are O(b^m n^m) where n is number of random outcomes (e.g. dice roll). We can also use Monte Carlo simulation to evalaute a position, by having the algorithm play against itself using random dice rolls. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nAccording to MEU(maximum expected utility), rational agent should choose action that maximizes expected utility.\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nRules of preferences for rational agent: 1. orderability, agent can't avoid deciding and has to choose either prefer one or be indifferent; 2. transitivity, if A>B and B>C, then A>C; 3. continuity, if A>B>C, then for some p, [p, A; 1-p, C] ~ B; 4. substitutability, A ~ B, then [p, A; 1-p, C]~[p,B; 1-p,C]; 5. monotonicity, if A>B, then agent prefers lottery with higher probability of A; 6. decomposability, compound lotteries can be decomposed to simpler forms. \n\n## AIMA Chapter 16.3 Utility Functions\nHuman behaviors are subject to irrationality: for example, the existence of certainty effect, ambiguity aversion, framing effect(different wordings of a factual statement could have different impacts), anchoring effect.\n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Back-up value** - optimal value of a node's children\n* **Preference elicitation** - the process of working out an agent's utility function\n* **Certainty equivalent** - the value an agent accepts in certainty instead of lottery\n* **Normative theory** - describes how a rational agent should act\n* **Descriptive theory** - describes how an agent actually acts\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"CSP has three components, a set of variables (X), set of domains (D), \\\n",
        "each corresponding to a variable, set of constraints (C). CSP is solved by performing \\\n",
        "consistent assignment. Assignment in the end can be complete or partial. CSP can be viewed \\\n",
        "as a constraint graph. \"\"\"\n",
        "chapter6_2 = \"\"\"CSP can be solved using search or inference (constraint propagation). \\\n",
        "AC-3 is an algorithm for ensuring arc consistency.\"\"\"\n",
        "chapter6_3 = \"\"\"Sometimes we need to search for a solution. \\\n",
        "**Backtracking search** uses DFS and chooses value for one variable at a time and backtracks when there's no \\\n",
        "available value to asisgn. There's heuristics in choosing which variable to assign next: \n",
        "1. Minimum remaining value, \"fair-first\", or choosing the most constrained variable\n",
        "2. Least-contraining-value, chooses the variable that rules out the least neighboring values. \n",
        "Forward checking uses both search and inference: it checks for arc consistency everytime a variable \\\n",
        "is assigned; this process if unnecessary if arc consistency was part of preprocessing step. It only checks \\\n",
        "arc consistency for the current variable. \n",
        "**Backjumping** is smarter than chronological backtracking as it backtracks to the assignment in conflict set.\"\"\"\n",
        "chapter6_4 = \"\"\"**Local search for CSPs**. Local searches eliminate violated constraints.\"\"\"\n",
        "chapter6_5 = \"\"\"Decomposing problems into independent subproblems significantly reduces time complexity. \\\n",
        "A tree-structured contraint graph is when two variabes are connected by only one path, and it can be solved in \\\n",
        "linear time proportional to number of variables. We can reach directed arc consistency by using topological sort. \\\n",
        "We can use **cutset conditioning** to convert CSP into tree structure: remove nodes where the remaining \\\n",
        "graph is tree-structured; finding the smallest cutset is NP-hard, but can be approximated. \\\n",
        "Another approach is **tree decomposition** by turning constraint graph into a set of \\\n",
        "connected subproblems, like divide-and-conquer; it works well when subproblem is not too big, \\\n",
        "i.e. the tree width of the constraint graph is small. **Cutset conditioning** uses space \\\n",
        "linear to the number of variables, whlie the space complexity for **tree composition** is \\\n",
        "exponential in the tree width of subproblems, w.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"node consistency\": \"all values satisify a variable's unary constraints\",\n",
        "\"arc consistency\": \"corresponds to binary constraints\",\n",
        "\"path consistency\": \"uses implicit constraints by looking at triples of variables\",\n",
        "\"strongly k-consistent\": \"n-consistent for n in range k to 1\",\n",
        "\"Maintaining arc consistency (MAC)\": \"Checks arc-consistency for all variables after a single assingnment \\\n",
        "with backtracking search; calls AC-3 after each assignment\",\n",
        "\"chronological backtracking\": \"the algorithm backtracks to the most recent decision point\",\n",
        "\"min-conflict\": \"works with local search, heuristic that selects the value resulting \\\n",
        "in the minimum number of conflicts with other variables\",\n",
        "\"topological sort\": \"an ordering such that each variable appears after its parent in the tree\"    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 875
        },
        "outputId": "f30b0588-7a77-4102-f2f0-7a38a7aace14"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nCSP has three components, a set of variables (X), set of domains (D), each corresponding to a variable, set of constraints (C). CSP is solved by performing consistent assignment. Assignment in the end can be complete or partial. CSP can be viewed as a constraint graph. \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nCSP can be solved using search or inference (constraint propagation). AC-3 is an algorithm for ensuring arc consistency.\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\nSometimes we need to search for a solution. Backtracking uses DFS and chooses value for one variable at a time and backtracks when there's no available value to asisgn. There's heuristics in choosing which variable to assign next: \n1. Minimum remaining value, \"fair-first\", or choosing the most constrained variable\n2. Least-contraining-value, chooses the variable that rules out the least neighboring values. \nForward checking uses both search and inference: it checks for arc consistency everytime a variable is assigned; this process if unnecessary if arc consistency was part of preprocessing step. It only checks arc consistency for the current variable. \n**Backjumping** is smarter than chronological backtracking as it backtracks to the assignment in conflict set.\n\n## AIMA Chapter 6.4 Local Search for CSPs\n**Local search for CSPs**. Local searches eliminate violated constraints.\n\n## AIMA Chapter 6.5 The Structure of Problems\nDecomposing problems into independent subproblems significantly reduces time complexity. A tree-structured contraint graph is when two variabes are connected by only one path, and it can be solved in linear time proportional to number of variables. We can reach directed arc consistency by using topological sort. We can use **cutset conditioning** to convert CSP into tree structure: remove nodes where the remaining graph is tree-structured; finding the smallest cutset is NP-hard, but can be approximated. Another approach is \"tree decomposition** by turning constraint graph into a set of connected subproblems, like divide-and-conquer; it works well when subproblem is not too big.\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Node consistency** - all values satisify a variable's unary constraints\n* **Arc consistency** - corresponds to binary constraints\n* **Path consistency** - uses implicit constraints by looking at triples of variables\n* **Strongly k-consistent** - n-consistent for n in range k to 1\n* **Maintaining arc consistency (mac)** - Checks arc-consistency for all variables after a single assingnment; calls AC-3 after each assignment\n* **Chronological backtracking** - the algorithm backtracks to the most recent decision point\n* **Min-conflict** - works with local search, heuristic that selects the value resulting in the minimum number of conflicts with other variables\n* **Topological sort** - an ordering such that each variable appears after its parent in the tree\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"**Knowledge-based agent**. The agent maintains a knowledge base which may \\\n",
        "contain some background knowledge in the beginning. It does three things: \n",
        "1. TELL KB what it perceives\n",
        "2. ASK KB what action it should take\n",
        "3. TELL KB what action was chosen\"\"\"\n",
        "chapter7_2 = \"\"\"**Wumpus world**\"\"\"\n",
        "chapter7_3 = \"\"\"**Logic**. If a sentence $\\alpha$ is true in model m, then m satisfies $\\alpha$, \\\n",
        "and that m is a model of $\\alpha$. **Entailment** refers to sentence a entails b if for every model where \\\n",
        "a is true, b is also true. KB is a set of sentences. A **sound** or **truth-preserving** \\\n",
        "infernce algorithm only derives entailed sentences. \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"For **knowledge-based agent**, there are two types of sentences: \\\n",
        "axioms (given sentence) and derived sentences (inferred from other sentences). \\\n",
        "**Atomic sentences** are represented by **propositional symbols**, which is a statement \\\n",
        "that can be true or false. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"completeness\": \"an inference algorithm is complete if it can derive any entailed sentences\",\n",
        "\"grounding\": \"the connection between KB and the real world; is KB true in the real world\",\n",
        "\"logical equivalence\": \"two sentences are logically equivalent if they are true in the same set of models.\",\n",
        "\"validity\": \"a sentence is valid if it's true in all models\",\n",
        "\"satisfiability\": \"a sentence is satisfiable if it's true in *some* model\",\n",
        "\"monotonicity\": \"set of entailed sentences can only increase as more information is added to KB\",\n",
        "\"definite clause\": \"disjunction of literals where exactly one is positive\",\n",
        "\"horn clause\": \"disjunction of literals where at most one is positive\"  \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 541
        },
        "outputId": "36cf11fb-2c43-4306-81f6-a5304add1c1a"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \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": "df987421-cd04-486e-8946-3bb678f8eba7"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nThere are four categories of AI: thinking humanly, represented by the Turing Test approach, requires user to have ability in NLP, knowledge representation, automated reasoning and ML; thinking humnaly, resides in the realm of cognitive science; thinking rationally, the law of thought approach, related to logic; acting rationally refers to rationaly agent that acts to achieve best expected outcome.\n\n## AIMA Chapter 27.1 The Limits of AI\nThe weak AI assumption is machines can act as if there were intelligent. Objections include arguments from disability in that there are things a machine cannot do, and the mathematical objection which remains unproved. There's also argument from informality, described by Turing as rules that machine can follow cannot capture complex human behavior.\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nThe strong AI assumption is machines are actually thinking. This relates to the mind-body issue that falls under two philosophical school, dualist and monist theory, characterized by whether mind and body are separate being.\n\n## AIMA 2.1 Agents and Environments\nAn agent uses sensors for percept (perceptual inputs) and actuators to carry out actions. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nRationality does not equal omniscience, instead it requires agent to gather information and learn from what it perceives.\n\n## AIMA 2.3 The Nature of Environments\nTask environment can be described using PEAS(performance, environment, actuators, sensors). Different property of environemnt includes fully vs. partially observable, single vs. multiagent, deterministic vs. stochastic, episodic vs. sequential, discrete vs. continuous, known vs. unknown\n\n## AIMA 2.4 The Structure of Agents\nTypes of agents: simple-reflex agent, model-based agent(agent that maintain internal state that depends on percept history and extend beyond the current observation), goal-based agent(uses search and planning), utility-based agent(based on utility function, an internalization of performance measure), learning agent.\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Known environment** - the outcome or outcome probabilities for all actions are given.\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\nProblem-solving agent is a type of goal-based agent. A problem can be defined as follows: initial state, actions, transition model, goal state, path cost. \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\nTree search doesn't check for visited node while graph-search does. Search algorithm can be measure using the following criteria: completeness, optimality, time and space complexity. Complexity is expressed with b(branching factor), d(depth of the shallowest goal node, m(maximum length of any path in the state space).\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\nUninformed search means we only know the problem definition. BFS uses a FIFO queue; it's complete if the shallowest goal node is at finite depth d. BFS is optimal if the path cost is a nondecreasing function of depth. Time and space complexity are both O(b^d). Uniform cost expands the node with the lowest path cost; it is optimal and complete if each step has a positive cost. DFS uses LIFO queue, and is usually implemented with a recursive call to itself; it is not optimal and of time complexity O(b^m), space complexity O(bm). Depth-limited search and iterative deepening DFS are variations of DFS. Bidirectional search runs two simulataneous search from intial and goal states, and of O(b^(d/2)). It checks if the frontier of two searches overlap.\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Search** - the process fo looking for a sequence of actions that reaches the goal\n* **Leaf node** - node with no children\n* **Rontier** - set of leaf nodes available for expansion at any given point\n* **Completeness** - the algorithm is guaranteed to find a solution when there is one\n* **Branching factor** - b, the maximum number of successors of any node\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n**Informed search**. **Greedy best-first search** evaluates nodes based on only heuristic function; it's neither optimal nor complete. **A\\* search**\n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Best-first search** - instance of tree-search or graph-search where the best node is selected for expansion based on some evaluation function, f(n)\n* **Heuristic function** - estimated cost of the cheapest path from the state at node n to a goal state\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nGames, or adversarial searches are multiagent. Game tree is defined by tge initlal state, actions functions, and transitions.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nCalculating minimax value assumes both players play optimally. Minimax algorithm performs complete DFS of game tree. Time complexity is O(b^m) and space complexity is O(bm) if all actions are generated at once, or O(m) if actions generated one at a time. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nIn alpha-beta pruning, alpha/beta are the best value we've found for either MAX or MIN. Branches are pruned once it's known that it's worst than alpha or beta value. Time complexity is O(b^(m/2)) if we can identify the best successor. The algorithm calls max-value and min-value function interchangeably and recursively.\n\n## AIMA Chapter 5.5 Stochastic Games\nGmaes are stochastic when randomness is introduced. Minimax value can be generalized to expecti-minimax value based on expected value, average over all possible outcomes of chance nodes. Time complexity of these games are O(b^m n^m) where n is number of random outcomes (e.g. dice roll). We can also use Monte Carlo simulation to evalaute a position, by having the algorithm play against itself using random dice rolls. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nAccording to MEU(maximum expected utility), rational agent should choose action that maximizes expected utility.\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nRules of preferences for rational agent: 1. orderability, agent can't avoid deciding and has to choose either prefer one or be indifferent; 2. transitivity, if A>B and B>C, then A>C; 3. continuity, if A>B>C, then for some p, [p, A; 1-p, C] ~ B; 4. substitutability, A ~ B, then [p, A; 1-p, C]~[p,B; 1-p,C]; 5. monotonicity, if A>B, then agent prefers lottery with higher probability of A; 6. decomposability, compound lotteries can be decomposed to simpler forms. \n\n## AIMA Chapter 16.3 Utility Functions\nHuman behaviors are subject to irrationality: for example, the existence of certainty effect, ambiguity aversion, framing effect(different wordings of a factual statement could have different impacts), anchoring effect.\n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Back-up value** - optimal value of a node's children\n* **Preference elicitation** - the process of working out an agent's utility function\n* **Certainty equivalent** - the value an agent accepts in certainty instead of lottery\n* **Normative theory** - describes how a rational agent should act\n* **Descriptive theory** - describes how an agent actually acts\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nCSP has three components, a set of variables (X), set of domains (D), each corresponding to a variable, set of constraints (C). CSP is solved by performing consistent assignment. Assignment in the end can be complete or partial. CSP can be viewed as a constraint graph. \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nCSP can be solved using search or inference (constraint propagation). AC-3 is an algorithm for ensuring arc consistency.\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\nSometimes we need to search for a solution. Backtracking uses DFS and chooses value for one variable at a time and backtracks when there's no available value to asisgn. There's heuristics in choosing which variable to assign next: \n1. Minimum remaining value, \"fair-first\", or choosing the most constrained variable\n2. Least-contraining-value, chooses the variable that rules out the least neighboring values. \nForward checking uses both search and inference: it checks for arc consistency everytime a variable is assigned; this process if unnecessary if arc consistency was part of preprocessing step. It only checks arc consistency for the current variable. \n**Backjumping** is smarter than chronological backtracking as it backtracks to the assignment in conflict set.\n\n## AIMA Chapter 6.4 Local Search for CSPs\n**Local search for CSPs**. Local searches eliminate violated constraints.\n\n## AIMA Chapter 6.5 The Structure of Problems\nDecomposing problems into independent subproblems significantly reduces time complexity. A tree-structured contraint graph is when two variabes are connected by only one path, and it can be solved in linear time proportional to number of variables. We can reach directed arc consistency by using topological sort. We can use **cutset conditioning** to convert CSP into tree structure: remove nodes where the remaining graph is tree-structured; finding the smallest cutset is NP-hard, but can be approximated. Another approach is \"tree decomposition** by turning constraint graph into a set of connected subproblems, like divide-and-conquer; it works well when subproblem is not too big.\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Node consistency** - all values satisify a variable's unary constraints\n* **Arc consistency** - corresponds to binary constraints\n* **Path consistency** - uses implicit constraints by looking at triples of variables\n* **Strongly k-consistent** - n-consistent for n in range k to 1\n* **Maintaining arc consistency (mac)** - Checks arc-consistency for all variables after a single assingnment; calls AC-3 after each assignment\n* **Chronological backtracking** - the algorithm backtracks to the most recent decision point\n* **Min-conflict** - works with local search, heuristic that selects the value resulting in the minimum number of conflicts with other variables\n* **Topological sort** - an ordering such that each variable appears after its parent in the tree\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}