assignments/assignment_2.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyM2Ub3jvb+2YVxRtgTJTCDV",
      "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_2.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **Assignment 2**\n",
        "\n",
        "---\n",
        "\n",
        "#### *Expression evaluation and optimising time complexity*\n"
      ],
      "metadata": {
        "id": "LvY2eU3SpHGY"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Problem 1.** Write a python code (preferably recursive) to evaluate well-defined expressions which are given\n",
        "in form of lists e.g. list1=[ ’(’, ’(’, 3, ’+’, 2, ’)’, ’-’, ’(’, ’(’, 1, ’-’, 2, ’)’, ’+’, 5, ’)’, ’)’ ] is the expression for\n",
        "$((3+2)-((1-2)+5))=1$ and hence should return $1$. (Notice that $(3+)2$ is not a well-defined expression.)\n",
        "\n",
        "\n",
        "* The only allowed operators in the expression are ’+’ and ’-’,\n",
        "* Every operator ’+’ or ’-’, along with its two operands are immediately contained within a pair of parenthesis e.g. (3+5+7) is not allowed, but ((3+5)+7) is allowed,\n",
        "* expression starts and end with parenthesis.\n",
        "\n",
        "**Input:** list1=[ ’(’, ’(’, 3, ’+’, 2, ’)’, ’-’, ’(’, ’(’, 1, ’-’, 2, ’)’, ’+’, 5, ’)’, ’)’ ]\n",
        "\n",
        "**Output:** 9"
      ],
      "metadata": {
        "id": "zVABInSD-hIy"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def evaluate(expr):\n",
        "  if len(expr) == 1:\n",
        "    return expr[0]\n",
        "\n",
        "  j = len(expr) - 1\n",
        "  while j >= 0:\n",
        "    # find an operation of the form (a+b) or (a-b)\n",
        "    if expr[j] == ')' and expr[j-4] == '(':\n",
        "      if expr[j-2] == '+':\n",
        "        a = expr[j-3]+expr[j-1]\n",
        "      else:\n",
        "        a = expr[j-3]-expr[j-1]\n",
        "\n",
        "      # collapse the operation into a value\n",
        "      # and reevaluate the new expression\n",
        "      expr = expr[:j-4] + [a] + expr[j+1:]\n",
        "      return evaluate(expr)\n",
        "    else:\n",
        "      j -= 1\n",
        "\n",
        "expr = [ '(', '(', 3, '+', 2, ')', '-', '(', '(', 1, '-', 2, ')', '+', 5, ')', ')' ]\n",
        "print(evaluate(expr))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "B81R3NYG3PKJ",
        "outputId": "4d72f47b-4e87-4fe9-cb5b-7b32bc52bea6"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Problem 2.** Given a sorted list $L$ of $n$ positive integers and a target $t$, find out if there are two integers $a$ and $b$ in $L$ such that $a × b = t$. Write a program running in time $O(n)$.\n",
        "\n",
        "**Input:** [1, 5, 6, 8, 13, 17, 22, 45], t=132\n",
        "\n",
        "**Output:** 6 and 22"
      ],
      "metadata": {
        "id": "avvoxDDI-_WP"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def find_factors(lst, t):\n",
        "  i = 0\n",
        "  j = len(lst) - 1\n",
        "\n",
        "  # multiplying values in the list from both the ends\n",
        "  # till we reach the target\n",
        "  while i < j:\n",
        "    if lst[i] * lst[j] == t:\n",
        "      return f'{lst[i]} and {lst[j]}'\n",
        "    elif lst[i] * lst[j] < t:\n",
        "      i += 1\n",
        "    else:\n",
        "      j -= 1\n",
        "    \n",
        "  return f'Product of no pair of numbers in the list gives {t}'\n",
        "\n",
        "lst = [1, 3, 5, 6, 8, 11, 13, 17, 22, 45]\n",
        "t = 132\n",
        "print(find_factors(lst, t))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "dHv3oA9h3YYx",
        "outputId": "3bdc2180-e626-4654-a69e-fc7d42339f25"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "6 and 22\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Problem 3.** Given a string S of length n and an ordering O on the characters appearing in S, sort the string S, respecting the ordering O, by modifying the given insertion code.\n",
        "\n",
        "**Input:** S=dcabesfshdsakcdc, O=bacdefshk\n",
        "\n",
        "**Output:** baacccdddefssshk"
      ],
      "metadata": {
        "id": "rT2EtImc_ltF"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def sort(s, o):\n",
        "  s = list(s)\n",
        "  for i in range(1, len(s)):\n",
        "    current = s[i]\n",
        "    j = i-1\n",
        "\n",
        "    # sort by their index in the reference order list \n",
        "    while j >= 0 and o.index(current) < o.index(s[j]):\n",
        "      s[j+1] = s[j]\n",
        "      j -= 1\n",
        "    s[j+1] = current\n",
        "    \n",
        "  return ''.join(s)\n",
        "\n",
        "s = 'dcabesfshdsakcdc'\n",
        "o = 'bacdefshk'\n",
        "print(sort(s, o))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "RYN4-w_S4u9M",
        "outputId": "cb89a5c4-8fda-4290-a89e-1eca1082217b"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "baacccdddefssshk\n"
          ]
        }
      ]
    }
  ]
}