Workshop 3 - Stretch material.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Stretch material \n",
    "\n",
    "This section contains a number of exercises that can be used as stretch material. They are, more or less, listed in increasing order of difficulty. These excercises will provide some practice material for the use of loops and if-statements, as well as algorithmic efficiency and recursion.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 1:\n",
    "Given an integer array <em>nums</em>, find the subarray (containing at least one number) which has the largest sum and return its sum. Return None if the argument of the function is not a list.\n",
    "\n",
    "Example:\n",
    "\n",
    "- Input: [-2,1,-3,4,-1,2,1,-5,4]\n",
    "- Output: 6\n",
    "- Explanation: [4,-1,2,1] has the largest sum = 6."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxSubArray(nums):\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    # Delete the line below and write your code here\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "nums = [-2,1,-3,4,-1,2,1,-5,4]\n",
    "# Uncomment the line below to check your solution,\n",
    "# note that if it doesn't return True, your solution is incorrect\n",
    "#print(maxSubArray(nums)==6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 2:\n",
    "Given a sorted list of integers, find the index of the integer <em>k</em> in the list and keep track of the number of iterations used to do so. Recall that indexing starts at 0 in python.\n",
    "\n",
    "This is obviously not a very interesting problem in and of itself, but it can teach us something about efficiency. To see that, you  will create two functions:\n",
    "\n",
    "- A linear search: loop through the list until you find the index of the element.\n",
    "- Bisection search: Suppose that we have a list A=[1,2,5,24,29,88,102,223,800,801],we want to find the index of 800. The idea is to approach it as follows:\n",
    "1. Look for the middle element in the list: 88\n",
    "2. Compare the middle element with 800: 88 < 800\n",
    "3. Disregard all the numbers that are less than 88\n",
    "4. Now our list is reduced to [102,223,800,801]\n",
    "5. Look for the middle element again and repeat the process.\n",
    "    \n",
    "Write two functions, linear_search() and binary_search(), that implement the methods described above. Use list <em>A</em> as an example, the answer is 9. How do the number of iterations compare between the two methods?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def linear_search(k, nums):\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :type k: int\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    # Delete the line below and write your code here\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(k, nums):\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :type k: int\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    # Delete the line below and write your code here\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A=[1,2,5,24,29,88,102,223,800,801]\n",
    "\n",
    "# Uncomment the line below to check your solution\n",
    "#print(linear_search(k, A)) \n",
    "#binary_search(linear_search(k, A)) \n",
    "\n",
    "# Now, let's try it again -- uncomment the lines below:\n",
    "bigList = list(range(9999999)); \n",
    "#binary_search(999999,bigList)\n",
    "#linear_search(999999,bigList)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 3\n",
    "\n",
    "Given a collection of distinct numbers, return all possible permutations.\n",
    "\n",
    "Example:\n",
    "    \n",
    "- Input: [1,2,3] \n",
    "- Ouput: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].\n",
    "\n",
    "<em>hint</em>: \n",
    "Try applying recursion. If you're unfamiliar with recursion, read this first: \n",
    "https://en.wikipedia.org/wiki/Recursion_(computer_science)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def permute(nums):\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :rtype: List[List[int]]\n",
    "    \"\"\"\n",
    "    # Delete the line below and write your code here\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "num = [1,2,3]\n",
    "# Uncomment the line below to check your solution\n",
    "#print(permute(num))\n",
    "\n",
    "# Let's try that again -- uncomment the lines below:\n",
    "#from pprint import pprint\n",
    "#pprint(permute([1,2,3,4,5]))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}