assignments/assignment_4 (quiz_1).ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyNjtNVs44+CN26wJYsZboyR",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/gayatri-p/cs142-lab/blob/main/assignments/assignment_4%20(quiz_1).ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **Quiz 1**\n",
        "\n",
        "---\n",
        "\n",
        "#### *Implementation of Divide and conquer algorithms including binary search and merge sort*\n"
      ],
      "metadata": {
        "id": "yggBS1wF38XI"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Problem 1(a).** Given a list of size $n$ consisting of consecutive 1s followed by consecutive 2s, find the position of transition from 1 to 2 in $O( \\log n)$ time.\n",
        "\n",
        "For example, if the list is $[1, 1, 1, 2, 2, 2, 2]$, the index is 3 where the transition occurs."
      ],
      "metadata": {
        "id": "kKIn1CKw4Ecy"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def find_transition(arr, low, high):\n",
        "  if len(arr) == 1:\n",
        "    return low\n",
        "\n",
        "  else:\n",
        "    # implementing binary search algorithm\n",
        "    mid = low + (high - low) // 2\n",
        "\n",
        "    if arr[mid] == 2:\n",
        "      if arr[mid-1] == 1:\n",
        "        return mid\n",
        "      # check left\n",
        "      return find_transition(arr, low, mid-1) \n",
        "    else:\n",
        "      if arr[mid+1] == 2:\n",
        "        return mid\n",
        "      # check right\n",
        "      return find_transition(arr, mid+1, high)\n",
        "\n",
        "arr = [1, 1, 1, 1, 1, 2, 2]\n",
        "print(find_transition(arr, 0, len(arr)))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hSnX4mQn7ytF",
        "outputId": "92c5a82e-09a4-4086-b99f-cd5a8e7e0987"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Problem 1(b).** Suppose you have a function $F$ such that given two lists $L_1$ and $L_2$, $f(L_1, L_2)$ returns the difference of the sum of elemets of $L_1$ and $L_2$. Now given a list of size $n$ that consists of $n-1$ many 1s and a single 2, find the position of 2 making at most $2\\log n$ many calls to the function $F$.\n",
        "\n",
        "```python\n",
        "def F(L1, L2):\n",
        "  diff = 0\n",
        "  for x in L1: diff += x\n",
        "  for x in L2: diff -= x\n",
        "  return diff\n",
        "```\n",
        "\n",
        "For example, if the list is $[1, 1, 1, 2, 1, 1]$, the index is 3 where 2 occurs."
      ],
      "metadata": {
        "id": "fkNOcdFp44HC"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "counter = 0\n",
        "\n",
        "def F(L1, L2):\n",
        "  global counter\n",
        "  counter += 1\n",
        "\n",
        "  diff = 0\n",
        "  for x in L1: diff += x\n",
        "  for x in L2: diff -= x\n",
        "  return diff\n",
        "\n",
        "def find_two(arr, prev=0):\n",
        "  if len(arr) == 1 :\n",
        "    # list should be [2] (else not found)\n",
        "    return prev if arr[0] == 2 else -1\n",
        "    \n",
        "  else:\n",
        "    n = len(arr)\n",
        "    mid = n // 2\n",
        "\n",
        "    # check if the middle element is two\n",
        "    if arr[mid] == 2:\n",
        "      return mid + prev\n",
        "\n",
        "    # left and right should contain equal no. of items\n",
        "    left = arr[:mid]\n",
        "    right = arr[mid+1:] if (n % 2) else arr[mid:]\n",
        "\n",
        "    # add 1 to take care of of odd cases\n",
        "    mid = mid + 1 if (n%2) else mid\n",
        "\n",
        "    diff = F(left, right)\n",
        "\n",
        "    if diff == -1:\n",
        "      # right part has the 2\n",
        "      return find_two(right, prev+mid)\n",
        "\n",
        "    else: # diff = 1\n",
        "      # left part has the 2\n",
        "      return find_two(left, prev)\n",
        "\n",
        "arr = [1, 1, 1, 1, 1, 2, 1, 1, 1]\n",
        "print(find_two(arr, 0))\n",
        "print('Number of calls of F:', counter)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "EqxnpiEF70Ij",
        "outputId": "39e82737-b02f-4fd1-90e0-ded252beea93"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5\n",
            "Number of calls of F: 3\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Problem 2(a).** Given a $L$ and an integer $N$, write a code of merge sort to sort $L$ that uses insertion sort as the base case when the list is of size $\\le N$."
      ],
      "metadata": {
        "id": "Q5arsxc955Kp"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def merge_sort(arr, N):\n",
        "  if len(arr) <= N:\n",
        "    # sort using insertion sort\n",
        "    # if length <= N\n",
        "    return insertion_sort(arr)\n",
        "\n",
        "  else:\n",
        "    mid = int(len(arr)/2)\n",
        "    a1 = merge_sort(arr[:mid], N)\n",
        "    a2 = merge_sort(arr[mid:], N)\n",
        "    a3 = []\n",
        "\n",
        "    while a1 and a2:\n",
        "      if a1[0] < a2[0]:\n",
        "        a3.append(a1[0])\n",
        "        del a1[0]\n",
        "      else:\n",
        "        a3.append(a2[0])\n",
        "        del a2[0]\n",
        "    \n",
        "    if a1:\n",
        "      a3 += a1\n",
        "    if a2:\n",
        "      a3 += a2\n",
        "    \n",
        "    return a3        \n",
        "\n",
        "def insertion_sort(arr):\n",
        "  if len(arr) == 1:\n",
        "    return arr\n",
        "  \n",
        "  for i in range(1, len(arr)):\n",
        "    current = arr[i]\n",
        "    j = i - 1\n",
        "    while j >= 0 and current < arr[j]:\n",
        "      arr[j+1] = arr[j]\n",
        "      j -= 1\n",
        "    arr[j+1] = current\n",
        "  \n",
        "  return arr\n",
        "\n",
        "array = [9, 8, 7, 6, 5, 4, 3, 2, 1]\n",
        "N = 4\n",
        "print(merge_sort(array, N))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hiWc5Uvu71Pg",
        "outputId": "12f60e45-cba2-48ba-b270-536ed433705f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Problem 2(b).** Suppose there are $n$ stairs. You are standing at the bottom ($0^{th}$ stair) and want to reach to the top.If you are at $i^{th}$, you can climb either 1 stair or jump $i$ stairs at a time. How many ways can you reach the top?\n",
        "\n",
        "\n",
        "1.   Write the recursive formulation to count the number of ways to reach the top.\n",
        "2.   Write a program to count the number in $O(n)$ time.\n",
        "\n"
      ],
      "metadata": {
        "id": "2fHbTDeV55Nl"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "ways = {0:0, 1:1}\n",
        "counter = 0\n",
        "\n",
        "def ways_to_reach(top):\n",
        "  global counter\n",
        "\n",
        "  if top in ways:\n",
        "    return ways[top]\n",
        "\n",
        "  else:\n",
        "    counter += 1\n",
        "    \n",
        "    # two ways to reach the top:\n",
        "    # i) +1 from the prev step\n",
        "    # ii) +i from the ith step (only for even steps)\n",
        "    \n",
        "    prev = ways_to_reach(top-1) # ways to reach top-1\n",
        "\n",
        "    if top != 2 and (top % 2) == 0:\n",
        "      # for even steps (except 2)\n",
        "      half = ways_to_reach(top/2) # ways to reach top/2\n",
        "      ways_to_reach_top = prev + half\n",
        "\n",
        "    else:\n",
        "      ways_to_reach_top = prev\n",
        "\n",
        "    ways[top] = ways_to_reach_top # memorization\n",
        "    return ways_to_reach_top\n",
        "\n",
        "top = 25\n",
        "print(ways_to_reach(top))\n",
        "print('Number of function runs:', counter)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "FSHL6qzu73IB",
        "outputId": "215fe041-d329-4c2f-9026-e8d5287e44a9"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "47\n",
            "Number of function runs: 24\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Problem 3.** Given two sorted lists of size $m$ and $n$, find the $k^{th}$ element of two sorted arrays in $O(\\log m + \\log n)$ time. (Hint: Write a program similar to the one done in assignment 3 for 'median finding')"
      ],
      "metadata": {
        "id": "gTfSv8PC7PCy"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#working code \n",
        "def find_k(arr1, arr2, m, n, k): \n",
        "  if m == 1 or n == 1:\n",
        "    if n == 1:\n",
        "      arr2, arr1 = arr1, arr2\n",
        "      n = m\n",
        "    if k == 1:\n",
        "      return min(arr1[0], arr2[0])\n",
        "    elif k == n + 1:\n",
        "      return max(arr1[0], arr2[0])\n",
        "    else:\n",
        "      if arr2[k - 1] < arr1[0]:\n",
        "        return arr2[k - 1]\n",
        "      else:\n",
        "        return max(arr1[0], arr2[k - 2])\n",
        "\n",
        "  mid1 = (m - 1)//2\n",
        "  mid2 = (n - 1)//2\n",
        "\n",
        "  if mid1 + mid2 + 1 < k:\n",
        "    if arr1[mid1] < arr2[mid2]:\n",
        "      return find_k(arr1[mid1 + 1:], arr2, m - mid1 - 1, n, k - mid1 - 1)\n",
        "    else:\n",
        "      return find_k(arr1, arr2[mid2 + 1:], m, n - mid2 - 1, k - mid2 - 1)\n",
        "  else:\n",
        "    if arr1[mid1] < arr2[mid2]:\n",
        "      return find_k(arr1, arr2[:mid2 + 1], m, mid2 + 1, k)\n",
        "    else:\n",
        "          return find_k(arr1[:mid1 + 1], arr2, mid1 + 1, n, k)\n",
        "\n",
        "list1=[3, 5, 6, 7,8,9,10,11]\n",
        "list2=[5, 8, 9, 11, 23]\n",
        "print(find_k(list1,list2,len(list1),len(list2),1))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "LbFThLroucin",
        "outputId": "958a95c6-c215-483a-e423-a9eb0b20dcc0"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "3\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#wip..?\n",
        "def find_k(l1, l2, n, m, k):\n",
        "  if len(l1)<=5 or len(l2)<=5:\n",
        "    if len(l1)<=5 and len(l2)<=5:\n",
        "    #   if len(l1)==0:\n",
        "    #     return l2[k]\n",
        "    #   elif len(l2)==0:\n",
        "    #     return l1[k]\n",
        "      pass\n",
        "    elif len(l1)<=5:\n",
        "      l2=l2[k-5:k]\n",
        "    elif len(l2)<=5:\n",
        "      l1=l1[k-5:k]\n",
        "    print(0, l1, l2, k)\n",
        "\n",
        "    a3=[]\n",
        "    while l1 and l2:\n",
        "      if l1[0] < l2[0]:\n",
        "        a3.append(l1[0])\n",
        "        del l1[0]\n",
        "      else:\n",
        "        a3.append(l2[0])\n",
        "        del l2[0]\n",
        "    if l1:\n",
        "      a3 += l1\n",
        "    if l2:\n",
        "      a3 += l2\n",
        "    return a3[k]\n",
        "\n",
        "  mid1 = len(l1) // 2\n",
        "  mid2 = len(l2) // 2 \n",
        "  \n",
        "  # if l1[mid1] < l2[mid2]:\n",
        "  #   print(1, l1[mid1:], l2, k-mid1)\n",
        "  #   return find_k(l1[mid1:], l2, n-mid1, m, k-mid1)\n",
        "  # else:\n",
        "  #   print(2, l1, l2[mid2:], k-mid2)\n",
        "  #   return find_k(l1, l2[mid2+1:], n, m-mid2, k-mid2)\n",
        "\n",
        "  # else:\n",
        "  if l1[mid1] < l2[mid2]:\n",
        "    print(3, l1, l2[:mid2],k )\n",
        "    return find_k(l1, l2[:mid2], n, mid2, k)\n",
        "  else:\n",
        "    print(4, l1[:mid1], l2, k)\n",
        "    return find_k(l1[:mid1], l2, mid1, m, k)\n",
        "  \n",
        "list1=[3, 5, 6, 7,8,9,10,11]\n",
        "list2=[5, 8, 9, 11, 23]\n",
        "k = 4\n",
        "lst=sorted(list1+list2)\n",
        "print('Sorted:',lst)\n",
        "print(f'{k}th element (in nlogn):', lst[k])\n",
        "print(list1, list2)\n",
        "print(find_k(list1, list2, len(list1), len(list2), k))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8TFWA9BynsTs",
        "outputId": "61e69e92-a6ad-4e9b-cb51-b4f328477e03"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Sorted: [3, 5, 5, 6, 7, 8, 8, 9, 9, 10, 11, 11, 23]\n",
            "4th element (in nlogn): 7\n",
            "[3, 5, 6, 7, 8, 9, 10, 11] [5, 8, 9, 11, 23]\n",
            "0 [] [5, 8, 9, 11, 23] 4\n",
            "23\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#also working code\n",
        "def find_kth(nums1, start1, nums2, start2, k):\n",
        "    remains1 = len(nums1) - start1\n",
        "    remains2 = len(nums2) - start2\n",
        "\n",
        "    if remains1 == 0:\n",
        "        return nums2[start2+k-1]\n",
        "    if remains2 == 0:\n",
        "        return nums1[start1+k-1]\n",
        "    if k == 1:\n",
        "        return min(nums1[start1+k-1], nums2[start2+k-1])\n",
        "\n",
        "    half = k//2\n",
        "    if remains1 > remains2:\n",
        "        k2 = min(half, remains2)\n",
        "        k1 = k - k2\n",
        "    else:\n",
        "        k1 = min(half, remains1)\n",
        "        k2 = k - k1\n",
        "\n",
        "    if nums1[start1+k1-1] > nums2[start2+k2-1]:\n",
        "        return find_kth(nums1, start1, nums2, start2+k2, k1)\n",
        "    else:\n",
        "        return find_kth(nums1, start1+k1, nums2, start2, k2)\n",
        "\n",
        "list1=[3, 5, 6, 7,8,9,10,11]\n",
        "list2=[5, 8, 9, 11, 23]\n",
        "k = 4\n",
        "lst=sorted(list1+list2)\n",
        "print('Sorted:',lst)\n",
        "print(f'{k}th element (in nlogn):', lst[k-1])\n",
        "print(list1, list2)\n",
        "print(find_k(list1, list2, len(list1), len(list2), k))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "4m62qtm6t3z3",
        "outputId": "d44db509-209b-4788-e635-77914bae1341"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Sorted: [3, 5, 5, 6, 7, 8, 8, 9, 9, 10, 11, 11, 23]\n",
            "4th element (in nlogn): 6\n",
            "[3, 5, 6, 7, 8, 9, 10, 11] [5, 8, 9, 11, 23]\n",
            "6\n"
          ]
        }
      ]
    }
  ]
}