{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_midterm notes_ZQ.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "fff40391-2f46-4b72-8ddd-8cadf7901a37"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "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": "code",
      "metadata": {
        "id": "8DvZ57A-djo1"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\" placeholder \"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" \n",
        "Define Intelligence: Human performance vs. rationality / internal thought process and reasoning vs. intelligent behavior.\n",
        " - Acting Humanly: Turing Test\n",
        " - Thinking Humanly: The cognitive modeling approach\n",
        " - Thinking rationally: The “laws of thought” approach\n",
        " - Acting rationally: The rational agent approach\n",
        "\\nThe rational-agent approach to AI has two advantages over the other approaches\n",
        "  - It is more general than the “laws of thought” approach because correct inference is just one of possible mechanisms for achieving rationality. \n",
        "  - It is more amenable to scientific development.\n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" \"\"\"\n",
        "chapter27_2 = \"\"\" \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" \"\"\"\n",
        "\n",
        "chapter2_2 = \"\"\"\n",
        "Rationality vs. perfection: Rationality maximizes expected performance, while perfection maximizes actual performance\n",
        "\\nRationality does not require omniscience: knows the actual outcome of its actions and can act accordingly \"\"\"\n",
        "\n",
        "chapter2_3 = \"\"\"\n",
        "Properties of task environments\n",
        " - Fully observable vs. Partially observable vs. Unobservable\n",
        " - Single-agent vs. Multiagent\n",
        " - Competitive vs. Cooperative\n",
        " - Deterministic vs. Nondeterministic (stochastic)\n",
        " - Episodic (previous episodes does not affect current one) vs. Sequential (has effect)\n",
        " - Static vs. Dynamic vs. Semidynamic (environment does not change with the passage of time but the agent’s performance score does)\n",
        " - Discrete vs. Continuous\n",
        " \"\"\"\n",
        "\n",
        "chapter2_4 = \"\"\"\n",
        "Agent = Architecture + Program (The agent program runs on the physical architecture to produce f)\n",
        "Different types of agents\n",
        " - Simple reflex agents: select actions on the basis of the current percept, ignoring the rest of the percept history\n",
        " - Model-based reflex agents: internal state based on percept history, transition model (how the world works), sensor model\n",
        " - Goal-based agents: goal + search + planning\n",
        " - Utility-based agents: utility function (an internalization of the performance measure) + expected utility\n",
        " - Model-free agent: can learn what action is best in a particular situation without ever learning exactly how that action changes the environment\n",
        " - Learning agent: learning element (responsible for making improvements) + performance element (responsible for selecting external actions)\n",
        "\\nDifferent types of representations:\n",
        " - Atomic representation: each state of the world is indivisible—it has no internal structure\n",
        " - Factored representation: splits up each state into a fixed set of variables or attributes, each of which can have a value\n",
        " - Structured representation: objects and their various and varying relationships can be described explicitly\n",
        " - Localist representation: one-to-one mapping between concepts and memory locations\n",
        " - Distributed representation: the representation of a concept is spread over many memory locations, with each location employed as part of the representation of multiple different concepts\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent function\": \"maps any given percept sequence to an action\",\n",
        "\"biological naturalism\": \"mental states are high-level features caused by low-level neurons processes, it is unspecified properties of the neurons matter\",\n",
        "\"consequentialism\": \"we evaluate an agent’s behavior by its consequences\",\n",
        "\"embodied cognition\": \"no sense to consider the brain separately: cognition takes place within a body, which is embedded in an environment\",\n",
        "\"Good Old-Fashioned AI (GOFAI)\": \"simplest logical agent design, difficult to capture every appropriate behavior in a set of logical rules\",\n",
        "\"qualification problem\": \"see above for GOFAI\",\n",
        "\"knowledge representation\" : \"to store what it knows or hears\",\n",
        "\"limited rationality\": \"acting appropriately when there is not enough time to do all the computations one might like\",\n",
        "\"rational agent\": \"For each possible percept sequence, act to maximize expected performance, given percept sequence and built-in knowledge\",\n",
        "\"standard model\": \"Objective that we provide to the agent (minimize cost, minimize loss, maximize reward...)\",\n",
        "\"strong AI\": \"the assertion that machines that do so are actually consciously thinking (not just simulating thinking)\",\n",
        "\"value alignment problem\": \"the values or objectives put into the machine must be aligned with those of the human\",\n",
        "\"weak AI\": \"the idea that machines could act as if they were intelligent\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "cellView": "form"
      },
      "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.2 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "Variable Print\n",
        " - print(\"%s speak %d languages\" % (\"C3PO\", 600))\n",
        "\\nDatatype\n",
        " - type(object), \n",
        " - isinstance(object, type)\n",
        "\\nSlicing: return a copy of sequence\n",
        " - t = (23, 'abc', 4.56, (2,3), 'def')\n",
        " - t[1:-1] >>> ('abc', 4.56, (2,3))\n",
        " - t[1:-1:2] >>> ('abc', (2,3)) every nth item\n",
        " - t[:2] >>> (23, 'abc') beginning to index 2\n",
        " - t[2:] >>> (4.56, (2,3), 'def') to the end\n",
        "\\nList Operation 1\n",
        " - [2*i for i in range(3)] >>> [0, 2, 4]\n",
        " - ['%.2f % random.random() for i in range(10)] >>> list of 10 random floats between [0.0, 1.0)\n",
        " - x = [1, 2, 3], y = x[:] >>> get a (shallow) copy of x sequence\n",
        " - testList[-3] >>> negative lookup from right, starting from -1\n",
        "\\nList Operation 2\n",
        " - li = [1, 11, 3, 4]\n",
        " - li.insert(2, 'i') >>> [1, 11, 'i', 3, 4]\n",
        "\\nList Operation 3\n",
        " - li = ['a', 'b', 'c', 'b']\n",
        " - li.index('b') >>> 1 index of the first occurrence\n",
        " - li.count('b') >>> 2 number of occurrences\n",
        " - li.remove('b') >>> li = ['a', 'c', 'b'] remove first occurrence\n",
        "\\nList Operation 4\n",
        " - li = [5, 2, 6, 8]\n",
        " - li.reverse() >>> li = [8, 6, 2, 5]\n",
        " - li.sort() >>> li = [2, 5, 6, 8]\n",
        " - li.sort(some_function) >>> sort list with some pre-defined function\n",
        " - sorted(li) >>> return a *copy* of sorted\n",
        "\\nString Operation 1\n",
        " - s = \"pretend this sentence makes sense.\"\n",
        " - words = s.split(\" \") >>> words = ['pretend', 'this', 'sentence', 'makes', 'sense.']\n",
        " - \"_\".join(words) >>> 'pretend_this_sentence_makes_sense.'\n",
        "\\nString Operation 2\n",
        " - s = 'dog'\n",
        " - s.capitalize() >>> Dog\n",
        " - s.upper() >>> DOG\n",
        "\\nString Operation 3 \n",
        " - 'hi--'.strip('–') >>> 'hi'\n",
        "\\nDictionary Method 1\n",
        " - d = {'user':'R2D2', 'p':1234}\n",
        " - d.keys() >>> dict_keys(['user', 'p'])\n",
        " - d.values() >>> dict_values(['R2D2', 1234])\n",
        " - d.items() >>> dict_items([('user', 'R2D2'), ('p', 1234)])\n",
        "\\nFor Loops and List Comprehension\n",
        " - list(range(5)) >>> [0,1,2,3,4]\n",
        " - for (x, y) in [('a',1), ('b',2), ('c',3), ('d',4)]\n",
        " - li = [3, 6, 2, 7], [elem * 2 for elem in li] >>> [6, 12, 4, 14]\n",
        " - li = [('a', 1), ('b', 2), ('c', 7), [n * 3 for (x, n) in li] >>> [3, 6, 21]\n",
        " - li = [3, 6, 2, 7, 1, 9], [elem * 2 for elem in li if elem > 4] >>> [12, 14, 18]\n",
        "\\nDictionary and Set Comprehensions\n",
        " - lst1 = [('a', 1), ('b', 2), ('c', 'hi’)], lst2 = ['x', 'a', 6]\n",
        " - d = { k: v for k,v in lst1 } >>> d: {'a': 1, 'b': 2, 'c': 'hi’}\n",
        " - d = dict(); for k, v in lst1: d[k] = vs = set(); >>>  d: {'a': 1, 'b': 2, 'c': 'hi’}\n",
        " - s = { x for x in lst2} >>> {'x', 'a', 6}\n",
        " - s = set(); for x in lst: s.add(x) >>> {'x', 'a', 6}\n",
        "\\nDefault Values for function Arguments: \n",
        " - def myfun(b, c=3, d=\"hello\"): return b + c\n",
        " - myfun(5,3,\"bob\") >>> 8, \n",
        " - myfun(5,3) >>> 8\n",
        " - myfun(5) >>> 8\n",
        " - Non-default argument always precede default arguments otherwise would result in SyntaxError\n",
        "\\nKeyword Arguments: \n",
        " - def myfun(a, b, c): return a-b\n",
        " - myfun(2, 1, 43) >>> 1\n",
        " - myfun(c=43, b=1, a=2) >>> 1\n",
        " - myfun(2, c=43, b=1) >>> 1\n",
        " - myfun(a=2, b=3, 5) >>> SyntaxError: positional argument follows keyword argument\n",
        "\\n*args - variable number of non-keyword arguments\n",
        " - def print_everything(*args): print(*args)\n",
        " - print_everything('a','b') >>> ('a','b')\n",
        " - lst = ['a','b'], print_everything(*lst) >>> ('a','b')\n",
        "\\n**kwargs - variable number of keyword arguments\n",
        " - def print_keyword_args(**kwargs): print(kwargs)\n",
        " - print_keyword_args(first_name=\"John\", last_name=\"Doe\") >>> {'first_name': 'John', 'last_name': 'Doe’}\n",
        " - my_dict = {'first_name':'Wei','last_name':'Xu’}, print_keyword_args(**my_dict) >>> {'first_name':'Wei','last_name':'Xu'}\n",
        "\\nargs and kwargs\n",
        " - def myfun(positional, args, kwargs): print(positional); if args: print(args); if kwargs: print(kwargs);\n",
        " - myfun(\"hello\", 1, 2, 3, a=\"hi\", b=\"bye\", c=\"ciao\") >>> hello, (1, 2, 3), {'a': 'hi', 'b': 'bye', 'c': 'ciao’}\n",
        "\\nFunctions are “first-class” objects\n",
        " - An entity that can be dynamically created, destroyed, passed to a function\n",
        " - returned as a value, and have all the rights as other variables in the programming language have\n",
        "\\nSubclasses: A class can extend the definition of another clas\n",
        " - Allows use (or extension) of methods and attributes already defined in the previous one.\n",
        " - To define a subclass, put the name of the superclass in parentheses after the subclass’s name on the first line of the definition.\n",
        " - class AI_Student(Student): fav_class = \"CIS 521”\n",
        "\\nSubclass and $__init__$ function: $parentClass.__init__(self, x, y)$\n",
        " - class AI_Student(Student): $def __init__(self, name, dept): Student.__init__(self, name, dept)$\n",
        "\\nRedefing methods\n",
        " - To redefine a method of the parent class, include a new definition using the same name in the subclass.\n",
        " - To execute the method in the parent class in addition to new code for some method, explicitly call the parent’s version of the method.\n",
        "  - parentClass.methodName(self, a, b, c), The only time you ever explicitly pass self as an argument is when calling a method of an ancestor.\n",
        "\\nMagic methods\n",
        " - allow user-defined classes to behave like built in types\n",
        " - $__str__$, $__init__$, $__len__$, $__copy__$, $__cmp__$, $__add__$, $__neg__$\n",
        " - if $__name__ == '__main__': main()$\n",
        "\\nIterator Objects\n",
        " - k = [1,2,3]\n",
        " - $k.__iter__()$ or  iter(k) >>> <list_iterator object at 0x104f8ca50>\n",
        " - $__next__$ method: i = iter(k); next(i) or $i.__next__()$ >>> 1\n",
        "  - Python iterators do not have a hasnext() method!\n",
        "  - Just catch the StopIteration exception\n",
        " - iterators uses memory efficienty!\n",
        "\\nGenerator Objects\n",
        " - Generators are iterators (with $__next()__$ method)\n",
        " - Creating Generators: yield\n",
        "  - Functions that contain the yield keyword automatically return a generator when called\n",
        " -  def f(n): yield n; yield n+1\n",
        "  - type(f) >>> <class 'function'>\n",
        "  - type(f(5)) >>> <class 'generator'>\n",
        "  - [i for i in f(6)] >>> [6, 7]\n",
        "  - gen = f(5); $gen.__next__()$ or next(gen)\n",
        " - Benefit of using generator\n",
        "  - Less code than writing a standard iterator\n",
        "  - Maintains local state automatically\n",
        "  - Values are computed one at a time, as they’re needed\n",
        "  - Avoids storing the entire sequence in memory\n",
        "  - Good for aggregating (summing, counting) items. One pass.\n",
        "  - Crucial for infinite sequences\n",
        "  - Bad if you need to inspect the individual values\n",
        " - Catch exception\n",
        "  - try: something; except StopIteration: break\n",
        "\\nImports\n",
        " - from math import * >>> import all\n",
        " - from queue import PriorityQueue\n",
        "  - q = PriorityQueue(); q.put(10); q.get()\n",
        "  - q.put((1, \"Hello\")); q.put((5, \"Diego Montoya\")\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"Strong typing\" : \"object has a fixed type, otherwise incompatible (eg. “foo” + 2)\",\n",
        "\"Immutable datatype\": \"datatype that cannot be changed. e.g. Tuple, String\",\n",
        "\"Static Typing\": \"like Java (int a = 1), the type of a cannot be changed later\",\n",
        "\"Dynamic Typing\": \"Python: if a variable is reassigned, its type is updated. e.g. a = None -> a = 1\",\n",
        "\"Function Overloading\": \"Java: multiple methods with the same name: add(int), add(int, int), python: no overloading\",\n",
        "\"Operator overloading\": \"(+, ==, -) possible using special methods on when you implement a class\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"\n",
        "Problem Solving Agent: the four phases\n",
        " - Goal Formulation\n",
        " - Problem formulation: description of the states and actions\n",
        " - Search: simulates sequences of actions in its model (until find solution)\n",
        " - Execution: execute the actions in the solution\n",
        "\\nHow to define a search problem\n",
        " - State space, Initial state, Goal states, Action, Transition model, Action cost function\n",
        "\"\"\"\n",
        "\n",
        "chapter3_2 = \"\"\" \"\"\"\n",
        "\n",
        "chapter3_3 = \"\"\"\n",
        "\\nFour components of a node:\n",
        " - state, parent, action, path-cost\n",
        "\\nActions for search frontier:\n",
        " - Is-empty, pop, top, add\n",
        "\\nDifferent types of queue:\n",
        " - Priority queue\n",
        " - FIFO queue (first in, first out)\n",
        " - LIFO queue (last in, first out) \n",
        "\\nMeasuring problem-solving performance\n",
        " - COMPLETENESS: Is the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not?\n",
        " - COST OPTIMALITY: Does it find a solution with the lowest path cost of all solutions?\n",
        " - TIME COMPLEXITY: How long does it take to find a solution?\n",
        " - SPACE COMPLEXITY: How much memory is needed to perform the search?\n",
        "\\nTime/space complexity variables\n",
        " - b, maximum branching factor of search tree\n",
        " - d, depth of the shallowest goal node\n",
        " - m, maximum length of any path in the state space (potentially ∞)\n",
        "\"\"\"\n",
        "\n",
        "chapter3_4 = \"\"\"\n",
        "best-first search\n",
        " - We choose a node, n with minimum value of some evaluation function. \n",
        " - At each step, the node with the minimal value as computed by the evaluation function is expanded.\n",
        "\\nBreadth-first search\n",
        " - Node searched = $1+b+b^2+b^3+...+b^d = O(b^d)$\n",
        " - Complete all nodes in the same depth before proceeding to next level\n",
        " - Do an early goal test, checking whether a node is a solution as soon as it is generated, rather than the late goal test\n",
        " - Late goal test: waiting until a node is popped off the queue\n",
        "\\nUniform-cost search (optimal)\n",
        " - A type of breadth-first search\n",
        " - Evaluation function is the cost of the path from the root to the current node\n",
        " - Dijkstra’s algorithm is uniform-cost search (with or without a goal)\n",
        "  - If without a goal, Dijkstra’s algorithm generate shortest paths to all nodes\n",
        "\\nDepth-first search\n",
        " - Always expands the deepest node in the frontier first\n",
        " - For finite state spaces that are trees it is efficient and complete\n",
        " - In cyclic state spaces it can get stuck in an infinite loop\n",
        "\\nBacktracking search\n",
        " - A variant of depth-first search called backtracking search that uses less memory\n",
        " - Only one successor is generated at a time rather than all successors\n",
        "\\nDepth-limited search\n",
        " - Set a depth limit l, and treat all nodes at depth l as if they had no successors\n",
        "\\nIterative deepening search\n",
        " - Solves the problem of picking a good value for l by trying all values: first 0, then 1, then 2, and so on\n",
        "\\nBidirectional search\n",
        " - Simultaneously searches forward from the initial state and backwards from the goal state, hoping that the two searches will meet\n",
        " - The motivation is that $b^{d/2}$ + $b^{d/2}$ is much less than $b^d$\n",
        "\n",
        "\\n\\nSeach Attribute Table, order = [Complete, Optimal Cost, Time, Space]\n",
        "\\nb = branching factor; m = maximum depth of the search tree;\n",
        "\\nd = depth of the shallowest solution, or is m when there is no solution; l = depth limit.\n",
        "\\nBreath-first: Yes, Yes, $O(b^d)$, $O(b^d)$\n",
        "\\nUniform-cost: Yes, Yes, $O(b^{1+\\lfloor{C^*/ε}})$, $O(b^{1+\\lfloor{C^*/ε}})$\n",
        "\\nDepth-first: No, No, $O(b^m)$, $O(b*m)$\n",
        "\\nDepth-limited: No, No, $O(b^l)$, $O(b*l)$\n",
        "\\nIterative Deepening: Yes, Yes, $O(b^d)$, $O(b*d)$\n",
        "\\nBidirectional: Yes, Yes, $O(b^{d/2})$, $O(b^{d/2})$\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" \"\"\"\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",
        "\"graph search\": \"checks for redundant paths\",\n",
        "\"informed algorithms\": \"the agent can estimate how far it is from the goal\",\n",
        "\"planning agents\": \"Agents that use factored or structured representations of states\",\n",
        "\"standardized problem\": \"llustrate or exercise various problem-solving methods\",\n",
        "\"tree search\": \"does not check for redundant paths\",\n",
        "\"uninformed algorithms\": \"the agent cannot estimate how far it is from the goal\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "Uniform-cost search\n",
        " - No heuristic function involved, f(n) = g(n)\n",
        "\\nGreedy best-first search\n",
        " - Expands node with the lowest h(n) value — closest to the goal, f(n) = h(n)\n",
        "\\nA* search\n",
        " - f(n) = g(n) + h(n) estimated cost of the best path that continues from n to a goal \n",
        " - Optimal if the heuristic function is admissible (optimistic)\n",
        " - The biggest problem with A* is the space complexity\n",
        "\\nWeighted A* search\n",
        " - Weight the heuristic value more heavily, f(n) = g(n) + W * h(n), for some W>1\n",
        " - Not optimal, but complete\n",
        " - It expands fewer nodes\n",
        "\\nIterative-deepening A* search (IDA*)\n",
        " - A* what iterative-deepening search is to depth-first (gives us the benefits of A* without keeping all reached states in memory)\n",
        " - The cutoff is the f-cost (g+h). at each iteration, the cutoff value is the smallest f-cost of any node that exceeded the cutoff on the previous iteration\n",
        " - In other words, each iteration exhaustively searches an f-contour, finds a node just beyond that contour, and uses that node’s f-cost as the next contour.\n",
        "\\nRecursive best-first search (RBFS)\n",
        " - Mimic the operation of standard best-first search, but using only linear space\n",
        " - Uses the f_limit variable to keep track of the f-value of the best alternative path available from any ancestor of the current node\n",
        " - If the current node exceeds this limit, the recursion unwinds back to the alternative path\n",
        " - As the recursion unwinds, RBFS replaces the f-value of each node along the path with a backed-up value — the best f-value of its children.\n",
        " - RBFS is optimal if the heuristic function h(n) is admissible\n",
        "\\nSimplified memory-bounded A* (SMA*)\n",
        " - Expand the best leaf until memory is full, then drop the worst leaf node—the one with the highest f-value (if tied, delete old)\n",
        " - Complete if there is any reachable solution.\n",
        " - Optimal if ant optimal solution is reachable\n",
        "\\nA*, IDA*, SMA*, RBFS\n",
        " - IDA*, SMA*, and RBFS are optimal search algorithms which are more space efficient than A*\n",
        "\\nBidirectional heuristic search\n",
        " - Just like A*, f(n) = g(n) + h(n), but from both directions\n",
        " - No guarantee to be optimal, even with admissible h(n)\n",
        "\"\"\"\n",
        "\n",
        "chapter3_6 = \"\"\" \n",
        "Effective branching factor b*\n",
        " - With a tree of depth d and total visited nodes N, $N+1 = 1 + b + b^2 + ... b^d$\n",
        " - e.g. if N = 52 and depth = 5, then b* = 1.92\n",
        "\\nEffective depth\n",
        " - If effective depth is reduced by kh, then search cost changes from $O(b^d)$ to $O(b^{d-kh})$\n",
        "\\nHeiristic domination (In the following example, assume h2(n) > h1(n) for all node n)\n",
        " - In this case, h2 dominates h1\n",
        " - Now assume the perfect heuristic is hn* and admissible heuristic h1, h2, then h1 < h2 < hn*\n",
        "  - In this case, h2 is closer to optimal and provides better estimates for all nodes n in the state space,\n",
        " - Now assume the perfect heuristic is hn* and inadmissible heuristic h1, h2, then h2 > h1 > hn*\n",
        "  - In this case, h1 is closer to optimal and provides better estimates for all nodes n in the state space,\n",
        "\\nRelaxed Problem\n",
        " - A problem with fewer restrictions on the actions (e.g. move onto an occupied cell in a grid)\n",
        " - Since any optimal solution in the original problem is also a solution for the relaxed problem\n",
        " - The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"admissibility (optimistic)\": \"an admissible heuristic is one that never overestimates the cost to reach a goal\",\n",
        "\"beam search (not optimal, not complete)\": \"limits the size of the frontier, keep only K nodes with the best f-scores, discarding any other nodes\",\n",
        "\"bounded-cost search\": \"a solution whose cost is less than some constant C\",\n",
        "\"bounded suboptimal serach\": \"look for a solution that is guaranteed to be within a constant factor W of the optimal cost\",\n",
        "\"euclidean distance\": \"straight distance between two points, d = sqrt(a^2 + b^2)\",\n",
        "\"manhattan distance\": \"the sum of the absolute differences between the two vectors\",\n",
        "\"monotonic\": \"the g costs are monotonic: the path cost always increases as you go along a path\",\n",
        "\"speedy search\": \"a greedy best-first search that uses as a heuristic the estimated number of actions required to reach a goal\",\n",
        "\"unbounded-cost search\": \"accept a solution of any cost, as long as we can find it quickly\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form"
      },
      "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\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Minimax solves for perfect information (fully observable), zero-sum games \"\"\"\n",
        "\n",
        "chapter5_2 = \"\"\"\n",
        "Alpha-Beta pruning\n",
        " - Alpha = the value of the best (i.e., highest-value) choice we have found so far along the path for max.\n",
        " - Beta = the value of the best (i.e., lowest-value) choice we have found so far along the path for min.\n",
        " - With perfect pruning, we can examine only $O(b^{m/2})$ nodes instead of $O(B^m)$ -> effective branching factor becomes $sqrt(b)$ instead of b\n",
        " - With perfect pruning, can solve a tree twice deep in the same amount of time.\n",
        " - With random pruning, the total number of nodes will roughtly be $O(b^{3m/4})$\n",
        "\\nRepeated states can occur because of transposition\n",
        " - Different permutations of the move sequence that end up in the same position\n",
        " - The problem can be addressed with a transposition table that caches the heuristic value of states\n",
        "\"\"\"\n",
        "\n",
        "chapter5_3 = \"\"\"\n",
        "Heuristic evaluation function Eval(s,p)\n",
        " - Estimate of the expected utility of state s to player p\n",
        " - For terminal states, Eval(s,p) = Utility(s,p)\n",
        " - For non-terminal states, the evaluation is somewhere between a loss and a win: utility(loss,p)<=Eval(s,p)<=Utility(win,p)\n",
        "\\nCuroff search\n",
        " - Cut off at depth d, and use eval function\n",
        " - The evaluation function should be applied only to positions that are quiescent\n",
        " - Quiescent: positions in which there is no pending move that would wildly swing the evaluation\n",
        " - Extra quiescence search: for nonquiescent positions the Is-Cutoff returns false, and the search continues until quiescent positions\n",
        "\"\"\"\n",
        "\n",
        "chapter5_5 = \"\"\" \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "Constraint on raional preferences\n",
        " - lottery: each action as a ticket. A lottery L with possible outcomes s1, s2... sn occur with probabilities p1, p2,...pn\n",
        " - Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable\n",
        " - Transitivity: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C\n",
        " - Continuity: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1-p.\n",
        " - Substitutability: If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them\n",
        " - Monotonicity: Suppose two lotteries have the same two possible outcomes, A and B. If an agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A(and vice versa)\n",
        " - Decomposability: Compound lotteries can be reduced to simpler ones using the laws of probability. This has been called the “no fun in gambling” rule\n",
        "\"\"\"\n",
        "\n",
        "chapter16_3 = \"\"\" \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "The minimax rule\n",
        " - Always assume that the opponent makes the best move\n",
        " - The backed-up value of each node in the tree is determined by the values of its children\n",
        "\\nAlpha-Beta Pruning\n",
        " - During Minimax, keep track of two additional values\n",
        "  - α: MAX’s current lower bound on MAX’s outcome\n",
        "  - β: MIN’s current upper bound on MIN’s outcome\n",
        " - MAX will never allow a move that could lead to a worse score (for MAX) than α\n",
        " - MIN will never allow a move that could lead to a better score (for MAX) than β\n",
        " - stop evaluating a branch whenever:\n",
        "  - When evaluating a MAX node: a value v ≥ β is backed-up (MIN will never select that MAX node)\n",
        "  - When evaluating a MIN node: a value v ≤ α is found (MAX will never select that MIN node)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"forward pruning (e.g. beam search)\": \"prunes moves that appear to be poor moves, but might possibly be good ones (type B strategy)\",\n",
        "\"horizon effect\": \"when facing opponent’s move that causes serious damage and is unavoidable, but can be temporarily avoided using delaying tactics\",\n",
        "\"late move reduction\": \"assumption that move ordering iswell, and therefore later moves are less likely to be good, and reduce search depth\",\n",
        "\"state space graph\": \"a graph where the vertices are states, the edges are moves and a state might be reached by multiple paths\",\n",
        "\"singular extensions\": \"moves that are “clearly better” than all other moves in a given position, even when the search would normally be cut off at that point\",\n",
        "\"Stochastic games\": \"inlucde unpredictability from a random element, such as the throwing of dice\",\n",
        "\"Type A strategy\": \"considers all possible moves to a certain depth, uses a heuristic evaluation function to estimate utility (wide but shallow)\",\n",
        "\"Type B strategy\": \"ignores moves that look bad, and follows promising lines “as far as possible.” (deep but narrow)\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "Different types of constraint\n",
        " - Unary constraint: restricts the value of a single variable\n",
        " - Binary constraint: relates two variables, e.g. A!=B (binary CSP is one with unary and binary constraint)\n",
        " - Global constraint: A constraint involving an arbitrary number of variables (does not need to involve all)\n",
        "\"\"\"\n",
        "\n",
        "chapter6_2 = \"\"\"\n",
        "Constraint propagation\n",
        " - Using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable, and so on\n",
        " - Local consistency: treat each variable as a node and each binary constraint as an edge, enforcing local consistency to eliminate inconsistent values\n",
        "\\nDifferent types of consistency\n",
        " - Node-consistent: all the values in the variable’s domain satisfy the variable’s unary constraints\n",
        " - Arc-consistent: every value in its domain satisfies the variable’s binary constraints (AC-3)\n",
        " - Path consistency: tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables\n",
        "  - A two-variable set {xi, xj} is path-consistent with respect to a third variable xm if, for every assignment {xi=a, xj=b} consistent with \n",
        "  - The constraints on {xi, xj}, there is an assignment to xm that satisfies the constraints on {xi, xm} and {xj, xm}.\n",
        "\\nK-consistency\n",
        " - A CSP is K-consistent if for any set of k-1 variables their consistent assignment, a consistent value can always be assigned to the kth variable\n",
        " - 1-consistency says that, given the empty set, we can make any set of one variable consistent (node consistency)\n",
        " - 2-consistency = arc consistency\n",
        " - 3-consistency = path consistency\n",
        " - A CSP is strongly k-consistent if it is k-consistent and is also (k-1)-consistent, (k-2)-consistent,...all the way down to 1-consistent\n",
        "\\nSolve for strong K consistency (n nodes, d values for domain)\n",
        " - Choose consistent value for x1 (1-consistent), and then x2 (2-consistent), and then x3... total run time is O(n^2 * d)\n",
        "\\nBound propagation\n",
        " - The domain values have lower and upper bounds, e.g. D1 = [0, 100], D2 = [0, 200]\n",
        " - A CSP bound-consistent if for every variable X (lower&upper bound), there exists some value of Y that satisfies constraint between X and Y\n",
        "\"\"\"\n",
        "\n",
        "chapter6_3 = \"\"\"\n",
        "Backtracking search for CSP (depth-first search, uninformed)\n",
        " - Repeatedly chooses an unassigned variable, and tries all values in the domain of that variable, trying to extend each one into a solution via recursive call\n",
        " - If the call succeeds, the solution is returned, and if it fails, the assignment is restored to the previous state, and we try the next value\n",
        " - If no value works then return failure.\n",
        "\\nValue ordering\n",
        " - Minimum-remaining-values (most constrained value): choosing the variable with the fewest “legal” values\n",
        " - Degree heuristic (most constraining value): select the variable that is involved in the largest number of constraints on other unassigned variables\n",
        " - Least-constraining-value: choose value that rules out the fewest choices for the neighboring variables in the constraint graph\n",
        "\\nForward checking vs. Maintaining Arc Consistency (MAC)\n",
        " - Forward checking: for a variable X assigned, check arc consistency with Y: delete from Y’s domain any value that is inconsistent with the value chosen for X\n",
        " - MAC: recursively propagate constraints when changes are made to the domains of variables (more powerful than forward checking)\n",
        "\"\"\"\n",
        "\n",
        "chapter6_4 = \"\"\" \"\"\"\n",
        "chapter6_5 = \"\"\" \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "\\nAC-3: Worst case complexity analysis\n",
        " - All nodes can be connected to every other node\n",
        "  - so each of n nodes must be compared against n-1 other nodes\n",
        "  - so total # of arcs is $2*n*(n-1)$ -> $O(n^2)$\n",
        " - If there are d values, checking arc (i,j) takes $O(d^2)$ time\n",
        " - Each arc (i,j) can only be inserted into the queue d times\n",
        " - Worst case complexity: $O(n^2 * d^3)$\n",
        " - For planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only $O(n * d^3)$\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"constraint graph\": \"The nodes of correspond to variables of the problem, and an edge connecting any two variables is a constraint\",  \n",
        "\"chronological backtracking\": \"when a branch of the search fails: back up to the preceding variable and try a different value for it\",  \n",
        "\"conflict-directed backjumping\": \"backjumping algorithm that uses conflict sets by replacing the most assigned value in the set\",\n",
        "\"constraint learning\": \"finding a minimum set of variables from the conflict set that causes the problem\",\n",
        "\"disjunctive constraint\": \"two tasks must not overlap in time\",\n",
        "\"directional arc consistency\": \"every Xi has to be consistent with Xj, with condition that i>j or i<j\",\n",
        "\"min-conflicts (heuristic)\": \"select the value that results in the minimum number of conflicts with other variables\",\n",
        "\"precedence constraints\": \"a task T1 must occur before T2\",\n",
        "\"solution in CSP\": \"a consistent (no violation), complete (every variable is assigned) assignment\",\n",
        "\"tabu search\": \"keeping a small list of recently visited states and forbidding the algorithm to return to those states\"\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" \n",
        "Knowledge-based agents: use a process of reasoning over an internal representation of knowledge to decide what actions to take\n",
        " - A knowledge base is a set of sentences\n",
        " - Each sentence is expressed in a language called a knowledge representation language and represents some assertion about the world\n",
        "\\nDeclarative vs. Procedural approach\n",
        " - Declarative: tell sentences one by one until the agent knows how to operate in its environment\n",
        " - Procedural: encodes desired behaviors directly as program code\n",
        "\"\"\"\n",
        "\n",
        "chapter7_2 = \"\"\" \"\"\"\n",
        "\n",
        "chapter7_3 = \"\"\"\n",
        "Model - possible world\n",
        " - If a sentence a is true in model m, we say that m satisfies a or sometimes m is a model of a\n",
        " - Use the notation M(a) to mean the set of all models of a\n",
        "\\nEntailment (logical inference)\n",
        " - The idea that a sentence follows logically from another sentence\n",
        " - a |= b, a entails the sentence b (if and only if in every model in which a is true, b is also true. a |= b if a => b)\n",
        " - a |= b if an only if M(a) ⊆ M(b) -> (a is a stronger assertion than b)\n",
        " - example: a = kitty is a cat |= b = kitty is an animal\n",
        "\\nInference and Entailment\n",
        " - if an inference algorithm i can derive a from KB, we write $KB|_i a$ (a is derived from KB by i”)\n",
        "\"\"\"\n",
        "\n",
        "chapter7_4 = \"\"\" \"\"\"\n",
        "chapter7_5 = \"\"\" \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "Proposational Logic\n",
        " - ¬ (not), ⋀ (and), ⋁ (or), ⟹ (implies), ⇔ (if and only if)\n",
        "\\nLogical Equivalence\n",
        " - (a ⋀ β) ≡ (β ⋀ a) >>> Commutativity of ⋀\n",
        " - (a ⋁ β) ≡ (β ⋁ a) >>> Commutativity of ⋁\n",
        " - ((a ⋀ β) ⋀ ɣ) ≡ (a ⋀ (β ⋀ ɣ)) >>> Associativity of ⋀\n",
        " - ((a ⋁ β) ⋁ ɣ) ≡ (a ⋁ (β ⋁ ɣ)) >>> Associativity of ⋁\n",
        " - ¬(¬a) ≡ a >>> Double-negation elimination\n",
        " - (a ⟹ β) ≡ (¬β ⟹ ¬a) >>> Contraposition\n",
        " - (a ⟹ β) ≡ (¬a ⋁ β) >>> Implication elimination\n",
        " - (a ⇔ β) ≡ ((a ⟹ β) ⋀ (β ⟹ a)) >>> Biconditional elimination\n",
        " - ¬(a ⋀ β) ≡ (¬a ⋁ ¬β) >>> DeMorgan\n",
        " - ¬(a ⋁ β) ≡ (¬a ⋀ ¬β) >>> DeMorgan\n",
        " - ((a ⋀ β) ⋁ ɣ) ≡ ((a ⋁ ɣ) ⋀ (β ⋁ ɣ))) Distributivity of ⋁ over ⋀\n",
        " - ((a ⋁ β) ⋀ ɣ) ≡ ((a ⋀ ɣ) ⋁ (β ⋀ ɣ))) Distributivity of ⋀ over ⋁\n",
        " - For distributivity rule, it is Distributivity of (outside) over (inside)\n",
        "\\nInference Rules\n",
        " - a⟹β, a >>> β  Modus Ponens\n",
        " - a⇔β >>> (a ⟹ β) ⋀ (β ⟹ a) Biconditional Elimination\n",
        " - a⋀β >>> a, And Elimination\n",
        " - (a ⟹ β) ⋀ (β ⟹ a) >>> a ⇔ β Biconditional Elimination\n",
        "\\nMonotonicity: if KB⊨a then KB⋀β ⊨a\n",
        " - We can safely add to the KB, without invalidating anything else that we inferred\n",
        "\\nResolution\n",
        " - If ℓi and m are complementary literals, which means that one is the negation of another, \n",
        " - then we can eliminate them via unit resolution\n",
        " - (ℓ1 ⋁… ⋁ ℓk), m >>> (ℓ1 ⋁ … ⋁ ℓi-1 ⋁ ℓi+1 ⋁… ⋁ ℓk)\n",
        " - The resolution rule only applies to clauses (==disjunction of literals)\n",
        " - Every sentense can be equivalent to a conjunction of clauses\n",
        "\\nResolution Algorithm\n",
        " - The resolution algorithm is complete\n",
        " - Inference procedures based on resolution work using the principle of proof by contradiction\n",
        " - To show KB⊨a then we can show that KB ⋀ ¬a is unsatisfiable\n",
        "  - First, convert (KB ⋀ ¬a) into CNF\n",
        "  - Then apply the resolution rule to the resulting clauses.\n",
        "  - Resolve every pair that contains complementary literals to produce a new clause \n",
        "  - If that new clause isn’t already present, then add it to the set.\n",
        "  - Continue the process until one of two things happens:\n",
        "   - There are no new clauses that can be added. In this case, the KB does not entail a\n",
        "   - Two clauses resolve to yield the empty clause, in which case the KB does entail a\n",
        "\\nHorn Clauses and Definite Clauses\n",
        " - Definite clause – disjunction of literals where exactly one is positive\n",
        " - Horn clause – disjunction of literals where at most one is positive\n",
        "  - This includes definite clauses\n",
        "  - And clauses with no positive literals\n",
        " - Horn clauses are closed under resolution. If you apply resolution to a horn clause, you get back a horn clause\n",
        "\\nKBs with only definite clauses\n",
        " - Every definite clause can be written as an implication whose premise is a conjunction of positive literals whose conclusion is a positive literal\n",
        " - ¬ L1,1 ⋁ ¬ Breeze ⋁ B1,1 can be written as the implication L1,1 ⋀ Breeze ⟹ B1,1\n",
        " - Inference with Horn clauses can be done through the forward-chaining and backward-chaining algorithms\n",
        " - Deciding entailment with Horn clauses can be done in linear time with respect to the size of the KB\n",
        "\\nForward Chaining\n",
        " - Forward Chaining is a kind of data-driven reasoning. An agent can start with known data,\n",
        " - Adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions\n",
        " - It doesn’t have to have a specific query in mind to do so.\n",
        "\\nBackward chaining \n",
        " - Works backwards from a query. If the query is known to be true, then no work is needed. \n",
        " - Otherwise, the algorithm finds implications in the KB whose conclusions is the query. \n",
        " - If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"logical inference\" : \"how the definition of entailment can be applied to derive conclusions\",\n",
        "\"model checking\": \"numerates all possible models to check that a is true in all models in which KB is true, M(KB)⊆M(a)\",\n",
        "\"sound (truth-perceiving)\": \"an inference algorithm that derives only entailed sentences is sound\",\n",
        "\"completeness\": \"an inference algorithm is complete if it can derive any sentence that is entailed\",\n",
        "\"Axiom\": \"a sentence that is given\",\n",
        "\"Derived sentences\": \"– a new sentence that is derived from others sentences\",\n",
        "\"inference\": \"The process of deriving new sentences from old sentences\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "cellView": "form"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "T3cm1WV542_a"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "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"
      ]
    }
  ]
}