{
  "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": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lzaavW96tcxM",
        "outputId": "344222ad-a216-45e3-9726-b566dead59fe"
      },
      "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": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8DvZ57A-djo1",
        "outputId": "ef81cd11-e574-43c8-fb57-4c2e2e3d803c"
      },
      "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": null,
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "outputs": [],
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 33,
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Chapter 1.1 summary. \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Agents specified by an agent fucntion that maps percepts onto actions. \n",
        "Agents can be anything that perceives its environment through sensors and acts upon that environment with actuators.\n",
        " How do we measure if a rational agent is doing the right thing? Create a performance measure.\n",
        " Performances measures will be more successful if they specify what should be done rather than how you think the agent should act.\n",
        " Rational agents are not necessarily omniscent, so can only act to maximize EXPECTED value of performance measure\n",
        " Most difficult environment would be: continuous, partially observable, stochastic, multiagent\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "  \"Turing Test: can a human decide whether responses are from a machine or a human\"\n",
        "  \"Chinese Room: Example of how turing test isn't real intelligence\"\n",
        "  \"agent\" : \"anything that can perceive and act in an environment (Architecture + program)\",\n",
        "  \"percept\" : \"agents perceptual inputs at an instance\",\n",
        "\"Rational Agent\" : \"an agent that percieves the env and does the right thing by maximizing expected val of performance measure\",\n",
        "\"Task environment.\": \"performance measure, environment, actuators, sensors\",\n",
        "\"Reflex agent\" : \"Act soley on current precept and ignores history\",\n",
        "\"Problem solving agent\": \"Plans ahead, considers sequence of actions that form path to goal\"\n",
        "}\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": 34,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 844
        },
        "id": "gYYeNcdM_maE",
        "outputId": "c2f1c34e-4d87-4373-9d91-91af1921ab17"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " Chapter 1.1 summary. \n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " Agents specified by an agent fucntion that maps percepts onto actions. \n",
              "Agents can be anything that perceives its environment through sensors and acts upon that environment with actuators.\n",
              " How do we measure if a rational agent is doing the right thing? Create a performance measure.\n",
              " Performances measures will be more successful if they specify what should be done rather than how you think the agent should act.\n",
              " Rational agents are not necessarily omniscent, so can only act to maximize EXPECTED value of performance measure\n",
              " Most difficult environment would be: continuous, partially observable, stochastic, multiagent\n",
              "\n",
              " \n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Turing test: can a human decide whether responses are from a machine or a humanchinese room: example of how turing test isn't real intelligenceagent** - anything that can perceive and act in an environment (Architecture + program)\n",
              "* **Percept** - agents perceptual inputs at an instance\n",
              "* **Rational agent** - an agent that percieves the env and does the right thing by maximizing expected val of performance measure\n",
              "* **Task environment.** - performance measure, environment, actuators, sensors\n",
              "* **Reflex agent** - Act soley on current precept and ignores history\n",
              "* **Problem solving agent** - Plans ahead, considers sequence of actions that form path to goal\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": 48,
      "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 = \"\"\" STRINGS: immutable, == is equality, 'is' is same object, methods return new string (cause immutable)\n",
        "LISTS: mutable, y=x[:] will shallow copy an list, x.append is inplace (Same for most methods (insert, count, remove, reverse, sort, etc.)), mixed types\n",
        "TUPLE: immutable, ordered, mixed types\n",
        "DICTIONARIES: keys must be hashable (immutable), unordered, d.keys for keys, d.values() for vals, d.items() gives list of item tuples,\n",
        "from collections import defaultdict automatically initializes nonexistance dictionary values: \n",
        "e.g. \n",
        "```\n",
        ">>d=defaultdict(str)\n",
        ">>d['a']\n",
        "\"\"\n",
        "```\n",
        "from collections import Counter automatically initializes nonextistance values to 0: e.g. \n",
        "```\n",
        ">>d=Counter()\n",
        ">>d['a']\n",
        "0\n",
        ">>d['dog'] += 10\n",
        ">>d['dog']\n",
        "10\n",
        "```\n",
        "FUNCTIONS: can return like: ret1, ret2, ret3. it returns a tuple. cannot overload functions. can provide default values. keyword arguments allow out of order, but have to be after all other arguments\n",
        "```\n",
        "def fun(*args):\n",
        "  print(args)\n",
        "\n",
        ">>fun(1, 2, 3, 4)\n",
        "(1,2,3,4)\n",
        "```\n",
        "accepts a variable number of arguments.\n",
        "\n",
        "```\n",
        "def kfun(**kwargs):\n",
        "  print(kwargs)\n",
        ">>kfun(x=\"a\", y=\"b\", z=\"c\")\n",
        "{\"x\": \"a\", \"y\": \"b\", \"z\": \"c\"}\n",
        "```\n",
        "accepts a variable number of keyword arguments\n",
        "\n",
        "default parameter values are evaluated only when def statement is first being executed\n",
        "```\n",
        "def prime(n, prime=[]):\n",
        "  if n == 0:\n",
        "    return prime\n",
        "  if n is prime:\n",
        "    prime.append(n)\n",
        "  return prime(n-1)\n",
        "\n",
        "prime(11)\n",
        "# 11, 7, 5, 3, 2, 1\n",
        "```\n",
        "SUBCLASSES:\n",
        "to define subclass put name in parenthesis\n",
        "e.g.\n",
        "```\n",
        "def Bird(Animal):\n",
        "  ....\n",
        "```\n",
        "LIST COMPREHENSION:\n",
        "to use if statements in list comprehension:\n",
        "```\n",
        "[x*x for x in range(10) if x % 2 == 0]\n",
        "# will be squares of even numbers\n",
        "[x*x if x % 2 == 0 else x for x in range(10)]\n",
        "# will be squares of evens and plain odds\n",
        "```\n",
        "ITERATORS: anything that can be iterated over has an iterator method\n",
        "GENERATORS: gens are iterators. fucntions that use yield automatically return generator when called\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6DvicR0oyTr0"
      },
      "source": []
    },
    {
      "cell_type": "code",
      "execution_count": 49,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "ydOK__lwWgdp",
        "outputId": "e23f8fb0-ed41-4c43-a988-4f3bb1af5c7b"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              " STRINGS: immutable, == is equality, 'is' is same object, methods return new string (cause immutable)\n",
              "LISTS: mutable, y=x[:] will shallow copy an list, x.append is inplace (Same for most methods (insert, count, remove, reverse, sort, etc.)), mixed types\n",
              "TUPLE: immutable, ordered, mixed types\n",
              "DICTIONARIES: keys must be hashable (immutable), unordered, d.keys for keys, d.values() for vals, d.items() gives list of item tuples,\n",
              "from collections import defaultdict automatically initializes nonexistance dictionary values: \n",
              "e.g. \n",
              "```\n",
              ">>d=defaultdict(str)\n",
              ">>d['a']\n",
              "\"\"\n",
              "```\n",
              "from collections import Counter automatically initializes nonextistance values to 0: e.g. \n",
              "```\n",
              ">>d=Counter()\n",
              ">>d['a']\n",
              "0\n",
              ">>d['dog'] += 10\n",
              ">>d['dog']\n",
              "10\n",
              "```\n",
              "FUNCTIONS: can return like: ret1, ret2, ret3. it returns a tuple. cannot overload functions. can provide default values. keyword arguments allow out of order, but have to be after all other arguments\n",
              "```\n",
              "def fun(*args):\n",
              "  print(args)\n",
              "\n",
              ">>fun(1, 2, 3, 4)\n",
              "(1,2,3,4)\n",
              "```\n",
              "accepts a variable number of arguments.\n",
              "\n",
              "```\n",
              "def kfun(**kwargs):\n",
              "  print(kwargs)\n",
              ">>kfun(x=\"a\", y=\"b\", z=\"c\")\n",
              "{\"x\": \"a\", \"y\": \"b\", \"z\": \"c\"}\n",
              "```\n",
              "accepts a variable number of keyword arguments\n",
              "\n",
              "default parameter values are evaluated only when def statement is first being executed\n",
              "```\n",
              "def prime(n, prime=[]):\n",
              "  if n == 0:\n",
              "    return prime\n",
              "  if n is prime:\n",
              "    prime.append(n)\n",
              "  return prime(n-1)\n",
              "\n",
              "prime(11)\n",
              "# 11, 7, 5, 3, 2, 1\n",
              "```\n",
              "SUBCLASSES:\n",
              "to define subclass put name in parenthesis\n",
              "e.g.\n",
              "```\n",
              "def Bird(Animal):\n",
              "  ....\n",
              "```\n",
              "LIST COMPREHENSION:\n",
              "to use if statements in list comprehension:\n",
              "```\n",
              "[x*x for x in range(10) if x % 2 == 0]\n",
              "# will be squares of even numbers\n",
              "[x*x if x % 2 == 0 else x for x in range(10)]\n",
              "# will be squares of evens and plain odds\n",
              "```\n",
              "ITERATORS: anything that can be iterated over has an iterator method\n",
              "GENERATORS: gens are iterators. fucntions that use yield automatically return generator when called\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - your definition here\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": 50,
      "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 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_4 = \"\"\" Dijkstra’s algorithm == uniform-cost search \n",
        "bidirectional search searches from both the initial state and the goal state at the same time and hopes that the two ends will meet\n",
        "bidirectional is complete, optimal, time=space=O(b^(d/2))\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Search problem definition:\n",
        "```\n",
        "1. States: set S\n",
        "2. Initial state: si in S\n",
        "3. Actions: set A\n",
        "4. Transition model: V s, V a in Actions(s), Result(s, a) -> sr (sr is successor of s)\n",
        "5. Path cost: Must be additive\n",
        "6. Goal test: Goal(s)\n",
        "```\n",
        "TREE SEARCH: root=initial state, nodes generated with transition model.\n",
        "state vs node. States do not have parents, children, depth, or path cost. They just represnt a physical config of the problem\n",
        "Problem: repeated states can turn a linear problem into an exponential one\n",
        "GRAPH SEARCH: modified tree search. check to see if a node has been visited before adding to search queue\n",
        "\n",
        "```\n",
        "\n",
        "```\n",
        "\n",
        "BREADTH-FIRST SEARCH: expand shallowest unexpanded node (FIFO frontier). Complete, optimal (if cost = 1 per step), time=O(b^d), space=O(b^d)\n",
        "DEPTH-FIRST SEARCH: expand deepest unexpanded node (LIFE frontier). Not complete (infinite depth and loops bad), not optimal, time=O(b^m), space=O(b*m)\n",
        "\n",
        "```\n",
        "\n",
        "```\n",
        "\n",
        "BFS vs DFS: DFS if limited space, many soln with long paths and wrong paths terminate quickly. BFS if infinite paths, soln with short paths, can discard unlikely paths quickly\n",
        "\n",
        "```\n",
        "\n",
        "```\n",
        "Depth-limited search: DFS but with limit l (no infinite path issue). If l=d then optimal. if l < d, then incomplete. if l > d, not optimal. time=O(b^l), space=O(bl)\n",
        "\n",
        "```\n",
        "\n",
        "```\n",
        "Iterative deepening search: use DLsearch as subroutine with increasing l (i.e. for l in [0, inf]: dfl at level l). Complete and optimal. Time=O(b^d), space=O(bd)\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",
        "\"solution\" : \"sequence of actions from the initial state to a goal state\",   \n",
        "\"optimal solution\" : \"a solution with the lowest path cost among all solutions\" ,\n",
        "\"Uninformed search\" : \"all non-goal nodes look equally as good (only has info from problem definition)\",\n",
        "\"completeness\" :\"does search always find a soln if it exists and return properly when it doesn't\",\n",
        "\"optimal\" : \"does search find optimal soln\",\n",
        "\"time complexity\" : \"number of nodes generated\",\n",
        "\"space complexity\" : \"number of nodes simultaneously in memory\",\n",
        "\"b\": \"maximum branching factor of search tree\",\n",
        "\"d\": \"depth of shallowest goal node\",\n",
        "\"m\": \"max len of any path in state space (could be infinite)\" \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 51,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 986
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "b0f0f673-3635-4235-9fe7-3e07fa110986"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              " Dijkstra’s algorithm == uniform-cost search \n",
              "bidirectional search searches from both the initial state and the goal state at the same time and hopes that the two ends will meet\n",
              "bidirectional is complete, optimal, time=space=O(b^(d/2))\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              " Search problem definition:\n",
              "```\n",
              "1. States: set S\n",
              "2. Initial state: si in S\n",
              "3. Actions: set A\n",
              "4. Transition model: V s, V a in Actions(s), Result(s, a) -> sr (sr is successor of s)\n",
              "5. Path cost: Must be additive\n",
              "6. Goal test: Goal(s)\n",
              "```\n",
              "TREE SEARCH: root=initial state, nodes generated with transition model.\n",
              "state vs node. States do not have parents, children, depth, or path cost. They just represnt a physical config of the problem\n",
              "Problem: repeated states can turn a linear problem into an exponential one\n",
              "GRAPH SEARCH: modified tree search. check to see if a node has been visited before adding to search queue\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "\n",
              "BREADTH-FIRST SEARCH: expand shallowest unexpanded node (FIFO frontier). Complete, optimal (if cost = 1 per step), time=O(b^d), space=O(b^d)\n",
              "DEPTH-FIRST SEARCH: expand deepest unexpanded node (LIFE frontier). Not complete (infinite depth and loops bad), not optimal, time=O(b^m), space=O(b*m)\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "\n",
              "BFS vs DFS: DFS if limited space, many soln with long paths and wrong paths terminate quickly. BFS if infinite paths, soln with short paths, can discard unlikely paths quickly\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "Depth-limited search: DFS but with limit l (no infinite path issue). If l=d then optimal. if l < d, then incomplete. if l > d, not optimal. time=O(b^l), space=O(bl)\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "Iterative deepening search: use DLsearch as subroutine with increasing l (i.e. for l in [0, inf]: dfl at level l). Complete and optimal. Time=O(b^d), space=O(bd)\n",
              " \n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Solution** - sequence of actions from the initial state to a goal state\n",
              "* **Optimal solution** - a solution with the lowest path cost among all solutions\n",
              "* **Uninformed search** - all non-goal nodes look equally as good (only has info from problem definition)\n",
              "* **Completeness** - does search always find a soln if it exists and return properly when it doesn't\n",
              "* **Optimal** - does search find optimal soln\n",
              "* **Time complexity** - number of nodes generated\n",
              "* **Space complexity** - number of nodes simultaneously in memory\n",
              "* **B** - maximum branching factor of search tree\n",
              "* **D** - depth of shallowest goal node\n",
              "* **M** - max len of any path in state space (could be infinite)\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": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 52,
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" CONSISTENCY: h(n) ≤ c(n,a,n′)+h(n′). Every consistent heuristic is admissable.\n",
        "BEAM SEARCH: limit size of frontier to save memory.\n",
        "ITERATIVE DEEPENING ASTAR SEARCH: benefits of a* without memory needs\n",
        "RECURSIVE BEST FIRST SEARCH: BFS but with linear space \n",
        "Weighted A∗ search focuses the search towards a goal, expanding fewer nodes,\n",
        "but sacrificing optimality\"\"\"\n",
        "chapter3_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "UNIFORM COST SEARCH: alg for traversing weighted tree. expand node with lowest path cost. test if a node is a goal state when it is selected for expansion, not when added to frontier.\n",
        "```\n",
        "\n",
        "```\n",
        "BEST FIRST SEARCH: nodes selected for expansion based on eval func f(n) (heuristic)\n",
        "```\n",
        "\n",
        "```\n",
        "GREEDY BEST FIRST SEARCH: expands node that is estimated to be closest to the goal. ignores g(n)\n",
        "```\n",
        "\n",
        "```\n",
        "A STAR SEARCH: best known Best-first search. f(n) = g(n) + h(n). heuristic must be admissible (doesn't overestimate cost to reach the goal)\n",
        "How to come up with heuristics: relax the problem. Cost of an optimal soln to a relaxed problem is an admissible heuristic for original problem.\n",
        "a relaxed problem is one with fewer restrictions on the actions. e.g. in tile game, if we can move tile anywhere, or if we could move tile to any adjacent square those would both be relaxed problems\n",
        "```\n",
        "\n",
        "```\n",
        "DOMINANCE: if h2(n) >= h1(n) for all n and both are admissible, then h2 dominates h1\n",
        "h* is the true distance to the goal and is the perfect heuristic (it is unachievable)\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 53,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 527
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "e24c26e1-dbf6-43f4-ab2e-3b3200e9bd02"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              " CONSISTENCY: h(n) ≤ c(n,a,n′)+h(n′). Every consistent heuristic is admissable.\n",
              "BEAM SEARCH: limit size of frontier to save memory.\n",
              "ITERATIVE DEEPENING ASTAR SEARCH: benefits of a* without memory needs\n",
              "RECURSIVE BEST FIRST SEARCH: BFS but with linear space \n",
              "Weighted A∗ search focuses the search towards a goal, expanding fewer nodes,\n",
              "but sacrificing optimality\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " \n",
              "UNIFORM COST SEARCH: alg for traversing weighted tree. expand node with lowest path cost. test if a node is a goal state when it is selected for expansion, not when added to frontier.\n",
              "```\n",
              "\n",
              "```\n",
              "BEST FIRST SEARCH: nodes selected for expansion based on eval func f(n) (heuristic)\n",
              "```\n",
              "\n",
              "```\n",
              "GREEDY BEST FIRST SEARCH: expands node that is estimated to be closest to the goal. ignores g(n)\n",
              "```\n",
              "\n",
              "```\n",
              "A STAR SEARCH: best known Best-first search. f(n) = g(n) + h(n). heuristic must be admissible (doesn't overestimate cost to reach the goal)\n",
              "How to come up with heuristics: relax the problem. Cost of an optimal soln to a relaxed problem is an admissible heuristic for original problem.\n",
              "a relaxed problem is one with fewer restrictions on the actions. e.g. in tile game, if we can move tile anywhere, or if we could move tile to any adjacent square those would both be relaxed problems\n",
              "```\n",
              "\n",
              "```\n",
              "DOMINANCE: if h2(n) >= h1(n) for all n and both are admissible, then h2 dominates h1\n",
              "h* is the true distance to the goal and is the perfect heuristic (it is unachievable)\n",
              " \n",
              "\n",
              "## Module 4 Definitions\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": 54,
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Simplest multiagent env: static (no change while one agent acts), discrete (finite set of percepts and actions), fully observable (we know the complete state of the environment), strategic (the next state is determined by the current state and the action of the agent and the actions of one other agent) \n",
        "Simple game: players alternate moves, zero-sum, clear set of legal moves, well defined outcomes (W, L, T)\n",
        "More complex games: stochastic (e.g. bananagrams), not fully observable (e.g. card games), RTS (continuous)\n",
        "```\n",
        "\n",
        "```\n",
        "MIN AND MAX Nodes:\n",
        "two players, MAX and MIN. Games is computed from MAXs POV. when MAX moves, try to maximize MAX outcome. when MIN moves, try to minimize MAXs outcome.\n",
        "evaltuation function: evaluates how good a board is for either player based only on state of current board\n",
        "\n",
        "```\n",
        "\n",
        "```\n",
        "MINIMAX: addume your oponenet makes the optimal move. each node is defined as either max or min of its children\n",
        "Even if your opponenent acts inoptimally, you will still do well.\n",
        "```\n",
        "\n",
        "```\n",
        "ALPHA BETA PRUNING:\n",
        "alpha is maxes current lower bound of max's outcome.\n",
        "beta is mins current upper bound on Min's outcome.\n",
        "MAX will never allow a move that would lead to a worse score than alpha.\n",
        "MIN will never allow a move that would lead to a better score than beta.\n",
        "When evaluating a MAX node and find val v, MIN will never select v >= beta. Thus can stop evaluating that node.\n",
        "When evaluating a MIN node and find val v, MAX will never select v <= alpha. Thus can stop evaluating that node.\n",
        "```\n",
        "\n",
        "```\n",
        "EXPECTIMAX: MINIMAX but you weight by the chance of going down each path\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 55,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 919
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "29346db3-48d9-4412-c5f6-72c1f7f13130"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " Simplest multiagent env: static (no change while one agent acts), discrete (finite set of percepts and actions), fully observable (we know the complete state of the environment), strategic (the next state is determined by the current state and the action of the agent and the actions of one other agent) \n",
              "Simple game: players alternate moves, zero-sum, clear set of legal moves, well defined outcomes (W, L, T)\n",
              "More complex games: stochastic (e.g. bananagrams), not fully observable (e.g. card games), RTS (continuous)\n",
              "```\n",
              "\n",
              "```\n",
              "MIN AND MAX Nodes:\n",
              "two players, MAX and MIN. Games is computed from MAXs POV. when MAX moves, try to maximize MAX outcome. when MIN moves, try to minimize MAXs outcome.\n",
              "evaltuation function: evaluates how good a board is for either player based only on state of current board\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "MINIMAX: addume your oponenet makes the optimal move. each node is defined as either max or min of its children\n",
              "Even if your opponenent acts inoptimally, you will still do well.\n",
              "```\n",
              "\n",
              "```\n",
              "ALPHA BETA PRUNING:\n",
              "alpha is maxes current lower bound of max's outcome.\n",
              "beta is mins current upper bound on Min's outcome.\n",
              "MAX will never allow a move that would lead to a worse score than alpha.\n",
              "MIN will never allow a move that would lead to a better score than beta.\n",
              "When evaluating a MAX node and find val v, MIN will never select v >= beta. Thus can stop evaluating that node.\n",
              "When evaluating a MIN node and find val v, MAX will never select v <= alpha. Thus can stop evaluating that node.\n",
              "```\n",
              "\n",
              "```\n",
              "EXPECTIMAX: MINIMAX but you weight by the chance of going down each path\n",
              "\n",
              "\n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Concept** - definition\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": 56,
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" global constraint = arbitrary num of vars \"\"\"\n",
        "chapter6_2 = \"\"\" node consistency: k=1, arc consistency: k=2, path consistency: k=3, strong k-consistent is k-1, ...2, 1 consistent \"\"\"\n",
        "chapter6_3 = \"\"\" MAC = maintaining arc consistency (recursively propogates constrains unlike forward checking) \"\"\"\n",
        "chapter6_4 = \"\"\" constraint weighing: concentrate serach on important constraints\"\"\"\n",
        "chapter6_5 = \"\"\" Cutset condidtioning: reduce constraint graph to a tree by assigning values to variables so that the remaining var form a tree\n",
        "Tree decomposition: transformation of the original graph into a tree where each node consists of a set of variables\n",
        "symmetry-breaking constraint: used to cut down on possible soln \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" CONSTRAINT SATISFACTION PROBLEMS: represent contrainst that soln must satisfy in declarative language, thus we can find soln to problems with generalized algorithms. \n",
        "```\n",
        "CSP:\n",
        "Finite set of var: X1, X2, .... Xn\n",
        "Nonempty domain of possible val for each var: D1, D2, ...Dn Di = {v1,...vk}\n",
        "Finite set of constraints: C1, C2, ... Cm\n",
        "constraints limit val that var can take. e.g. X1 != X2\n",
        "```\n",
        "CSP is complete when every variable is assigned a value. A solution is a complete and consistent assignment.\n",
        "\n",
        "CSP REPRESENTATIONS: Constraint graph: Nodes are var, arcs are binary constraints\n",
        "\n",
        "TYPES OF CONSTRAINTS: UNARY: constraint involves one var (e.g. X1 != Blue). BINARY: Constraint involves two var (e.g. X1 != X2). PREFERENCE can be represented by cost for variable assignment\n",
        "\n",
        "```\n",
        "\n",
        "```\n",
        "CSP AS SEARCH PROBLEM: n var of domain size d. Branching factor = n*d, then n-1*d, etc. n!*d^n leaves. can always use DFS as soln is always at same depth. Var assignment is commutative (X1=Blue then X2=Green equals X2=Green then X1=Blue), thus tree search not graph search. \n",
        "\n",
        "IMPROVING EFF: Heuristics for backtracking. E.g. which var should be assigned next: Most constrained var (tie: most constraining variable). e.g what order should var's vals be tried: least constraining value. E.g. Check inevitable failure early (Forward checking)\n",
        "\n",
        "```\n",
        "\n",
        "```\n",
        "FORWARD CHECKING: keep track of remaining vals for open vars. Stop search if any unassigned var is out of moves\n",
        "\n",
        "```\n",
        "\n",
        "```\n",
        "CONSTRAINT PROPOGATION: goes beyond forward checking and repeatedly enforces constraints.\n",
        "INFERENCE: eliminates value for a var if the val would violate local consistency.\n",
        "ARC-CONSISTENCY: Xi arc-consistent with Xj if every val in Di has some value in Dj that satisfies the binary constraint\n",
        "AC-3: 1. Only examine Xi where at least one neighbor of Xi has lost a val in previous iteration. 2. If Xi loses a value only because of arc inconsistencies with Yj, don't need to check Yj on next iter. 3. Removing a val on Xi can only make Yj arc-inconsistent with respect to Xi itself, thus only need to check that (j, i) is arc-consistent.\n",
        "Worst case complexity: O(n^2*d^3)\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"BACKTRACKING\" : \"DFS for CSPs with single variable assignments. DFS chooses vals for var. Stops when var has no more assignments\",    \n",
        "\"NODE CONSISTENCY\": \"satisfies unary constraints (trivial)\",\n",
        "\"ARC CONSISTENCY\":\"satisfies binary constraints \"\n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 57,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "79f5f113-4004-4e8c-c707-e3de08209898"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              " global constraint = arbitrary num of vars \n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              " node consistency: k=1, arc consistency: k=2, path consistency: k=3, strong k-consistent is k-1, ...2, 1 consistent \n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " MAC = maintaining arc consistency (recursively propogates constrains unlike forward checking) \n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              " constraint weighing: concentrate serach on important constraints\n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " Cutset condidtioning: reduce constraint graph to a tree by assigning values to variables so that the remaining var form a tree\n",
              "Tree decomposition: transformation of the original graph into a tree where each node consists of a set of variables\n",
              "symmetry-breaking constraint: used to cut down on possible soln \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              " CONSTRAINT SATISFACTION PROBLEMS: represent contrainst that soln must satisfy in declarative language, thus we can find soln to problems with generalized algorithms. \n",
              "```\n",
              "CSP:\n",
              "Finite set of var: X1, X2, .... Xn\n",
              "Nonempty domain of possible val for each var: D1, D2, ...Dn Di = {v1,...vk}\n",
              "Finite set of constraints: C1, C2, ... Cm\n",
              "constraints limit val that var can take. e.g. X1 != X2\n",
              "```\n",
              "CSP is complete when every variable is assigned a value. A solution is a complete and consistent assignment.\n",
              "\n",
              "CSP REPRESENTATIONS: Constraint graph: Nodes are var, arcs are binary constraints\n",
              "\n",
              "TYPES OF CONSTRAINTS: UNARY: constraint involves one var (e.g. X1 != Blue). BINARY: Constraint involves two var (e.g. X1 != X2). PREFERENCE can be represented by cost for variable assignment\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "CSP AS SEARCH PROBLEM: n var of domain size d. Branching factor = n*d, then n-1*d, etc. n!*d^n leaves. can always use DFS as soln is always at same depth. Var assignment is commutative (X1=Blue then X2=Green equals X2=Green then X1=Blue), thus tree search not graph search. \n",
              "\n",
              "IMPROVING EFF: Heuristics for backtracking. E.g. which var should be assigned next: Most constrained var (tie: most constraining variable). e.g what order should var's vals be tried: least constraining value. E.g. Check inevitable failure early (Forward checking)\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "FORWARD CHECKING: keep track of remaining vals for open vars. Stop search if any unassigned var is out of moves\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "CONSTRAINT PROPOGATION: goes beyond forward checking and repeatedly enforces constraints.\n",
              "INFERENCE: eliminates value for a var if the val would violate local consistency.\n",
              "ARC-CONSISTENCY: Xi arc-consistent with Xj if every val in Di has some value in Dj that satisfies the binary constraint\n",
              "AC-3: 1. Only examine Xi where at least one neighbor of Xi has lost a val in previous iteration. 2. If Xi loses a value only because of arc inconsistencies with Yj, don't need to check Yj on next iter. 3. Removing a val on Xi can only make Yj arc-inconsistent with respect to Xi itself, thus only need to check that (j, i) is arc-consistent.\n",
              "Worst case complexity: O(n^2*d^3)\n",
              "\n",
              "\n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Backtracking** - DFS for CSPs with single variable assignments. DFS chooses vals for var. Stops when var has no more assignments\n",
              "* **Node consistency** - satisfies unary constraints (trivial)\n",
              "* **Arc consistency** - satisfies binary constraints \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": 58,
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" KNOWLEDGE BASE: set of sentences that are written in a knowledge representation language. These sentences contain some assertations about the world.\n",
        "SENTENCES: axioms=sentence that is given. derived sentences=sentence that is derived from other sentences (inference).\n",
        "```\n",
        "\n",
        "```\n",
        "MODELS: mathematical abstractions that have a fixed set of truth values for each sentence.\n",
        "if a sentence alpha is true in model m, then m satisfies alpha or m is a model of alpha. M(alpha)=set of all models of alpha\n",
        "```\n",
        "\n",
        "```\n",
        "Inference rules: a->b,a/b | a and b / a | a <-> b / (a->b) and (b->a)\n",
        "```\n",
        "\n",
        "```\n",
        "Monotonicity implies soundness: adding information to the KB does not invalidate any information that has already been inferred.\n",
        "\n",
        "```\n",
        "\n",
        "```\n",
        "CONJUNCTIVE NORMAL FORM (CNF): Everything is a conjunction of clauses\n",
        "```\n",
        "1. Eliminate <=>. a <=> b becomes (a =>b) and (b=>a)\n",
        "2. Eliminate =>. a=>b becomes -a || b\n",
        "3. Move - inwards. Eliminate double negation and apply demorgan\n",
        "4. Apply distributivity to distribute or over and whenever possible\n",
        "```\n",
        "```\n",
        "\n",
        "```\n",
        "RESOLUTION ALG: To show KB entails a, show that KB and not a is unsatisfiable.\n",
        "```\n",
        "1. convert KB and not a into CNF\n",
        "2. Apply resolution rule to resulting clauses\n",
        "3. Resolve every pair that contains complementary literals to produce a new clause\n",
        "4. If new clause isn't already present add it to the set.\n",
        "5. Continue until...\n",
        "a. no new clauses can be added. Thus KB does not ential a\n",
        "b. two clauses resolve to yield the empty clause. thus kb does not entail a\n",
        "```\n",
        "\n",
        "```\n",
        "\n",
        "```\n",
        "\n",
        "not A or not B or C equivalent to A and B => C\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"ENTAILMENT\" : \"alpha entails beta if alpha follows logically from beta (|a| <= |b|)\",    \n",
        "\"SOUND\":\"inference alg should only derive entailed sentences\",\n",
        "\"COMPLETE\": \"if alg can derive all entailed sentences\",\n",
        "\"HORN Clause\": \"disjunction of literals where at most one is positive\",\n",
        "\"Definite clause\": \"disjunctino of literals where exactly one is positive\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 59,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 997
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "89835489-637e-4c67-c446-5c3aebd1df20"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              " Your summary here \n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              " Your summary here \n",
              "\n",
              "## Module 7 Lecture Notes\n",
              " KNOWLEDGE BASE: set of sentences that are written in a knowledge representation language. These sentences contain some assertations about the world.\n",
              "SENTENCES: axioms=sentence that is given. derived sentences=sentence that is derived from other sentences (inference).\n",
              "```\n",
              "\n",
              "```\n",
              "MODELS: mathematical abstractions that have a fixed set of truth values for each sentence.\n",
              "if a sentence alpha is true in model m, then m satisfies alpha or m is a model of alpha. M(alpha)=set of all models of alpha\n",
              "```\n",
              "\n",
              "```\n",
              "Inference rules: a->b,a/b | a and b / a | a <-> b / (a->b) and (b->a)\n",
              "```\n",
              "\n",
              "```\n",
              "Monotonicity implies soundness: adding information to the KB does not invalidate any information that has already been inferred.\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "CONJUNCTIVE NORMAL FORM (CNF): Everything is a conjunction of clauses\n",
              "```\n",
              "1. Eliminate <=>. a <=> b becomes (a =>b) and (b=>a)\n",
              "2. Eliminate =>. a=>b becomes -a || b\n",
              "3. Move - inwards. Eliminate double negation and apply demorgan\n",
              "4. Apply distributivity to distribute or over and whenever possible\n",
              "```\n",
              "```\n",
              "\n",
              "```\n",
              "RESOLUTION ALG: To show KB entails a, show that KB and not a is unsatisfiable.\n",
              "```\n",
              "1. convert KB and not a into CNF\n",
              "2. Apply resolution rule to resulting clauses\n",
              "3. Resolve every pair that contains complementary literals to produce a new clause\n",
              "4. If new clause isn't already present add it to the set.\n",
              "5. Continue until...\n",
              "a. no new clauses can be added. Thus KB does not ential a\n",
              "b. two clauses resolve to yield the empty clause. thus kb does not entail a\n",
              "```\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "\n",
              "not A or not B or C equivalent to A and B => C\n",
              " \n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Entailment** - alpha entails beta if alpha follows logically from beta (|a| <= |b|)\n",
              "* **Sound** - inference alg should only derive entailed sentences\n",
              "* **Complete** - if alg can derive all entailed sentences\n",
              "* **Horn clause** - disjunction of literals where at most one is positive\n",
              "* **Definite clause** - disjunctino of literals where exactly 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": 60,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "36a3c29f-9595-45d1-987e-8726c3072ec8"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " Chapter 1.1 summary. \n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " Agents specified by an agent fucntion that maps percepts onto actions. \n",
              "Agents can be anything that perceives its environment through sensors and acts upon that environment with actuators.\n",
              " How do we measure if a rational agent is doing the right thing? Create a performance measure.\n",
              " Performances measures will be more successful if they specify what should be done rather than how you think the agent should act.\n",
              " Rational agents are not necessarily omniscent, so can only act to maximize EXPECTED value of performance measure\n",
              " Most difficult environment would be: continuous, partially observable, stochastic, multiagent\n",
              "\n",
              " \n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Turing test: can a human decide whether responses are from a machine or a humanchinese room: example of how turing test isn't real intelligenceagent** - anything that can perceive and act in an environment (Architecture + program)\n",
              "* **Percept** - agents perceptual inputs at an instance\n",
              "* **Rational agent** - an agent that percieves the env and does the right thing by maximizing expected val of performance measure\n",
              "* **Task environment.** - performance measure, environment, actuators, sensors\n",
              "* **Reflex agent** - Act soley on current precept and ignores history\n",
              "* **Problem solving agent** - Plans ahead, considers sequence of actions that form path to goal\n",
              "\n",
              "\n",
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              " STRINGS: immutable, == is equality, 'is' is same object, methods return new string (cause immutable)\n",
              "LISTS: mutable, y=x[:] will shallow copy an list, x.append is inplace (Same for most methods (insert, count, remove, reverse, sort, etc.)), mixed types\n",
              "TUPLE: immutable, ordered, mixed types\n",
              "DICTIONARIES: keys must be hashable (immutable), unordered, d.keys for keys, d.values() for vals, d.items() gives list of item tuples,\n",
              "from collections import defaultdict automatically initializes nonexistance dictionary values: \n",
              "e.g. \n",
              "```\n",
              ">>d=defaultdict(str)\n",
              ">>d['a']\n",
              "\"\"\n",
              "```\n",
              "from collections import Counter automatically initializes nonextistance values to 0: e.g. \n",
              "```\n",
              ">>d=Counter()\n",
              ">>d['a']\n",
              "0\n",
              ">>d['dog'] += 10\n",
              ">>d['dog']\n",
              "10\n",
              "```\n",
              "FUNCTIONS: can return like: ret1, ret2, ret3. it returns a tuple. cannot overload functions. can provide default values. keyword arguments allow out of order, but have to be after all other arguments\n",
              "```\n",
              "def fun(*args):\n",
              "  print(args)\n",
              "\n",
              ">>fun(1, 2, 3, 4)\n",
              "(1,2,3,4)\n",
              "```\n",
              "accepts a variable number of arguments.\n",
              "\n",
              "```\n",
              "def kfun(**kwargs):\n",
              "  print(kwargs)\n",
              ">>kfun(x=\"a\", y=\"b\", z=\"c\")\n",
              "{\"x\": \"a\", \"y\": \"b\", \"z\": \"c\"}\n",
              "```\n",
              "accepts a variable number of keyword arguments\n",
              "\n",
              "default parameter values are evaluated only when def statement is first being executed\n",
              "```\n",
              "def prime(n, prime=[]):\n",
              "  if n == 0:\n",
              "    return prime\n",
              "  if n is prime:\n",
              "    prime.append(n)\n",
              "  return prime(n-1)\n",
              "\n",
              "prime(11)\n",
              "# 11, 7, 5, 3, 2, 1\n",
              "```\n",
              "SUBCLASSES:\n",
              "to define subclass put name in parenthesis\n",
              "e.g.\n",
              "```\n",
              "def Bird(Animal):\n",
              "  ....\n",
              "```\n",
              "LIST COMPREHENSION:\n",
              "to use if statements in list comprehension:\n",
              "```\n",
              "[x*x for x in range(10) if x % 2 == 0]\n",
              "# will be squares of even numbers\n",
              "[x*x if x % 2 == 0 else x for x in range(10)]\n",
              "# will be squares of evens and plain odds\n",
              "```\n",
              "ITERATORS: anything that can be iterated over has an iterator method\n",
              "GENERATORS: gens are iterators. fucntions that use yield automatically return generator when called\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - your definition here\n",
              "\n",
              "\n",
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              " Dijkstra’s algorithm == uniform-cost search \n",
              "bidirectional search searches from both the initial state and the goal state at the same time and hopes that the two ends will meet\n",
              "bidirectional is complete, optimal, time=space=O(b^(d/2))\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              " Search problem definition:\n",
              "```\n",
              "1. States: set S\n",
              "2. Initial state: si in S\n",
              "3. Actions: set A\n",
              "4. Transition model: V s, V a in Actions(s), Result(s, a) -> sr (sr is successor of s)\n",
              "5. Path cost: Must be additive\n",
              "6. Goal test: Goal(s)\n",
              "```\n",
              "TREE SEARCH: root=initial state, nodes generated with transition model.\n",
              "state vs node. States do not have parents, children, depth, or path cost. They just represnt a physical config of the problem\n",
              "Problem: repeated states can turn a linear problem into an exponential one\n",
              "GRAPH SEARCH: modified tree search. check to see if a node has been visited before adding to search queue\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "\n",
              "BREADTH-FIRST SEARCH: expand shallowest unexpanded node (FIFO frontier). Complete, optimal (if cost = 1 per step), time=O(b^d), space=O(b^d)\n",
              "DEPTH-FIRST SEARCH: expand deepest unexpanded node (LIFE frontier). Not complete (infinite depth and loops bad), not optimal, time=O(b^m), space=O(b*m)\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "\n",
              "BFS vs DFS: DFS if limited space, many soln with long paths and wrong paths terminate quickly. BFS if infinite paths, soln with short paths, can discard unlikely paths quickly\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "Depth-limited search: DFS but with limit l (no infinite path issue). If l=d then optimal. if l < d, then incomplete. if l > d, not optimal. time=O(b^l), space=O(bl)\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "Iterative deepening search: use DLsearch as subroutine with increasing l (i.e. for l in [0, inf]: dfl at level l). Complete and optimal. Time=O(b^d), space=O(bd)\n",
              " \n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Solution** - sequence of actions from the initial state to a goal state\n",
              "* **Optimal solution** - a solution with the lowest path cost among all solutions\n",
              "* **Uninformed search** - all non-goal nodes look equally as good (only has info from problem definition)\n",
              "* **Completeness** - does search always find a soln if it exists and return properly when it doesn't\n",
              "* **Optimal** - does search find optimal soln\n",
              "* **Time complexity** - number of nodes generated\n",
              "* **Space complexity** - number of nodes simultaneously in memory\n",
              "* **B** - maximum branching factor of search tree\n",
              "* **D** - depth of shallowest goal node\n",
              "* **M** - max len of any path in state space (could be infinite)\n",
              "\n",
              "\n",
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              " CONSISTENCY: h(n) ≤ c(n,a,n′)+h(n′). Every consistent heuristic is admissable.\n",
              "BEAM SEARCH: limit size of frontier to save memory.\n",
              "ITERATIVE DEEPENING ASTAR SEARCH: benefits of a* without memory needs\n",
              "RECURSIVE BEST FIRST SEARCH: BFS but with linear space \n",
              "Weighted A∗ search focuses the search towards a goal, expanding fewer nodes,\n",
              "but sacrificing optimality\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " \n",
              "UNIFORM COST SEARCH: alg for traversing weighted tree. expand node with lowest path cost. test if a node is a goal state when it is selected for expansion, not when added to frontier.\n",
              "```\n",
              "\n",
              "```\n",
              "BEST FIRST SEARCH: nodes selected for expansion based on eval func f(n) (heuristic)\n",
              "```\n",
              "\n",
              "```\n",
              "GREEDY BEST FIRST SEARCH: expands node that is estimated to be closest to the goal. ignores g(n)\n",
              "```\n",
              "\n",
              "```\n",
              "A STAR SEARCH: best known Best-first search. f(n) = g(n) + h(n). heuristic must be admissible (doesn't overestimate cost to reach the goal)\n",
              "How to come up with heuristics: relax the problem. Cost of an optimal soln to a relaxed problem is an admissible heuristic for original problem.\n",
              "a relaxed problem is one with fewer restrictions on the actions. e.g. in tile game, if we can move tile anywhere, or if we could move tile to any adjacent square those would both be relaxed problems\n",
              "```\n",
              "\n",
              "```\n",
              "DOMINANCE: if h2(n) >= h1(n) for all n and both are admissible, then h2 dominates h1\n",
              "h* is the true distance to the goal and is the perfect heuristic (it is unachievable)\n",
              " \n",
              "\n",
              "## Module 4 Definitions\n",
              "\n",
              "\n",
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " Simplest multiagent env: static (no change while one agent acts), discrete (finite set of percepts and actions), fully observable (we know the complete state of the environment), strategic (the next state is determined by the current state and the action of the agent and the actions of one other agent) \n",
              "Simple game: players alternate moves, zero-sum, clear set of legal moves, well defined outcomes (W, L, T)\n",
              "More complex games: stochastic (e.g. bananagrams), not fully observable (e.g. card games), RTS (continuous)\n",
              "```\n",
              "\n",
              "```\n",
              "MIN AND MAX Nodes:\n",
              "two players, MAX and MIN. Games is computed from MAXs POV. when MAX moves, try to maximize MAX outcome. when MIN moves, try to minimize MAXs outcome.\n",
              "evaltuation function: evaluates how good a board is for either player based only on state of current board\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "MINIMAX: addume your oponenet makes the optimal move. each node is defined as either max or min of its children\n",
              "Even if your opponenent acts inoptimally, you will still do well.\n",
              "```\n",
              "\n",
              "```\n",
              "ALPHA BETA PRUNING:\n",
              "alpha is maxes current lower bound of max's outcome.\n",
              "beta is mins current upper bound on Min's outcome.\n",
              "MAX will never allow a move that would lead to a worse score than alpha.\n",
              "MIN will never allow a move that would lead to a better score than beta.\n",
              "When evaluating a MAX node and find val v, MIN will never select v >= beta. Thus can stop evaluating that node.\n",
              "When evaluating a MIN node and find val v, MAX will never select v <= alpha. Thus can stop evaluating that node.\n",
              "```\n",
              "\n",
              "```\n",
              "EXPECTIMAX: MINIMAX but you weight by the chance of going down each path\n",
              "\n",
              "\n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              " global constraint = arbitrary num of vars \n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              " node consistency: k=1, arc consistency: k=2, path consistency: k=3, strong k-consistent is k-1, ...2, 1 consistent \n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " MAC = maintaining arc consistency (recursively propogates constrains unlike forward checking) \n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              " constraint weighing: concentrate serach on important constraints\n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " Cutset condidtioning: reduce constraint graph to a tree by assigning values to variables so that the remaining var form a tree\n",
              "Tree decomposition: transformation of the original graph into a tree where each node consists of a set of variables\n",
              "symmetry-breaking constraint: used to cut down on possible soln \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              " CONSTRAINT SATISFACTION PROBLEMS: represent contrainst that soln must satisfy in declarative language, thus we can find soln to problems with generalized algorithms. \n",
              "```\n",
              "CSP:\n",
              "Finite set of var: X1, X2, .... Xn\n",
              "Nonempty domain of possible val for each var: D1, D2, ...Dn Di = {v1,...vk}\n",
              "Finite set of constraints: C1, C2, ... Cm\n",
              "constraints limit val that var can take. e.g. X1 != X2\n",
              "```\n",
              "CSP is complete when every variable is assigned a value. A solution is a complete and consistent assignment.\n",
              "\n",
              "CSP REPRESENTATIONS: Constraint graph: Nodes are var, arcs are binary constraints\n",
              "\n",
              "TYPES OF CONSTRAINTS: UNARY: constraint involves one var (e.g. X1 != Blue). BINARY: Constraint involves two var (e.g. X1 != X2). PREFERENCE can be represented by cost for variable assignment\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "CSP AS SEARCH PROBLEM: n var of domain size d. Branching factor = n*d, then n-1*d, etc. n!*d^n leaves. can always use DFS as soln is always at same depth. Var assignment is commutative (X1=Blue then X2=Green equals X2=Green then X1=Blue), thus tree search not graph search. \n",
              "\n",
              "IMPROVING EFF: Heuristics for backtracking. E.g. which var should be assigned next: Most constrained var (tie: most constraining variable). e.g what order should var's vals be tried: least constraining value. E.g. Check inevitable failure early (Forward checking)\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "FORWARD CHECKING: keep track of remaining vals for open vars. Stop search if any unassigned var is out of moves\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "CONSTRAINT PROPOGATION: goes beyond forward checking and repeatedly enforces constraints.\n",
              "INFERENCE: eliminates value for a var if the val would violate local consistency.\n",
              "ARC-CONSISTENCY: Xi arc-consistent with Xj if every val in Di has some value in Dj that satisfies the binary constraint\n",
              "AC-3: 1. Only examine Xi where at least one neighbor of Xi has lost a val in previous iteration. 2. If Xi loses a value only because of arc inconsistencies with Yj, don't need to check Yj on next iter. 3. Removing a val on Xi can only make Yj arc-inconsistent with respect to Xi itself, thus only need to check that (j, i) is arc-consistent.\n",
              "Worst case complexity: O(n^2*d^3)\n",
              "\n",
              "\n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Backtracking** - DFS for CSPs with single variable assignments. DFS chooses vals for var. Stops when var has no more assignments\n",
              "* **Node consistency** - satisfies unary constraints (trivial)\n",
              "* **Arc consistency** - satisfies binary constraints \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",
              " KNOWLEDGE BASE: set of sentences that are written in a knowledge representation language. These sentences contain some assertations about the world.\n",
              "SENTENCES: axioms=sentence that is given. derived sentences=sentence that is derived from other sentences (inference).\n",
              "```\n",
              "\n",
              "```\n",
              "MODELS: mathematical abstractions that have a fixed set of truth values for each sentence.\n",
              "if a sentence alpha is true in model m, then m satisfies alpha or m is a model of alpha. M(alpha)=set of all models of alpha\n",
              "```\n",
              "\n",
              "```\n",
              "Inference rules: a->b,a/b | a and b / a | a <-> b / (a->b) and (b->a)\n",
              "```\n",
              "\n",
              "```\n",
              "Monotonicity implies soundness: adding information to the KB does not invalidate any information that has already been inferred.\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "CONJUNCTIVE NORMAL FORM (CNF): Everything is a conjunction of clauses\n",
              "```\n",
              "1. Eliminate <=>. a <=> b becomes (a =>b) and (b=>a)\n",
              "2. Eliminate =>. a=>b becomes -a || b\n",
              "3. Move - inwards. Eliminate double negation and apply demorgan\n",
              "4. Apply distributivity to distribute or over and whenever possible\n",
              "```\n",
              "```\n",
              "\n",
              "```\n",
              "RESOLUTION ALG: To show KB entails a, show that KB and not a is unsatisfiable.\n",
              "```\n",
              "1. convert KB and not a into CNF\n",
              "2. Apply resolution rule to resulting clauses\n",
              "3. Resolve every pair that contains complementary literals to produce a new clause\n",
              "4. If new clause isn't already present add it to the set.\n",
              "5. Continue until...\n",
              "a. no new clauses can be added. Thus KB does not ential a\n",
              "b. two clauses resolve to yield the empty clause. thus kb does not entail a\n",
              "```\n",
              "\n",
              "```\n",
              "\n",
              "```\n",
              "\n",
              "not A or not B or C equivalent to A and B => C\n",
              " \n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Entailment** - alpha entails beta if alpha follows logically from beta (|a| <= |b|)\n",
              "* **Sound** - inference alg should only derive entailed sentences\n",
              "* **Complete** - if alg can derive all entailed sentences\n",
              "* **Horn clause** - disjunction of literals where at most one is positive\n",
              "* **Definite clause** - disjunctino of literals where exactly one is positive\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 60,
      "metadata": {
        "id": "0hjCbHHqmV8p"
      },
      "outputs": [],
      "source": []
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
