Section 4 Further Problem-solving and Programming Skills.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "Meta"
    ]
   },
   "source": [
    "# Introduction\n",
    "This is a course/reference for CAIE Computer Science Problem-solving and Programming, meant to help you understand the content alongside the textbooks. I try to cover most of the syllabus directly related to Python programming, trying to provide an alternate explanation where possible. I also talk about some parts (like expressions, and the `range()` function) which are sometimes not well explained by textbooks.\n",
    "\n",
    "This reference is interactive—you can try out the examples as soon as you read the explanation, without having to launch an IDE. The expetcation is that you use this and you textbooks to get an overview of the concepts, and then dig in by researching—I'll provide some links where appropriate.\n",
    "\n",
    "**Note:** this lesson expects that you have familarity with programming in any one of these ways:\n",
    "* Completed CAIE 9608/2 or 9618/2 syllabus\n",
    "* A few years of experience programming with Python 3\n",
    "* Been through my section 2 notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "Meta",
     "Jupyter"
    ]
   },
   "source": [
    "## 0: Jupyter Notebooks\n",
    "What you're reading right now is called a [Jupyter](https://jupyter.org/index.html) Notebook. It allows me to write documentation (explanation), place graphics/diagrams, and write executable Python code in the same place. You can execute my code, edit it, or just create a new cell and experiment.\n",
    "\n",
    "\\[Over\\]Simply put, a Jupyter notebook is a file with various cells. A cell is a block of code, explanation (like this one), or a multimedia element. To execute a cell, click on it to select it, and press **Ctrl + Enter** (or **Cmd + Return**). Go ahead, and try it with the cell below—you should get a message telling that you succeeded. If you already know Python programming, you can edit that code too!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "Meta",
     "Jupyter"
    ]
   },
   "outputs": [],
   "source": [
    "print(\"You successfully executed a cell. Congratulations!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "Meta",
     "Jupyter"
    ]
   },
   "source": [
    "## 1: Tags\n",
    "Each cell has one or more tags. If it's visible, you should see the words `Meta` and `Jupyter` written in two small boxes on the top-left of this cell, and you don't have to do anything. If not, click **View > Cell Toolbar > Tags**.\n",
    "\n",
    "Tags tell you which syllabuses a given cell pertains to, or otherwise describes the content. For example, this cell has two tags:\n",
    "* `Meta` This cell is not about any syllabus-specific content, and just describes something about the course.\n",
    "* `Jupyter` This cell describes how to use Jupyter or its features.\n",
    "\n",
    "Here is a full list of tags you'll encounter.\n",
    "\n",
    "| Tag | Explanation |\n",
    "|:-|:-|\n",
    "| `IGXXXX` | This represents a [CAIE IGCSE syllabus](https://www.cambridgeinternational.org/programmes-and-qualifications/cambridge-upper-secondary/cambridge-igcse/subjects/https://www.cambridgeinternational.org/programmes-and-qualifications/cambridge-upper-secondary/cambridge-igcse/subjects/), with syllabus code XXXX. You must understand this content. |\n",
    "| `ALYYYY` | This represents a [CAIE AS & A Level syllabus](https://www.cambridgeinternational.org/programmes-and-qualifications/cambridge-advanced/cambridge-international-as-and-a-levels/subjects/https://www.cambridgeinternational.org/programmes-and-qualifications/cambridge-advanced/cambridge-international-as-and-a-levels/subjects/), with syllabus code YYYY. You must understand this content. |\n",
    "| `General` | This is something not explicitly mentioned by the syllabus, but is common knowledge amongst programmers. Knowing this may help you get a better grasp of the syllabus. |\n",
    "| `Extended` | Content that might be interesting or useful, but not explicitly covered by the syllabus. You should avoid using this on exams. |\n",
    "| `Used` | May appear with some `General` or `Extended` topics. You can use these in your exams. |\n",
    "| `Meta` | These are not content about programming itself, instead it may explain something about my writing style, or help getting around Jupyter. |\n",
    "| `Jupyter` | May appear with some `Meta` tags. These are about the Jupyter environment. |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "Meta",
     "Jupyter"
    ]
   },
   "source": [
    "## 2: Installation?\n",
    "If you don't want to edit my code and save those changes, then you don't have to install anything—you can keep coming back to this notebook in your browser using Binder.\n",
    "\n",
    "However, if you would like to experiment, create notebooks, or want more customizability, install Jupyter. I'll give you a simple method below, but visit the [official website](https://jupyter.org/install.html) for more detail about Anaconda and other methods.\n",
    "\n",
    "This method uses a command line. While you can just follow these instructions, it might be worthwhile understanding what's going on. If any of this is unfamiliar, take a look at my [advice for programming learners](https://eccentricorange.github.io/CAIE-Computer-Science/things-to-know.html#a-command-line).\n",
    "\n",
    "1. If you don't already have it, download and install Python from the its [website](https://www.python.org/downloads/). Make sure you get version 3.3 or newer.\n",
    "    * If you need to check whether you have Python, open a command line, type `python --version`, and press **Enter**.\n",
    "    * If you get a version number, you have Python; if not, you don't.\n",
    "2. Open up a command line.\n",
    "    * If you're on Windows, press **Windows + R** to bring up the run dialog box. Type `powershell` and hit **Enter**.\n",
    "    * If you're on MacOS, launch the application called **Terminal**.\n",
    "    * If you're on a Linux-based OS, I suppose you know what to do.\n",
    "3. Type in `pip3 install notebook` (try `pip install notebook` if that didn't work) and press **Enter**. If you're asked whether you want to continue, type `y` for 'yes' and press **Enter**. Wait for the installation to complete.\n",
    "\n",
    "To launch Jupyter, open a command line, and go to the folder you want to save your files in. Type in `jupyter notebook` and press enter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "Meta",
     "Jupyter"
    ]
   },
   "source": [
    "## 3: Learn more\n",
    "Now that you've had a basic introduction to Jupyter, we can jump into the lesson.\n",
    "\n",
    "If you're interested in learning more, I'll leave links to some sources below:\n",
    "* [Anaconda](https://docs.anaconda.com/anaconda/)\n",
    "* [Jupyter demo and more detailed overview](https://mybinder.org/v2/gh/ipython/ipython-in-depth/master?filepath=binder/Index.ipynb)\n",
    "* [Guide to using Jupyter](https://www.dataquest.io/blog/jupyter-notebook-tutorial/)\n",
    "* [Installing Jupyter Notebook and more](https://jupyter.org/install.html)\n",
    "* [Jupyter documentation](https://jupyter-notebook.readthedocs.io/en/stable/index.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "Meta"
    ]
   },
   "source": [
    "## 4: My sources\n",
    "Most of the content here is about explaining skills, which I've acquired over time through practice and reverse-engineering others' examples. It would not make sense for me to cite these. However, for trasparency, I'll do my best to explain where I got information from.\n",
    "\n",
    "I sometimes refer sources online, for things like definitions, and I'll make sure to leave you a hyperlink to these (though it may take the form of suggested further reading).\n",
    "\n",
    "A lot of what I know also comes from the following:\n",
    "* My computer teacher at school, who taught me Python and a lot of rigour\n",
    "* My robotics mentor, who introduced me to programming through C++\n",
    "* Random YouTube vidoes \\([my recommendations](https://eccentricorange.github.io/CAIE-Computer-Science/yt-channels.html)\\)\n",
    "* [My A Level texboook](https://www.hoddereducation.co.uk/subjects/ict/products/general/cambridge-international-as-a-level-computer-sc-(3))\n",
    "* CAIE syllabus specifications: I look up individual topics as per these documents."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "# 4.3: Further programming\n",
    "\n",
    "## 4.3.1 Programming paradigms\n",
    "There are several **paradigms** (styles) of programming, of which one or more may be adopted in a project depending on the requirements and the platform(s) used. Often, a **programming language** would be tied to a particular paradigm. For example, [Python](https://www.python.org/) is an object-oriented programming language, [LabVIEW](http://labview.com) (language: G) is a data-flow language, and [C++](https://isocpp.org/) supports multiple paradigms.\n",
    "\n",
    "1. **Low-level programming**\n",
    "\n",
    "   This is used to program instructions that the CPU can execute directly, for example using **assembly programming**. This has already been covered in papers 1 and 3.\n",
    "\n",
    "2. **Imperative programming**\n",
    "\n",
    "   This involves writing about _how_ a program accomplished something in a rather detailed manner. This is probably what you have been doing upto now.\n",
    "\n",
    "3. **Object-oriented programming**\n",
    "\n",
    "   The program consists **objects** that can have **methods** (actions/functions/procedures) and **properties** (attributes). This is implemented using the concept of a `class`.\n",
    "\n",
    "4. **Declarative programming**\n",
    "\n",
    "   Programs are written without paying much attention to the details of their execution. This is often used to specify *facts* and *rules* in order to solve a problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "## 4.3.3: Exception handling\n",
    "The importance of **error handling** or **exception handling** cannot be overstated. Every programmer eventually runs into code that **throws** an error. It is crucial that the program should be able **handle** the error and continue execution; if not, it must have a way to report it to the user without simply crashing.\n",
    "\n",
    "In Python 3, the `try:` keyword is used to attempt execution of a block of code that might throw an error. We then execute the next block(s) of code depending on whether or not an error occurred. Anything after the `else:` keyword is executed only if no errors occur. One or more `except:` statements can be specified so that different code can execute depending upon the exact exception **raised**. Here is a concise summary:\n",
    "```python\n",
    "try:\n",
    "    ### code to attempt\n",
    "\n",
    "except errorTypeOne:\n",
    "    ### code to execute if errorTypeOne occurred\n",
    "\n",
    "except errorTypeTwo:\n",
    "    ### code to execute if errorTypeTwo occurred\n",
    "\n",
    "... # various errors\n",
    "\n",
    "except:\n",
    "    ### code to execute if an exception occurred\n",
    "      # but it was not explicitly handled above\n",
    "\n",
    "else:\n",
    "    # code to execute if no error occurred\n",
    "\n",
    "finally:\n",
    "    # code to execute regardless of errors\n",
    "```\n",
    "\n",
    "A list of common built-in exceptions can be found [here](https://docs.python.org/3/library/exceptions.html), from Python's official website."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "### Attempt a division problem\n",
    "try:\n",
    "    dividend = float(input(\"Enter a dividend: \"))\n",
    "    divisor = float(input(\"Enter a divisor: \"))\n",
    "    quotient = dividend / divisor\n",
    "\n",
    "### Handle [any] error that comes up (such as divide-by-zero)\n",
    "except:\n",
    "    print (\"You entered an invalid value.\")\n",
    "\n",
    "### Output results if operation was successful\n",
    "else:\n",
    "    print (dividend, \"/\", divisor, \"=\", quotient)\n",
    "\n",
    "### Execute this regardless of program\n",
    "finally:\n",
    "    print (\"This division program has completed executing.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "### Attempt a division problem\n",
    "try:\n",
    "    dividend = float(input(\"Enter a dividend: \"))\n",
    "    divisor = float(input(\"Enter a divisor: \"))\n",
    "    quotient = dividend / divisor\n",
    "\n",
    "### Handle error wherein the entered value cannot be converted to a number by the float() function\n",
    "except ValueError:\n",
    "    print (\"One of the values you entered is not a number, so it cannot be used for division.\")\n",
    "\n",
    "### Handle error wherein a zero was entered for the divisor, which is mathematically not defined (aka impossible)\n",
    "except ZeroDivisionError:\n",
    "    print (\"You tried dividing by 0, which is mathematically not possible.\")\n",
    "\n",
    "### Handle other generic error\n",
    "except:\n",
    "    print (\"Congratulations! You made an error the author of this notebook could not think of!\")\n",
    "\n",
    "### Output results if operation was successful\n",
    "else:\n",
    "    print (dividend, \"/\", divisor, \"=\", quotient)\n",
    "\n",
    "### Execute this regardless of program\n",
    "finally:\n",
    "    print (\"This division program has completed executing.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "## 4.3.2: Open a binary file\n",
    "Binary/**Random** files are accessed using a module called `pickle`. Unlike the case for text file, the **methods** will not **inherit** from the file **object**; rather, the file object will be passed as a parameter.\n",
    "\n",
    "```python\n",
    "# General syntax of using a text file\n",
    "fileObject = open(\"path.txt\", \"mode\")\n",
    "fileObject.write(\"text to write\")\n",
    "identifier = fileObject.read()\n",
    "fileObject.close()\n",
    "```\n",
    "\n",
    "```python\n",
    "# General syntax of using a binary file\n",
    "fileObject = open(\"path.dat\", \"mode\")\n",
    "pickle.dump(contentsIdetifier, fileObject)\n",
    "identifier = pickle.load(fileObject)\n",
    "fileObject.close()\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "### Import the pickle module\n",
    "import pickle\n",
    "\n",
    "### Open the file\n",
    "fileObject = open(\"binaryFile.dat\", \"wb\")\n",
    "\n",
    "### Write a list to the file\n",
    "pickle.dump([1, 2, 4, 7], fileObject)\n",
    "\n",
    "### Close the file\n",
    "fileObject.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "### Import the pickle module\n",
    "import pickle\n",
    "\n",
    "### Open the file\n",
    "fileObject = open(\"binaryFile.dat\", \"rb\")\n",
    "\n",
    "### Print out the contents of the file\n",
    "print (pickle.load(fileObject))\n",
    "\n",
    "### Close the file\n",
    "fileObject.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "## 4.1.4: Recursion\n",
    "Recursion occurs when a procedure or function is defined in terms of itself, and calls itself repeatedly. It is one of the most elegant tools in a programmer's arsenal. Recursion is useful when an action has to performed on something, and then repeated on a subsection of the same thing. Searching for an element in a binary tree is a good example, and this will come up later in this notebook. We define recursive functions by using base case(s) and general case(s). The **general case** is the recursive element that calls itself repeatedly; the **base case** is a pre-defined condition that is not recursive. The general case recursively calls itself, until the base case is reached.\n",
    "\n",
    "It is useful to know that many operations that are performed recursively can be done just as well with a loop."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 1: The general structure of recursion\n",
    "\n",
    "```python\n",
    "def recursiveRoutine(parameters):\n",
    "    \n",
    "    if condition(parameters): # general case\n",
    "        return recursiveRoutine(someOperation(parameters))\n",
    "    \n",
    "    else:  # base case\n",
    "        return parameter\n",
    "```\n",
    "It must be noted, however, that this is just an example of some of the recursive functions you're likely to run into. Like everything else in programming, there are many ways to do it, and you'll likely run into recursive functions with a different format."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 2: Example of calculating factorials\n",
    "A commonly used mathematical function, called a **factorial**, is an example of recursion. The factorial (denoted as $x!$) of any positive integer $x$, is the product of every integer between $x$ and $1$ inclusive. For example, $5! = 5 \\times 4 \\times 3 \\times 2 \\times 1$ so $5! = 120$.\n",
    "\n",
    "Here, we define the general case as $x! = x \\times (x - 1)!$ and the base case as $0! = 1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "def factorial(x):\n",
    "\n",
    "    if x == 0:\n",
    "        answer = 1\n",
    "    \n",
    "    else:\n",
    "        answer = x * factorial(x - 1)\n",
    "    \n",
    "    return answer\n",
    "\n",
    "print(\"0! =\", factorial(0))\n",
    "print(\"5! =\", factorial(5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "Extended",
     "Used"
    ]
   },
   "outputs": [],
   "source": [
    "### Demonstrate the same code using a loop\n",
    "def factorial(x):\n",
    "    answer = 1\n",
    "    \n",
    "    for counter in range(x, 1, -1):\n",
    "        answer = answer * counter\n",
    "    \n",
    "    return answer\n",
    "    \n",
    "print(\"0! =\", factorial(0))\n",
    "print(\"5! =\", factorial(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "## 4.1.1: Abstraction\n",
    "\n",
    "### Classes: objects, properties and methods\n",
    "A class can be thought of as a template, that allows a programmer to define several **objects** with the same (or similar) **properties** and **methods** without rewriting the definition each time. This is analogous to using a pre-defined keyword (such as `int` for `INTEGER`) to define multiples identifiers with same data type. Indeed, it can be useful to think of a data type as a class—each identifier, then, is an **instance** of the `int` class. Consider defining a class `human`: this would have properties `name`, `height`, `mother_tounge`, `favoutite_book` and `sex`; it could have methods `sleep()`, `eat(food_name)`, `study()`, `exercise()` and `readBook(book_name)`. Each method can be executed, and each property behaves as a variable. If a programmer had to define identifiers for a hundred different humans, they needn't declare each property individually each time—instead, they can use an instance of the class `human` by declaring an identifier for each person, and all instances automatically **inherit** all the properties and methods defined in the base class.\n",
    "\n",
    "Each element is accessed using a dot, with the syntax:\n",
    "```python\n",
    "identifier = class.property\n",
    "class.procedure_method()\n",
    "class.procedure_method(arguments)\n",
    "identifier = class.function_method()\n",
    "identifier = class.function_method(arguments)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "### Define a class for animals\n",
    "class animal():\n",
    "    \n",
    "    ### define properties for the class\n",
    "    name = \"\"\n",
    "    height = 0      # in metres :D\n",
    "    sex = \"\"\n",
    "\n",
    "    ### define the methods—this requires the use of a keyword self\n",
    "    def sleep(self):\n",
    "        print (self.name, \"is sleeping now.\")\n",
    "            # a property of a class can be accessed using\n",
    "            # the self keyword\n",
    "    \n",
    "    def eat(self, food_name):\n",
    "        print(self.name, \"is eating\", food_name, \"now.\")\n",
    "\n",
    "### Set an instance of the class\n",
    "elephant = animal()\n",
    "elephant.name = \"Dumbo\"     # each property can be accessed individually (written to here)\n",
    "elephant.height = 3\n",
    "elephant.sex = \"male\"\n",
    "print(elephant.name, \"is\", elephant.height, \"metres tall.\")             # (read from here)\n",
    "elephant.eat(\"papaya\")\n",
    "elephant.sleep()\n",
    "\n",
    "### Set another instance of the class\n",
    "cow = animal()\n",
    "cow.name = \"Moo\"     # each property can be accessed individually\n",
    "cow.height = 1.8\n",
    "cow.sex = \"female\"\n",
    "cow.sleep()\n",
    "cow.eat(\"grass\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "Setting the properties this way is a rather lengthy process. Most programming languages allow a **constructor** to be defined, which lets a value to be passed into the declaration of the class itself, as a parameter. This involves the `__init__()` construct.\n",
    "\n",
    "It is usual to use two identifiers with the same name (but in different **scopes**) when using a constructor. Consider a constructor into which a name and an age are passed as parameters: this would also have the word `self` to indicate that it is part of a class and must be able to access its methods and properties.\n",
    "```python\n",
    "class animal():\n",
    "    name = \"\"\n",
    "    age = 0\n",
    "\n",
    "    def __init__ (self, name, age):\n",
    "        self.name = name\n",
    "        self.age = age\n",
    "\n",
    "cow = animal(\"Moo\", 10)\n",
    "```\n",
    "Consider the statement `self.name = name`: it must be kept in mind that this is a valid assignment operation and the identifiers on either side of the equals sign are distinct. The identifier `self.name` is a property of the class `animal`—this is what other methods defined within `animal`, and indeed any other function from an instance of the class (such as `cow.age`), would access. The identifier `name`, is simply an argument passed into the constructor—no method or routine outside the definition of the `__init()__` can access it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "### Define a class for animals\n",
    "class animal():\n",
    "    ### define properties for the class\n",
    "    name = \"\"\n",
    "    height = 0\n",
    "    sex = \"\"\n",
    "\n",
    "    ### define the constructor\n",
    "    def __init__(self, name, height, sex):\n",
    "        self.name = name        # don't confuse the identical names!\n",
    "        self.height = height\n",
    "        self.sex = sex\n",
    "\n",
    "    ### define the other methods—this requires the use of a keyword self\n",
    "    def sleep(self):\n",
    "        print (self.name, \"is sleeping now.\")\n",
    "            # a property of a class can be accessed using\n",
    "            # the self keyword\n",
    "    \n",
    "    def eat(self, food_name):\n",
    "        print(self.name, \"is eating\", food_name, \"now.\")\n",
    "\n",
    "### Set an instance of the class\n",
    "elephant = animal(\"Dumbo\", 3, \"male\")   # the initialization is much shorter indeed\n",
    "print(elephant.name, \"is\", elephant.height, \"metres tall.\")\n",
    "elephant.eat(\"papaya\")\n",
    "elephant.sleep()\n",
    "\n",
    "### Set another instance of the class\n",
    "cow = animal(\"Moo\", 1.8, \"female\")\n",
    "cow.sleep()\n",
    "cow.eat(\"grass\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "### Define a class for books\n",
    "class book():\n",
    "    ISBN = \"\"\n",
    "    title = \"\"\n",
    "    author = \"\"\n",
    "\n",
    "    # initialize\n",
    "    def __init__ (self, ISBN, title, author):\n",
    "        self.ISBN = ISBN\n",
    "        self.title = title\n",
    "        self.author = author\n",
    "        self.validateISBN()     # notice how the function is called as a method\n",
    "        \n",
    "    # define a validation routine, using ISBN 13\n",
    "    # https://isbn-information.com/the-13-digit-isbn.html\n",
    "    def validateISBN(self):\n",
    "        valid = False\n",
    "\n",
    "        while not valid:\n",
    "\n",
    "            valid = (len(self.ISBN) == 13)\n",
    "\n",
    "            if valid:\n",
    "                checkDigit = 0\n",
    "                multiplyDigits = [1, 3]\n",
    "                currentDigit = False\n",
    "\n",
    "                for digit in self.ISBN[0:12]:\n",
    "                    checkDigit += int(digit) * multiplyDigits[currentDigit]\n",
    "                    currentDigit = not currentDigit\n",
    "\n",
    "                checkDigit %= 10\n",
    "\n",
    "                if checkDigit != 0:\n",
    "                    checkDigit = 10 - checkDigit\n",
    "                \n",
    "                valid = (int(self.ISBN[12]) == checkDigit)\n",
    "\n",
    "            if not valid:\n",
    "                self.ISBN = input(\"The ISBN for \" + self.title + \" is incorrect. Please re-enter: \")\n",
    "            \n",
    "engineering = book(\"9789056995010\", \"The Art of Doing Science and Engineering\", \"Richard Hamming\")\n",
    "intelligence = book(\"9781493402697\", \"Mechanical Intelligence\", \"Alan Turing\")  # the actual ISBN is 9781493302697"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### Inheritance\n",
    "Classes can also inherit from other classes, which turns out to be extremely useful. Continuing with the example of the class `human`, consider creating classes for other animals—a class `dog` for example. The class `dog` would have some methods and properties that are the same as for the class `human`: the methods `sleep()` and `eat(food_name)` and properties `name`, `height` and `sex`. Properties and methods about books, studying and languages would be of little use for a dog. However, a dog may also have additional properties `is_pet` and `favourite_bone`, and methods `scratchEar()` and `bark()`. It is clear that `dog` and `human` cannot be defined identically but it would also be wasteful to repeatedly define the common elements. A programmer could define both classes efficiently but still maintain the flexibility if they first define a **parent** class `animal` with the common elements, and then define `dog` and `human` as **child** classes.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "### Define a class for humans thats inherits from the animals class\n",
    "class human(animal):    # the parent class is specified in parenthesis\n",
    "\n",
    "    mother_tongue = \"\"\n",
    "    favourite_book = \"\"\n",
    "\n",
    "    def __init__(self, name, height, sex, mother_tongue, favourite_book):   # notice how all parameters are passed\n",
    "        animal.__init__(self, name, height, sex)  # set the inherited properties\n",
    "        self.mother_tongue = mother_tongue\n",
    "        self.favourite_book = favourite_book\n",
    "    \n",
    "    ### define the other methods—these apply only to humans\n",
    "    def study(self):\n",
    "        print (self.name, \"is studying right now.\")\n",
    "    \n",
    "    def exercise(self):\n",
    "        print (self.name, \"is exercising.\")\n",
    "    \n",
    "    def readBook(self, book_name):\n",
    "        print (self.name, \"is reading\", ('\\\"' + book_name + '\\\"'), \"now\" + (\" and it is his favoutite book.\" if book_name == self.favourite_book else \".\"))\n",
    "\n",
    "### Set an instance of the class\n",
    "mark = human(\"Mark\", 1.8, \"male\", \"English\", \"The Art of Doing Science and Engineering, Richard Hamming\")\n",
    "mark.eat(\"cake\")    # access method from parent\n",
    "mark.sleep()\n",
    "mark.readBook(\"Humble Pi, Matt Parker\")     # access method from child\n",
    "mark.readBook(\"The Art of Doing Science and Engineering, Richard Hamming\")\n",
    "print (mark.name, \"speaks\", mark.mother_tongue, \"at home.\")     # access properties from both classes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### Polymorphism\n",
    "Operators and subroutines can behave in different ways, depending on different condition. You have already met two examples of this at AS Level P2, but might not have explicitly noticed. This feature (an operator/procedure can choose a behaviour depending on the oprands/arguments it is provided) is called **overloading** and the example below demonstrates **operator overloading**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "a = 1\n",
    "b = 2\n",
    "addedValue = a + b + 4\n",
    "print (addedValue)\n",
    "# In this case, the plus sign (+) is used to add together numeric values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "concatenatedString = \"Hello\" + ' ' + \"World\" + '!'\n",
    "print (concatenatedString)\n",
    "# In this case, the plus sign (+) is used to concatenate two strings."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "What was the other **polymorphic** operator?\n",
    "\n",
    "\n",
    "It is possible to define methods to do this, and demonstrate inheritance at the same time. Consider writing a program about school buses. All of them would require methods to take in fuel and get the amount of it remaining, so it might be a good idea to define those in the parent class and then let child classes inherit them. However, different busses might use different types of fuel (such as diesel, petrol or natural gas) and might require different methods—this would lead to different identifiers and make the program difficult to use. A programmer can use the efficiency benefits of inheritance, but still use **same identifiers** for buses with different systems using the concept of polymorphism.\n",
    "\n",
    "The table below summarises the classes that would be produced this way.\n",
    "\n",
    "| Class | Parent class | Child classes | Methods | Properties |\n",
    "| :- | :- | :- | :- | :- |\n",
    "| `bus` | | `dieselBased` <br> `petrolBased` <br> `CNGBased` | `accelerate()` <br> `decelerate()` | `route` <br> `driverCode` |\n",
    "| `dieselBased` | `bus` | | `getFuelLevel()` <br> `refuel()` | `fuelLevel` |\n",
    "| `petrolBased` | `bus` | | `getFuelLevel()` <br> `refuel()` | `fuelLevel` |\n",
    "| `CNGBased` | `bus` | | `getFuelLevel()` <br> `refuel()` | `fuelLevel` |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "### Define the parent bus class\n",
    "class bus():\n",
    "\n",
    "    def __init__ (self, route, driverCode):\n",
    "        self.route = route\n",
    "        self.driverCode = driverCode\n",
    "        self.velocity = 0\n",
    "    \n",
    "    def accelerate(self, acceleration, time):\n",
    "        self.velocity += acceleration * time\n",
    "        \n",
    "        if self.velocity > 60:      # speed limits!\n",
    "            self.velocity = 60\n",
    "\n",
    "        self.fuelLevel -= 0.05 * self.velocity * time\n",
    "\n",
    "    def decelerate(self, deceleration, time):\n",
    "        self.velocity -= deceleration * time\n",
    "        \n",
    "        if self.velocity < 0:\n",
    "            self.velocity = 0\n",
    "\n",
    "        self.fuelLevel -= 0.05 * self.velocity * time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "### Define the child bus classes\n",
    "class dieselBased (bus):\n",
    "\n",
    "    def __init__ (self, route, driverCode, fuelLevel):\n",
    "        bus.__init__ (self, route, driverCode)\n",
    "        self.fuelLevel = fuelLevel\n",
    "\n",
    "    def getFuelLevel (self):\n",
    "        print (\"There are\", self.fuelLevel, \"litres of diesel left.\")\n",
    "    \n",
    "    def refuel (self, value):\n",
    "        self.fuelLevel += value\n",
    "        print (\"There are now\", self.fuelLevel, \"litres of diesel in the tank of.\")\n",
    "\n",
    "\n",
    "class petrolBased (bus):\n",
    "\n",
    "    def __init__ (self, route, driverCode, fuelLevel):\n",
    "        bus.__init__ (self, route, driverCode)\n",
    "        self.fuelLevel = fuelLevel\n",
    "\n",
    "    def getFuelLevel (self):\n",
    "        print (\"There are\", self.fuelLevel, \"litres of petrol left.\")\n",
    "    \n",
    "    def refuel (self, value):\n",
    "        self.fuelLevel += value\n",
    "        print (\"There are now\", self.fuelLevel, \"litres of petrol in the tank.\")\n",
    "\n",
    "\n",
    "class CNGBased (bus):\n",
    "\n",
    "    def __init__ (self, route, driverCode, fuelLevel):\n",
    "        bus.__init__ (self, route, driverCode)\n",
    "        self.fuelLevel = fuelLevel\n",
    "\n",
    "    def getFuelLevel (self):\n",
    "        print (\"There are\", self.fuelLevel, \"litres of CNG left.\")\n",
    "    \n",
    "    def refuel (self, value):\n",
    "        self.fuelLevel += value\n",
    "        print (\"There are now\", self.fuelLevel, \"litres of CNG in the tank.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "### Demonstrate the classes\n",
    "busAA002 = dieselBased(\"AA\", \"AA001\", 0)\n",
    "busAA002.refuel(10)\n",
    "busAA002.accelerate(3, 2)\n",
    "\n",
    "busAA003 = petrolBased(\"AA\", \"AA003\", 0)\n",
    "busAA003.refuel(20)\n",
    "busAA003.accelerate(3, 5)\n",
    "\n",
    "print (busAA002.driverCode, \"is driving at\", busAA002.velocity, \"kmph.\", end = ' ')\n",
    "busAA002.getFuelLevel()\n",
    "print (busAA003.driverCode, \"is driving at\", busAA003.velocity, \"kmph.\", end= ' ')\n",
    "busAA003.getFuelLevel()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "# 4.1: Computational thinking and problem-solving\n",
    "\n",
    "## 4.1.3: Abstract Data Types (ADTs)\n",
    "An ADT is a collection of data and a set of operations on that data.\n",
    "\n",
    "ADTs come in two flavours:\n",
    "\n",
    "* **Composite:** these are ADTs defined using other built-in data types. For example, queues are built using arrays of some atomic datatype, and records store information as various other datatypes.\n",
    "\n",
    "* **Non-composite:** these are defined _from scratch_, without relying on any other data types. For example, **enumerated (enum)** is a data type on its own.\n",
    "\n",
    "Many of the ADTs we will explore below (stack, queue, linked list) are built from arrays and seem to be different ways of storing items with an index, but it is worth noting that they have vastly different applications. Stacks are used to maintain program control, and you can see a **call stack** (this is internally the backbone of recursion) whenever you run a program in the debugging mode of an IDE. Queues are often used to \"place events on hold\", such as in a printer's buffer. A linked list is often used internally to implement other data structures (such as arrays); here, rather ironically, linked lists will be implmented using arrays."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 1: Stacks\n",
    "A stack is a list containing several items, operation on the **last in, first out (LIFO)** principle. Items can be **pushed** (added) onto the stack, and **popped** (removed) from the stack. It has a **pointer** that helps keep track of the current element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "numberOfElements = 10\n",
    "\n",
    "stack = [None for index in range (numberOfElements)]\n",
    "basePointer = 0\n",
    "topPointer = -1\n",
    "stackFull = 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 2: Queue\n",
    "A queue is a list containing several items operating on the **first in, first out (FIFO)** principle. Items can be **enqueued** (added) to the queue and **dequeued** (removed) from the queue. It has a **pointer** that helps keep track of the current element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "numberOfElements = 10\n",
    "\n",
    "queue = [None for index in range(numberOfElements)]\n",
    "frontPointer = 0\n",
    "rearPointer = -1\n",
    "queueFull = 10\n",
    "queueLength = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 3: Linked List\n",
    "A linked list is a list containing several items in which every item in the list points to the next item in the list. In a linked list, a new item is always added to the start of the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "numberOfElements = 10\n",
    "myLinkedList = [0 for index in range(numberOfElements + 1)]\n",
    "myLinkedListPointers = [index for index in range(numberOfElements + 1)]\n",
    "startPointer = -1\n",
    "heapStartPointer = 0\n",
    "nullPointer = -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 4: Records\n",
    "It could be useful to think of this ADT with databases in mind: as a record holds data about a particular entry in a table for an entity, the ADT record holds data about a particular entry."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "### Define a record for students as a class\n",
    "class student():\n",
    "    name = \"\"\n",
    "    no_of_subjects = 0\n",
    "    sex = \"\"\n",
    "\n",
    "### Declare instances\n",
    "alex = student()\n",
    "alex.name = \"Alex\"\n",
    "alex.no_of_subjects = 2\n",
    "alex.sex = \"male\"\n",
    "\n",
    "kat = student()\n",
    "kat.name = \"Katherine\"\n",
    "kat.no_of_subjects = 4\n",
    "kat.sex = \"female\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 5: Binary trees\n",
    "A binary tree can also be implemented as a class. The best way to understand one is probably to visualize it, and the following image from [Wikimedia Commons](https://commons.wikimedia.org/wiki/File:Binary_tree.png) shows a binary tree. Each circle is a **node** and this is the part that is an identifier and can store an element of data. Some nodes also have nodes under them, and these are called **branches**. In the diagram below, the <b><span style=\"color:blue\">blue</span></b> nodes branch off from the <b><span style=\"color:red\">red</span></b> nodes, and themselves branch further. The <b><span style=\"color:green\">green</span></b> nodes do not branch further, and are called **leaves**.\n",
    "\n",
    "<a title=\"No machine-readable author provided. Rune~commonswiki assumed (based on copyright claims)., CC BY-SA 3.0 &lt;http://creativecommons.org/licenses/by-sa/3.0/&gt;, via Wikimedia Commons\" href=\"https://commons.wikimedia.org/wiki/File:Binary_tree.png\"><img width=\"512\" alt=\"Binary tree\" src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/d/df/Binary_tree.png/512px-Binary_tree.png\"></a>\n",
    "\n",
    "Since a tree always has the same structure, i.e., every node has a value and either branches or terminates as a leaf, recursion is used to perform many of the operations associated with trees."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "### Define a class for a node of the tree\n",
    "  # Unlink other data structures, it is more useful to write the related algorithms (insertion, searching et cetera) here, and not separately\n",
    "class node():\n",
    "\n",
    "    def __init__ (self, data):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.data = data\n",
    "\n",
    "    def printTree(self):\n",
    "        if self.left:\n",
    "            self.left.printTree()   # recursion\n",
    "        \n",
    "        print(self.data)            # base case\n",
    "\n",
    "        if self.right:\n",
    "            self.right.printTree()  # recursion\n",
    "\n",
    "    def insertNode(self, data):\n",
    "        if self.data:\n",
    "            \n",
    "            if data < self.data:\n",
    "                if self.left is None:\n",
    "                    self.left = node(data)\n",
    "                \n",
    "                else:\n",
    "                    self.left.insertNode(data)      # recursion\n",
    "            elif data > self.data:\n",
    "                if self.right is None:\n",
    "                    self.right = node(data)\n",
    "                \n",
    "                else:\n",
    "                    self.right.insertNode(data)     # recursion\n",
    "        \n",
    "        else:\n",
    "            self.data = data                        # base case\n",
    "\n",
    "    def find(self, value):\n",
    "        if value < self.data:\n",
    "            if self.left is None:\n",
    "                return False\n",
    "            return self.left.find(value)    # recursion\n",
    "\n",
    "        elif value > self.data:    \n",
    "            if self.right is None:\n",
    "                return False\n",
    "            return self.right.find(value)   # recursion\n",
    "\n",
    "        else:                               # base case\n",
    "            return True\n",
    "            print('i')\n",
    "\n",
    "tree = node(None)\n",
    "\n",
    "for i in range(10):\n",
    "    tree.insertNode(i)\n",
    "\n",
    "print (tree.find(7))\n",
    "print (tree.find(34))\n",
    "\n",
    "tree.printTree()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "## 4.1.2 Algorithms for manipulating or reading ADTs\n",
    "Here we will look at the algorithms used to read from, or write to, ADTs. We will use `global` to access global variables within a function definition."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 1: Push onto a stack\n",
    "To push an element onto a stack, we first check whether or not the stack is already full. If it is not full, we write the new element `item` to the position `[topPointer]`, and then increment `topPointer` by 1; else we print out an error message."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "def push(item):\n",
    "    global topPointer\n",
    "    \n",
    "    if topPointer < (stackFull - 1):\n",
    "        topPointer += 1\n",
    "        stack[topPointer] = item\n",
    "    \n",
    "    else:\n",
    "        print (\"Stack is full, cannot push\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 2: Pop from a stack\n",
    "To pop an element from the from the stack, we first check whether or not the stack is already empty. If it is not empty, we access the element `item` at the position `[topPointer]`, and then decrement `topPointer` by 1; else we print out an error message."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "def pop():\n",
    "    global topPointer, basePointer\n",
    "    item = None\n",
    "\n",
    "    if topPointer == (basePointer - 1):\n",
    "        print(\"Stack is empty, cannot pop\")\n",
    "\n",
    "    else:\n",
    "        item = stack[topPointer]\n",
    "        topPointer -= 1\n",
    "    \n",
    "    return item"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 3: Enqueue an element\n",
    "To enqueue an element `item`, we first check whether or not a queue is already full. If it is not full, we add `item` at the position `[rearPointer]` and increment `queueLength`; else we print out an error message. If `rearPointer` and the queue is not full, the `item` is stored in the first element of the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "def enQueue(item):\n",
    "    global queueLength, rearPointer\n",
    "\n",
    "    if queueLength < queueFull:\n",
    "\n",
    "        if rearPointer < (len(queue) - 1):\n",
    "            rearPointer += 1\n",
    "        \n",
    "        else:\n",
    "            rearPointer = 0\n",
    "        \n",
    "        queueLength += 1\n",
    "        queue[rearPointer] = item\n",
    "        \n",
    "    else:\n",
    "        print(\"Queue is full, cannot enqueue\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 4: Dequeue an element\n",
    "To dequeue an element, we first check if the queue is already empty. If it is not empty, we access the element at position the `[frontPointer]` and decrement `queueLength` by 1; else we print out an error message. If `frontPointer` points to the last element, it is updated to point to the first element in the array, rather than the next element in the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "def deQueue():\n",
    "    global queueLength, frontPointer\n",
    "    item = None\n",
    "\n",
    "    if queueLength == 0:\n",
    "        print(\"Queue is empty, cannot dequeue\")\n",
    "    \n",
    "    else:\n",
    "        item = queue[frontPointer]\n",
    "\n",
    "        if frontPointer == (len(queue) - 1):\n",
    "            frontPointer = 0\n",
    "        \n",
    "        else:\n",
    "            frontPointer += 1\n",
    "        \n",
    "        queueLength -= 1\n",
    "    \n",
    "    return item"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 5: Finding an item in a linked list\n",
    "To find an item `itemSearch` in a linked list, we step through every element while following the pointers. If `itemSearch` is found (i.e., `itemSearch` equals the element at `[itemPointer]`), then the search loop terminates; else it searches till it reaches `nullPointer`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "def find(itemSearch):\n",
    "    found = False\n",
    "    itemPointer = startPointer\n",
    "\n",
    "    while (itemPointer != nullPointer) and (not found):\n",
    "\n",
    "        if myLinkedList[itemPointer] == itemSearch:\n",
    "            found = True\n",
    "        \n",
    "        else:\n",
    "            itemPointer = myLinkedListPointers[itemPointer]\n",
    "    \n",
    "    return itemPointer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 6: Insert an item in a linked list\n",
    "To insert `itemAdd` into a linked list, we first check whether or not the linked list is full. If it is not full, we insert `item` at the location `heapStartPointer` points to. Then make the element at previously at `startPointer` point to `item`, and make `item` and male `heapStartPointer` point to the next free location."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "def insert(itemAdd):\n",
    "    global startPointer\n",
    "\n",
    "    if heapStartPointer == nullPointer:\n",
    "        print(\"Link list full, cannot insert\")\n",
    "    \n",
    "    else:\n",
    "        tempPointer = startPointer\n",
    "        startPointer = heapStartPointer\n",
    "        heapStartPointer = myLinkedListPointers[heapStartPointer]\n",
    "        myLinkedList[startPointer] = itemAdd\n",
    "        myLinkedListPointers[startPointer] = tempPointer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 7: Delete an item from a linked list\n",
    "To delete an item `itemDelete` from a linked list, we first check to see if the list is empty, i.e., if `startPointer` = `nullPointer`. If it is not empty, we traverse the linked list to find the `itemDelete`. If `itemDelete` exists, we \"delete\" it and set the pointers so as to skip `itemDelete`. The `heapStartPointer` is set to point to `itemDelete`, marking it an empty element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "def delete(itemDelete):\n",
    "    global startPointer, heapStartPointer\n",
    "\n",
    "    if startPointer == nullPointer:\n",
    "        print(\"Linked list empty\")\n",
    "    \n",
    "    else:\n",
    "        index = startPointer\n",
    "\n",
    "        while (myLinkedList[index] != itemDelete) and (index != nullPointer):\n",
    "            oldIndex = index\n",
    "            index = myLinkedListPointers[index]\n",
    "        \n",
    "        if index == nullPointer:\n",
    "            print(\"Item\", itemDelete, \"not found\")\n",
    "        \n",
    "        else:\n",
    "            myLinkedList[index] = None\n",
    "            tempPointer = myLinkedListPointers[index]\n",
    "            myLinkedListPointers[index] = heapStartPointer\n",
    "            heapStartPointer = index\n",
    "            myLinkedListPointers[oldIindex] = tempPointer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "## 4.1.2: Algorithms for sorting and searching\n",
    "Computers often have to search vast amounts of data for various purposes. It is also often critical for them to sort data (in either ascending or descinding order). A search engine such as Google provides an excellent example of both jobs, though its [actual implentation](https://www.google.com/search/howsearchworks/) is understandably much more complex. Suppose, a search query \"quickSort\" has been typed into the Google search bar: within fraction of a second, their servers must find approximately 10 (yes just ten) results out of the trillions of webpages indexed on Google search, and show them on the first page. Not only does Google search find these needles in a digital haystack spanning several continents, but it also displays the reults in a very speficic sequence. This should give you an appreciation of the importance and ubiquity searching and sorting algorithms.\n",
    "\n",
    "Here we will meet \\[simple\\] common algorithms for sorting and searching.\n",
    "\n",
    "References (YouTube videos):\n",
    "* [\\[Link\\]](https://www.youtube.com/watch?v=WaNLJf8xzC4) A fun and intuitive introduction to different sortingm ethods  from TED-ed.\n",
    "* [\\[Link\\]](https://www.youtube.com/watch?v=RGuJga2Gl_k) Sorting and Big O notion from Tom Scott."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 0: Generate random numbers\n",
    "We would need to generate lists of random numbers to test our code. Here is the function to do that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "from random import randint  # Import the function to generate random integers\n",
    "\n",
    "## Subroutine to generate random list of unique integers\n",
    "def generateRandom(n):\n",
    "\n",
    "    arr = []\n",
    "\n",
    "    for i in range(n):\n",
    "        r = randint(0, 10 * n)\n",
    "\n",
    "        while r in arr:\n",
    "            r = randint(0, 10 * n)\n",
    "        \n",
    "        arr.append(r)\n",
    "    \n",
    "    return arr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 1: Linear search\n",
    "This is the simplest of the searching algorithms.\n",
    "The program traverses an array, going through every element until a match is found. An element `[i]` is checked in the iteration `i`. If element `[i]` matches the required `element`, the programs returns `i` and halts; else it goes to `[i + 1]` until all elements have been searched."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "def linearSearch(listIn, element):\n",
    "    index = -1\n",
    "    \n",
    "    for i in range(len(listIn)):\n",
    "        if listIn[i] == element:\n",
    "            index = i\n",
    "            break\n",
    "    \n",
    "    return index\n",
    "\n",
    "# Test\n",
    "arr = generateRandom(10)\n",
    "x = arr[5]\n",
    "print (\"In list\", arr, \"element\", x, \"occurs at position\", linearSearch(arr, x))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 2: Bubble sort\n",
    "This is the simplest sorting algorithm. The program traverses an array, while comparing the current `[i]` element to the next element `[i + 1]`. If the element `[i + 1]` was greater than the element `[i]`, they are swapped."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "def bubbleSort(listIn):\n",
    "    key = None\n",
    "    \n",
    "    for i in range (len(listIn)):\n",
    "\n",
    "        for j in range (len(listIn) - 1):\n",
    "\n",
    "            if listIn[j] > listIn[j + 1]:\n",
    "                key = listIn[j]\n",
    "                listIn[j] = listIn[j + 1]\n",
    "                listIn[j + 1] = key\n",
    "\n",
    "# Test\n",
    "arr = generateRandom(10)\n",
    "print(\"Unsorted array:\\t\", arr)\n",
    "bubbleSort(arr)\n",
    "print(\"Sorted array:\\t\", arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 3: Insertion sort\n",
    "This is more efficient than bubble sort as it requires far lesser passes. The program works by placing items into the correct position until they array sorted.\n",
    "\n",
    "This is a comparison sort in which the sorted array (or list) is built one entry at a time. The program starts at element `[i]`, and compares it with every element ranging from `[i - 1]` to `[0]`. If the element `[i]` is lesser than any the given current element `[j]`, it is swapped with `[j]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "def insertionSort(listIn):\n",
    "    key = None\n",
    "\n",
    "    for i in range(1, len(listIn)):\n",
    "        key = listIn[i]\n",
    "        j = i - 1\n",
    "        \n",
    "        while (j >= 0 and key < listIn[j]):\n",
    "            listIn[j + 1] = listIn[j]\n",
    "            j = j - 1\n",
    "        listIn[j + 1] = key\n",
    "\n",
    "# Test\n",
    "arr = generateRandom(10)\n",
    "print(\"Unsorted array:\\t\", arr)\n",
    "insertionSort(arr)\n",
    "print(\"Sorted array:\\t\", arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### 4: Binary search\n",
    "In order to use binary search, an array must be sorted. The algorithm works by dividing and sub-dividing the array into halves until the required element is found.\n",
    "\n",
    "If there are $n$ elements and the value $x$ is required, the algorithm checks whether $x = \\lfloor0.5n\\rfloor$, $x < \\lfloor0.5n\\rfloor$, or $x > \\lfloor0.5n\\rfloor$. If $x = \\lfloor0.5n\\rfloor$, the current index is returned, else the search space is halved in the required direction.\n",
    "\n",
    "Binary search is not as easy to code as the other algorithms. So, it may help you to get different takes on it as you figure it out.\n",
    "* [\\[Link\\]](https://www.youtube.com/watch?v=KXJSjte_OAI) Video from Tom Scott that explains binary search in the context of database indexing.\n",
    "* [\\[Link\\]](https://www.youtube.com/watch?v=tgVSkMA8joQ) Video from mCoding that has an unusual but quite clearly explained perspective on binary searching."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "### Binary search using recursion\n",
    "def binarySearch (listIn, lowerBound, upperBound, element):\n",
    "    if upperBound >= lowerBound:\n",
    "        middleIndex = (upperBound + lowerBound) // 2\n",
    "\n",
    "        if listIn[middleIndex] == element:\n",
    "            return middleIndex\n",
    "        \n",
    "        elif x < listIn[middleIndex]:\n",
    "            return binarySearch(listIn, lowerBound, middleIndex - 1, element)\n",
    "        \n",
    "        else:\n",
    "            return binarySearch(listIn, middleIndex + 1, upperBound, element)\n",
    "    \n",
    "    else:\n",
    "        return -1\n",
    "            \n",
    "\n",
    "# Test\n",
    "arr = generateRandom(10)\n",
    "insertionSort(arr)  # Since binary search requires an array to be sorted\n",
    "x = arr[3]\n",
    "print (\"In list\", arr, \"element\", x, \"occurs at position\", binarySearch(arr, 0, len(arr) - 1, x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "outputs": [],
   "source": [
    "### Binary search using a loop\n",
    "def binarySearch(listIn, element):\n",
    "    upperBound = len(listIn)\n",
    "    lowerBound = 0\n",
    "    found = False\n",
    "    index = -1\n",
    "\n",
    "    while (not found) and (lowerBound != upperBound):\n",
    "        index = int((upperBound + lowerBound) / 2)\n",
    "\n",
    "        found = (element == listIn[index])\n",
    "\n",
    "        if element == listIn[index]:\n",
    "            return index\n",
    "\n",
    "        if element > listIn[index]:\n",
    "            lowerBound = index + 1\n",
    "        \n",
    "        if element < listIn[index]:\n",
    "            upperBound = index\n",
    "\n",
    "    return index\n",
    "\n",
    "# Test\n",
    "arr = generateRandom(10)\n",
    "insertionSort(arr)  # Since binary search requires an array to be sorted\n",
    "x = arr[8]\n",
    "print (\"In list\", arr, \"element\", x, \"occurs at position\", binarySearch(arr, x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "AL9608",
     "AL9618"
    ]
   },
   "source": [
    "### Efficiency of sorting and searching algorithms\n",
    "The efficiency of a sorting algorithm may be roughly encapsulated by its *Big O Notation*, written as $O(f(n))$ for an algorithm where $f$ is a function of the number of elements $n$. The algorithm then takes $f(n)$ passes for $n$ elements on average.\n",
    "    \n",
    "| Algorithm | Big O |\n",
    "| :- | :-: |\n",
    "| [Bubble sort](https://en.wikipedia.org/wiki/Bubble_sort) | $$O(n^2)$$ |\n",
    "| [Insertion sort](https://en.wikipedia.org/wiki/Insertion_sort) | $$O(n^2)$$ |\n",
    "| [Quicksort](https://en.wikipedia.org/wiki/Quicksort) | $$O(n\\log n)$$ |\n",
    "| [Bogosort](https://en.wikipedia.org/wiki/Bogosort) | $$O((n+1)!)$$ |\n",
    "| [Linear search](https://en.wikipedia.org/wiki/Linear_search) | $$O(n)$$ |\n",
    "| [Binary search](https://en.wikipedia.org/wiki/Binary_search_algorithm) | $$O(\\log_2 n)$$ |\n",
    "\n",
    "It is important to keep in mind that the Big O formula of an algorithm does not descibe how well it performs. For example: bubble sort and insertion sort, from the table above, have the same formula $O(n^2)$ but insertion sort is typically faster. Rather, the function $n^2$ only indicates that the graphs of the performance of both functions (that is, number of comparisions required $O(f(n))$ against the number of elements $n$), have the same basic parabolic shape. The big O equation only tells us how well the performance of an algorithm **scales** with the number of inputs."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Tags",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  },
  "metadata": {
   "interpreter": {
    "hash": "f4c28fa8f5722cf028809cd2948e812853f425d5427ac6e7746038839e0ae36f"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}