{
 "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",
   "execution_count": 1,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 0
    },
    "id": "lzaavW96tcxM",
    "outputId": "1f1b6614-aa92-4cf8-8db8-4a17cb7004f0"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The example summary is 116 words long, so you could write an additional 384 words.\n"
     ]
    }
   ],
   "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)))"
   ]
  },
  {
   "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",
   "execution_count": 2,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 0
    },
    "id": "8DvZ57A-djo1",
    "outputId": "b4aba39c-6daa-48c9-c6ed-888389ed3f25"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 500\n",
      "The length in characters is 3030\n"
     ]
    }
   ],
   "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))"
   ]
  },
  {
   "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",
   "execution_count": 3,
   "metadata": {
    "id": "2RECnJArJew4"
   },
   "outputs": [],
   "source": [
    "name = \"\"\n",
    "permission = True\n",
    "anonymous = False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "GZZXyrV-xuAp"
   },
   "source": [
    "# Module 1 - Intro to AI"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "id": "Y2NfE1CKxzS-"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
    "\n",
    "chapter1_1 = \"\"\" The target of AI: making model think and act rationally and work like people. \n",
    "\n",
    "Turning test aims to check how closly one's answers resemble those a human would give.\"\"\" \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 = \"\"\"\n",
    "Model has to be constructed with sensors and actuators. People need give input and interpret the outputs. \n",
    "Another problem is that, they are still dealing with random variables, can not represent objects and relations explicitly. \"\"\"\n",
    "\n",
    "chapter27_2 = \"\"\" How model deals with general situations?? \n",
    "\n",
    "-Anytime algorithms and decision-theoretic metareasonging\"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
    "chapter2_1 = \"\"\"\"\"\"\n",
    "chapter2_2 = \"\"\"\"\"\"\n",
    "chapter2_3 = \"\"\"\"\"\"\n",
    "chapter2_4 = \"\"\"\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module1_lecture_notes = \"\"\" Agent design goal is to construct the agent funcion f which maximize \n",
    "the expected performance measure and design an agent program for a special structure.The hardest Environment is\n",
    "Continuous, Partially Observable, Stochastic and Multiagent\"\"\"\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\" : \"the agent’s perceptual inputs instantly\",\n",
    "\"percept sequence\" : \"complete history of perceptions\",\n",
    "\"agent function\": \"agent's behaviors\",\n",
    "\"A rational agent\": \"perceives its environment and and behaves rationally, maximize its performance measure\",\n",
    "\"P, performance measure\": \"Test if the agent is doing the right decision, safe, fast for car\",\n",
    "'E, environment': 'road',\n",
    "\"A, actuators\": \"accelerator, brake\",\n",
    "\"S, Sensors\" : \"GPS\",\n",
    "\"Reflex agents\": \"selects an action based on the current percept\",\n",
    "\"A problem-solving agent\": \"plan ahead, form a sequence of actions as a path, which called as search\",\n",
    "\"Search problem\": \"Goal, States, Actions, Performace measure, Solution\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "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",
   "execution_count": 5,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 670
    },
    "id": "gYYeNcdM_maE",
    "outputId": "35762d27-25b6-4120-d057-ae1a8ff181cb"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 1: Rational Agents and Task Environments\n",
       "## AIMA Chapter 1.1 What is AI?\n",
       " The target of AI: making model think and act rationally and work like people. \n",
       "\n",
       "Turning test aims to check how closly one's answers resemble those a human would give.\n",
       "\n",
       "## AIMA Chapter 27.1 The Limits of AI\n",
       "\n",
       "Model has to be constructed with sensors and actuators. People need give input and interpret the outputs. \n",
       "Another problem is that, they are still dealing with random variables, can not represent objects and relations explicitly. \n",
       "\n",
       "## AIMA Chapter 27.1 Can Machines Really Think?\n",
       " How model deals with general situations?? \n",
       "\n",
       "-Anytime algorithms and decision-theoretic metareasonging\n",
       "\n",
       "## Module 1 Lecture Notes\n",
       " Agent design goal is to construct the agent funcion f which maximize \n",
       "the expected performance measure and design an agent program for a special structure.The hardest Environment is\n",
       "Continuous, Partially Observable, Stochastic and Multiagent\n",
       "\n",
       "## Module 1 Definitions\n",
       "* **Agent** - anything that can perceive and act in an environment\n",
       "* **Percept** - the agent’s perceptual inputs instantly\n",
       "* **Percept sequence** - complete history of perceptions\n",
       "* **Agent function** - agent's behaviors\n",
       "* **A rational agent** - perceives its environment and and behaves rationally, maximize its performance measure\n",
       "* **P, performance measure** - Test if the agent is doing the right decision, safe, fast for car\n",
       "* **E, environment** - road\n",
       "* **A, actuators** - accelerator, brake\n",
       "* **S, sensors** - GPS\n",
       "* **Reflex agents** - selects an action based on the current percept\n",
       "* **A problem-solving agent** - plan ahead, form a sequence of actions as a path, which called as search\n",
       "* **Search problem** - Goal, States, Actions, Performace measure, Solution\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "9xRbdqDox2zD"
   },
   "source": [
    "#Module 2 - Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "id": "DpBvu7EMx7sy"
   },
   "outputs": [],
   "source": [
    "# No readings for this module.  Instead you can summarize the lecture instead.\n",
    "\n",
    "# Lecture notes \n",
    "module2_lecture_notes = \"\"\"\n",
    "- Strings start with r will be regarded as a raw string(\\ not work).\n",
    "\n",
    "- Strings are immutable, y.strip() not change x. Lists are mutable, y.append(5) will add 5 to x(COPY). y = x[:] shallow copy, a new object.\n",
    "\n",
    "- Defaultdict will provide a suitable default value for the input keys. \n",
    "\n",
    "- *args accepts non-keyword arguments to the funciton.(only value)\n",
    "\n",
    "- **kwargs accpets different number of variables for the same function.（key - value)\n",
    "\n",
    "- Multiple Inheritance will call the oldest function version. \n",
    "\n",
    "- Generators benefits : Less code, Maintains local state, one-time value computed when needed,\\\n",
    "save memory, aggregating easily, crucial for infi-sequences, hard to use when check individual value \n",
    "\n",
    "\"\"\"\n",
    "\n",
    "# Each definition should be at most 20 words long.\n",
    "module2_definitions = {\n",
    "\"Positive features\": \"Fast development, Portable(dif platform works), Various bulit-in types(list, dict...), large collection of support libraries(NP,matlab..)\",\n",
    "\"Fixed/Static\" : \"'test' + 2 not allowed\" ,\n",
    "\"dynamic\" : \"x = 1, x = 'ok' types vary acceptable\",\n",
    "\"list.remove('a')\": \"remove the first a\",\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 412
    },
    "id": "ydOK__lwWgdp",
    "outputId": "e58d726b-5188-4351-ff65-b3f1fc1e75fe"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 2: Python\n",
       "## Module 2 Lecture Notes\n",
       "\n",
       "- Strings start with r will be regarded as a raw string(\\ not work).\n",
       "\n",
       "- Strings are immutable, y.strip() not change x. Lists are mutable, y.append(5) will add 5 to x(COPY). y = x[:] shallow copy, a new object.\n",
       "\n",
       "- Defaultdict will provide a suitable default value for the input keys. \n",
       "\n",
       "- *args accepts non-keyword arguments to the funciton.(only value)\n",
       "\n",
       "- **kwargs accpets different number of variables for the same function.（key - value)\n",
       "\n",
       "- Multiple Inheritance will call the oldest function version. \n",
       "\n",
       "- Generators benefits : Less code, Maintains local state, one-time value computed when needed,save memory, aggregating easily, crucial for infi-sequences, hard to use when check individual value \n",
       "\n",
       "\n",
       "\n",
       "## Module 2 Definitions\n",
       "* **Positive features** - Fast development, Portable(dif platform works), Various bulit-in types(list, dict...), large collection of support libraries(NP,matlab..)\n",
       "* **Fixed/static** - 'test' + 2 not allowed\n",
       "* **Dynamic** - x = 1, x = 'ok' types vary acceptable\n",
       "* **List.remove('a')** - remove the first a\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "46MQLR-Gx8dZ"
   },
   "source": [
    "#Module 3 - Search Problems"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "id": "BN0b1eVYx-nd"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
    "chapter3_1 = \"\"\"\"\"\"\n",
    "chapter3_2 = \"\"\"\"\"\"\n",
    "chapter3_3 = \"\"\"\"\"\"\n",
    "chapter3_4 = \"\"\"\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module3_lecture_notes = \"\"\"\n",
    "- Tree search enumerate all paths fron the initial state(root).\n",
    "\n",
    "- Graph search will check whether the node has been visited before \\\n",
    "adding to search queue.\n",
    "\n",
    "- Uninformed search: All non-goal nodes have equal weights.\n",
    "\n",
    "- Informed Search: Some nodes are ranked.\n",
    "\n",
    "- Completeness means always find the solution. \\\n",
    "Optimal means find the best solution.\n",
    "\n",
    "- Breadth-first search: Expand node from shallow to deep, frontier is FIFO\n",
    "\n",
    "- BFS problem: Waste Memory and Time\n",
    "\n",
    "- Depth-first search: Find the deepest uneexpanded node, frontier is LIFO\n",
    "\n",
    "- DFS problem: Cannot deal with infinite paths\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",
    "\"Evaluation\" : \"Completeness, Optimality, Time complexity, Space complexity\",\n",
    "\"b\" : \"maximum branching factor\",\n",
    "\"d\":\"depth\",\n",
    "\"m\":\"max length\",\n",
    "\"BFS properties\": \"Complete, Optimal, Time $O(b^d)$, Space $O(b^d)$\",\n",
    "\"DFS properties\": \"Not Complete, Not Optimal, Time $O(b^m)$, Space $O(b * d)$\",\n",
    "\"Depth-limited Search\": \"with depth limit l, Incomplete(l<d), not optimal(l>d), Time $O(b^l)$, Space $O(b * l)$\",\n",
    "\"Iterative deepening Search\": \"Complete & optimal, Time $O(b^d)$, Space O(bd)\"\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 544
    },
    "id": "lvtN3p7ET3Tx",
    "outputId": "e755373e-5238-4800-d7df-0a597229fd20"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 3: Search Problems\n",
       "## Module 3 Lecture Notes\n",
       "\n",
       "- Tree search enumerate all paths fron the initial state(root).\n",
       "\n",
       "- Graph search will check whether the node has been visited before adding to search queue.\n",
       "\n",
       "- Uninformed search: All non-goal nodes have equal weights.\n",
       "\n",
       "- Informed Search: Some nodes are ranked.\n",
       "\n",
       "- Completeness means always find the solution. Optimal means find the best solution.\n",
       "\n",
       "- Breadth-first search: Expand node from shallow to deep, frontier is FIFO\n",
       "\n",
       "- BFS problem: Waste Memory and Time\n",
       "\n",
       "- Depth-first search: Find the deepest uneexpanded node, frontier is LIFO\n",
       "\n",
       "- DFS problem: Cannot deal with infinite paths\n",
       "\n",
       "\n",
       "\n",
       "## Module 3 Definitions\n",
       "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
       "* **Evaluation** - Completeness, Optimality, Time complexity, Space complexity\n",
       "* **B** - maximum branching factor\n",
       "* **D** - depth\n",
       "* **M** - max length\n",
       "* **Bfs properties** - Complete, Optimal, Time $O(b^d)$, Space $O(b^d)$\n",
       "* **Dfs properties** - Not Complete, Not Optimal, Time $O(b^m)$, Space $O(b * d)$\n",
       "* **Depth-limited search** - with depth limit l, Incomplete(l<d), not optimal(l>d), Time $O(b^l)$, Space $O(b * l)$\n",
       "* **Iterative deepening search** - Complete & optimal, Time $O(b^d)$, Space O(bd)\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "vsazFT1Weup4"
   },
   "source": [
    "```\n",
    "def Tree_Search():\n",
    "  initialize the frontier\n",
    "  loop\n",
    "    if frontier empty: \n",
    "      return failure\n",
    "    node = frontier.pop()\n",
    "    if node contains target:\n",
    "      return solution, expend node, frontier.append(node) \n",
    "         \n",
    "```\n",
    "\n",
    "```\n",
    "def Graph_Search():\n",
    "  initialize the frontier\n",
    "  ** initialize the explored set **\n",
    "  loop\n",
    "    if frontier empty: \n",
    "      return failure\n",
    "    node = frontier.pop()\n",
    "    if node contains target:\n",
    "      return solution, \n",
    "     ** explored.append(node)**\n",
    "     ** if node not in explored:**\n",
    "        expend node, frontier.append(node) \n",
    "```\n",
    "```\n",
    "def Breadth-first search():\n",
    "  initialize the frontier, FIFO\n",
    "  initialize the explored set\n",
    "  frontier, Explored.append(first-node)\n",
    "  while frontier not empty:\n",
    "    node = frontier.pop()\n",
    "    for child in node.children:\n",
    "      **if child is goal**  \n",
    "        return child\n",
    "      if child not in explored:\n",
    "        explored.append(child)\n",
    "        frontier.append(child\n",
    "  return failure\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "frjSbyQ5l7Ug"
   },
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "WHREsHSSyA-h"
   },
   "source": [
    "#Module 4 - Informed Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "id": "tuFC8w7CyCns"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
    "chapter3_5 = \"\"\"\"\"\"\n",
    "chapter3_6 = \"\"\"\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module4_lecture_notes = \"\"\"\n",
    "- Informed Search uses domain-specific info to be faster than uninformed search\n",
    "\n",
    "- Uniform-cost search: Cost is the number of nodes, all moves equal, search in a cost range\n",
    "\n",
    "- Greedy Best-First Search: Select node with min **f(n) = h(n)**, using priority queue\n",
    "\n",
    "- A* search(best first search): f(n) = g(n)+h(n), cost so far + estimated cost, 0 <= h(n) <= h*(n)\n",
    "\n",
    "- If h(n) is admissible, A* using Tree Search is optimal\n",
    "\n",
    "- The cost of an optimal solution to a relaxed problem is an admissible heuristic for the\n",
    "original problem\n",
    "\n",
    "- If h2 dominates h1, h2 is optimistic and more accurate than h1\n",
    "\n",
    "- A* search is optimal, applies to pathing/video games/ robot motion/ resource planning\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module4_definitions = {\n",
    "\"Optimal Solution\": \"A solution is optimal if no solution has the lowest cost\",\n",
    "\"State space\" : \"the set of all possible actions\",\n",
    "\"Frontier\" : \"states which are avaliable for expanding\",\n",
    "\"h(n) is admissible\": \"if it never overestimates the cost to reach the goal\",\n",
    "\"relaxed problem\": \"Fewer restrications than original problem\",\n",
    "\"dominance\":\"for all n, h2(n) > h1(n) then h2 dominates h1\"\n",
    "\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "k2Vwon-M8aRn"
   },
   "source": [
    "```\n",
    "def greedy best-first search:\n",
    "  frontier = PriorityQueue()\n",
    "  frontie.put(start,0)\n",
    "  came_from = {}\n",
    "  came_from[start] = None\n",
    "  \n",
    "  while not frontier.empty():\n",
    "    current = frontier.get()\n",
    "    if current == goal:\n",
    "      break\n",
    "    for next in graph.neighbors(current):\n",
    "      if next not in came_from:\n",
    "      priority = hn(goal, next)\n",
    "      frontier.put(next, priority)\n",
    "      came_from[next] = current\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 451
    },
    "id": "vqtEs0gHs9sO",
    "outputId": "f3548e04-9d1b-4e5a-8a62-7ef0104508eb"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 4: Informed Search\n",
       "## Module 4 Lecture Notes\n",
       "\n",
       "- Informed Search uses domain-specific info to be faster than uninformed search\n",
       "\n",
       "- Uniform-cost search: Cost is the number of nodes, all moves equal, search in a cost range\n",
       "\n",
       "- Greedy Best-First Search: Select node with min **f(n) = h(n)**, using priority queue\n",
       "\n",
       "- A* search(best first search): f(n) = g(n)+h(n), cost so far + estimated cost, 0 <= h(n) <= h*(n)\n",
       "\n",
       "- If h(n) is admissible, A* using Tree Search is optimal\n",
       "\n",
       "- The cost of an optimal solution to a relaxed problem is an admissible heuristic for the\n",
       "original problem\n",
       "\n",
       "- If h2 dominates h1, h2 is optimistic and more accurate than h1\n",
       "\n",
       "- A* search is optimal, applies to pathing/video games/ robot motion/ resource planning\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "## Module 4 Definitions\n",
       "* **Optimal solution** - A solution is optimal if no solution has the lowest cost\n",
       "* **State space** - the set of all possible actions\n",
       "* **Frontier** - states which are avaliable for expanding\n",
       "* **H(n) is admissible** - if it never overestimates the cost to reach the goal\n",
       "* **Relaxed problem** - Fewer restrications than original problem\n",
       "* **Dominance** - for all n, h2(n) > h1(n) then h2 dominates h1\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "F3FPMzG9yUls"
   },
   "source": [
    "#Module 5 - Adversarial Search and Games"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "id": "iEIOpL7vyWcc"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
    "chapter5_1 = \"\"\"\"\"\"\n",
    "chapter5_2 = \"\"\"\"\"\"\n",
    "chapter5_3 = \"\"\"\"\"\"\n",
    "chapter5_5 = \"\"\"\"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
    "chapter16_1 =\"\"\"\"\"\"\n",
    "chapter16_2 =\"\"\"\"\"\"\n",
    "chapter16_3 = \"\"\"\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module5_lecture_notes = \"\"\" \n",
    "- Game Environment has multiagent. Examples like\n",
    "Chess, Checkers, Go, Mancala, Tic-Tac-Toe, Othello. \n",
    "\n",
    "- four propertiex for game: two players orderly play the game, zero-sum \\\n",
    "one loss one win, legal moves are clear, results are well defined(win, lose, draw)\n",
    "\n",
    "- More difficult games: stohastic, lack info(Most card games (e.g. Hearts, Bridge and Scrabble),\\\n",
    "continuous and no pause between rounds, cooperate games\n",
    "\n",
    "- Game search uses tree structure, node represents 'board position', edge -> legal moves\n",
    "\n",
    "- Solving a tree-structued CSP takes linear time in the number of variables\n",
    "- Evaluation function f(n) > 0, max wins at position n\n",
    "\n",
    "- MinMax rule: best moves. If MIN not move optimally, MAX will be better. \n",
    "\n",
    "- Pruning Stop condition: {MAX} v >= beta, MIN never choose that MAX node \\\n",
    "{MIN} v <= alpha MAx never select MIN node. \n",
    "\n",
    "- Expectimax Search： Uncertain outcomes, unpredictable opponents, actions may fail. Compute the average score. \n",
    "\n",
    "-The key idea behind inference in CSPs is enforcing k- consistency\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module5_definitions = {\n",
    "\"Static\": \"No change while agent considering\",\n",
    "\"Discrete\":\" A finite set of percepts and actions.\",\n",
    "\"Fully observable\":\"Complete state of environment got by sensor\",\n",
    "\"Strategic\": \"current state + action + another agent makes the next state\",\n",
    "\"$alpha$\" : \"MAX lower bound\",\n",
    "\"$beta$\" : \"MIN upper bound\",\n",
    "\"Objectivist / frequentist answer\":\" Averages over repeated experiments， summrized from history(rolling dice)\",\n",
    "\"Subjectivist / Bayesian answer\" : \"Degrees of belief about unobserved variables, give predictions for unobserved data(guess tomorrow raining)\"\n",
    "\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "9UgdH_j6ACWn"
   },
   "source": [
    "```\n",
    "  def value(state):\n",
    "    if target: return state's utility\n",
    "    if MAX_agent: return max_value(state)\n",
    "    if EXP_agent: return exp_value(state)\n",
    "\n",
    "  def max_value():\n",
    "    initialize v = -inf\n",
    "    for case in successor:\n",
    "      v = max(v, value(case))\n",
    "    return v\n",
    "\n",
    "  def exp_value():\n",
    "    initialize v = 0\n",
    "    for case in successor:\n",
    "      p = prob(case)\n",
    "      v += p * value(case)\n",
    "    return v\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 540
    },
    "id": "KUc_LgzDvWf-",
    "outputId": "1c1f64f0-224d-4b8e-8f09-687c1022c021"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 5: Adversarial Search and Games\n",
       "## Module 5 Lecture Notes\n",
       " \n",
       "- Game Environment has multiagent. Examples like\n",
       "Chess, Checkers, Go, Mancala, Tic-Tac-Toe, Othello. \n",
       "\n",
       "- four propertiex for game: two players orderly play the game, zero-sum one loss one win, legal moves are clear, results are well defined(win, lose, draw)\n",
       "\n",
       "- More difficult games: stohastic, lack info(Most card games (e.g. Hearts, Bridge and Scrabble),continuous and no pause between rounds, cooperate games\n",
       "\n",
       "- Game search uses tree structure, node represents 'board position', edge -> legal moves\n",
       "\n",
       "- Solving a tree-structued CSP takes linear time in the number of variables\n",
       "- Evaluation function f(n) > 0, max wins at position n\n",
       "\n",
       "- MinMax rule: best moves. If MIN not move optimally, MAX will be better. \n",
       "\n",
       "- Pruning Stop condition: {MAX} v >= beta, MIN never choose that MAX node {MIN} v <= alpha MAx never select MIN node. \n",
       "\n",
       "- Expectimax Search： Uncertain outcomes, unpredictable opponents, actions may fail. Compute the average score. \n",
       "\n",
       "-The key idea behind inference in CSPs is enforcing k- consistency\n",
       "\n",
       "\n",
       "\n",
       "## Module 5 Definitions\n",
       "* **Static** - No change while agent considering\n",
       "* **Discrete** -  A finite set of percepts and actions.\n",
       "* **Fully observable** - Complete state of environment got by sensor\n",
       "* **Strategic** - current state + action + another agent makes the next state\n",
       "* **$alpha$** - MAX lower bound\n",
       "* **$beta$** - MIN upper bound\n",
       "* **Objectivist / frequentist answer** -  Averages over repeated experiments， summrized from history(rolling dice)\n",
       "* **Subjectivist / bayesian answer** - Degrees of belief about unobserved variables, give predictions for unobserved data(guess tomorrow raining)\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "qVSQhTVSyYYO"
   },
   "source": [
    "#Module 6 - \"Constraint Satisfaction Problems\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "id": "Wm4mfW82yaRH"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
    "chapter6_1 = \"\"\"\"\"\"\n",
    "chapter6_2 = \"\"\"\"\"\"\n",
    "chapter6_3 = \"\"\"\"\"\"\n",
    "chapter6_4 = \"\"\"\"\"\"\n",
    "chapter6_5 = \"\"\"\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module6_lecture_notes = \"\"\"  \n",
    "- Search Assumptions: a single agent, deterministic actions, fully\n",
    "observed state, discrete state space\n",
    "\n",
    "- CSP: Finite set of variables and constraints, nonempty domain of possible values. \\\n",
    "\n",
    "- CSP application: Map Coloring, Scheuling problems, Floor planning for VLSI, Sudoku\n",
    "\n",
    "- CSP Benefits: Clean specifications and generic goal, find the violates variables, auto - prune off\n",
    "\n",
    "- CSP variables: discrete variables(finite: Boolean, n variables | infinite: int/string <= ), continuous variables(start/end time, linear)\n",
    "\n",
    "- Varieties Constraints: Unary, Binary, Higher-order(crypt-arithmetic column constraints), Preference(A is btter than B)\n",
    "\n",
    "- CSP Structure: Initial State + Successor function + Goal test(reach goal) + Path Cost(constant cost/step)\n",
    "\n",
    "- Improving backtracking efficiency focuses on the most constrained variable first and try the least constriaining value.**Forward checking can detect failure early**\n",
    "\n",
    "- Minimum remaining values (MRV) starts with the least legal values(lowest number of choices)\n",
    "\n",
    "- Forward checking stops when any unassigned variable has no choices value and it doesn't provide\n",
    "early detection for all failures\n",
    "\n",
    "- Local consistency -> Node consistency: satisfies unary constraints\n",
    "\n",
    "- Arc consistency -> satisfies binary constraints wchich can be run as a preprocessor or after each assignment\n",
    "\n",
    "- For one pair of arcs, it has two arcs connected them\n",
    "\n",
    "- X -> Y is consistent if every value x of X there is some allowed y. If X loses a value(Y has no consistent value for X), recheck neighbors of X.\n",
    "\n",
    "- With d values, it takes O($b ^ d$) time as the worst case\n",
    "\n",
    "- Waltz algorithm interprets line drawings of solid polyhedra as 3D objects. Variable, each intersection. \n",
    "\n",
    "- Inefficiences: 1. only check Xi which has lost a value 2. no need to check Yj if lose because Yj 3. only\n",
    "need to check that (j,i) is still arc-consistent.\n",
    "\n",
    "- Each of n nodes must be compared against n-1 other nodes, 2*n*(n-1), O($n ^ 2$) num of comparision\n",
    "\n",
    "- d values, check arc(i, j), O($d^2$)\n",
    "\n",
    "- Insert arc(i,j) d times, O($n^2d^3$)\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module6_definitions = {\n",
    "\"Consistent\" : \"assignment doesn't violate constraints\", \n",
    "\"Complete\" : \"Every variable is assigned (Sudoku)\",\n",
    "\"Solution of CSP\" : \"Consistent + Complete\",\n",
    "\"backtracking search\" : \"Depth-first search for CSPs with single-variable assignments(basic uninformed algorithm)\",\n",
    "\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "H7x2y-hfvWW8"
   },
   "source": [
    "```\n",
    "def The Waltz/Mackworth Constraint Propagation Algorithm():\n",
    "  Assign every node in the constraint graph\n",
    "  While until no change associated with any node:\n",
    "    for node i:\n",
    "      for neighboring node j: \n",
    "        remove any value from i which is not consistent with j\n",
    "```\n",
    "\n",
    "```\n",
    "def AC-3 ():\n",
    "while queue is not empty{\n",
    "  (Xi,Xj) = queue.pop()\n",
    "  if REMOVE-INCONSISTENT-VALUES(Xi, Xj) then\n",
    "  for each Xk in neighbors[Xi] – {Xj} do\n",
    "    queue.append((Xk, Xi)）\n",
    "\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 727
    },
    "id": "kKWbCsbfxL3R",
    "outputId": "3f023b0d-747c-4065-82a0-a8589ebff1e4"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 6: Constraint Satisfaction Problems\n",
       "## Module 6 Lecture Notes\n",
       "  \n",
       "- Search Assumptions: a single agent, deterministic actions, fully\n",
       "observed state, discrete state space\n",
       "\n",
       "- CSP: Finite set of variables and constraints, nonempty domain of possible values. \n",
       "- CSP application: Map Coloring, Scheuling problems, Floor planning for VLSI, Sudoku\n",
       "\n",
       "- CSP Benefits: Clean specifications and generic goal, find the violates variables, auto - prune off\n",
       "\n",
       "- CSP variables: discrete variables(finite: Boolean, n variables | infinite: int/string <= ), continuous variables(start/end time, linear)\n",
       "\n",
       "- Varieties Constraints: Unary, Binary, Higher-order(crypt-arithmetic column constraints), Preference(A is btter than B)\n",
       "\n",
       "- CSP Structure: Initial State + Successor function + Goal test(reach goal) + Path Cost(constant cost/step)\n",
       "\n",
       "- Improving backtracking efficiency focuses on the most constrained variable first and try the least constriaining value.**Forward checking can detect failure early**\n",
       "\n",
       "- Minimum remaining values (MRV) starts with the least legal values(lowest number of choices)\n",
       "\n",
       "- Forward checking stops when any unassigned variable has no choices value and it doesn't provide\n",
       "early detection for all failures\n",
       "\n",
       "- Local consistency -> Node consistency: satisfies unary constraints\n",
       "\n",
       "- Arc consistency -> satisfies binary constraints wchich can be run as a preprocessor or after each assignment\n",
       "\n",
       "- For one pair of arcs, it has two arcs connected them\n",
       "\n",
       "- X -> Y is consistent if every value x of X there is some allowed y. If X loses a value(Y has no consistent value for X), recheck neighbors of X.\n",
       "\n",
       "- With d values, it takes O($b ^ d$) time as the worst case\n",
       "\n",
       "- Waltz algorithm interprets line drawings of solid polyhedra as 3D objects. Variable, each intersection. \n",
       "\n",
       "- Inefficiences: 1. only check Xi which has lost a value 2. no need to check Yj if lose because Yj 3. only\n",
       "need to check that (j,i) is still arc-consistent.\n",
       "\n",
       "- Each of n nodes must be compared against n-1 other nodes, 2*n*(n-1), O($n ^ 2$) num of comparision\n",
       "\n",
       "- d values, check arc(i, j), O($d^2$)\n",
       "\n",
       "- Insert arc(i,j) d times, O($n^2d^3$)\n",
       "\n",
       "\n",
       "## Module 6 Definitions\n",
       "* **Consistent** - assignment doesn't violate constraints\n",
       "* **Complete** - Every variable is assigned (Sudoku)\n",
       "* **Solution of csp** - Consistent + Complete\n",
       "* **Backtracking search** - Depth-first search for CSPs with single-variable assignments(basic uninformed algorithm)\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "RYESi2kMybL8"
   },
   "source": [
    "#Module 7 - Logical Agents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "id": "qIRJ4YYCzNHL"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
    "\n",
    "chapter7_1 = \"\"\"\"\"\"\n",
    "chapter7_2 = \"\"\"\"\"\"\n",
    "chapter7_3 = \"\"\"\"\"\"\n",
    "chapter7_4 = \"\"\"\"\"\"\n",
    "chapter7_5 = \"\"\"\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module7_lecture_notes = \"\"\" \n",
    "- A KB contains a set of sentence written in a knowledge representation\n",
    "language which can bedivided into **Axioms** + **Derived sentences**. It has \\\n",
    "some background information.\n",
    "\n",
    "- A knowledge-based agent can add to the information in the KB and pop KB to\n",
    "derive new \n",
    "\n",
    "- If sentence alpha is true in model m then we say: m satisfies alpha, or\n",
    "m is a model of alpha, M(alpha). e.g. alpha:No water in (1,1), M(alpha): \\\n",
    "all instances in which (1,1) has no water \n",
    "\n",
    "- The KB is false when any model contradicts the known knowledge.\n",
    "\n",
    "- simpler sentences + parentheses and logical connectives = Complex sentences \n",
    "\n",
    "- CNF(Conjunctive Normal Form): 1. eliminate biconditional 2. IMPLICATION ELIMINATION\\\n",
    "3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\\\n",
    "4. Combination of all the disjuncts and Distribution of ∨ over ∧\n",
    "\n",
    "- The resolution algorithm is complete! \n",
    "\n",
    "- Forward Chaining is data-driven reasoning. With known\n",
    "data, adding premises as new percepts come in, and derive new conclusions\\\n",
    "(by forward chaining algorithm). It doesn’t have to use a specific query.\n",
    "\n",
    "- Backward chaining works backwards from a query. \\\n",
    "If the query is true, end \\\n",
    "Otherwise, the algorithm finds implications in the KB (conclusion in query).\\\n",
    "If all the premises of one of implications\\\n",
    "can be proved to be true (via backward chaining), \\\n",
    "then the query is true.\n",
    "\n",
    "- Backward chaining is goal-directed reasoning. \n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module7_definitions = {\n",
    "\"knowledge base(KB)\" : \"A central component of a knowledge-based agent\", \n",
    "\"inference\" : \"deriving new sentences from the axioms\",\n",
    "\"Logic\" : \"A general class of representations for knowledge-based agents\",\n",
    "\"Ential $\\models$\": \"alpha entails beta, alpha will be more specific and stronger\\\n",
    " if and only if M(α) ⊆ M(β)\" ,\n",
    "\"logical inference \": \"The process using entailment to find the conclusions\",\n",
    "\"Sound\": \"The inference algorithm only derive entailed sentences\",\n",
    "\"Complete\": \"The inference algorithm if it derived all entailed sentences\",\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"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "sG6ERS0g4_df"
   },
   "source": [
    "$\\neg$ not\n",
    "\n",
    "$\\wedge$  and, conjunction, only when P,Q = True, **return**  True, else False\n",
    "\n",
    "$\\vee$ or, disjunction, only when P,Q = False **return**  False else True\n",
    "\n",
    "$\\Rightarrow$ implies, only when P = Ture, Q = False **return** False else True \n",
    "\n",
    "$\\Leftrightarrow$ if and only if, P,Q are same **return**  True else Flase\n",
    "\n",
    "$\\vdash$, A $\\vdash_i$ B，B is derived from A by i \n",
    "\n",
    "A $\\equiv$ B, if and only if A $\t\\vDash$ B and B $\t\\vDash$ A\n",
    "\n",
    "\n",
    "**Logical Equivalence**\n",
    "\n",
    "A $\\wedge$ B $\\equiv$ B $\\wedge$ A\n",
    "\n",
    "A $\\vee$ B $\\equiv$ B $\\vee$ A\n",
    "\n",
    "((A $\\wedge$ B)$ \\wedge$ C $\\equiv$ (A $\\wedge$( B$ \\wedge$ C))\n",
    "\n",
    "((A $\\vee$ B)$ \\vee$ C $\\equiv$ (A $\\vee$( B$ \\vee$ C))\n",
    "\n",
    "A $\\Rightarrow$ B $\\equiv$ ($\\neg$ B $\\Rightarrow$ $\\neg$ A)\n",
    "\n",
    "A $\\Rightarrow$ B $\\equiv$ ($\\neg$ A  $\\vee$ B) IMPLICATION ELIMINATION!!!\n",
    "\n",
    "A $\\Longleftrightarrow$ B $\\equiv$ (A $\\Rightarrow$ B) $\\wedge$ (B $\\Rightarrow$ A) Biconditional elimination!!!\n",
    "\n",
    "$\\neg$(A $\\wedge$ B) $\\equiv$ ($\\neg$A $\\vee$ $\\neg$B), $\\neg$(A $\\vee$ B) $\\equiv$ ($\\neg$A $\\wedge$ $\\neg$B) De Morgan\n",
    "\n",
    "(A $\\wedge$ B) $\\vee$ C $\\equiv$ (A $\\wedge$ B) $\\vee$ (A $\\wedge$ C)\n",
    "\n",
    "(A $\\vee$ B) $\\wedge$ C $\\equiv$ (A $\\vee$ B) $\\wedge$ (A $\\vee$ C)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "FKulMiMUFxFS"
   },
   "source": [
    "```\n",
    "def Resolution Algorithm():\n",
    "  clauses = convert KB and neg alpha into CNF\n",
    "  new = {}\n",
    "  while true :\n",
    "    for each pair C1, C2 in clauses:\n",
    "      resolvents = PL-RESOLVE(C1, C2)\n",
    "      if resolvents contains the empty clause, return true\n",
    "      new.append(resolvents)\n",
    "    if clauses entails new, return false\n",
    "    clauses.append(new)\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 634
    },
    "id": "lXNcHuKjyNXa",
    "outputId": "1cc89ca9-4014-4138-ad0c-c40335811691"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 7: Logical Agents\n",
       "## Module 7 Lecture Notes\n",
       " \n",
       "- A KB contains a set of sentence written in a knowledge representation\n",
       "language which can bedivided into **Axioms** + **Derived sentences**. It has some background information.\n",
       "\n",
       "- A knowledge-based agent can add to the information in the KB and pop KB to\n",
       "derive new \n",
       "\n",
       "- If sentence alpha is true in model m then we say: m satisfies alpha, or\n",
       "m is a model of alpha, M(alpha). e.g. alpha:No water in (1,1), M(alpha): all instances in which (1,1) has no water \n",
       "\n",
       "- The KB is false when any model contradicts the known knowledge.\n",
       "\n",
       "- simpler sentences + parentheses and logical connectives = Complex sentences \n",
       "\n",
       "- CNF(Conjunctive Normal Form): 1. eliminate biconditional 2. IMPLICATION ELIMINATION3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules4. Combination of all the disjuncts and Distribution of ∨ over ∧\n",
       "\n",
       "- The resolution algorithm is complete! \n",
       "\n",
       "- Forward Chaining is data-driven reasoning. With known\n",
       "data, adding premises as new percepts come in, and derive new conclusions(by forward chaining algorithm). It doesn’t have to use a specific query.\n",
       "\n",
       "- Backward chaining works backwards from a query. If the query is true, end Otherwise, the algorithm finds implications in the KB (conclusion in query).If all the premises of one of implicationscan be proved to be true (via backward chaining), then the query is true.\n",
       "\n",
       "- Backward chaining is goal-directed reasoning. \n",
       "\n",
       "\n",
       "## Module 7 Definitions\n",
       "* **Knowledge base(kb)** - A central component of a knowledge-based agent\n",
       "* **Inference** - deriving new sentences from the axioms\n",
       "* **Logic** - A general class of representations for knowledge-based agents\n",
       "* **Ential $\\models$** - alpha entails beta, alpha will be more specific and stronger if and only if M(α) ⊆ M(β)\n",
       "* **Logical inference ** - The process using entailment to find the conclusions\n",
       "* **Sound** - The inference algorithm only derive entailed sentences\n",
       "* **Complete** - The inference algorithm if it derived all entailed sentences\n",
       "* **Definite clause** - disjunction of literals where exactly one is positive\n",
       "* **Horn clause** - disjunction of literals where at most one is positive\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "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",
   "execution_count": 18,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 3841
    },
    "id": "T3cm1WV542_a",
    "outputId": "2f5d9e27-2270-47f5-d25b-7017ce5e6bd7"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 1: Rational Agents and Task Environments\n",
       "## AIMA Chapter 1.1 What is AI?\n",
       " The target of AI: making model think and act rationally and work like people. \n",
       "\n",
       "Turning test aims to check how closly one's answers resemble those a human would give.\n",
       "\n",
       "## AIMA Chapter 27.1 The Limits of AI\n",
       "\n",
       "Model has to be constructed with sensors and actuators. People need give input and interpret the outputs. \n",
       "Another problem is that, they are still dealing with random variables, can not represent objects and relations explicitly. \n",
       "\n",
       "## AIMA Chapter 27.1 Can Machines Really Think?\n",
       " How model deals with general situations?? \n",
       "\n",
       "-Anytime algorithms and decision-theoretic metareasonging\n",
       "\n",
       "## Module 1 Lecture Notes\n",
       " Agent design goal is to construct the agent funcion f which maximize \n",
       "the expected performance measure and design an agent program for a special structure.The hardest Environment is\n",
       "Continuous, Partially Observable, Stochastic and Multiagent\n",
       "\n",
       "## Module 1 Definitions\n",
       "* **Agent** - anything that can perceive and act in an environment\n",
       "* **Percept** - the agent’s perceptual inputs instantly\n",
       "* **Percept sequence** - complete history of perceptions\n",
       "* **Agent function** - agent's behaviors\n",
       "* **A rational agent** - perceives its environment and and behaves rationally, maximize its performance measure\n",
       "* **P, performance measure** - Test if the agent is doing the right decision, safe, fast for car\n",
       "* **E, environment** - road\n",
       "* **A, actuators** - accelerator, brake\n",
       "* **S, sensors** - GPS\n",
       "* **Reflex agents** - selects an action based on the current percept\n",
       "* **A problem-solving agent** - plan ahead, form a sequence of actions as a path, which called as search\n",
       "* **Search problem** - Goal, States, Actions, Performace measure, Solution\n",
       "\n",
       "\n",
       "# Module 2: Python\n",
       "## Module 2 Lecture Notes\n",
       "\n",
       "- Strings start with r will be regarded as a raw string(\\ not work).\n",
       "\n",
       "- Strings are immutable, y.strip() not change x. Lists are mutable, y.append(5) will add 5 to x(COPY). y = x[:] shallow copy, a new object.\n",
       "\n",
       "- Defaultdict will provide a suitable default value for the input keys. \n",
       "\n",
       "- *args accepts non-keyword arguments to the funciton.(only value)\n",
       "\n",
       "- **kwargs accpets different number of variables for the same function.（key - value)\n",
       "\n",
       "- Multiple Inheritance will call the oldest function version. \n",
       "\n",
       "- Generators benefits : Less code, Maintains local state, one-time value computed when needed,save memory, aggregating easily, crucial for infi-sequences, hard to use when check individual value \n",
       "\n",
       "\n",
       "\n",
       "## Module 2 Definitions\n",
       "* **Positive features** - Fast development, Portable(dif platform works), Various bulit-in types(list, dict...), large collection of support libraries(NP,matlab..)\n",
       "* **Fixed/static** - 'test' + 2 not allowed\n",
       "* **Dynamic** - x = 1, x = 'ok' types vary acceptable\n",
       "* **List.remove('a')** - remove the first a\n",
       "\n",
       "\n",
       "# Module 3: Search Problems\n",
       "## Module 3 Lecture Notes\n",
       "\n",
       "- Tree search enumerate all paths fron the initial state(root).\n",
       "\n",
       "- Graph search will check whether the node has been visited before adding to search queue.\n",
       "\n",
       "- Uninformed search: All non-goal nodes have equal weights.\n",
       "\n",
       "- Informed Search: Some nodes are ranked.\n",
       "\n",
       "- Completeness means always find the solution. Optimal means find the best solution.\n",
       "\n",
       "- Breadth-first search: Expand node from shallow to deep, frontier is FIFO\n",
       "\n",
       "- BFS problem: Waste Memory and Time\n",
       "\n",
       "- Depth-first search: Find the deepest uneexpanded node, frontier is LIFO\n",
       "\n",
       "- DFS problem: Cannot deal with infinite paths\n",
       "\n",
       "\n",
       "\n",
       "## Module 3 Definitions\n",
       "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
       "* **Evaluation** - Completeness, Optimality, Time complexity, Space complexity\n",
       "* **B** - maximum branching factor\n",
       "* **D** - depth\n",
       "* **M** - max length\n",
       "* **Bfs properties** - Complete, Optimal, Time $O(b^d)$, Space $O(b^d)$\n",
       "* **Dfs properties** - Not Complete, Not Optimal, Time $O(b^m)$, Space $O(b * d)$\n",
       "* **Depth-limited search** - with depth limit l, Incomplete(l<d), not optimal(l>d), Time $O(b^l)$, Space $O(b * l)$\n",
       "* **Iterative deepening search** - Complete & optimal, Time $O(b^d)$, Space O(bd)\n",
       "\n",
       "\n",
       "# Module 4: Informed Search\n",
       "## Module 4 Lecture Notes\n",
       "\n",
       "- Informed Search uses domain-specific info to be faster than uninformed search\n",
       "\n",
       "- Uniform-cost search: Cost is the number of nodes, all moves equal, search in a cost range\n",
       "\n",
       "- Greedy Best-First Search: Select node with min **f(n) = h(n)**, using priority queue\n",
       "\n",
       "- A* search(best first search): f(n) = g(n)+h(n), cost so far + estimated cost, 0 <= h(n) <= h*(n)\n",
       "\n",
       "- If h(n) is admissible, A* using Tree Search is optimal\n",
       "\n",
       "- The cost of an optimal solution to a relaxed problem is an admissible heuristic for the\n",
       "original problem\n",
       "\n",
       "- If h2 dominates h1, h2 is optimistic and more accurate than h1\n",
       "\n",
       "- A* search is optimal, applies to pathing/video games/ robot motion/ resource planning\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "## Module 4 Definitions\n",
       "* **Optimal solution** - A solution is optimal if no solution has the lowest cost\n",
       "* **State space** - the set of all possible actions\n",
       "* **Frontier** - states which are avaliable for expanding\n",
       "* **H(n) is admissible** - if it never overestimates the cost to reach the goal\n",
       "* **Relaxed problem** - Fewer restrications than original problem\n",
       "* **Dominance** - for all n, h2(n) > h1(n) then h2 dominates h1\n",
       "\n",
       "\n",
       "# Module 5: Adversarial Search and Games\n",
       "## Module 5 Lecture Notes\n",
       " \n",
       "- Game Environment has multiagent. Examples like\n",
       "Chess, Checkers, Go, Mancala, Tic-Tac-Toe, Othello. \n",
       "\n",
       "- four propertiex for game: two players orderly play the game, zero-sum one loss one win, legal moves are clear, results are well defined(win, lose, draw)\n",
       "\n",
       "- More difficult games: stohastic, lack info(Most card games (e.g. Hearts, Bridge and Scrabble),continuous and no pause between rounds, cooperate games\n",
       "\n",
       "- Game search uses tree structure, node represents 'board position', edge -> legal moves\n",
       "\n",
       "- Solving a tree-structued CSP takes linear time in the number of variables\n",
       "- Evaluation function f(n) > 0, max wins at position n\n",
       "\n",
       "- MinMax rule: best moves. If MIN not move optimally, MAX will be better. \n",
       "\n",
       "- Pruning Stop condition: {MAX} v >= beta, MIN never choose that MAX node {MIN} v <= alpha MAx never select MIN node. \n",
       "\n",
       "- Expectimax Search： Uncertain outcomes, unpredictable opponents, actions may fail. Compute the average score. \n",
       "\n",
       "-The key idea behind inference in CSPs is enforcing k- consistency\n",
       "\n",
       "\n",
       "\n",
       "## Module 5 Definitions\n",
       "* **Static** - No change while agent considering\n",
       "* **Discrete** -  A finite set of percepts and actions.\n",
       "* **Fully observable** - Complete state of environment got by sensor\n",
       "* **Strategic** - current state + action + another agent makes the next state\n",
       "* **$alpha$** - MAX lower bound\n",
       "* **$beta$** - MIN upper bound\n",
       "* **Objectivist / frequentist answer** -  Averages over repeated experiments， summrized from history(rolling dice)\n",
       "* **Subjectivist / bayesian answer** - Degrees of belief about unobserved variables, give predictions for unobserved data(guess tomorrow raining)\n",
       "\n",
       "\n",
       "# Module 6: Constraint Satisfaction Problems\n",
       "## Module 6 Lecture Notes\n",
       "  \n",
       "- Search Assumptions: a single agent, deterministic actions, fully\n",
       "observed state, discrete state space\n",
       "\n",
       "- CSP: Finite set of variables and constraints, nonempty domain of possible values. \n",
       "- CSP application: Map Coloring, Scheuling problems, Floor planning for VLSI, Sudoku\n",
       "\n",
       "- CSP Benefits: Clean specifications and generic goal, find the violates variables, auto - prune off\n",
       "\n",
       "- CSP variables: discrete variables(finite: Boolean, n variables | infinite: int/string <= ), continuous variables(start/end time, linear)\n",
       "\n",
       "- Varieties Constraints: Unary, Binary, Higher-order(crypt-arithmetic column constraints), Preference(A is btter than B)\n",
       "\n",
       "- CSP Structure: Initial State + Successor function + Goal test(reach goal) + Path Cost(constant cost/step)\n",
       "\n",
       "- Improving backtracking efficiency focuses on the most constrained variable first and try the least constriaining value.**Forward checking can detect failure early**\n",
       "\n",
       "- Minimum remaining values (MRV) starts with the least legal values(lowest number of choices)\n",
       "\n",
       "- Forward checking stops when any unassigned variable has no choices value and it doesn't provide\n",
       "early detection for all failures\n",
       "\n",
       "- Local consistency -> Node consistency: satisfies unary constraints\n",
       "\n",
       "- Arc consistency -> satisfies binary constraints wchich can be run as a preprocessor or after each assignment\n",
       "\n",
       "- For one pair of arcs, it has two arcs connected them\n",
       "\n",
       "- X -> Y is consistent if every value x of X there is some allowed y. If X loses a value(Y has no consistent value for X), recheck neighbors of X.\n",
       "\n",
       "- With d values, it takes O($b ^ d$) time as the worst case\n",
       "\n",
       "- Waltz algorithm interprets line drawings of solid polyhedra as 3D objects. Variable, each intersection. \n",
       "\n",
       "- Inefficiences: 1. only check Xi which has lost a value 2. no need to check Yj if lose because Yj 3. only\n",
       "need to check that (j,i) is still arc-consistent.\n",
       "\n",
       "- Each of n nodes must be compared against n-1 other nodes, 2*n*(n-1), O($n ^ 2$) num of comparision\n",
       "\n",
       "- d values, check arc(i, j), O($d^2$)\n",
       "\n",
       "- Insert arc(i,j) d times, O($n^2d^3$)\n",
       "\n",
       "\n",
       "## Module 6 Definitions\n",
       "* **Consistent** - assignment doesn't violate constraints\n",
       "* **Complete** - Every variable is assigned (Sudoku)\n",
       "* **Solution of csp** - Consistent + Complete\n",
       "* **Backtracking search** - Depth-first search for CSPs with single-variable assignments(basic uninformed algorithm)\n",
       "\n",
       "\n",
       "# Module 7: Logical Agents\n",
       "## Module 7 Lecture Notes\n",
       " \n",
       "- A KB contains a set of sentence written in a knowledge representation\n",
       "language which can bedivided into **Axioms** + **Derived sentences**. It has some background information.\n",
       "\n",
       "- A knowledge-based agent can add to the information in the KB and pop KB to\n",
       "derive new \n",
       "\n",
       "- If sentence alpha is true in model m then we say: m satisfies alpha, or\n",
       "m is a model of alpha, M(alpha). e.g. alpha:No water in (1,1), M(alpha): all instances in which (1,1) has no water \n",
       "\n",
       "- The KB is false when any model contradicts the known knowledge.\n",
       "\n",
       "- simpler sentences + parentheses and logical connectives = Complex sentences \n",
       "\n",
       "- CNF(Conjunctive Normal Form): 1. eliminate biconditional 2. IMPLICATION ELIMINATION3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules4. Combination of all the disjuncts and Distribution of ∨ over ∧\n",
       "\n",
       "- The resolution algorithm is complete! \n",
       "\n",
       "- Forward Chaining is data-driven reasoning. With known\n",
       "data, adding premises as new percepts come in, and derive new conclusions(by forward chaining algorithm). It doesn’t have to use a specific query.\n",
       "\n",
       "- Backward chaining works backwards from a query. If the query is true, end Otherwise, the algorithm finds implications in the KB (conclusion in query).If all the premises of one of implicationscan be proved to be true (via backward chaining), then the query is true.\n",
       "\n",
       "- Backward chaining is goal-directed reasoning. \n",
       "\n",
       "\n",
       "## Module 7 Definitions\n",
       "* **Knowledge base(kb)** - A central component of a knowledge-based agent\n",
       "* **Inference** - deriving new sentences from the axioms\n",
       "* **Logic** - A general class of representations for knowledge-based agents\n",
       "* **Ential $\\models$** - alpha entails beta, alpha will be more specific and stronger if and only if M(α) ⊆ M(β)\n",
       "* **Logical inference ** - The process using entailment to find the conclusions\n",
       "* **Sound** - The inference algorithm only derive entailed sentences\n",
       "* **Complete** - The inference algorithm if it derived all entailed sentences\n",
       "* **Definite clause** - disjunction of literals where exactly one is positive\n",
       "* **Horn clause** - disjunction of literals where at most one is positive\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title\n",
    "# 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))"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "CIS midterm notes",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
