{
  "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": 29,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lzaavW96tcxM",
        "outputId": "80c7c54a-6de6-4700-803e-02e3a2d9161e"
      },
      "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": 30,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8DvZ57A-djo1",
        "outputId": "a5194929-3b3e-4ec4-ad43-19cfc46f76e5"
      },
      "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": 31,
      "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": 32,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Y2NfE1CKxzS-",
        "outputId": "b6a738e8-23af-45d6-8b5e-80b77d058dc0"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 107\n",
            "The length in characters is 738\n",
            "The length in words is 195\n",
            "The length in characters is 1228\n",
            "The length in words is 327\n",
            "The length in characters is 1973\n",
            "The length in words is 158\n",
            "The length in characters is 1021\n",
            "The length in words is 452\n",
            "The length in characters is 2938\n",
            "The length in words is 404\n",
            "The length in characters is 2599\n",
            "The length in words is 482\n",
            "The length in characters is 2975\n"
          ]
        }
      ],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" \n",
        "Machine learning is a subset of AI <br/>\n",
        "A computer which can pass the Turing test will require the following: <br/>\n",
        "- Natural Language Processing <br/>\n",
        "- Knowledge Representation to store: to story information <br/>\n",
        "- Automated reasoning: answer questions <br/>\n",
        "- Machine learning: adapt to change <br/>\n",
        "To pass a \"Total Turing Test\" a computer will also require the following: <br/>\n",
        "- Computer Vision and Speech Recognition <br/>\n",
        "- Robotics <br/>\n",
        "The cognitive Learning Approach concludes that we must also understand how humans think. We can learn about human thought in 3 ways: <br/>\n",
        "- Introspection: catching our thoughts <br/>\n",
        "- Experiments: observing a person in action <br/>\n",
        "- Brain Imaging: observing the brain in action <br/>\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",
        "Descartes suggests that one's consciousness implies one's existence. Related to this idea is the idea of mind body dualism. This is the idea that your mind is the separate from your body. <br/>\n",
        "- He came to the conclusion that perhaps the thing that differentiated the automatons from people is that automatons can only react, in particular predetermined fashions. <br/>\n",
        "The essence of the Turing test is that notion of passing, the notion of passing for something that you are not and convincing other people that you're something other than who you truly are. <br/>\n",
        "John Searle argues that Turing's test is insufficient. He contends that the Turing test could be solved through simple, simple manipulation and argues intuitively that simple, simple manipulation isn't true intelligence. Thus, giving the appearance of conversation is not sufficient to show that something is truly capable of intelligence. <br/>\n",
        "For example, the actions could be something like increase the speed of rotation of its wheels or turn on a light or make some sound. <br/>\n",
        "An *intelligent agent*, is not physical and the environment that it operates on is not a physical environment. The agent can still perceive and act on its environment. <br/>\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "Our definition of agents could even be satisfied by something as simple as a thermostat. It perceives the environment in the room with a thermometer and then acts to alter it. If it falls beneath a certain temperature. It does this by adjusting the boiler to increase the temperature in the radiators and therefore the room. Once it senses the temperature is exceeded the threshold, it acts again to turn the boiler off. <br/>\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. <br/><br/>\n",
        "- A human agent has eyes, ears, and other organs for sensors and hands, legs, vocal tract, and so on for actuators <br/>\n",
        "- A robotic agent might have cameras and infrared range finders for sensors and various motors for actuators <br/>\n",
        "- A software agent received file contents, network packets, and human input (keyboard/mouse/touchscreen) as sensory inputs and acts on the environment by writing files, sending network packets, and displaying information or generating sounds\n",
        "The term **percept** is used to refer to the content an agent's sensors are perceiving, while the percept sequence is the complete history of everything that the agent has ever peceived. <br/>\n",
        "In general, *an agent's choice of action at any given instant can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on anything it hasn't perceived.* <br/>\n",
        "- An agent's behaviour is described the agent function, which maps any given percept sequence to an action. <br/>\n",
        "An agent is defined as anything that can perceive its environment and act on it: <br/>\n",
        "- The parts of an agent that are used to perceive the environments are called it sensors. <br/>\n",
        "- The parts of the agent that allow it to act on the environment or call this actuators. <br/>\n",
        "- The signal that the agent receives from its sensors is called a percept. <br/>\n",
        "- A percept will represent an agent's perception for an instant in time. It could be represented as a vector of all the inputs that the agent receives through its sensors. <br/>\n",
        "We can say that *an agent is specified by a function called the agent function that takes in as input a sequence of percepts and then maps that sequence onto a sequence of actions.* The actions are going to be drawn from a set of possible actions that the robot could do via its actual orders. <br/>\n",
        "\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "AI has generally stuck to one notion called \"consequentialism\" <br/>\n",
        "- Consequentialism: we evaluate an agent's behaviour by its consequences <br/>\n",
        "- When an agent is pluncked down in an environment, it generates a sequence of actions according to the percepts it receives <br/>\n",
        "- This sequence of actions causes the environment to go through a sequence of states <br/>\n",
        "- If the sequence is desirable, then the agent has performed well <br/>\n",
        "Performance measure is used to measure desirability of a sequence of states <br/>\n",
        "- As a general rule, it is better to design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave <br/>\n",
        "- A rational agent: selects an action which maximises the performance measure for each possible percept sequence <br/>\n",
        "An omniscient agent knows the actual outcome of its actions and can act accordingly <br/>\n",
        "- Information gathering: doing actions in order to modify future percepts <br/>\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "A task environment is considered *fully observable*. If a task agent sensors can detect all of aspects of the environment that are relevant to the agent's choice of action. <br/>\n",
        "Self-driving cars operate in a *partially observable* environment. They have access to only the information that they can perceive via their sensors. So they have access to some information about their immediate surroundings, but not to the entire global picture. <br/>\n",
        "\n",
        "If an agent has no sensors at all then it is unobservable <br/>\n",
        "- Deterministic: if the next state of the environment is completely determined by the current state and the action executed by the agent <br/>\n",
        "- Non-deterministic: if the possibilities are listed without being quantified (i.e. there's a chance of rain tomorrow) <br/>\n",
        "- Stochastic: if it explicitly deals with probabilities (i.e. there's a 25% chance of rain tomorrow) <br/>\n",
        "Episodic versus Sequential <br/>\n",
        "In an episodic task, the agent's experience is divided into atomic episodes <br/>\n",
        "- In each episode the agent receives a percept and then performs a single action; the next episode does not dpeend on the actions taken in previous episodes <br/>\n",
        "Static versus Dynamic <br/>\n",
        "- Static environments do not change, while dynamic environment continuously ask the agent what it wants to do <br/>\n",
        "- If the environment itself does not change with the passage of time but the agent's performance score does, then that environment is semidynamic <br/>\n",
        "Distinct versus continous: how time is perceived <br/>\n",
        "Known versus Unknown <br/>\n",
        "- It is possible for a known environment to be partially observable (i.e. a solitaire game where one knows the rules but cannot see the cards) <br/>\n",
        "- It is also possible for an unknown environment to be fully observable (i.e. a video game where one can see the game state but doesn't know which buttons to press) <br/>\n",
        "The hardest case is \"partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown\" <br/>\n",
        "The laws of Thought Approach transcribes processes of thought, so-called 'logic' <br/>\n",
        "- Logic is conventionally understood as requiring knowledge of the world that is certain <br/>\n",
        "- The theory of probability fills gaps in uncertainty <br/>\n",
        "The Rational Agent Approach <br/>\n",
        "- A rational agent is one which acts so as to achieve the best outcome or the best expected outcome <br/>\n",
        "The rational agent approach has 2 advantages over the other approaches: <br/>\n",
        "- More general than \"Law of Though\" because correct inference is just one of several possible outcomes <br/>\n",
        "- More amenable to scientific development <br/>\n",
        "AI has focused on the study and construction of agents that do the right thing. <br/>\n",
        "- Defined by the objective\n",
        "The standard model assures that we will supply a fully specified objective to the machine <br/>\n",
        "The value alignment problem: the values or objectives put into the machine must be aligned with those of the human <br/>\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "Job of an AI is to design an agent program that implements the agent function - the mapping from percepts to actions <br/>\n",
        "An agent can escape from infinite loops if the agent can randomise its actions <br/>\n",
        "Model-based reflex agents <br/>\n",
        "The most effective way to handle partial observability is for the agent to *keep track of the part of the world it can't see now.* <br/>\n",
        "- The agent should maintian some sort of internal state that depends on the percept history and thereby reflects at least some of the unobserved aspects of the current state <br/>\n",
        "Updating this internal state information as time goes by requires 2 kinds of knowledge to be enconded in the agent program: <br/>\n",
        "- Information about how the world changes over time, which can be divided roughly into 2 parts: effects of the agent's actions and how the world evolves independently; this knowledge of how the world works is called the transition model of the world <br/>\n",
        "- Information about how the state of the world is reflected in the agent's percepts; known as a sensor model <br/>\n",
        "Agents utilising these models are known as model-based agents <br/>\n",
        "Goal-based agents <br/>\n",
        "Goals alone are not enough to generate high-quality behaviour in most environments <br/>\n",
        "Goal-based agents are more flexible because the knowledge that supports its decisions is represented explicitly and can be modified <br/>\n",
        "Utility-based agents <br/>\n",
        "An agent's utility function is an internalisation of the performance meaure; provided that the internal utility function and the external performance measure are in agreement <br/>\n",
        "- Like goal-based agents, a utility-based agent has many advantages in terms of flexibility and learning <br/>\n",
        "- When there are conflicting goals, where only some of which can be achieved (i.e. speed and safety), the utility function specifies the appropriate tradeoff <br/>\n",
        "- When there are several goals that the agent can aim for, none of which can be achieved with certainty, then the utility function specifies the way in which the likelihood of success can be weighed against the importance of the goals <br/>\n",
        "A rational utility-based agent chooses the action that maximises the expected utility of the action outcomes <br/>\n",
        "How the components of agent programs work <br/>\n",
        "In an atomic representation, each state of the world is indivisible <br/>\n",
        "A factored representation splits up each state into a fixed set of variables or attributes, each of which can have a higher value <br/>\n",
        "A structured representation is one where objects and their various and varying relationships are described explicitly <br/>\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "- Let's define *rational behavior* as doing the right thing, since it's obviously better to do the right thing than it is to do the wrong thing. <br/>\n",
        "- The minimum algorithm works when we're playing against a rational opponent who's also trying to maximize their own score in the game. <br/>\n",
        "- Our job as the A.I. practitioner is to design and implement rational agents. Our choice of algorithms for our agent program will depend on the kind of task environment that we're dealing with. <br/>\n",
        "- Another way of thinking about deterministic environments is on where the resulting state of the world is going to be completely determined based on the current state and the action that the agent picked. <br/>\n",
        "- In non-deterministic environments, the agent can pick an action, but then the outcome is uncertain. There can be many possible resulting states of the environment based on the agent executing that action. <br/>\n",
        "- Environments with nondeterministic outcomes are often times stochastic in nature. Stochastic means probabilistic. If we can quantify how likely each of the possible outcomes is, then the environment is a stochastic environment. <br/>\n",
        "- A non-deterministic environment is similar, but we just haven't quantified the likelihood of the different possible outcomes. <br/>\n",
        "- TASC environments can be either episodic or sequential. <br/>\n",
        "- An episodic environment is one in which the agent needs to process self-contained episodes. The agent perceives the environment and then performs a single action and the choice of each action is not dependent on any previous action. <br/>\n",
        "- In sequential environments the current decision can affect all future actions. In this case, an immediate decision is going to impact the space of possible choices that will come next. In such cases, agents will need to plan ahead multiple steps in the future in order to come up with the desired outcome. <br/>\n",
        "- Static versus Dynamic<br/>\n",
        "- A static environment is one where the environment remains unchanged while the agent is deliberating about what action to take. An example of this is like a crossword puzzle where you can think as long as you'd like before taking the action to write out a word or enter a letter. <br/>\n",
        "- This stands in contrast with dynamic environments where while the agent is thinking about what action to take, the environment is changing all around it. Self-driving cars have to quickly react to action. <br/>\n",
        "- An environment can be categorized as *semi dynamic* if it doesn't actually change with the passage of time. But the agents score does change. <br/>\n",
        "- Environment can be represented using a discrete number of distinct states in discrete environments. There's also a limited number of clearly defined actions. This means that there's a finite set of actions that an agent can take. <br/>\n",
        "- In continuous environments we need to think about the state representation of the environment or the way we handle time as being continuous. <br/>\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"the content an agent's sensors are perceiving\",\n",
        "\"percept sequence\" : \"the complete history of everything that the agent has ever peceived\",\n",
        "\"sensors\" : \"parts of an agent that are used to perceive the environments\",\n",
        "\"actuators\" : \"parts of an that allow it to act on an environment\",\n",
        "\"agent function\" : \"takes in a sequence of percepts and then returns an action.\",\n",
        "\"Rational agent\" : \"one the selects an action to maximise the expected value of its performance measure for each possible percept sequence\"\n",
        "\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter1_1.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter1_1))\n",
        "\n",
        "print(\"The length in words is\", len(chapter27_1.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter27_1))\n",
        "\n",
        "print(\"The length in words is\", len(chapter2_1.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter2_1))\n",
        "\n",
        "print(\"The length in words is\", len(chapter2_2.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter2_2))\n",
        "\n",
        "print(\"The length in words is\", len(chapter2_3.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter2_3))\n",
        "\n",
        "print(\"The length in words is\", len(chapter2_4.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter2_4))\n",
        "\n",
        "print(\"The length in words is\", len(module1_lecture_notes.split(' ')))\n",
        "print(\"The length in characters is\", len(module1_lecture_notes))\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": 33,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "gYYeNcdM_maE",
        "outputId": "df64e504-bf5d-4a89-c1d9-2f7cfb776968"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " \n",
              "Machine learning is a subset of AI <br/>\n",
              "A computer which can pass the Turing test will require the following: <br/>\n",
              "- Natural Language Processing <br/>\n",
              "- Knowledge Representation to store: to story information <br/>\n",
              "- Automated reasoning: answer questions <br/>\n",
              "- Machine learning: adapt to change <br/>\n",
              "To pass a \"Total Turing Test\" a computer will also require the following: <br/>\n",
              "- Computer Vision and Speech Recognition <br/>\n",
              "- Robotics <br/>\n",
              "The cognitive Learning Approach concludes that we must also understand how humans think. We can learn about human thought in 3 ways: <br/>\n",
              "- Introspection: catching our thoughts <br/>\n",
              "- Experiments: observing a person in action <br/>\n",
              "- Brain Imaging: observing the brain in action <br/>\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              "\n",
              "Descartes suggests that one's consciousness implies one's existence. Related to this idea is the idea of mind body dualism. This is the idea that your mind is the separate from your body. <br/>\n",
              "- He came to the conclusion that perhaps the thing that differentiated the automatons from people is that automatons can only react, in particular predetermined fashions. <br/>\n",
              "The essence of the Turing test is that notion of passing, the notion of passing for something that you are not and convincing other people that you're something other than who you truly are. <br/>\n",
              "John Searle argues that Turing's test is insufficient. He contends that the Turing test could be solved through simple, simple manipulation and argues intuitively that simple, simple manipulation isn't true intelligence. Thus, giving the appearance of conversation is not sufficient to show that something is truly capable of intelligence. <br/>\n",
              "For example, the actions could be something like increase the speed of rotation of its wheels or turn on a light or make some sound. <br/>\n",
              "An *intelligent agent*, is not physical and the environment that it operates on is not a physical environment. The agent can still perceive and act on its environment. <br/>\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              "\n",
              "Our definition of agents could even be satisfied by something as simple as a thermostat. It perceives the environment in the room with a thermometer and then acts to alter it. If it falls beneath a certain temperature. It does this by adjusting the boiler to increase the temperature in the radiators and therefore the room. Once it senses the temperature is exceeded the threshold, it acts again to turn the boiler off. <br/>\n",
              "\n",
              "\n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              "\n",
              "An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. <br/><br/>\n",
              "- A human agent has eyes, ears, and other organs for sensors and hands, legs, vocal tract, and so on for actuators <br/>\n",
              "- A robotic agent might have cameras and infrared range finders for sensors and various motors for actuators <br/>\n",
              "- A software agent received file contents, network packets, and human input (keyboard/mouse/touchscreen) as sensory inputs and acts on the environment by writing files, sending network packets, and displaying information or generating sounds\n",
              "The term **percept** is used to refer to the content an agent's sensors are perceiving, while the percept sequence is the complete history of everything that the agent has ever peceived. <br/>\n",
              "In general, *an agent's choice of action at any given instant can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on anything it hasn't perceived.* <br/>\n",
              "- An agent's behaviour is described the agent function, which maps any given percept sequence to an action. <br/>\n",
              "An agent is defined as anything that can perceive its environment and act on it: <br/>\n",
              "- The parts of an agent that are used to perceive the environments are called it sensors. <br/>\n",
              "- The parts of the agent that allow it to act on the environment or call this actuators. <br/>\n",
              "- The signal that the agent receives from its sensors is called a percept. <br/>\n",
              "- A percept will represent an agent's perception for an instant in time. It could be represented as a vector of all the inputs that the agent receives through its sensors. <br/>\n",
              "We can say that *an agent is specified by a function called the agent function that takes in as input a sequence of percepts and then maps that sequence onto a sequence of actions.* The actions are going to be drawn from a set of possible actions that the robot could do via its actual orders. <br/>\n",
              "\n",
              "\n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              "\n",
              "AI has generally stuck to one notion called \"consequentialism\" <br/>\n",
              "- Consequentialism: we evaluate an agent's behaviour by its consequences <br/>\n",
              "- When an agent is pluncked down in an environment, it generates a sequence of actions according to the percepts it receives <br/>\n",
              "- This sequence of actions causes the environment to go through a sequence of states <br/>\n",
              "- If the sequence is desirable, then the agent has performed well <br/>\n",
              "Performance measure is used to measure desirability of a sequence of states <br/>\n",
              "- As a general rule, it is better to design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave <br/>\n",
              "- A rational agent: selects an action which maximises the performance measure for each possible percept sequence <br/>\n",
              "An omniscient agent knows the actual outcome of its actions and can act accordingly <br/>\n",
              "- Information gathering: doing actions in order to modify future percepts <br/>\n",
              "\n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              "\n",
              "A task environment is considered *fully observable*. If a task agent sensors can detect all of aspects of the environment that are relevant to the agent's choice of action. <br/>\n",
              "Self-driving cars operate in a *partially observable* environment. They have access to only the information that they can perceive via their sensors. So they have access to some information about their immediate surroundings, but not to the entire global picture. <br/>\n",
              "\n",
              "If an agent has no sensors at all then it is unobservable <br/>\n",
              "- Deterministic: if the next state of the environment is completely determined by the current state and the action executed by the agent <br/>\n",
              "- Non-deterministic: if the possibilities are listed without being quantified (i.e. there's a chance of rain tomorrow) <br/>\n",
              "- Stochastic: if it explicitly deals with probabilities (i.e. there's a 25% chance of rain tomorrow) <br/>\n",
              "Episodic versus Sequential <br/>\n",
              "In an episodic task, the agent's experience is divided into atomic episodes <br/>\n",
              "- In each episode the agent receives a percept and then performs a single action; the next episode does not dpeend on the actions taken in previous episodes <br/>\n",
              "Static versus Dynamic <br/>\n",
              "- Static environments do not change, while dynamic environment continuously ask the agent what it wants to do <br/>\n",
              "- If the environment itself does not change with the passage of time but the agent's performance score does, then that environment is semidynamic <br/>\n",
              "Distinct versus continous: how time is perceived <br/>\n",
              "Known versus Unknown <br/>\n",
              "- It is possible for a known environment to be partially observable (i.e. a solitaire game where one knows the rules but cannot see the cards) <br/>\n",
              "- It is also possible for an unknown environment to be fully observable (i.e. a video game where one can see the game state but doesn't know which buttons to press) <br/>\n",
              "The hardest case is \"partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown\" <br/>\n",
              "The laws of Thought Approach transcribes processes of thought, so-called 'logic' <br/>\n",
              "- Logic is conventionally understood as requiring knowledge of the world that is certain <br/>\n",
              "- The theory of probability fills gaps in uncertainty <br/>\n",
              "The Rational Agent Approach <br/>\n",
              "- A rational agent is one which acts so as to achieve the best outcome or the best expected outcome <br/>\n",
              "The rational agent approach has 2 advantages over the other approaches: <br/>\n",
              "- More general than \"Law of Though\" because correct inference is just one of several possible outcomes <br/>\n",
              "- More amenable to scientific development <br/>\n",
              "AI has focused on the study and construction of agents that do the right thing. <br/>\n",
              "- Defined by the objective\n",
              "The standard model assures that we will supply a fully specified objective to the machine <br/>\n",
              "The value alignment problem: the values or objectives put into the machine must be aligned with those of the human <br/>\n",
              "\n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              "\n",
              "Job of an AI is to design an agent program that implements the agent function - the mapping from percepts to actions <br/>\n",
              "An agent can escape from infinite loops if the agent can randomise its actions <br/>\n",
              "Model-based reflex agents <br/>\n",
              "The most effective way to handle partial observability is for the agent to *keep track of the part of the world it can't see now.* <br/>\n",
              "- The agent should maintian some sort of internal state that depends on the percept history and thereby reflects at least some of the unobserved aspects of the current state <br/>\n",
              "Updating this internal state information as time goes by requires 2 kinds of knowledge to be enconded in the agent program: <br/>\n",
              "- Information about how the world changes over time, which can be divided roughly into 2 parts: effects of the agent's actions and how the world evolves independently; this knowledge of how the world works is called the transition model of the world <br/>\n",
              "- Information about how the state of the world is reflected in the agent's percepts; known as a sensor model <br/>\n",
              "Agents utilising these models are known as model-based agents <br/>\n",
              "Goal-based agents <br/>\n",
              "Goals alone are not enough to generate high-quality behaviour in most environments <br/>\n",
              "Goal-based agents are more flexible because the knowledge that supports its decisions is represented explicitly and can be modified <br/>\n",
              "Utility-based agents <br/>\n",
              "An agent's utility function is an internalisation of the performance meaure; provided that the internal utility function and the external performance measure are in agreement <br/>\n",
              "- Like goal-based agents, a utility-based agent has many advantages in terms of flexibility and learning <br/>\n",
              "- When there are conflicting goals, where only some of which can be achieved (i.e. speed and safety), the utility function specifies the appropriate tradeoff <br/>\n",
              "- When there are several goals that the agent can aim for, none of which can be achieved with certainty, then the utility function specifies the way in which the likelihood of success can be weighed against the importance of the goals <br/>\n",
              "A rational utility-based agent chooses the action that maximises the expected utility of the action outcomes <br/>\n",
              "How the components of agent programs work <br/>\n",
              "In an atomic representation, each state of the world is indivisible <br/>\n",
              "A factored representation splits up each state into a fixed set of variables or attributes, each of which can have a higher value <br/>\n",
              "A structured representation is one where objects and their various and varying relationships are described explicitly <br/>\n",
              "\n",
              "\n",
              "## Module 1 Lecture Notes\n",
              "\n",
              "- Let's define *rational behavior* as doing the right thing, since it's obviously better to do the right thing than it is to do the wrong thing. <br/>\n",
              "- The minimum algorithm works when we're playing against a rational opponent who's also trying to maximize their own score in the game. <br/>\n",
              "- Our job as the A.I. practitioner is to design and implement rational agents. Our choice of algorithms for our agent program will depend on the kind of task environment that we're dealing with. <br/>\n",
              "- Another way of thinking about deterministic environments is on where the resulting state of the world is going to be completely determined based on the current state and the action that the agent picked. <br/>\n",
              "- In non-deterministic environments, the agent can pick an action, but then the outcome is uncertain. There can be many possible resulting states of the environment based on the agent executing that action. <br/>\n",
              "- Environments with nondeterministic outcomes are often times stochastic in nature. Stochastic means probabilistic. If we can quantify how likely each of the possible outcomes is, then the environment is a stochastic environment. <br/>\n",
              "- A non-deterministic environment is similar, but we just haven't quantified the likelihood of the different possible outcomes. <br/>\n",
              "- TASC environments can be either episodic or sequential. <br/>\n",
              "- An episodic environment is one in which the agent needs to process self-contained episodes. The agent perceives the environment and then performs a single action and the choice of each action is not dependent on any previous action. <br/>\n",
              "- In sequential environments the current decision can affect all future actions. In this case, an immediate decision is going to impact the space of possible choices that will come next. In such cases, agents will need to plan ahead multiple steps in the future in order to come up with the desired outcome. <br/>\n",
              "- Static versus Dynamic<br/>\n",
              "- A static environment is one where the environment remains unchanged while the agent is deliberating about what action to take. An example of this is like a crossword puzzle where you can think as long as you'd like before taking the action to write out a word or enter a letter. <br/>\n",
              "- This stands in contrast with dynamic environments where while the agent is thinking about what action to take, the environment is changing all around it. Self-driving cars have to quickly react to action. <br/>\n",
              "- An environment can be categorized as *semi dynamic* if it doesn't actually change with the passage of time. But the agents score does change. <br/>\n",
              "- Environment can be represented using a discrete number of distinct states in discrete environments. There's also a limited number of clearly defined actions. This means that there's a finite set of actions that an agent can take. <br/>\n",
              "- In continuous environments we need to think about the state representation of the environment or the way we handle time as being continuous. <br/>\n",
              "\n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Agent** - anything that can perceive and act in an environment\n",
              "* **Percept** - the content an agent's sensors are perceiving\n",
              "* **Percept sequence** - the complete history of everything that the agent has ever peceived\n",
              "* **Sensors** - parts of an agent that are used to perceive the environments\n",
              "* **Actuators** - parts of an that allow it to act on an environment\n",
              "* **Agent function** - takes in a sequence of percepts and then returns an action.\n",
              "* **Rational agent** - one the selects an action to maximise the expected value of its performance measure for each possible percept sequence\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": 42,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DpBvu7EMx7sy",
        "outputId": "a41444e2-0f34-495e-ff91-c92fd5f7392b"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 439\n",
            "The length in characters is 2265\n"
          ]
        }
      ],
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "Strongly typed means that variables have a pre-defined type and one which matters when performing operations, while dynamically typed refers to the fact that the variable is a value attached to a name, such that its type is only determined during runtime. An example of the former in Python is print(1+1) outputting 2 while print(1+'1') would produce an error. An example of the latter is how i = 2 might be an integer but its type can be changed to a string through str(i).\n",
        "Dictionaries map a key to a value in key:value pairs. By definition, the values of the dictionary can be any type, while the key are unique and must be of an immutable type such as a string or a number rather than an array or list. The solution is to flip the order of the pairs such that: points_to_names = {'home' : [0,0], 'school' : [1,2], 'market': [-1,1]}\n",
        "```\n",
        "# Working with Lists\n",
        "def extract_and_apply(l, p, f):\n",
        "    return [f(x) for x in l if p(x)]\n",
        "def concatenate(seqs):\n",
        "    return [j for i in seqs for j in i]\n",
        "def transpose(matrix):\n",
        "    return [list(m) for m in zip(*matrix)]\n",
        "# Sequence Slicing\n",
        "def copy(seq):\n",
        "    return seq[:]\n",
        "def all_but_last(seq):\n",
        "    return seq[:-1]\n",
        "def every_other(seq):\n",
        "    return seq[::2]\n",
        "# Combinatorial Algorithms\n",
        "def prefixes(seq):\n",
        "    for i in range(len(seq)+1):\n",
        "        yield seq[0:i]\n",
        "def suffixes(seq):\n",
        "    for i in range(len(seq)+1):\n",
        "        yield seq[i:]\n",
        "def slices(seq):\n",
        "    for j in range(len(seq)+1):\n",
        "        for i in range(len(seq)+1):\n",
        "            if len(seq[j:i])>0:\n",
        "                yield seq[j:i]\n",
        "# Text Processing\n",
        "def normalize(text):\n",
        "    return ‘ ‘.join(text.lower().split())\n",
        "def no_vowels(text):\n",
        "    return ‘‘.join([x for x in text if x not in (‘a’,’A’,’e’,’E’,’i’,’I’,’o’,’O’,’u’,’U’)])\n",
        "def digits_to_words(text):\n",
        "    dic = {'0':'zero','1':'one','2':'two','3':'three','4':'four','5':'five','6':'six','7':'seven','8':'eight','9':'nine'}\n",
        "    y = ‘‘\n",
        "    for x in text:\n",
        "        if x.isdigit() == True:\n",
        "            y = y+dic[x]+’ ‘\n",
        "    if y != ‘‘:\n",
        "        y = y.rstrip(y[-1])\n",
        "    return y\n",
        "def to_mixed_case(name):\n",
        "    name = name.lower()\n",
        "    for x in range(len(name)):\n",
        "        if name[x-1] == ‘_’:\n",
        "            name = name.replace(name[x],name[x].upper())\n",
        "    name2 = name.replace(‘_’,’’)\n",
        "    return name2.replace(name2[0],name2[0].lower())\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "'mutability' : 'your definition here',\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(module2_lecture_notes.split(' ')))\n",
        "print(\"The length in characters is\", len(module2_lecture_notes))\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 43,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "ydOK__lwWgdp",
        "outputId": "35f7a866-cef6-4f54-adce-f629f9c4b3fc"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "\n",
              "Strongly typed means that variables have a pre-defined type and one which matters when performing operations, while dynamically typed refers to the fact that the variable is a value attached to a name, such that its type is only determined during runtime. An example of the former in Python is print(1+1) outputting 2 while print(1+'1') would produce an error. An example of the latter is how i = 2 might be an integer but its type can be changed to a string through str(i).\n",
              "Dictionaries map a key to a value in key:value pairs. By definition, the values of the dictionary can be any type, while the key are unique and must be of an immutable type such as a string or a number rather than an array or list. The solution is to flip the order of the pairs such that: points_to_names = {'home' : [0,0], 'school' : [1,2], 'market': [-1,1]}\n",
              "```\n",
              "# Working with Lists\n",
              "def extract_and_apply(l, p, f):\n",
              "    return [f(x) for x in l if p(x)]\n",
              "def concatenate(seqs):\n",
              "    return [j for i in seqs for j in i]\n",
              "def transpose(matrix):\n",
              "    return [list(m) for m in zip(*matrix)]\n",
              "# Sequence Slicing\n",
              "def copy(seq):\n",
              "    return seq[:]\n",
              "def all_but_last(seq):\n",
              "    return seq[:-1]\n",
              "def every_other(seq):\n",
              "    return seq[::2]\n",
              "# Combinatorial Algorithms\n",
              "def prefixes(seq):\n",
              "    for i in range(len(seq)+1):\n",
              "        yield seq[0:i]\n",
              "def suffixes(seq):\n",
              "    for i in range(len(seq)+1):\n",
              "        yield seq[i:]\n",
              "def slices(seq):\n",
              "    for j in range(len(seq)+1):\n",
              "        for i in range(len(seq)+1):\n",
              "            if len(seq[j:i])>0:\n",
              "                yield seq[j:i]\n",
              "# Text Processing\n",
              "def normalize(text):\n",
              "    return ‘ ‘.join(text.lower().split())\n",
              "def no_vowels(text):\n",
              "    return ‘‘.join([x for x in text if x not in (‘a’,’A’,’e’,’E’,’i’,’I’,’o’,’O’,’u’,’U’)])\n",
              "def digits_to_words(text):\n",
              "    dic = {'0':'zero','1':'one','2':'two','3':'three','4':'four','5':'five','6':'six','7':'seven','8':'eight','9':'nine'}\n",
              "    y = ‘‘\n",
              "    for x in text:\n",
              "        if x.isdigit() == True:\n",
              "            y = y+dic[x]+’ ‘\n",
              "    if y != ‘‘:\n",
              "        y = y.rstrip(y[-1])\n",
              "    return y\n",
              "def to_mixed_case(name):\n",
              "    name = name.lower()\n",
              "    for x in range(len(name)):\n",
              "        if name[x-1] == ‘_’:\n",
              "            name = name.replace(name[x],name[x].upper())\n",
              "    name2 = name.replace(‘_’,’’)\n",
              "    return name2.replace(name2[0],name2[0].lower())\n",
              "```\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": 66,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "BN0b1eVYx-nd",
        "outputId": "1d9fa7d0-7ecc-49ab-dfba-39bc8cacb94f"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 338\n",
            "The length in characters is 2057\n",
            "The length in words is 1\n",
            "The length in characters is 7\n",
            "The length in words is 193\n",
            "The length in characters is 1231\n",
            "The length in words is 159\n",
            "The length in characters is 1028\n",
            "The length in words is 5\n",
            "The length in characters is 19\n"
          ]
        }
      ],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"\n",
        "A sequence of actions form a path, and a solution is a path from the initial state to a goal state\n",
        "- We assume action costs are additive\n",
        "An optimal solution has the lowest path cost among all solution\n",
        "Abstraction - the process of removing detail from a representation\n",
        "Search algorithms - takes a search problem as input and returns a solution or an indication of failure\n",
        "Frontier separates two regions of the state-space graph\n",
        "- An interior region where every state has been expanded\n",
        "- An exterior region of states that have not yet been reached\n",
        "The frontier is the set of nodes that have been reached but not yet expanded\n",
        "Best First Search - on each iteration the node on the frontier with minimum f(n) value is chosen\n",
        "Priority queue - first pops the node with the minimum cost according to f(n)\n",
        "FIFO queue - First-In-First-Out queue pops the node added to the queue first\n",
        "LIFO queue - Last-In-First-Out queue (stack) pops out first the most recently added queue\n",
        "Graph search - checks for redundant paths\n",
        "Tree-like search - does not check for redundant paths\n",
        "- Breadth First Search is a tree-like search </br>\n",
        "Algorithms can be evaluated in four ways:\n",
        "- completeness - is the algorithm guaranteed to find a solution when there is one?\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 money is needed? </br>\n",
        "A complete algorithm must be capable of systematically exploring every state that is reachable from the initial state\n",
        "- A search algorithm must be systematic in the way it explores an infant state space </br>\n",
        "In computer science, the typical measure is the size of the state-space graph\n",
        "- $|V|+|E|$\n",
        "- Where $|V|$ is the number of vertices\n",
        "- Where $|E|$ is the number of edges (stinct state/action pairs) </br>\n",
        "Complexity can also be measured in terms of depth (d), the number of actions in an optimal solution\n",
        "- m, maximum number of actions in any path\n",
        "- b, branching factor or number of successors of a node </br>\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "Searc\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "Depth First Search (DFS) always expands the deepest node in the frontier first\n",
        "- Usually implemented as a tree-like search\n",
        "- The search then 'backs up' to the next deepest node with unexpanded successors\n",
        "- Not cost-optimal - returns the first solution it finds, even if it is not the cheapest\n",
        "- For solutions where a tree-like search is feasible, DFS requires less memory\n",
        "- Memory complexity of only $O(bm)$ </br>\n",
        "Depth Limited Search can be used to prevent DFS from wandering down an infinite path\n",
        "- We supply a depth limit, $\\ell$, as if they have no successors\n",
        "- Time complexity is $O(b^{\\ell})$\n",
        "- Space complexity is $O(b\\ell)$\n",
        "- However, $\\ell$ must be optimal </br>\n",
        "Iterative Deepening search solves the problem of optimising the $\\ell$ value, by trying all values until a solution is found\n",
        "- Time complexity is $O(b^d)$ when there is a solution or $O(b^m)$ when there is not\n",
        "- Space complexity is $O(bd)$ when there is a solution or $O(bm)$ when there is not\n",
        "Bidirectional search simultaneously searches forwards and backwards from the initial state, hoping that the two searches will meet\n",
        "- Needs to keep track of 2 frontiers and 2 tables of ready states\n",
        "- Time complexity is $O(b^{d/2})\n",
        "- Space complexity is $O(b^{d/2})\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "Bread-First Search (BFS) is appropriate when all actions have the same cost\n",
        "- The root node is expanded first, then all the successors of the root node are expanded next, then their successors\n",
        "- **Asymptotic** search strategy that is **complete** even on infinite spaces\n",
        "- BFS can be improved with FIFO queue\n",
        "- Cost-optimal for problems whose actions have the same cost\n",
        "- The total number of gneerated notes is: $1+b+b^2+b^3+...+b^d = O(b^d)$\n",
        "- At $d = 14$, even with infinite memory, its would take 3.5 years </br>\n",
        "Dijkstra's algorithm (or Uniform-Cost Search) spreads out in waves of uniform path cost\n",
        "- Complexity of UCS is characterised in terms of **$C^{*}$**, the cost of the optimal solution, and $\\epsilon$, a lower bound of each action, with $\\epsilon >0$\n",
        "- Worst case time complexity is: $O(b^{1+LC^{*}/\\epsilon ⅃})$\n",
        "- Which can be worse than BFS as UCS can explore large trees of actions with low costs before exploring paths invading a high-cost and perhaps useful action\n",
        "- UCS is **complete** and **cost-optimal**\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search, forming a path to a goal state\",    \n",
        "\"Search problem\" : \"a set of states that the environment can be in - the state space\",\n",
        "\"Initial state\" : \"where the agent starts\",\n",
        "\"Action\" : \"returns a finite set of actions\",\n",
        "\"Cost function\" : \"gives the numeric cost of applying an action\"\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter3_1.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter3_1))\n",
        "\n",
        "print(\"The length in words is\", len(chapter3_2.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter3_2))\n",
        "\n",
        "print(\"The length in words is\", len(chapter3_3.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter3_3))\n",
        "\n",
        "print(\"The length in words is\", len(chapter3_4.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter3_4))\n",
        "\n",
        "print(\"The length in words is\", len(module3_lecture_notes.split(' ')))\n",
        "print(\"The length in characters is\", len(module3_lecture_notes))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 67,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "a062803d-b16a-46c7-84c0-22aa47f41c08"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              "\n",
              "A sequence of actions form a path, and a solution is a path from the initial state to a goal state\n",
              "- We assume action costs are additive\n",
              "An optimal solution has the lowest path cost among all solution\n",
              "Abstraction - the process of removing detail from a representation\n",
              "Search algorithms - takes a search problem as input and returns a solution or an indication of failure\n",
              "Frontier separates two regions of the state-space graph\n",
              "- An interior region where every state has been expanded\n",
              "- An exterior region of states that have not yet been reached\n",
              "The frontier is the set of nodes that have been reached but not yet expanded\n",
              "Best First Search - on each iteration the node on the frontier with minimum f(n) value is chosen\n",
              "Priority queue - first pops the node with the minimum cost according to f(n)\n",
              "FIFO queue - First-In-First-Out queue pops the node added to the queue first\n",
              "LIFO queue - Last-In-First-Out queue (stack) pops out first the most recently added queue\n",
              "Graph search - checks for redundant paths\n",
              "Tree-like search - does not check for redundant paths\n",
              "- Breadth First Search is a tree-like search </br>\n",
              "Algorithms can be evaluated in four ways:\n",
              "- completeness - is the algorithm guaranteed to find a solution when there is one?\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 money is needed? </br>\n",
              "A complete algorithm must be capable of systematically exploring every state that is reachable from the initial state\n",
              "- A search algorithm must be systematic in the way it explores an infant state space </br>\n",
              "In computer science, the typical measure is the size of the state-space graph\n",
              "- $|V|+|E|$\n",
              "- Where $|V|$ is the number of vertices\n",
              "- Where $|E|$ is the number of edges (stinct state/action pairs) </br>\n",
              "Complexity can also be measured in terms of depth (d), the number of actions in an optimal solution\n",
              "- m, maximum number of actions in any path\n",
              "- b, branching factor or number of successors of a node </br>\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              "\n",
              "Searc\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              "\n",
              "Depth First Search (DFS) always expands the deepest node in the frontier first\n",
              "- Usually implemented as a tree-like search\n",
              "- The search then 'backs up' to the next deepest node with unexpanded successors\n",
              "- Not cost-optimal - returns the first solution it finds, even if it is not the cheapest\n",
              "- For solutions where a tree-like search is feasible, DFS requires less memory\n",
              "- Memory complexity of only $O(bm)$ </br>\n",
              "Depth Limited Search can be used to prevent DFS from wandering down an infinite path\n",
              "- We supply a depth limit, $\\ell$, as if they have no successors\n",
              "- Time complexity is $O(b^{\\ell})$\n",
              "- Space complexity is $O(b\\ell)$\n",
              "- However, $\\ell$ must be optimal </br>\n",
              "Iterative Deepening search solves the problem of optimising the $\\ell$ value, by trying all values until a solution is found\n",
              "- Time complexity is $O(b^d)$ when there is a solution or $O(b^m)$ when there is not\n",
              "- Space complexity is $O(bd)$ when there is a solution or $O(bm)$ when there is not\n",
              "Bidirectional search simultaneously searches forwards and backwards from the initial state, hoping that the two searches will meet\n",
              "- Needs to keep track of 2 frontiers and 2 tables of ready states\n",
              "- Time complexity is $O(b^{d/2})\n",
              "- Space complexity is $O(b^{d/2})\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              "\n",
              "Bread-First Search (BFS) is appropriate when all actions have the same cost\n",
              "- The root node is expanded first, then all the successors of the root node are expanded next, then their successors\n",
              "- **Asymptotic** search strategy that is **complete** even on infinite spaces\n",
              "- BFS can be improved with FIFO queue\n",
              "- Cost-optimal for problems whose actions have the same cost\n",
              "- The total number of gneerated notes is: $1+b+b^2+b^3+...+b^d = O(b^d)$\n",
              "- At $d = 14$, even with infinite memory, its would take 3.5 years </br>\n",
              "Dijkstra's algorithm (or Uniform-Cost Search) spreads out in waves of uniform path cost\n",
              "- Complexity of UCS is characterised in terms of **$C^{*}$**, the cost of the optimal solution, and $\\epsilon$, a lower bound of each action, with $\\epsilon >0$\n",
              "- Worst case time complexity is: $O(b^{1+LC^{*}/\\epsilon ⅃})$\n",
              "- Which can be worse than BFS as UCS can explore large trees of actions with low costs before exploring paths invading a high-cost and perhaps useful action\n",
              "- UCS is **complete** and **cost-optimal**\n",
              "\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search, forming a path to a goal state\n",
              "* **Search problem** - a set of states that the environment can be in - the state space\n",
              "* **Initial state** - where the agent starts\n",
              "* **Action** - returns a finite set of actions\n",
              "* **Cost function** - gives the numeric cost of applying an action\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": 77,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "tuFC8w7CyCns",
        "outputId": "5eef00a9-b779-43a7-8cef-38ed8dd438d5"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 446\n",
            "The length in characters is 2729\n",
            "The length in words is 106\n",
            "The length in characters is 613\n"
          ]
        }
      ],
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "Informed search strategies utilise a heuristic function , $(n)$\n",
        "- $h(n)$ - estimated cost of the cheapest path from the state at node n to a goal state\n",
        "Greedy Best-First search is a best-first search which expands first the node with the lowest $h(n)$ value - the node which appears to be the closest to the goal\n",
        "- However, greediness can lead to a worse result sometimes\n",
        "- **Complete** for n finite spaces but not in finite ones\n",
        "- Worst-case time and space complexity is $O(|V|)$\n",
        "- A good heuristic function can result in $O(bm)$\n",
        "- A* Search is one of the most common informed search algorithms, a best-first search which uses: $f(n) = g(n) + h(n)$\n",
        "- A* search is complete\n",
        "- Depends on certain properties of the heuristic\n",
        "Admissible heuristic - one that never overestimates the cost to reach a goal (also known as optimistic)\n",
        "A* is **cost-optimal**, which can be shown with a proof by contradiction\n",
        "A* search be visualised by using search contours\n",
        "- Monoatomic - path cost always increases as you go along a path as action costs are always positive\n",
        "- satisficing solutions - willing to accept solutions that are suboptimal, but are 'good enough'\n",
        "If we allow A* search to use an inadmissible heuristic - one that may overestimate - then we risk missing the optimal solution\n",
        "- However, the heuristic can potnetially be more accurate, thereby reducing the number of nodes expanded\n",
        "We can use a weighted A* search where the heuristic function is weighted more heavily, giving us the evaluation function: $f(n) = g(n) + W + h(n)$ for some $W>1$\n",
        "Bounded Suboptimal Search - we look for a solution that is guaranteed to be within a constant factor W of the optimal cost\n",
        "Bounded Cost Search - we look for a solution whoose value cost is less than some constant C\n",
        "Unbounded Cost Search - we accept a solution of any cost as long as we can find it quickly\n",
        "- Example is Speed search. Greedy best-first search that uses the estimated number of actions requires as a heuristic - regardless of cost\n",
        "Main problem for A* is memory\n",
        "**Beam Search** limits the size of the frontier. This makes the search incomplete and suboptimal, but we can choose h to make good use of available memory\n",
        "Iterative-Deepening A* Search (IDA*) gives all the benefits of A* without the requirement to keep all reached state in memory, at a cost of visiting some states multiple times\n",
        "Recursive Best-First Search (RBFS) attempts to minimise standardbest-first search, but using only linear space\n",
        "- Unlike recursive DFS, an $f_{limit}$ prevents indefinite recursion\n",
        "- Optimal if the heuristic $h(n)$ is admissible\n",
        "Both IDA* and RBFS suffer from using too little memory\n",
        "- Solution is to determine how much memory is admissible and allow an algorithm to use all of it\n",
        "\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "Simplified Memory-bounded A* (SMA*) proceeds with A* as normal until memory is full. At which point it will always drop the worst $f$ leaf node (highest-value) and expands the best leaf\n",
        "- If all the leaf nodes have the same value, then SMA* expands the newest best leaf and deletes the oldest worst leaf\n",
        "- SMA* is complete if the depth of the shallowest goal node is less the memory size\n",
        "- A* pruning with a given heuristic h reduces the **effective depth** by a constant $k_{h}$ compared to the true depth\n",
        "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter3_5.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter3_5))\n",
        "\n",
        "print(\"The length in words is\", len(chapter3_6.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter3_6))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 78,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 915
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "9cdf495f-1575-4585-a5d2-4815112924e0"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              "\n",
              "Informed search strategies utilise a heuristic function , $(n)$\n",
              "- $h(n)$ - estimated cost of the cheapest path from the state at node n to a goal state\n",
              "Greedy Best-First search is a best-first search which expands first the node with the lowest $h(n)$ value - the node which appears to be the closest to the goal\n",
              "- However, greediness can lead to a worse result sometimes\n",
              "- **Complete** for n finite spaces but not in finite ones\n",
              "- Worst-case time and space complexity is $O(|V|)$\n",
              "- A good heuristic function can result in $O(bm)$\n",
              "- A* Search is one of the most common informed search algorithms, a best-first search which uses: $f(n) = g(n) + h(n)$\n",
              "- A* search is complete\n",
              "- Depends on certain properties of the heuristic\n",
              "Admissible heuristic - one that never overestimates the cost to reach a goal (also known as optimistic)\n",
              "A* is **cost-optimal**, which can be shown with a proof by contradiction\n",
              "A* search be visualised by using search contours\n",
              "- Monoatomic - path cost always increases as you go along a path as action costs are always positive\n",
              "- satisficing solutions - willing to accept solutions that are suboptimal, but are 'good enough'\n",
              "If we allow A* search to use an inadmissible heuristic - one that may overestimate - then we risk missing the optimal solution\n",
              "- However, the heuristic can potnetially be more accurate, thereby reducing the number of nodes expanded\n",
              "We can use a weighted A* search where the heuristic function is weighted more heavily, giving us the evaluation function: $f(n) = g(n) + W + h(n)$ for some $W>1$\n",
              "Bounded Suboptimal Search - we look for a solution that is guaranteed to be within a constant factor W of the optimal cost\n",
              "Bounded Cost Search - we look for a solution whoose value cost is less than some constant C\n",
              "Unbounded Cost Search - we accept a solution of any cost as long as we can find it quickly\n",
              "- Example is Speed search. Greedy best-first search that uses the estimated number of actions requires as a heuristic - regardless of cost\n",
              "Main problem for A* is memory\n",
              "**Beam Search** limits the size of the frontier. This makes the search incomplete and suboptimal, but we can choose h to make good use of available memory\n",
              "Iterative-Deepening A* Search (IDA*) gives all the benefits of A* without the requirement to keep all reached state in memory, at a cost of visiting some states multiple times\n",
              "Recursive Best-First Search (RBFS) attempts to minimise standardbest-first search, but using only linear space\n",
              "- Unlike recursive DFS, an $f_{limit}$ prevents indefinite recursion\n",
              "- Optimal if the heuristic $h(n)$ is admissible\n",
              "Both IDA* and RBFS suffer from using too little memory\n",
              "- Solution is to determine how much memory is admissible and allow an algorithm to use all of it\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              "\n",
              "Simplified Memory-bounded A* (SMA*) proceeds with A* as normal until memory is full. At which point it will always drop the worst $f$ leaf node (highest-value) and expands the best leaf\n",
              "- If all the leaf nodes have the same value, then SMA* expands the newest best leaf and deletes the oldest worst leaf\n",
              "- SMA* is complete if the depth of the shallowest goal node is less the memory size\n",
              "- A* pruning with a given heuristic h reduces the **effective depth** by a constant $k_{h}$ compared to the true depth\n",
              "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n",
              "\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 4 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",
        "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": 155,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "iEIOpL7vyWcc",
        "outputId": "2bf5c2bf-9d2b-4bc8-ab7e-197538f95dcd"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 149\n",
            "The length in characters is 862\n",
            "The length in words is 328\n",
            "The length in characters is 2111\n",
            "The length in words is 169\n",
            "The length in characters is 1119\n"
          ]
        }
      ],
      "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 = \"\"\"\n",
        "Minimax algorithm eprforms a complete depth-first exploration of the game tree\n",
        "- If the maximum depth of the tree is m and there are b legal moves at each point, then the time complexity is $O(bm)$\n",
        "- Space complexity is O(bm) for an algorithm that generates all actions at once\n",
        "- O(m) for algorithms that generate actions one at a time\n",
        "- Exponential complexity makes minimax impractical for complex games\n",
        "- Minimax search is DFS\n",
        "\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "Alpha-Beta pruning allows us to reduce the exponential in the depth of the tree\n",
        "- alpha is the value of the best chpice we have found so far at any choice point along the path for MAX (highest value)\n",
        "- beta is the value of the best choice we have found so far at any choice point along the path for MIN (lowest value)\n",
        "- If perfect alpha-beta requires only $O(b^{m/2})$ nodes for minimax\n",
        "Horizon effect arises when a program is facing an opponent's node that more that causes serious damage and is ultimately unavoidable, but on be temporarily avoid by the use of delaying tactics\n",
        "Monte Carlo Tree Search (MCTS) does not use a heuristic evaluation function. Instead, the value of a state is estimated as the average utility over a number of simulations of complete games\n",
        "Pure Monte Carlo search is to do N simulations starting from the current state of the game\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "Stochastic games include a random element\n",
        "- A game tree must therefore include chance nodes\n",
        "Expected Value - average over all possible outcome of the chance nodes\n",
        "A single variable is node-consistent if all the values in the variable's domain satisfy the variable's unary constraint\n",
        "- Unary constraints can easily be removed by reducing the domain of variables\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "Maximum Expected Utility - a rational agent should choose the action that maximises the agent's expected utility\n",
        "- MEU formulates the gneeral notion that an intelligent agent should 'do the right thing'\n",
        "- MEU does not operationalise that advice. Estimating the probability distribution P(s) over possible states requires perception, learning, knowledge, representation, and infenrence\n",
        "An agent acts so as to maximise a utility function tha tcorrectly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all possible environments)\n",
        "**Monotonicity** - suppose 2 lotteries have the same 2 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\n",
        "**Decomposability** - compounted lotteries can be reduced to simpler ones using the laws of probability\n",
        "- No fun in gambling rule: compresses 2 consecutive loterries into a single equivalent lottery\n",
        "$$[p, A ; 1-p,[q, B ; 1-q, C]] \\sim[p, A ;(1-p) q, B ;(1-p)(1-q), C]$$\n",
        "- The above contraints are known as the **axioms of utility theory**\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter5_3.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter5_3))\n",
        "\n",
        "print(\"The length in words is\", len(chapter5_5.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter5_5))\n",
        "\n",
        "print(\"The length in words is\", len(chapter16_1.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter16_1))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 156,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "108446b7-5f6d-4dd1-aafa-ec9bed7b649d"
      },
      "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",
              "\n",
              "Minimax algorithm eprforms a complete depth-first exploration of the game tree\n",
              "- If the maximum depth of the tree is m and there are b legal moves at each point, then the time complexity is $O(bm)$\n",
              "- Space complexity is O(bm) for an algorithm that generates all actions at once\n",
              "- O(m) for algorithms that generate actions one at a time\n",
              "- Exponential complexity makes minimax impractical for complex games\n",
              "- Minimax search is DFS\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "\n",
              "Alpha-Beta pruning allows us to reduce the exponential in the depth of the tree\n",
              "- alpha is the value of the best chpice we have found so far at any choice point along the path for MAX (highest value)\n",
              "- beta is the value of the best choice we have found so far at any choice point along the path for MIN (lowest value)\n",
              "- If perfect alpha-beta requires only $O(b^{m/2})$ nodes for minimax\n",
              "Horizon effect arises when a program is facing an opponent's node that more that causes serious damage and is ultimately unavoidable, but on be temporarily avoid by the use of delaying tactics\n",
              "Monte Carlo Tree Search (MCTS) does not use a heuristic evaluation function. Instead, the value of a state is estimated as the average utility over a number of simulations of complete games\n",
              "Pure Monte Carlo search is to do N simulations starting from the current state of the game\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "\n",
              "Stochastic games include a random element\n",
              "- A game tree must therefore include chance nodes\n",
              "Expected Value - average over all possible outcome of the chance nodes\n",
              "A single variable is node-consistent if all the values in the variable's domain satisfy the variable's unary constraint\n",
              "- Unary constraints can easily be removed by reducing the domain of variables\n",
              "A variable in a CSP is **arc-consistent**\n",
              "The Arc-Consistent algorithm (AC-3) has a time complexity of $O(d^2)$\n",
              "- O(cd^3) in worst case\n",
              "Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables\n",
              "Stronger forms of propagation can be defined with the notion of k-consistency\n",
              "- A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable\n",
              "A CSP is strongly k-consistent if it is both k consistent and (k-1) consistent, and (k-2) cosnsitent, ... all the way to 1-n consistent\n",
              "CSP is NP-complete in general\n",
              "Global Contraint - one involving an arbitrary number of variables\n",
              "CSPs are **commutative** - the order of application of any given set of actions does not matter\n",
              "- Forward checking - whenever a variable X is assigned, the forward-checking process establishes arc-consistency\n",
              "- Conflict Directed Backjuping - one that uses conflict sets\n",
              "Local search algorithms are very effective in solving many CSPs as they use a complete-state formulation\n",
              "- Complete state formulation - where each sate assigns a value to every variable, and the searchc hanges the value of one variable at a time\n",
              "A constraint graph can be reduced by assigned values to some variables so that the ramining variables form a tree\n",
              "A constraint graph can also be reduced by constraining a **tree decomposition**:\n",
              "- A transformation of the original graph into a tree where each node in the tree consists of a set of variables\n",
              "- **Tree width** of a **tree decomposition** is one less than the size of the longest node\n",
              "- Tree width of **the graph** is the minimum width among all its tree decomposition\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              "\n",
              "Maximum Expected Utility - a rational agent should choose the action that maximises the agent's expected utility\n",
              "- MEU formulates the gneeral notion that an intelligent agent should 'do the right thing'\n",
              "- MEU does not operationalise that advice. Estimating the probability distribution P(s) over possible states requires perception, learning, knowledge, representation, and infenrence\n",
              "An agent acts so as to maximise a utility function tha tcorrectly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all possible environments)\n",
              "**Monotonicity** - suppose 2 lotteries have the same 2 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\n",
              "**Decomposability** - compounted lotteries can be reduced to simpler ones using the laws of probability\n",
              "- No fun in gambling rule: compresses 2 consecutive loterries into a single equivalent lottery\n",
              "$$[p, A ; 1-p,[q, B ; 1-q, C]] \\sim[p, A ;(1-p) q, B ;(1-p)(1-q), C]$$\n",
              "- The above contraints are known as the **axioms of utility theory**\n",
              "\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",
              " Your summary here \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": 170,
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "A variable in a CSP is **arc-consistent**\n",
        "The Arc-Consistent algorithm (AC-3) has a time complexity of $O(d^2)$\n",
        "- O(cd^3) in worst case\n",
        "Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables\n",
        "Stronger forms of propagation can be defined with the notion of k-consistency\n",
        "- A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable\n",
        "A CSP is strongly k-consistent if it is both k consistent and (k-1) consistent, and (k-2) cosnsitent, ... all the way to 1-n consistent\n",
        "CSP is NP-complete in general\n",
        "Global Contraint - one involving an arbitrary number of variables\n",
        "CSPs are **commutative** - the order of application of any given set of actions does not matter\n",
        "- Forward checking - whenever a variable X is assigned, the forward-checking process establishes arc-consistency\n",
        "- Conflict Directed Backjuping - one that uses conflict sets\n",
        "Local search algorithms are very effective in solving many CSPs as they use a complete-state formulation\n",
        "- Complete state formulation - where each sate assigns a value to every variable, and the searchc hanges the value of one variable at a time\n",
        "A constraint graph can be reduced by assigned values to some variables so that the ramining variables form a tree\n",
        "A constraint graph can also be reduced by constraining a **tree decomposition**:\n",
        "- A transformation of the original graph into a tree where each node in the tree consists of a set of variables\n",
        "- **Tree width** of a **tree decomposition** is one less than the size of the longest node\n",
        "- Tree width of **the graph** is the minimum width among all its tree decomposition\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 171,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 810
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "754f75f0-4c81-41ee-87ea-3d0b2e3a748c"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              "\n",
              "A variable in a CSP is **arc-consistent**\n",
              "The Arc-Consistent algorithm (AC-3) has a time complexity of $O(d^2)$\n",
              "- O(cd^3) in worst case\n",
              "Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables\n",
              "Stronger forms of propagation can be defined with the notion of k-consistency\n",
              "- A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable\n",
              "A CSP is strongly k-consistent if it is both k consistent and (k-1) consistent, and (k-2) cosnsitent, ... all the way to 1-n consistent\n",
              "CSP is NP-complete in general\n",
              "Global Contraint - one involving an arbitrary number of variables\n",
              "CSPs are **commutative** - the order of application of any given set of actions does not matter\n",
              "- Forward checking - whenever a variable X is assigned, the forward-checking process establishes arc-consistency\n",
              "- Conflict Directed Backjuping - one that uses conflict sets\n",
              "Local search algorithms are very effective in solving many CSPs as they use a complete-state formulation\n",
              "- Complete state formulation - where each sate assigns a value to every variable, and the searchc hanges the value of one variable at a time\n",
              "A constraint graph can be reduced by assigned values to some variables so that the ramining variables form a tree\n",
              "A constraint graph can also be reduced by constraining a **tree decomposition**:\n",
              "- A transformation of the original graph into a tree where each node in the tree consists of a set of variables\n",
              "- **Tree width** of a **tree decomposition** is one less than the size of the longest node\n",
              "- Tree width of **the graph** is the minimum width among all its tree decomposition\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " Your summary here \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 6 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",
        "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": 167,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qIRJ4YYCzNHL",
        "outputId": "030377c2-dc97-4a57-9be8-4bf56d886012"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 364\n",
            "The length in characters is 2933\n"
          ]
        }
      ],
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "Logical agents form representatives of a complex world and use a process of inference to derive new representations about the world, and use these representative to deduce what to do\n",
        "**Logic** can be developed to support knowledge-based agent\n",
        "- These agents can combine and recombine information to suice a myriad of purposes\n",
        "- Knowledge-based agents can accept new tasks in the form of explicitly described goals\n",
        "- They can achieve competency, quickly by learning new knowledge\n",
        "- They can adapt to changes in the environment by updating the relevant knowledge\n",
        "The central component of a knowledge-based agent is its knowledge base\n",
        "- knowledge-base - a set of **sentences**\n",
        "- Each sentence is expressed in a language called a knowledge representation language\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "Atomic sentences consist of a single preposition symbol\n",
        "Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. There are 5 connectives in common use:\n",
        "- $\\lnot$ (not) i.e. $\\lnot W_{1,3}$ is the negation of $W_{1,3}$. A **literal** is either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal)\n",
        "- $\\land$ (and) A sentence whose main connective $\\land$, i.e. $W_{1,3}\\land P_{3,1}$ is called a conjunction, its parts are the conjucts\n",
        "- $\\lor$ (or) A sentence whose main connective is $\\lor$, i.e. $(W_{1,3}\\land P_{3,1})\\lor W_{2,2}$ is a disjunction, its parts are disjuncts\n",
        "- $\\implies$ (implies) A sentence such as $(W_{1,3}\\land P_{3,1})\\implies \\lnot W_{2,2}$ is called an implication. Its **premise** or **antecedent** is $(W_{1,3}\\land P_{3,1})$ and its **conlusion** or **consequent** is $\\lnot W_{2,2}$. Implications are also known as **rules** or **if-then**\n",
        "- $\\iff$ (iff) A **biconditional**\n",
        "- Valid sentences are known as tautologies\n",
        "The deductive theorem is known as:\n",
        "- For any sentences $\\\\alpha $ and $\\\\beta$ $(\\\\alpha \\\\vDash \\\\beta)$, iff $\\\\alpha \\implies \\\\beta$ is valid\n",
        "- Proving $\\\\beta$ from $\\\\alpha$ by checking the unsatisfiability of $(\\\\alpha \\land \\lnot \\\\beta)$ corresponds exactly to the standard mathematical proof technique of **reductio ad absurdum** or **refutation** or **proof by contradiction**\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "**Inference and Proofs**\n",
        "Best known rule is called **Modus Ponens**\n",
        "- $\\\\alpha \\implies \\\\beta, \\\\alpha\\\\beta$\n",
        "- Whenever any sentences of form $\\\\alpha\\implies\\\\beta$ and $\\\\alpha$ are given then the sentence $\\\\beta$ can be inferred\n",
        "And-Elimination:\n",
        "- $\\\\alpha\\land\\\\beta_{\\cdot\\\\alpha}$\n",
        "- From a conjunction, any of the conjucts can be inferred\n",
        "Starting with a knowledgebase R, through $R_{5}$, show how to prove $\\lnot P_{1,2}$ that is there is not pit in [1,2]\n",
        "- Apply biconditional elimination to $R_{2}$ i.e. $R_{6}:(B_{1,1}\\implies(P_{1,3}\\lor P_{2,1}))\\land((P_{1,2}\\lor P_{2,1})\\implies B_{1,1})$\n",
        "- Apply And-Elimination to $R_{6}$ to obtain $R_{7}:((P_{1,2}\\lor P_{2,1} \\implies B_{1,1}))$\n",
        "- Logical equivalence for contrapositives gives $R_{8}:(\\lnot B_{1,1}\\implies\\lnot(P_{1,2}\\lor P_{2,1}))$\n",
        "- Apply Modus Ponens with $R_{8}$ and the percept $R_{4}(i.e., \\lnot B_{1,1})$ to obtain $R_{9}:\\lnot(P_{1,2}\\lor P_{2,1})$\n",
        "- Apply De Morgan's rule, giving $R_{10}:\\lnot P_{1,2}\\land\\lnot P_{2,1}$ thus neither [1,2] or [2,1] contains pits\n",
        "Monotonicity - the set of entailed sentences can only increase as information is added to the knowledgebase\n",
        "###Proof by Reduction\n",
        "**Resolution** - yields a complete inference algorithm when coupled with any complete search algorithm\n",
        "The united resolution can be gneeralised to the full resolution rule:\n",
        "- $$\\\\frac{\\ell_{1}\\\\vee\\cdots\\\\vee\\ell_{k},\\quad m_{1}\\\\vee\\cdots\\\\vee m_{n}}{\\ell_{1}\\\\vee\\cdots\\\\vee\\ell_{i-1}\\\\vee\\ell_{i+1}\\\\vee\\cdots\\\\vee\\ell_{k}\\\\vee m_{1}\\\\vee\\cdots\\\\vee m_{j-1}\\\\vee m_{j+1}\\\\vee\\cdots\\\\vee m_{n}}$$\n",
        "where $\\ell_{i}$ and $M_{j}$ are complementary literals\n",
        "We can resolve P and $\\lnot P$ to deduce $$\\\\frac{P\\\\vee\\neg Q\\\\vee R, \\quad\\neg P\\\\vee Q}{\\neg Q\\\\vee Q\\\\vee R}$$\n",
        "The resulting clause should contain only one copy of each literal\n",
        "- The removal of multiple copies of literals is called factory\n",
        "- i.e. resolve $(A\\lor B)$ with $(A\\lor\\lnot B)$ thus we obtain $(A\\lor A)$ which is reduced to A\n",
        "Every sentence of propositional logical is logically equivalent to a conjunction of clauses\n",
        "###Horn Clauses and Definite Clauses\n",
        "**Definite clause** - a disjunction of literals of which exactly one is positive\n",
        "- i.e. $(\\lnot L_{1,1}\\lor\\lnot Breeze\\lor V_{1,1})$ is a definite clause\n",
        "- $(\\lnot B_{1,1}\\lor P_{1,2} \\lor P_{2,1})$ is not because it has 2 positive clauses\n",
        "- All definite clauses are horn clauses, as are clauses with no positive literals\n",
        "Every definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is a single positive literal\n",
        "A **fact** is a sentence consisting of a single positive literal\n",
        "- True $\\implies L_{1,1}$ or simplying $L_{1,1}$\n",
        "**Forward and Backward Chaining**\n",
        "Forward chaining is **sound** as every inference is essentially an application of Modus Ponens\n",
        "Forward chaining is **complete** as every entailed atomic sentence will be derived\n",
        "Backward chaining is a form of **goal-directed reasoning**\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Horn form\" : \"premise is called the body and the conclusion is called the head\",\n",
        "\"Horn clause\" : \"disjunction of literals of which at most one is positive\",\n",
        "\"Goal clauses\" : \"clauses with no positive literals\",\n",
        "\"Conjunctive Normal Form\" : \"a sentence expressed a conjunction of clauses\"\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter7_5.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter7_5))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 168,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "9868400c-2b78-4d20-e594-70578f4ab355"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              "\n",
              "Logical agents form representatives of a complex world and use a process of inference to derive new representations about the world, and use these representative to deduce what to do\n",
              "**Logic** can be developed to support knowledge-based agent\n",
              "- These agents can combine and recombine information to suice a myriad of purposes\n",
              "- Knowledge-based agents can accept new tasks in the form of explicitly described goals\n",
              "- They can achieve competency, quickly by learning new knowledge\n",
              "- They can adapt to changes in the environment by updating the relevant knowledge\n",
              "The central component of a knowledge-based agent is its knowledge base\n",
              "- knowledge-base - a set of **sentences**\n",
              "- Each sentence is expressed in a language called a knowledge representation language\n",
              "\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",
              "\n",
              "Atomic sentences consist of a single preposition symbol\n",
              "Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. There are 5 connectives in common use:\n",
              "- $\\lnot$ (not) i.e. $\\lnot W_{1,3}$ is the negation of $W_{1,3}$. A **literal** is either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal)\n",
              "- $\\land$ (and) A sentence whose main connective $\\land$, i.e. $W_{1,3}\\land P_{3,1}$ is called a conjunction, its parts are the conjucts\n",
              "- $\\lor$ (or) A sentence whose main connective is $\\lor$, i.e. $(W_{1,3}\\land P_{3,1})\\lor W_{2,2}$ is a disjunction, its parts are disjuncts\n",
              "- $\\implies$ (implies) A sentence such as $(W_{1,3}\\land P_{3,1})\\implies \\lnot W_{2,2}$ is called an implication. Its **premise** or **antecedent** is $(W_{1,3}\\land P_{3,1})$ and its **conlusion** or **consequent** is $\\lnot W_{2,2}$. Implications are also known as **rules** or **if-then**\n",
              "- $\\iff$ (iff) A **biconditional**\n",
              "- Valid sentences are known as tautologies\n",
              "The deductive theorem is known as:\n",
              "- For any sentences $\\alpha $ and $\\beta$ $(\\alpha \\vDash \\beta)$, iff $\\alpha \\implies \\beta$ is valid\n",
              "- Proving $\\beta$ from $\\alpha$ by checking the unsatisfiability of $(\\alpha \\land \\lnot \\beta)$ corresponds exactly to the standard mathematical proof technique of **reductio ad absurdum** or **refutation** or **proof by contradiction**\n",
              "\n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              "\n",
              "**Inference and Proofs**\n",
              "Best known rule is called **Modus Ponens**\n",
              "- $\\alpha \\implies \\beta, \\alpha\\beta$\n",
              "- Whenever any sentences of form $\\alpha\\implies\\beta$ and $\\alpha$ are given then the sentence $\\beta$ can be inferred\n",
              "And-Elimination:\n",
              "- $\\alpha\\land\\beta_{\\cdot\\alpha}$\n",
              "- From a conjunction, any of the conjucts can be inferred\n",
              "Starting with a knowledgebase R, through $R_{5}$, show how to prove $\\lnot P_{1,2}$ that is there is not pit in [1,2]\n",
              "- Apply biconditional elimination to $R_{2}$ i.e. $R_{6}:(B_{1,1}\\implies(P_{1,3}\\lor P_{2,1}))\\land((P_{1,2}\\lor P_{2,1})\\implies B_{1,1})$\n",
              "- Apply And-Elimination to $R_{6}$ to obtain $R_{7}:((P_{1,2}\\lor P_{2,1} \\implies B_{1,1}))$\n",
              "- Logical equivalence for contrapositives gives $R_{8}:(\\lnot B_{1,1}\\implies\\lnot(P_{1,2}\\lor P_{2,1}))$\n",
              "- Apply Modus Ponens with $R_{8}$ and the percept $R_{4}(i.e., \\lnot B_{1,1})$ to obtain $R_{9}:\\lnot(P_{1,2}\\lor P_{2,1})$\n",
              "- Apply De Morgan's rule, giving $R_{10}:\\lnot P_{1,2}\\land\\lnot P_{2,1}$ thus neither [1,2] or [2,1] contains pits\n",
              "Monotonicity - the set of entailed sentences can only increase as information is added to the knowledgebase\n",
              "###Proof by Reduction\n",
              "**Resolution** - yields a complete inference algorithm when coupled with any complete search algorithm\n",
              "The united resolution can be gneeralised to the full resolution rule:\n",
              "- $$\\frac{\\ell_{1}\\vee\\cdots\\vee\\ell_{k},\\quad m_{1}\\vee\\cdots\\vee m_{n}}{\\ell_{1}\\vee\\cdots\\vee\\ell_{i-1}\\vee\\ell_{i+1}\\vee\\cdots\\vee\\ell_{k}\\vee m_{1}\\vee\\cdots\\vee m_{j-1}\\vee m_{j+1}\\vee\\cdots\\vee m_{n}}$$\n",
              "where $\\ell_{i}$ and $M_{j}$ are complementary literals\n",
              "We can resolve P and $\\lnot P$ to deduce $$\\frac{P\\vee\n",
              "eg Q\\vee R, \\quad\n",
              "eg P\\vee Q}{\n",
              "eg Q\\vee Q\\vee R}$$\n",
              "The resulting clause should contain only one copy of each literal\n",
              "- The removal of multiple copies of literals is called factory\n",
              "- i.e. resolve $(A\\lor B)$ with $(A\\lor\\lnot B)$ thus we obtain $(A\\lor A)$ which is reduced to A\n",
              "Every sentence of propositional logical is logically equivalent to a conjunction of clauses\n",
              "###Horn Clauses and Definite Clauses\n",
              "**Definite clause** - a disjunction of literals of which exactly one is positive\n",
              "- i.e. $(\\lnot L_{1,1}\\lor\\lnot Breeze\\lor V_{1,1})$ is a definite clause\n",
              "- $(\\lnot B_{1,1}\\lor P_{1,2} \\lor P_{2,1})$ is not because it has 2 positive clauses\n",
              "- All definite clauses are horn clauses, as are clauses with no positive literals\n",
              "Every definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is a single positive literal\n",
              "A **fact** is a sentence consisting of a single positive literal\n",
              "- True $\\implies L_{1,1}$ or simplying $L_{1,1}$\n",
              "**Forward and Backward Chaining**\n",
              "Forward chaining is **sound** as every inference is essentially an application of Modus Ponens\n",
              "Forward chaining is **complete** as every entailed atomic sentence will be derived\n",
              "Backward chaining is a form of **goal-directed reasoning**\n",
              "\n",
              "\n",
              "## Module 7 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Horn form** - premise is called the body and the conclusion is called the head\n",
              "* **Horn clause** - disjunction of literals of which at most one is positive\n",
              "* **Goal clauses** - clauses with no positive literals\n",
              "* **Conjunctive normal form** - a sentence expressed a conjunction of clauses\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": 169,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "436faa34-e955-4bbc-937c-0791aa589d75"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " \n",
              "Machine learning is a subset of AI <br/>\n",
              "A computer which can pass the Turing test will require the following: <br/>\n",
              "- Natural Language Processing <br/>\n",
              "- Knowledge Representation to store: to story information <br/>\n",
              "- Automated reasoning: answer questions <br/>\n",
              "- Machine learning: adapt to change <br/>\n",
              "To pass a \"Total Turing Test\" a computer will also require the following: <br/>\n",
              "- Computer Vision and Speech Recognition <br/>\n",
              "- Robotics <br/>\n",
              "The cognitive Learning Approach concludes that we must also understand how humans think. We can learn about human thought in 3 ways: <br/>\n",
              "- Introspection: catching our thoughts <br/>\n",
              "- Experiments: observing a person in action <br/>\n",
              "- Brain Imaging: observing the brain in action <br/>\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              "\n",
              "Descartes suggests that one's consciousness implies one's existence. Related to this idea is the idea of mind body dualism. This is the idea that your mind is the separate from your body. <br/>\n",
              "- He came to the conclusion that perhaps the thing that differentiated the automatons from people is that automatons can only react, in particular predetermined fashions. <br/>\n",
              "The essence of the Turing test is that notion of passing, the notion of passing for something that you are not and convincing other people that you're something other than who you truly are. <br/>\n",
              "John Searle argues that Turing's test is insufficient. He contends that the Turing test could be solved through simple, simple manipulation and argues intuitively that simple, simple manipulation isn't true intelligence. Thus, giving the appearance of conversation is not sufficient to show that something is truly capable of intelligence. <br/>\n",
              "For example, the actions could be something like increase the speed of rotation of its wheels or turn on a light or make some sound. <br/>\n",
              "An *intelligent agent*, is not physical and the environment that it operates on is not a physical environment. The agent can still perceive and act on its environment. <br/>\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              "\n",
              "Our definition of agents could even be satisfied by something as simple as a thermostat. It perceives the environment in the room with a thermometer and then acts to alter it. If it falls beneath a certain temperature. It does this by adjusting the boiler to increase the temperature in the radiators and therefore the room. Once it senses the temperature is exceeded the threshold, it acts again to turn the boiler off. <br/>\n",
              "\n",
              "\n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              "\n",
              "An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. <br/><br/>\n",
              "- A human agent has eyes, ears, and other organs for sensors and hands, legs, vocal tract, and so on for actuators <br/>\n",
              "- A robotic agent might have cameras and infrared range finders for sensors and various motors for actuators <br/>\n",
              "- A software agent received file contents, network packets, and human input (keyboard/mouse/touchscreen) as sensory inputs and acts on the environment by writing files, sending network packets, and displaying information or generating sounds\n",
              "The term **percept** is used to refer to the content an agent's sensors are perceiving, while the percept sequence is the complete history of everything that the agent has ever peceived. <br/>\n",
              "In general, *an agent's choice of action at any given instant can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on anything it hasn't perceived.* <br/>\n",
              "- An agent's behaviour is described the agent function, which maps any given percept sequence to an action. <br/>\n",
              "An agent is defined as anything that can perceive its environment and act on it: <br/>\n",
              "- The parts of an agent that are used to perceive the environments are called it sensors. <br/>\n",
              "- The parts of the agent that allow it to act on the environment or call this actuators. <br/>\n",
              "- The signal that the agent receives from its sensors is called a percept. <br/>\n",
              "- A percept will represent an agent's perception for an instant in time. It could be represented as a vector of all the inputs that the agent receives through its sensors. <br/>\n",
              "We can say that *an agent is specified by a function called the agent function that takes in as input a sequence of percepts and then maps that sequence onto a sequence of actions.* The actions are going to be drawn from a set of possible actions that the robot could do via its actual orders. <br/>\n",
              "\n",
              "\n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              "\n",
              "AI has generally stuck to one notion called \"consequentialism\" <br/>\n",
              "- Consequentialism: we evaluate an agent's behaviour by its consequences <br/>\n",
              "- When an agent is pluncked down in an environment, it generates a sequence of actions according to the percepts it receives <br/>\n",
              "- This sequence of actions causes the environment to go through a sequence of states <br/>\n",
              "- If the sequence is desirable, then the agent has performed well <br/>\n",
              "Performance measure is used to measure desirability of a sequence of states <br/>\n",
              "- As a general rule, it is better to design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave <br/>\n",
              "- A rational agent: selects an action which maximises the performance measure for each possible percept sequence <br/>\n",
              "An omniscient agent knows the actual outcome of its actions and can act accordingly <br/>\n",
              "- Information gathering: doing actions in order to modify future percepts <br/>\n",
              "\n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              "\n",
              "A task environment is considered *fully observable*. If a task agent sensors can detect all of aspects of the environment that are relevant to the agent's choice of action. <br/>\n",
              "Self-driving cars operate in a *partially observable* environment. They have access to only the information that they can perceive via their sensors. So they have access to some information about their immediate surroundings, but not to the entire global picture. <br/>\n",
              "\n",
              "If an agent has no sensors at all then it is unobservable <br/>\n",
              "- Deterministic: if the next state of the environment is completely determined by the current state and the action executed by the agent <br/>\n",
              "- Non-deterministic: if the possibilities are listed without being quantified (i.e. there's a chance of rain tomorrow) <br/>\n",
              "- Stochastic: if it explicitly deals with probabilities (i.e. there's a 25% chance of rain tomorrow) <br/>\n",
              "Episodic versus Sequential <br/>\n",
              "In an episodic task, the agent's experience is divided into atomic episodes <br/>\n",
              "- In each episode the agent receives a percept and then performs a single action; the next episode does not dpeend on the actions taken in previous episodes <br/>\n",
              "Static versus Dynamic <br/>\n",
              "- Static environments do not change, while dynamic environment continuously ask the agent what it wants to do <br/>\n",
              "- If the environment itself does not change with the passage of time but the agent's performance score does, then that environment is semidynamic <br/>\n",
              "Distinct versus continous: how time is perceived <br/>\n",
              "Known versus Unknown <br/>\n",
              "- It is possible for a known environment to be partially observable (i.e. a solitaire game where one knows the rules but cannot see the cards) <br/>\n",
              "- It is also possible for an unknown environment to be fully observable (i.e. a video game where one can see the game state but doesn't know which buttons to press) <br/>\n",
              "The hardest case is \"partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown\" <br/>\n",
              "The laws of Thought Approach transcribes processes of thought, so-called 'logic' <br/>\n",
              "- Logic is conventionally understood as requiring knowledge of the world that is certain <br/>\n",
              "- The theory of probability fills gaps in uncertainty <br/>\n",
              "The Rational Agent Approach <br/>\n",
              "- A rational agent is one which acts so as to achieve the best outcome or the best expected outcome <br/>\n",
              "The rational agent approach has 2 advantages over the other approaches: <br/>\n",
              "- More general than \"Law of Though\" because correct inference is just one of several possible outcomes <br/>\n",
              "- More amenable to scientific development <br/>\n",
              "AI has focused on the study and construction of agents that do the right thing. <br/>\n",
              "- Defined by the objective\n",
              "The standard model assures that we will supply a fully specified objective to the machine <br/>\n",
              "The value alignment problem: the values or objectives put into the machine must be aligned with those of the human <br/>\n",
              "\n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              "\n",
              "Job of an AI is to design an agent program that implements the agent function - the mapping from percepts to actions <br/>\n",
              "An agent can escape from infinite loops if the agent can randomise its actions <br/>\n",
              "Model-based reflex agents <br/>\n",
              "The most effective way to handle partial observability is for the agent to *keep track of the part of the world it can't see now.* <br/>\n",
              "- The agent should maintian some sort of internal state that depends on the percept history and thereby reflects at least some of the unobserved aspects of the current state <br/>\n",
              "Updating this internal state information as time goes by requires 2 kinds of knowledge to be enconded in the agent program: <br/>\n",
              "- Information about how the world changes over time, which can be divided roughly into 2 parts: effects of the agent's actions and how the world evolves independently; this knowledge of how the world works is called the transition model of the world <br/>\n",
              "- Information about how the state of the world is reflected in the agent's percepts; known as a sensor model <br/>\n",
              "Agents utilising these models are known as model-based agents <br/>\n",
              "Goal-based agents <br/>\n",
              "Goals alone are not enough to generate high-quality behaviour in most environments <br/>\n",
              "Goal-based agents are more flexible because the knowledge that supports its decisions is represented explicitly and can be modified <br/>\n",
              "Utility-based agents <br/>\n",
              "An agent's utility function is an internalisation of the performance meaure; provided that the internal utility function and the external performance measure are in agreement <br/>\n",
              "- Like goal-based agents, a utility-based agent has many advantages in terms of flexibility and learning <br/>\n",
              "- When there are conflicting goals, where only some of which can be achieved (i.e. speed and safety), the utility function specifies the appropriate tradeoff <br/>\n",
              "- When there are several goals that the agent can aim for, none of which can be achieved with certainty, then the utility function specifies the way in which the likelihood of success can be weighed against the importance of the goals <br/>\n",
              "A rational utility-based agent chooses the action that maximises the expected utility of the action outcomes <br/>\n",
              "How the components of agent programs work <br/>\n",
              "In an atomic representation, each state of the world is indivisible <br/>\n",
              "A factored representation splits up each state into a fixed set of variables or attributes, each of which can have a higher value <br/>\n",
              "A structured representation is one where objects and their various and varying relationships are described explicitly <br/>\n",
              "\n",
              "\n",
              "## Module 1 Lecture Notes\n",
              "\n",
              "- Let's define *rational behavior* as doing the right thing, since it's obviously better to do the right thing than it is to do the wrong thing. <br/>\n",
              "- The minimum algorithm works when we're playing against a rational opponent who's also trying to maximize their own score in the game. <br/>\n",
              "- Our job as the A.I. practitioner is to design and implement rational agents. Our choice of algorithms for our agent program will depend on the kind of task environment that we're dealing with. <br/>\n",
              "- Another way of thinking about deterministic environments is on where the resulting state of the world is going to be completely determined based on the current state and the action that the agent picked. <br/>\n",
              "- In non-deterministic environments, the agent can pick an action, but then the outcome is uncertain. There can be many possible resulting states of the environment based on the agent executing that action. <br/>\n",
              "- Environments with nondeterministic outcomes are often times stochastic in nature. Stochastic means probabilistic. If we can quantify how likely each of the possible outcomes is, then the environment is a stochastic environment. <br/>\n",
              "- A non-deterministic environment is similar, but we just haven't quantified the likelihood of the different possible outcomes. <br/>\n",
              "- TASC environments can be either episodic or sequential. <br/>\n",
              "- An episodic environment is one in which the agent needs to process self-contained episodes. The agent perceives the environment and then performs a single action and the choice of each action is not dependent on any previous action. <br/>\n",
              "- In sequential environments the current decision can affect all future actions. In this case, an immediate decision is going to impact the space of possible choices that will come next. In such cases, agents will need to plan ahead multiple steps in the future in order to come up with the desired outcome. <br/>\n",
              "- Static versus Dynamic<br/>\n",
              "- A static environment is one where the environment remains unchanged while the agent is deliberating about what action to take. An example of this is like a crossword puzzle where you can think as long as you'd like before taking the action to write out a word or enter a letter. <br/>\n",
              "- This stands in contrast with dynamic environments where while the agent is thinking about what action to take, the environment is changing all around it. Self-driving cars have to quickly react to action. <br/>\n",
              "- An environment can be categorized as *semi dynamic* if it doesn't actually change with the passage of time. But the agents score does change. <br/>\n",
              "- Environment can be represented using a discrete number of distinct states in discrete environments. There's also a limited number of clearly defined actions. This means that there's a finite set of actions that an agent can take. <br/>\n",
              "- In continuous environments we need to think about the state representation of the environment or the way we handle time as being continuous. <br/>\n",
              "\n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Agent** - anything that can perceive and act in an environment\n",
              "* **Percept** - the content an agent's sensors are perceiving\n",
              "* **Percept sequence** - the complete history of everything that the agent has ever peceived\n",
              "* **Sensors** - parts of an agent that are used to perceive the environments\n",
              "* **Actuators** - parts of an that allow it to act on an environment\n",
              "* **Agent function** - takes in a sequence of percepts and then returns an action.\n",
              "* **Rational agent** - one the selects an action to maximise the expected value of its performance measure for each possible percept sequence\n",
              "\n",
              "\n",
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "\n",
              "Strongly typed means that variables have a pre-defined type and one which matters when performing operations, while dynamically typed refers to the fact that the variable is a value attached to a name, such that its type is only determined during runtime. An example of the former in Python is print(1+1) outputting 2 while print(1+'1') would produce an error. An example of the latter is how i = 2 might be an integer but its type can be changed to a string through str(i).\n",
              "Dictionaries map a key to a value in key:value pairs. By definition, the values of the dictionary can be any type, while the key are unique and must be of an immutable type such as a string or a number rather than an array or list. The solution is to flip the order of the pairs such that: points_to_names = {'home' : [0,0], 'school' : [1,2], 'market': [-1,1]}\n",
              "```\n",
              "# Working with Lists\n",
              "def extract_and_apply(l, p, f):\n",
              "    return [f(x) for x in l if p(x)]\n",
              "def concatenate(seqs):\n",
              "    return [j for i in seqs for j in i]\n",
              "def transpose(matrix):\n",
              "    return [list(m) for m in zip(*matrix)]\n",
              "# Sequence Slicing\n",
              "def copy(seq):\n",
              "    return seq[:]\n",
              "def all_but_last(seq):\n",
              "    return seq[:-1]\n",
              "def every_other(seq):\n",
              "    return seq[::2]\n",
              "# Combinatorial Algorithms\n",
              "def prefixes(seq):\n",
              "    for i in range(len(seq)+1):\n",
              "        yield seq[0:i]\n",
              "def suffixes(seq):\n",
              "    for i in range(len(seq)+1):\n",
              "        yield seq[i:]\n",
              "def slices(seq):\n",
              "    for j in range(len(seq)+1):\n",
              "        for i in range(len(seq)+1):\n",
              "            if len(seq[j:i])>0:\n",
              "                yield seq[j:i]\n",
              "# Text Processing\n",
              "def normalize(text):\n",
              "    return ‘ ‘.join(text.lower().split())\n",
              "def no_vowels(text):\n",
              "    return ‘‘.join([x for x in text if x not in (‘a’,’A’,’e’,’E’,’i’,’I’,’o’,’O’,’u’,’U’)])\n",
              "def digits_to_words(text):\n",
              "    dic = {'0':'zero','1':'one','2':'two','3':'three','4':'four','5':'five','6':'six','7':'seven','8':'eight','9':'nine'}\n",
              "    y = ‘‘\n",
              "    for x in text:\n",
              "        if x.isdigit() == True:\n",
              "            y = y+dic[x]+’ ‘\n",
              "    if y != ‘‘:\n",
              "        y = y.rstrip(y[-1])\n",
              "    return y\n",
              "def to_mixed_case(name):\n",
              "    name = name.lower()\n",
              "    for x in range(len(name)):\n",
              "        if name[x-1] == ‘_’:\n",
              "            name = name.replace(name[x],name[x].upper())\n",
              "    name2 = name.replace(‘_’,’’)\n",
              "    return name2.replace(name2[0],name2[0].lower())\n",
              "```\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",
              "\n",
              "A sequence of actions form a path, and a solution is a path from the initial state to a goal state\n",
              "- We assume action costs are additive\n",
              "An optimal solution has the lowest path cost among all solution\n",
              "Abstraction - the process of removing detail from a representation\n",
              "Search algorithms - takes a search problem as input and returns a solution or an indication of failure\n",
              "Frontier separates two regions of the state-space graph\n",
              "- An interior region where every state has been expanded\n",
              "- An exterior region of states that have not yet been reached\n",
              "The frontier is the set of nodes that have been reached but not yet expanded\n",
              "Best First Search - on each iteration the node on the frontier with minimum f(n) value is chosen\n",
              "Priority queue - first pops the node with the minimum cost according to f(n)\n",
              "FIFO queue - First-In-First-Out queue pops the node added to the queue first\n",
              "LIFO queue - Last-In-First-Out queue (stack) pops out first the most recently added queue\n",
              "Graph search - checks for redundant paths\n",
              "Tree-like search - does not check for redundant paths\n",
              "- Breadth First Search is a tree-like search </br>\n",
              "Algorithms can be evaluated in four ways:\n",
              "- completeness - is the algorithm guaranteed to find a solution when there is one?\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 money is needed? </br>\n",
              "A complete algorithm must be capable of systematically exploring every state that is reachable from the initial state\n",
              "- A search algorithm must be systematic in the way it explores an infant state space </br>\n",
              "In computer science, the typical measure is the size of the state-space graph\n",
              "- $|V|+|E|$\n",
              "- Where $|V|$ is the number of vertices\n",
              "- Where $|E|$ is the number of edges (stinct state/action pairs) </br>\n",
              "Complexity can also be measured in terms of depth (d), the number of actions in an optimal solution\n",
              "- m, maximum number of actions in any path\n",
              "- b, branching factor or number of successors of a node </br>\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              "\n",
              "Searc\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              "\n",
              "Depth First Search (DFS) always expands the deepest node in the frontier first\n",
              "- Usually implemented as a tree-like search\n",
              "- The search then 'backs up' to the next deepest node with unexpanded successors\n",
              "- Not cost-optimal - returns the first solution it finds, even if it is not the cheapest\n",
              "- For solutions where a tree-like search is feasible, DFS requires less memory\n",
              "- Memory complexity of only $O(bm)$ </br>\n",
              "Depth Limited Search can be used to prevent DFS from wandering down an infinite path\n",
              "- We supply a depth limit, $\\ell$, as if they have no successors\n",
              "- Time complexity is $O(b^{\\ell})$\n",
              "- Space complexity is $O(b\\ell)$\n",
              "- However, $\\ell$ must be optimal </br>\n",
              "Iterative Deepening search solves the problem of optimising the $\\ell$ value, by trying all values until a solution is found\n",
              "- Time complexity is $O(b^d)$ when there is a solution or $O(b^m)$ when there is not\n",
              "- Space complexity is $O(bd)$ when there is a solution or $O(bm)$ when there is not\n",
              "Bidirectional search simultaneously searches forwards and backwards from the initial state, hoping that the two searches will meet\n",
              "- Needs to keep track of 2 frontiers and 2 tables of ready states\n",
              "- Time complexity is $O(b^{d/2})\n",
              "- Space complexity is $O(b^{d/2})\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              "\n",
              "Bread-First Search (BFS) is appropriate when all actions have the same cost\n",
              "- The root node is expanded first, then all the successors of the root node are expanded next, then their successors\n",
              "- **Asymptotic** search strategy that is **complete** even on infinite spaces\n",
              "- BFS can be improved with FIFO queue\n",
              "- Cost-optimal for problems whose actions have the same cost\n",
              "- The total number of gneerated notes is: $1+b+b^2+b^3+...+b^d = O(b^d)$\n",
              "- At $d = 14$, even with infinite memory, its would take 3.5 years </br>\n",
              "Dijkstra's algorithm (or Uniform-Cost Search) spreads out in waves of uniform path cost\n",
              "- Complexity of UCS is characterised in terms of **$C^{*}$**, the cost of the optimal solution, and $\\epsilon$, a lower bound of each action, with $\\epsilon >0$\n",
              "- Worst case time complexity is: $O(b^{1+LC^{*}/\\epsilon ⅃})$\n",
              "- Which can be worse than BFS as UCS can explore large trees of actions with low costs before exploring paths invading a high-cost and perhaps useful action\n",
              "- UCS is **complete** and **cost-optimal**\n",
              "\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search, forming a path to a goal state\n",
              "* **Search problem** - a set of states that the environment can be in - the state space\n",
              "* **Initial state** - where the agent starts\n",
              "* **Action** - returns a finite set of actions\n",
              "* **Cost function** - gives the numeric cost of applying an action\n",
              "\n",
              "\n",
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              "\n",
              "Informed search strategies utilise a heuristic function , $(n)$\n",
              "- $h(n)$ - estimated cost of the cheapest path from the state at node n to a goal state\n",
              "Greedy Best-First search is a best-first search which expands first the node with the lowest $h(n)$ value - the node which appears to be the closest to the goal\n",
              "- However, greediness can lead to a worse result sometimes\n",
              "- **Complete** for n finite spaces but not in finite ones\n",
              "- Worst-case time and space complexity is $O(|V|)$\n",
              "- A good heuristic function can result in $O(bm)$\n",
              "- A* Search is one of the most common informed search algorithms, a best-first search which uses: $f(n) = g(n) + h(n)$\n",
              "- A* search is complete\n",
              "- Depends on certain properties of the heuristic\n",
              "Admissible heuristic - one that never overestimates the cost to reach a goal (also known as optimistic)\n",
              "A* is **cost-optimal**, which can be shown with a proof by contradiction\n",
              "A* search be visualised by using search contours\n",
              "- Monoatomic - path cost always increases as you go along a path as action costs are always positive\n",
              "- satisficing solutions - willing to accept solutions that are suboptimal, but are 'good enough'\n",
              "If we allow A* search to use an inadmissible heuristic - one that may overestimate - then we risk missing the optimal solution\n",
              "- However, the heuristic can potnetially be more accurate, thereby reducing the number of nodes expanded\n",
              "We can use a weighted A* search where the heuristic function is weighted more heavily, giving us the evaluation function: $f(n) = g(n) + W + h(n)$ for some $W>1$\n",
              "Bounded Suboptimal Search - we look for a solution that is guaranteed to be within a constant factor W of the optimal cost\n",
              "Bounded Cost Search - we look for a solution whoose value cost is less than some constant C\n",
              "Unbounded Cost Search - we accept a solution of any cost as long as we can find it quickly\n",
              "- Example is Speed search. Greedy best-first search that uses the estimated number of actions requires as a heuristic - regardless of cost\n",
              "Main problem for A* is memory\n",
              "**Beam Search** limits the size of the frontier. This makes the search incomplete and suboptimal, but we can choose h to make good use of available memory\n",
              "Iterative-Deepening A* Search (IDA*) gives all the benefits of A* without the requirement to keep all reached state in memory, at a cost of visiting some states multiple times\n",
              "Recursive Best-First Search (RBFS) attempts to minimise standardbest-first search, but using only linear space\n",
              "- Unlike recursive DFS, an $f_{limit}$ prevents indefinite recursion\n",
              "- Optimal if the heuristic $h(n)$ is admissible\n",
              "Both IDA* and RBFS suffer from using too little memory\n",
              "- Solution is to determine how much memory is admissible and allow an algorithm to use all of it\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              "\n",
              "Simplified Memory-bounded A* (SMA*) proceeds with A* as normal until memory is full. At which point it will always drop the worst $f$ leaf node (highest-value) and expands the best leaf\n",
              "- If all the leaf nodes have the same value, then SMA* expands the newest best leaf and deletes the oldest worst leaf\n",
              "- SMA* is complete if the depth of the shallowest goal node is less the memory size\n",
              "- A* pruning with a given heuristic h reduces the **effective depth** by a constant $k_{h}$ compared to the true depth\n",
              "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n",
              "\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Concept** - definition\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",
              "\n",
              "Minimax algorithm eprforms a complete depth-first exploration of the game tree\n",
              "- If the maximum depth of the tree is m and there are b legal moves at each point, then the time complexity is $O(bm)$\n",
              "- Space complexity is O(bm) for an algorithm that generates all actions at once\n",
              "- O(m) for algorithms that generate actions one at a time\n",
              "- Exponential complexity makes minimax impractical for complex games\n",
              "- Minimax search is DFS\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "\n",
              "Alpha-Beta pruning allows us to reduce the exponential in the depth of the tree\n",
              "- alpha is the value of the best chpice we have found so far at any choice point along the path for MAX (highest value)\n",
              "- beta is the value of the best choice we have found so far at any choice point along the path for MIN (lowest value)\n",
              "- If perfect alpha-beta requires only $O(b^{m/2})$ nodes for minimax\n",
              "Horizon effect arises when a program is facing an opponent's node that more that causes serious damage and is ultimately unavoidable, but on be temporarily avoid by the use of delaying tactics\n",
              "Monte Carlo Tree Search (MCTS) does not use a heuristic evaluation function. Instead, the value of a state is estimated as the average utility over a number of simulations of complete games\n",
              "Pure Monte Carlo search is to do N simulations starting from the current state of the game\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "\n",
              "Stochastic games include a random element\n",
              "- A game tree must therefore include chance nodes\n",
              "Expected Value - average over all possible outcome of the chance nodes\n",
              "A single variable is node-consistent if all the values in the variable's domain satisfy the variable's unary constraint\n",
              "- Unary constraints can easily be removed by reducing the domain of variables\n",
              "A variable in a CSP is **arc-consistent**\n",
              "The Arc-Consistent algorithm (AC-3) has a time complexity of $O(d^2)$\n",
              "- O(cd^3) in worst case\n",
              "Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables\n",
              "Stronger forms of propagation can be defined with the notion of k-consistency\n",
              "- A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable\n",
              "A CSP is strongly k-consistent if it is both k consistent and (k-1) consistent, and (k-2) cosnsitent, ... all the way to 1-n consistent\n",
              "CSP is NP-complete in general\n",
              "Global Contraint - one involving an arbitrary number of variables\n",
              "CSPs are **commutative** - the order of application of any given set of actions does not matter\n",
              "- Forward checking - whenever a variable X is assigned, the forward-checking process establishes arc-consistency\n",
              "- Conflict Directed Backjuping - one that uses conflict sets\n",
              "Local search algorithms are very effective in solving many CSPs as they use a complete-state formulation\n",
              "- Complete state formulation - where each sate assigns a value to every variable, and the searchc hanges the value of one variable at a time\n",
              "A constraint graph can be reduced by assigned values to some variables so that the ramining variables form a tree\n",
              "A constraint graph can also be reduced by constraining a **tree decomposition**:\n",
              "- A transformation of the original graph into a tree where each node in the tree consists of a set of variables\n",
              "- **Tree width** of a **tree decomposition** is one less than the size of the longest node\n",
              "- Tree width of **the graph** is the minimum width among all its tree decomposition\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              "\n",
              "Maximum Expected Utility - a rational agent should choose the action that maximises the agent's expected utility\n",
              "- MEU formulates the gneeral notion that an intelligent agent should 'do the right thing'\n",
              "- MEU does not operationalise that advice. Estimating the probability distribution P(s) over possible states requires perception, learning, knowledge, representation, and infenrence\n",
              "An agent acts so as to maximise a utility function tha tcorrectly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all possible environments)\n",
              "**Monotonicity** - suppose 2 lotteries have the same 2 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\n",
              "**Decomposability** - compounted lotteries can be reduced to simpler ones using the laws of probability\n",
              "- No fun in gambling rule: compresses 2 consecutive loterries into a single equivalent lottery\n",
              "$$[p, A ; 1-p,[q, B ; 1-q, C]] \\sim[p, A ;(1-p) q, B ;(1-p)(1-q), C]$$\n",
              "- The above contraints are known as the **axioms of utility theory**\n",
              "\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",
              " Your summary here \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",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " Your summary here \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              "\n",
              "Logical agents form representatives of a complex world and use a process of inference to derive new representations about the world, and use these representative to deduce what to do\n",
              "**Logic** can be developed to support knowledge-based agent\n",
              "- These agents can combine and recombine information to suice a myriad of purposes\n",
              "- Knowledge-based agents can accept new tasks in the form of explicitly described goals\n",
              "- They can achieve competency, quickly by learning new knowledge\n",
              "- They can adapt to changes in the environment by updating the relevant knowledge\n",
              "The central component of a knowledge-based agent is its knowledge base\n",
              "- knowledge-base - a set of **sentences**\n",
              "- Each sentence is expressed in a language called a knowledge representation language\n",
              "\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",
              "\n",
              "Atomic sentences consist of a single preposition symbol\n",
              "Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. There are 5 connectives in common use:\n",
              "- $\\lnot$ (not) i.e. $\\lnot W_{1,3}$ is the negation of $W_{1,3}$. A **literal** is either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal)\n",
              "- $\\land$ (and) A sentence whose main connective $\\land$, i.e. $W_{1,3}\\land P_{3,1}$ is called a conjunction, its parts are the conjucts\n",
              "- $\\lor$ (or) A sentence whose main connective is $\\lor$, i.e. $(W_{1,3}\\land P_{3,1})\\lor W_{2,2}$ is a disjunction, its parts are disjuncts\n",
              "- $\\implies$ (implies) A sentence such as $(W_{1,3}\\land P_{3,1})\\implies \\lnot W_{2,2}$ is called an implication. Its **premise** or **antecedent** is $(W_{1,3}\\land P_{3,1})$ and its **conlusion** or **consequent** is $\\lnot W_{2,2}$. Implications are also known as **rules** or **if-then**\n",
              "- $\\iff$ (iff) A **biconditional**\n",
              "- Valid sentences are known as tautologies\n",
              "The deductive theorem is known as:\n",
              "- For any sentences $\\alpha $ and $\\beta$ $(\\alpha \\vDash \\beta)$, iff $\\alpha \\implies \\beta$ is valid\n",
              "- Proving $\\beta$ from $\\alpha$ by checking the unsatisfiability of $(\\alpha \\land \\lnot \\beta)$ corresponds exactly to the standard mathematical proof technique of **reductio ad absurdum** or **refutation** or **proof by contradiction**\n",
              "\n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              "\n",
              "**Inference and Proofs**\n",
              "Best known rule is called **Modus Ponens**\n",
              "- $\\alpha \\implies \\beta, \\alpha\\beta$\n",
              "- Whenever any sentences of form $\\alpha\\implies\\beta$ and $\\alpha$ are given then the sentence $\\beta$ can be inferred\n",
              "And-Elimination:\n",
              "- $\\alpha\\land\\beta_{\\cdot\\alpha}$\n",
              "- From a conjunction, any of the conjucts can be inferred\n",
              "Starting with a knowledgebase R, through $R_{5}$, show how to prove $\\lnot P_{1,2}$ that is there is not pit in [1,2]\n",
              "- Apply biconditional elimination to $R_{2}$ i.e. $R_{6}:(B_{1,1}\\implies(P_{1,3}\\lor P_{2,1}))\\land((P_{1,2}\\lor P_{2,1})\\implies B_{1,1})$\n",
              "- Apply And-Elimination to $R_{6}$ to obtain $R_{7}:((P_{1,2}\\lor P_{2,1} \\implies B_{1,1}))$\n",
              "- Logical equivalence for contrapositives gives $R_{8}:(\\lnot B_{1,1}\\implies\\lnot(P_{1,2}\\lor P_{2,1}))$\n",
              "- Apply Modus Ponens with $R_{8}$ and the percept $R_{4}(i.e., \\lnot B_{1,1})$ to obtain $R_{9}:\\lnot(P_{1,2}\\lor P_{2,1})$\n",
              "- Apply De Morgan's rule, giving $R_{10}:\\lnot P_{1,2}\\land\\lnot P_{2,1}$ thus neither [1,2] or [2,1] contains pits\n",
              "Monotonicity - the set of entailed sentences can only increase as information is added to the knowledgebase\n",
              "###Proof by Reduction\n",
              "**Resolution** - yields a complete inference algorithm when coupled with any complete search algorithm\n",
              "The united resolution can be gneeralised to the full resolution rule:\n",
              "- $$\\frac{\\ell_{1}\\vee\\cdots\\vee\\ell_{k},\\quad m_{1}\\vee\\cdots\\vee m_{n}}{\\ell_{1}\\vee\\cdots\\vee\\ell_{i-1}\\vee\\ell_{i+1}\\vee\\cdots\\vee\\ell_{k}\\vee m_{1}\\vee\\cdots\\vee m_{j-1}\\vee m_{j+1}\\vee\\cdots\\vee m_{n}}$$\n",
              "where $\\ell_{i}$ and $M_{j}$ are complementary literals\n",
              "We can resolve P and $\\lnot P$ to deduce $$\\frac{P\\vee\n",
              "eg Q\\vee R, \\quad\n",
              "eg P\\vee Q}{\n",
              "eg Q\\vee Q\\vee R}$$\n",
              "The resulting clause should contain only one copy of each literal\n",
              "- The removal of multiple copies of literals is called factory\n",
              "- i.e. resolve $(A\\lor B)$ with $(A\\lor\\lnot B)$ thus we obtain $(A\\lor A)$ which is reduced to A\n",
              "Every sentence of propositional logical is logically equivalent to a conjunction of clauses\n",
              "###Horn Clauses and Definite Clauses\n",
              "**Definite clause** - a disjunction of literals of which exactly one is positive\n",
              "- i.e. $(\\lnot L_{1,1}\\lor\\lnot Breeze\\lor V_{1,1})$ is a definite clause\n",
              "- $(\\lnot B_{1,1}\\lor P_{1,2} \\lor P_{2,1})$ is not because it has 2 positive clauses\n",
              "- All definite clauses are horn clauses, as are clauses with no positive literals\n",
              "Every definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is a single positive literal\n",
              "A **fact** is a sentence consisting of a single positive literal\n",
              "- True $\\implies L_{1,1}$ or simplying $L_{1,1}$\n",
              "**Forward and Backward Chaining**\n",
              "Forward chaining is **sound** as every inference is essentially an application of Modus Ponens\n",
              "Forward chaining is **complete** as every entailed atomic sentence will be derived\n",
              "Backward chaining is a form of **goal-directed reasoning**\n",
              "\n",
              "\n",
              "## Module 7 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Horn form** - premise is called the body and the conclusion is called the head\n",
              "* **Horn clause** - disjunction of literals of which at most one is positive\n",
              "* **Goal clauses** - clauses with no positive literals\n",
              "* **Conjunctive normal form** - a sentence expressed a conjunction of clauses\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": null,
      "metadata": {
        "id": "UtMViq6FiiQl"
      },
      "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
}
