07_Algorithmic problem solving.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "05d4d58b-d56b-44f3-8d52-fc798723172b",
   "metadata": {},
   "source": [
    "## Lecture 7 - Algorithmic problem solving"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c599074a-8b96-41ac-9404-2981b9a2f691",
   "metadata": {},
   "source": [
    "# Goals:\n",
    "- Algorithms are designed to solve computational problems.\n",
    "- Communicate the way of solving, searching for correct (prove) and efficient solutions.\n",
    "\n",
    "# Problem:\n",
    "- Set of inputs -> space of outputs (m -> n) mapping.\n",
    "- Binary relation between inputs and outputs, not necessarily strictly bijection (one-to-one).\n",
    "- Specify a predicate: Are there two people with the same birthday in the class today?\n",
    "- Mathematic problems - Scientific computing:\n",
    "    - What is the derivative of x^2 at x=1?\n",
    "- The algorithm should be general enough to apply to, say, C2 functions.\n",
    "    - Apply to arbitrarily large inputs.\n",
    "\n",
    "# Algorithm:\n",
    "- Procedure (function) generating outputs, ideally correct outputs.\n",
    "- m -> 1\n",
    "\n",
    "# Question:\n",
    "- Devise an algorithm that finds out if two people have the same birthday.\n",
    "- Do you know any famous algorithms?\n",
    "\n",
    "\n",
    "# Efficiency, complexity:\n",
    "- Abstract sense, not seconds or hours\n",
    "- how many fundamental operations can algorithm do over real time\n",
    "- dont measure time, count ops (operations) -> asymptotic analysis\n",
    "- does not even need to be connected to the implementation - certain tasks has certain efficiency\n",
    "- exact performance depends on size of the input space (birthday problem for 10 or 1000 people in class)\n",
    "- most efficient O(1) access of item in dictionary\n",
    "- least efficient O(n!)\n",
    "    - Traveling Salesman Problem (**TSP**): The TSP involves finding the shortest possible route that visits a set of cities and returns to the origin city. A brute force approach, which tries every possible permutation to find the shortest tour, has a time complexity of O(n!).\n",
    "\n",
    "# For Us:\n",
    "- Breaking down complex problems into smaller, manageable parts.\n",
    "- Pieces should be clearly defined and well-tested (later in your coding life).\n",
    "- Efficient use of data structures.\n",
    "- We use only built-in libraries today.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4617c070-72f8-40b1-9794-c290f0b18293",
   "metadata": {},
   "source": [
    "## Bubble Sort\n",
    "\n",
    "### Concept\n",
    "Bubble Sort is a simple sorting algorithm. It repeatedly steps through the list, \n",
    "compares each pair of adjacent items, and swaps them if they are in the wrong order. \n",
    "The process is repeated until no more swaps are needed, indicating that the list is sorted.\n",
    "\n",
    "### Process\n",
    "1. **Start at the beginning** of the list.\n",
    "2. **Compare the first two elements**. If the first is greater than the second, swap them.\n",
    "3. **Move to the next pair** of elements, repeat the comparison and swap if necessary.\n",
    "4. Continue this process for each pair of adjacent elements until the end of the list.\n",
    "5. After each pass, the largest unsorted element is correctly placed at the end.\n",
    "6. **Repeat** these steps for the remaining list (excluding the last sorted elements).\n",
    "7. The sorting is complete when a pass requires no swaps.\n",
    "\n",
    "### Characteristics\n",
    "- **Time Complexity**:\n",
    "  - **Best Case**: O(n) when the list is already sorted.\n",
    "  - **Worst Case**: O(n^2) when the list is sorted in reverse order.\n",
    "- **Space Complexity**: O(1), as it only requires a small, constant amount of additional space.\n",
    "- **Stability**: Bubble Sort is stable, meaning it preserves the order of equal elements.\n",
    "- **Adaptability**: It can adapt to a situation where the list is already sorted, making it efficient in such cases.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05f56fbf-15fe-4152-ba8a-7c3459d62657",
   "metadata": {},
   "source": [
    "<img src=\"https://cdn.emre.me/sorting/bubble_sort.gif\" />\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a20dde5e-0202-40de-8ecf-3a14b98748aa",
   "metadata": {},
   "source": [
    "### warm up task\n",
    "\n",
    "- find a maximum value in a list\n",
    "- what steps would you take?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "91aa260f-55b9-4d8e-ae7b-1d2af7a6bb7e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_maximum(arr):\n",
    "    pass\n",
    "\n",
    "# Example usage\n",
    "arr = [3, 6, 2, 8, 4]\n",
    "print(f\"Maximum number in the array is: {find_maximum(arr)}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "99926678-b66d-497c-aca8-4d9993246af2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# give an array of arbitrary length, find on what position lies a value\n",
    "# assume array is of integers\n",
    "# if value is not found, return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "533961bd-a01e-40a1-af09-af713065c766",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Element found at index: 1\n"
     ]
    }
   ],
   "source": [
    "def linear_search(arr, x):\n",
    "    pass\n",
    "# Example usage\n",
    "arr = [3, 4, 1, 7, 9]\n",
    "x = 4\n",
    "print(f\"Element found at index: {linear_search(arr, x)}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0d11799-fc5b-495e-8130-ee1c4c7bb387",
   "metadata": {},
   "source": [
    "## Linear Search\n",
    "\n",
    "### Time Complexity\n",
    "- **O(n)**, where `n` is the number of elements in the list.\n",
    "\n",
    "### Performance Characteristics\n",
    "- **Worst-Case Scenario**: The element is at the end or not present, requiring `n` comparisons.\n",
    "- **Average-Case Scenario**: On average, `n/2` comparisons are made.\n",
    "\n",
    "### Efficiency\n",
    "- Linear search is less efficient for larger datasets, with performance degrading linearly with the size of the data.\n",
    "\n",
    "## Question:\n",
    "- What is the complexity of searching in `m x n` matrix?\n",
    "\n",
    "## Can we devise a better algorithm?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "edebf315-f531-4776-b9db-d124526dd8a9",
   "metadata": {},
   "source": [
    "## Binary Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "7746271a-cab9-4199-98d3-9db30d254c1c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Element found at index: 0\n"
     ]
    }
   ],
   "source": [
    "def binary_search(arr, x):\n",
    "    pass\n",
    "# Example usage\n",
    "arr = [1, 3, 5, 7, 9]\n",
    "x = 1\n",
    "print(f\"Element found at index: {binary_search(arr, x)}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "08a296b4-c0d4-469b-af51-808c3f013314",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "### Time Complexity\n",
    "- **O(log n)**, assuming the data is sorted.\n",
    "   - How would we achieve this in real life?\n",
    "\n",
    "### Performance Characteristics\n",
    "- **Worst-Case and Average-Case Scenario**: The search space is halved with each step, significantly reducing the number of comparisons.\n",
    "\n",
    "### Efficiency\n",
    "- Significantly more efficient than linear search for large, sorted datasets. Efficiency increases as the dataset size grows.\n",
    "\n",
    "## Comparison\n",
    "\n",
    "- **Dataset Size Dependency**: Linear search's performance is proportional to the dataset size, while binary search's performance is logarithmically proportional.\n",
    "- **Precondition**: Binary search requires sorted data, unlike linear search.\n",
    "- **Practical Implications**: For small datasets, the speed difference might be negligible. However, for large datasets, especially if sorted, binary search is exponentially faster than linear search."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f79e199b-2f0d-43f7-bab4-65c26eb3f031",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "e1f78c59-be1a-4559-8a3d-4e4b09460583",
   "metadata": {},
   "source": [
    "### Find sum of all subarrays of size k in an array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "20389694-c8ba-4c11-a691-66bd2675baca",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[13, 20, 24, 28]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def double_iteration(arr:list[int], k:int)->list[int]:\n",
    "    pass\n",
    "arr = [1,5,7,8,9,11]\n",
    "double_iteration(arr, 3) #O(n*k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "71036d24-e149-4b27-becd-4f28a529664e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[13, 20, 24, 28]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fixed_sliding_window(arr:list[int], k:int)->list[int]:\n",
    "    pass\n",
    "\n",
    "arr = [1,5,7,8,9,11] \n",
    "fixed_sliding_window(arr, 3)#O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "2d0ffb86-4760-4464-a88c-41599bfad16e",
   "metadata": {},
   "outputs": [],
   "source": [
    "#lets compare the algorithms\n",
    "import random\n",
    "\n",
    "arr = [random.randint(0, 10000) for _ in range(1000)]\n",
    "k = 120"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "273e4662-8129-46fa-9e8c-7d03c0c656e5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "21.4 ms ± 2.77 ms per loop (mean ± std. dev. of 10 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -r 10 -n 10 double_iteration(arr, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "fd06c4e2-52fc-4877-a9d0-54723b6887d5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "608 µs ± 60.7 µs per loop (mean ± std. dev. of 10 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -r 10 -n 10 fixed_sliding_window(arr, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "92e15508-e51d-4dc0-8801-a823910c9bf8",
   "metadata": {},
   "outputs": [],
   "source": [
    "## imagine sliding windows with more complicated functions (mean, meadian) \n",
    "# create a structure which adds -> removes elements from the end and start of the window\n",
    "# idea is to always keep one pass through the data "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42a6c6ea-e586-4002-b817-3866ee8c0836",
   "metadata": {},
   "source": [
    "# lets get back to data processing level a bit\n",
    "## Lets try to make a small project of putting together a dataset of Tarantino movies from wikipedia"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "id": "1abb1df0-1e3a-4b54-a944-3bcac8164888",
   "metadata": {},
   "outputs": [],
   "source": [
    "#lets prepare step by step what we will do"
   ]
  }
 ],
 "metadata": {
  "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.11.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}