{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Basic Data Structure & Algorithms in Python\n", "\n", "### 1. Know-What" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "1.1 What are **list, tuple, array**? Can you explain the difference between them?" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# list example\n", "ls = ['a', 'b' ,'c']" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'a'" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ls[0]" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(ls)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ls[1] = 'x'\n", "'x' in ls" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['a', 'x', 'y']" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ls.append('y')\n", "ls.remove('c')\n", "ls" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['a', 'x']" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ls.pop()\n", "ls" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "('a', 'b', 'c', 'a')" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# tuple example\n", "tup = ('a', 'b', 'c', 'a')\n", "tup" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "ename": "TypeError", "evalue": "'tuple' object does not support item assignment", "output_type": "error", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[1;31mTypeError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m\u001b[0m in \u001b[0;36m\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mtup\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;34m'a'\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[1;31mTypeError\u001b[0m: 'tuple' object does not support item assignment" ] } ], "source": [ "tup[1] = 'a'" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'a', 'b', 'c'}" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# set example\n", "st = {'a', 'b', 'c', 'a'}\n", "st" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "1.2. What is **list comprehension** in Python? " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Question: Given a random number generator from 0 to 1, and a list of N objects, how to generate a list of length K (K" ], "text/plain": [ "" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from IPython.display import Image\n", "Image(url= \"https://www.geeksforgeeks.org/wp-content/uploads/kadane-Algorithm.png\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We have come up with several algorithms to do the maximum subarray problem. Let's code each of them and test if they work correctly." ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7\n", "12\n" ] } ], "source": [ "## input : a list of numbers\n", "## output : the largest sum of subarray\n", "\n", "## 1. Calculate a list of cumulative sum up to each element\n", "## return maxSum = max cumulative sum - min cumulative sum\n", "\n", "def maxSubarray(nums):\n", " \n", " cSum, maxSum, minSum = 0, 0, 0\n", " \n", " for i in range(len(nums)):\n", " cSum += nums[i]\n", " maxSum = max(cSum, maxSum)\n", " minSum = min(cSum, minSum)\n", " \n", " return maxSum - minSum\n", " \n", "# test1\n", "nums1 = [-2, -3, 4, -1, -2, 1, 5, -3] \n", "print(maxSubarray(nums1))\n", "\n", "# test2\n", "nums2 = [2, 3, 2, 3, -4, -4, -4] \n", "print(maxSubarray(nums2))" ] }, { "cell_type": "code", "execution_count": 52, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2\n", "-10\n" ] } ], "source": [ "## 2. Calculate a list of cumulative sum up to each element to get list 1\n", "## reverse the original array and do the same to get list 2\n", "## return maxSum = max cumulative sum of list 1 - max cumulative sum of list 2\n", "\n", "def maxSubarray(nums):\n", " \n", " cSum, maxSum = 0, 0\n", " cSum2, maxSum2 = 0, 0\n", " \n", " for i in range(len(nums)):\n", " cSum += nums[i]\n", " maxSum = max(cSum, maxSum)\n", " \n", " for i in range(len(nums)):\n", " j = len(nums) - 1 - i\n", " cSum2 += nums[j]\n", " maxSum2 = max(cSum2, maxSum2)\n", " \n", " return maxSum2 - maxSum\n", " \n", "# test1\n", "nums1 = [-2, -3, 4, -1, -2, 1, 5, -3] \n", "print(maxSubarray(nums1))\n", "\n", "# test2\n", "nums2 = [2, 3, 2, 3, -4, -4, -4] \n", "print(maxSubarray(nums2))" ] }, { "cell_type": "code", "execution_count": 64, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7\n", "10\n", "0\n" ] } ], "source": [ "## 3. Calculate cumulative sum up to each element\n", "## if the sum is negative, give up and start from 0\n", "## if the sum is positive, go on and add the next element\n", "\n", "def maxSubarray(nums):\n", " \n", " cSum = 0 ## cumulative sum up to index i, take positive part\n", " maxSum = 0 ## max sum of subarray\n", " \n", " for i in range(len(nums)):\n", " \n", " cSum += nums[i]\n", " \n", " if cSum < 0:\n", " cSum = 0\n", " \n", " maxSum = max(maxSum, cSum)\n", " \n", " return maxSum\n", " \n", "# test1\n", "nums1 = [-2, -3, 4, -1, -2, 1, 5, -3] \n", "print(maxSubarray(nums1))\n", "\n", "# test2\n", "nums2 = [2, 3, 2, 3, -4, -4, -4] \n", "print(maxSubarray(nums2))\n", "\n", "# test3\n", "nums3 = [-2, -2, -3, -3, -4, -4]\n", "print(maxSubarray(nums3))" ] }, { "cell_type": "code", "execution_count": 65, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7\n", "10\n", "0\n" ] } ], "source": [ "## 4. Calculate cumulative sum up to index i , Ti\n", "## Tmin = min(T1, T2, ..., Ti)\n", "## max sum = Tn - Tmin\n", "\n", "def maxSubarray(nums):\n", " \n", " cSum = 0 ## cumulative sum up to index i\n", " Tmin = 0 ## min sum of first few elements\n", " maxSum = 0 ## max sum of subarray\n", " \n", " for i in range(len(nums)):\n", " \n", " cSum += nums[i]\n", " Tmin = min(Tmin, cSum)\n", " maxSum = max(maxSum, cSum - Tmin)\n", " \n", " return maxSum\n", " \n", "# test1\n", "nums1 = [-2, -3, 4, -1, -2, 1, 5, -3] \n", "print(maxSubarray(nums1))\n", "\n", "# test2\n", "nums2 = [2, 3, 2, 3, -4, -4, -4] \n", "print(maxSubarray(nums2))\n", "\n", "# test3\n", "nums3 = [-2, -2, -3, -3, -4, -4]\n", "print(maxSubarray(nums3))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Modeling Maximum Drawdown**: \n", "Given a time series of stock returns, what is the largest contiguous loss during the time window? and for how long does it last?\n", " " ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [], "source": [ "def maxDrawdown(nums):\n", " \n", " '''return maximum drawdown (%), and the corresponding time window'''\n", " cSum = 0 ## cumulative sum up to index i\n", " Tmax = nums[0] ## max sum of first few elements\n", " minSum = 0 ## min sum of subarray\n", " idx1 = 0 ## start index of the subarray\n", " idx2 = 0 ## end index of the subarray\n", " idxT = 0 ## end index of Tmin\n", " \n", " for i in range(len(nums)):\n", " \n", " cSum += nums[i]\n", " \n", " if Tmax < cSum:\n", " Tmax = cSum\n", " idxT = i + 1\n", " \n", " if minSum > cSum - Tmax:\n", " minSum = cSum - Tmax\n", " idx1 = idxT\n", " idx2 = i\n", " \n", " return idx1, idx2, minSum" ] }, { "cell_type": "code", "execution_count": 82, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(0, 1, -3)\n", "(4, 6, -12)\n", "(0, 5, -16)\n" ] } ], "source": [ "# test1\n", "nums1 = [-2, -3, 4, -1, -2, 1, 5, -3] \n", "print(maxDrawdown(nums1))\n", "\n", "# test2\n", "nums2 = [2, 3, 2, 3, -4, -4, -4] \n", "print(maxDrawdown(nums2))\n", "\n", "# test3\n", "nums3 = [-2, -2, -3, -3, -4, -4]\n", "print(maxDrawdown(nums3))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Try your algorithm on AAPL stock price data:**" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[]" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAD8CAYAAACb4nSYAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3Xd4m+W5+PHvo21Z8p6xs3dCIANCSCHMMsvsANpS2lNK20N/benppuP09HQeDl2ctofTFloKFAqUAmVTVoAAgQyyt5N4T9myLVmynt8f7ytZdmRbdmxLsu/Pdfmy8kp6/byOdevW/SyltUYIIcTUYEl1A4QQQkwcCfpCCDGFSNAXQogpRIK+EEJMIRL0hRBiCpGgL4QQU4gEfSGEmEIk6AshxBQiQV8IIaYQW6obAFBUVKRnzZqV6mYIIURGefvtt5u01sUjeU5aBP1Zs2axcePGVDdDCCEyilKqaqTPkfKOEEJMIRL0hRBiCpGgL4QQU4gEfSGEmEIk6AshxBQiQV8IIaYQCfpCCDGFSNAXQoypg02dvLSnMdXNEINIi8lZQojJ4+xbXwTg0I8vSW1DREKS6QshxkUg1JvqJogEJOgLIcZFkz+Y6iaIBCToCyHGTDDcl903+XtS2BIxGAn6QogxU93aHbvd2CGZfjqSoC+EGDNHJOinPQn6Qogxc7ilK3ZbavrpSYZsCiHGzN76DjxOG1aLkkw/TUmmL8QUobVm/d4mPn7nm/x9c/W4/IxddR0sLPNS7HVKpp+mJNMXYgrYcKCZ257dw5sHWwDoCvZy+fKKMf0ZWmt21bZz6UnTONDYKZl+mpKgL8Qkt63axzV3bKDE6+R7ly3lYFMn9755mECoF5fdOmY/p649QHsgzKIyLx2BMFuOto3ZucXYkfKOEJPcu9U+AB78zFquXzuL0+cV0ROOsPWob0x/zsPvGCWjpRW5FHmcNMVl+q2dPeyoaR/TnydGR4K+EJPcoeZO7FZFRX4WACtn5gOwNUEm3hvR7K7rGPHPePeoj589u4dLlpWzYnoexV4nnT29dAbDAFzyy1e4+JevHMdViLEiQV+ISe5wcxfTC9xYLQqAfLcdp81CQ4Ka+29f2s8FP3+ZbdXJfwro6gnzhfs3UeRx8oMrT0ApRbHXCfQN26zxBcbgSsRYkKAvxCRX1dzFzAJ37N/RoJyoo3VHrVGC2VOffLb/kyd3cbCpk9uuPok8twOAIo/xfeAInt6IHnH7xdiSoC/EJKa1pqq5k5mF2f2ODxb087LsALR0JrduTp0vwL1vHuYjp85g7dyifueHY2flxq/NI1JDgr4Qk1iTv4fOnl5mFrr7HS/xOmnoOLbkYjNLQEfjllMYyp83VNEb0Xx63dx+x+ODvt+s6wMEQpERtV+MPQn6Qkxi0TLN/BJvv+ODZfq+7hBgdP4mY29DB/NKPEwv6P+mUuB2oBTUtwepbet7A5E19lNPxukLMYlFR+IsLOsf9Eu8Llq7QvSEIzhsRu63q6491rlb1dxFMlo7QxRkO445brNaWFDi5dcv7uO1/U2x4xL0U08yfSEmsd11HRRmO2LllqiBo2u6esJc+PNXeG1/MwBHWrroCQ9fimnp6kkY9AHu/uRqPnn6bHbW9nUKB5M4pxhfEvSFmMR21Xcck+UDFHv6d7S2dYX63R+OaPY3+oc9f0tnD/nuxEG/JMfFLZcs4dWvn8Pnz50PSKafDoYN+kqp6UqpF5RSO5VS25VSXzCP/5dSapdSaqtS6m9Kqby453xDKbVPKbVbKXXBeF6AECIxrTX7G/zML/Ecc19lgTFRK1q7bw/0Bf1TZhmTt3bVDT2DtjeiaevqoXCQTD+qINvBaXMKgeQ7cv+8oYpnttcl9VgxMslk+mHg37TWi4E1wE1KqSXAs8AJWusTgT3ANwDM+64BlgIXAr9WSo3dAh9CiKR0BMP4g2Eq893H3De32IPDZolNwvLFZfrLp+fhsFn6lWUG6glHuPeNKiIa8ocJ+gBOuxFqAuFeqpo7CfUawb+mrZuDTf07jbXWfOuRbdx499uD/uzoqCExcsMGfa11rdb6HfN2B7ATqNBaP6O1jo7F2gBUmrcvB/6itQ5qrQ8C+4DVY990IcRQ6sxZsGW5rmPus1stLC7Pia2/Ex21A5DndrCg1MPO2sEz/Uc2V/Ptv28HGLSmH89lM/K+9u4Q5//sZe569RAAl92+nrNvfbFfAB9ub91f/XMv33pkG/94t3bYnyuONaKavlJqFrACeGPAXf8CPGnergCOxN131Dw28Fw3KqU2KqU2NjY2jqQZQogk1JpBvzxB0AdYVpHD9pp2IhFNe6BvLH13Ty+LynLYNcQaPK+bHb6QZNA3M/3GjiDBcITXDxjPjwb4V/f1jfAZbjbwvgajr0EN+1NFIkkHfaWUB3gI+KLWuj3u+C0YJaB7oocSPP2Yz2Fa6zu01idrrU8uLi4eWauFEMOq8xnj4xNl+gDLp+fjD4Z5t9rXL9OPaM2iMi+NHcGEG6ForfsF/cE6cuM5zSWcm82Zvu8cbiUS0bE3pCfisvboMNNcc3bwQNFzeFwy4nw0kgr6Sik7RsC/R2v9cNzx64H3AR/RWkcD+1FgetzTK4GasWmuECJZNW0BlDLG5Cfy3sWlOKwW/rapOhb0b1w3h0+fOZfF5TkA7EpQ19/b4KeuvW82b3LlHSPUtJiZfVtXiANNnbFVOOvjzvd2VSsAWYOs9R9dIqK3V2r6o5HM6B0F/B7YqbW+Le74hcDXgMu01vEzOR4FrlFKOZVSs4H5wJtj22whxHDqfAGKPM7Y5KuBct12zl1cwmNbamjpDOJ12fjmxYvJzbKzyBzmGR3B09bVwwazJPP4lhosCt53YjmQbHnHCOAtXX31+jcPtsTKSm3mm86Dbx+N1eq7esIkEg36Pb0y5n80ksn03wNcB5yjlNpsfl0M3A54gWfNY78F0FpvBx4AdgBPATdprWVwrhATrLY9MGg9P+rKFRU0d/bw9Pb6fuWUQo+TEq8zNoLn+jvf4po7NtAZDPPY1lrWzCnkl9esYMt3z09q9y1nNNOPW8jtn7saYrd9XSE2H2njm397l7VzC/n0mXNoD4S5+BevHLPMc/QcIQn6o5LM6J31WmultT5Ra73c/HpCaz1Paz097thn4p7zA631XK31Qq31k0OdXwgxPvY3+JlRcOxwzXhnLSwh322nsSN4TA19UXlObATPliPGhiuPbanhYFMnl500DYtFDVp3H8hmtWCzqFjArsjLYv0+YwCH12Wjuq2bz9z9NsUeJ7d/eCU5LuO8O2rb+fGTu2Ln6asik9SMYXEsmZErxCTU7A9S3dbNiZW5Qz7OYbPwvhOnAcQCbdTiMi/7Gvx09/R9UP+fF/dhsyguPKFsxG1y2a00mx3D6xYUxyZqzS7KJhiOUNce4DuXLqEg20G2o+/TQ3wZJ36UUUhq+qMiQV+ISWirWRI5sTJvmEfClSuNEdUDs/bF5Tn09Eb4zUv7Y8eOtHSzbkFxbLOUkXDZLbGgvW5+39r78Wv9zykybrudfSNz4jP65rjRRD2yNv+oSNAXYhJ696gPpWDptJxhH7tieh7Lp+exZMBjF5Ubnbm/fH4vxV4nbjP7vvSk8lG1yWnry95Pm1sY275xdtxa/9HhpdmOxEE/fmipZPqjI0FfiAz0X0/vYtPh1oT3dfWE+cubhzmxIheva/iau1KKv/3r2tiiaFFzijzku+2ct7iEV756NifPKsBps/DeJSMv7UDfUgxWsy8g+oY0u7gv04+21+3se4MIxGX08eUdGb0zOjK7QYgM09UT5n9e2M8/dzXyj/93OhZL//mQv/rnPmp8AX5x7Yqkz2mMzO7PYbOw4ZvnxjL0z509j/evrMDjHF3YiC7F4HZYUUqxZk4hB5s6mZabdcxj4zP9+M1e+mf6EvRHQ4K+EBmm2ZzgtLO2nae213Hxsr5yy74GP7975QDvX1nJKbMKjvtnxZdkVs8+vvNFl2KIBvQvnDufq0+ZTjhBmcYd15HbEQjT1RPG7bDRHhf0ZfTO6Eh5R4gME12GwGZR/OzZPbHFyrTWfOfv28iyW/nGxYtS2cSEom8g2c7odxtziz3kuY8tQWUP+DRR325k+9FMXynJ9EdLgr4QGSY6guUT75nF3gZ/bAbrszvqeW1/M1+5YCFFHudQp0iJaXlGGWdgQI+OGjppet9Io/ghm0BsglZ7IITDasHrtElH7ihJ0Bciw0Qz/evWzGJhqZefP7uHls4efvLULuYUZ3Pt6hkpbmFi0dFB0fV2olx2K/fecCp3ffyU2LH4IZtely22Cmd7d4icLDsOm1U6ckdJgr4QGSZa0y/yOrjlksUcbO7krP96gQNNnfz7pUuxWdPzZb3EXMTtcMuxm66vnVfUbzMWt72v03ft3EJe2duE1pr27jA5WTYcViU1/VGSjlwhMkyzP0iW3YrbYWPdgmJu+9BJPLKphstOmsa6Bem7THk000+mLGOxKH501TJWzy7gtX1NPL29nsMtXfi6Q+Rm2emNaKnpj5IEfSEyTEtnD4Wevqz4yhWVXLmicohnpIdo7f7y5dOSeny0TBUdTLp+XxPtgRAF2Q78gbAE/VGSoC9EhmnqHH4z8nS1/4cXYxnhllezi7KZluvi1X1N+LpDzCrMpsEapCcsHbmjIUFfiAzT7A9SmjP0ksnpyjrSiI8xcew984p4Zkc9Wmtys+zYbRbpyB2l9OzxEUIMqr49SIk3/YZkjqfT5xfh6w7RHggzpzgbh1URko7cUZGgL0QGCYR6afIHY2Pep4q1c41VOZWCi5eV47BZpKY/SlLeESKD1PmMvWSnWtAv9jpZVpFLTpaN0hwXdquFjkDi7RTF0CToC5FBatq6AZiWl5k1/eNx5ydOwWb2CditFhmnP0oS9IXIIDVmpl8xxTJ9oN/SEg6rlHdGS2r6QmSQaKZfNsyG55OdUdOXIZujIUFfiAxS3dpNsdfZb8njqcguyzCMmgR9ITLEgUY/j22t4aQk9r2d7OwDyjt1vgCX/mo9u+raU9iqzCBBX4gM8bPn9mJViu9fsTTVTUk5u7X/5KzNR1p5t9rHJ+/amMJWZQYJ+kJkgCZ/kKe21fKBkyspT7C94FTjHDBOP2iWeqrbumk1l54WiUnQFyLN+AesN6+15tuPbKM3ovnIqTNT1Kr0MnDIZvyY/br2QCqalDFkyKYQaeTOVw/yH4/v4MHPrKXW101rV4j27hBPbqvjlosXM6/Ek+ompgW71UJEQ29EY7WofkG/yR8c4plCgr4QaeLOVw/yvcd2APB2VQs/fGIXYCw9cPnyadxwxuxUNi+t2G3GJK1QbwSrxUpHoG/DdAn6Q5PyjhBp4M8bqvjeYzu4YGkpJV4nbx5sjd23pDyHH191IkqNfIXKycplDlnt6ukFjPJOdAXPpg6p6Q9Fgr4QKXakpYvvP76DsxYWc/uHV7J0Wg7P7awH4OdXL+ehz64lyzG1x+UPNKvIDcC+Bj8AHYEQ5bkuHFYLTZ2S6Q9Fgr4QKfan1w+hgR9dtQy71cJicy9ZgHMWl+CyS8AfKPo72llrjMv3B8N4XXaKPA7J9IchNX0hUqyxI0hZjis2FPPcxaU8u6Oea1fPIMdlT3Hr0lNZjos8tz0W9NsDYbwuGzaLkpr+MCToC5FiHYEwOVl9L8VVM/N59ktnprBF6U8pxeKyHHbWdQDG77Aiz0W2w0pDhwT9oUh5R4gUaw+E8Dolox+pxeU57K5rpzei6QiEzPKOUzL9YUjQFyLF2rv7Z/oiOYvLvQRCEQ41d9JhlneKvU6a/D30RmQFzsFI0BcixdoDIandj0K0M3dHTbvZkWujLNdFb0TTLNn+oCToC5FiRpYqQX+k5pV4sFoU7xxupTei8brslOYY+wzUt0vQH4wEfSFSKNwbwR+U8s5ouOxW5hZn88reJgAK3A7KzKAv6+8MToK+ECkUXVxNMv3RWVyeE5ugNbfEE8v0JegPbtigr5SarpR6QSm1Uym1XSn1BfN4gVLqWaXUXvN7vnlcKaV+qZTap5TaqpRaOd4XIUSmii4UluOSTH804ieyzS/1UORxYFFQ75OgP5hkMv0w8G9a68XAGuAmpdQS4OvA81rr+cDz5r8BLgLmm183Ar8Z81YLMUn4uo2FwnKyJNMfjWjQL8txkeOyY7NaKPY6qZdMf1DDBn2tda3W+h3zdgewE6gALgf+aD7sj8AV5u3LgT9pwwYgTylVPuYtF2ISaDdXh/RKpj8qi8u9gJHlR5XmuKS8M4QR1fSVUrOAFcAbQKnWuhaMNwagxHxYBXAk7mlHzWMDz3WjUmqjUmpjY2PjyFsuxCTQV96RTH80ij1O5hZnc8qsgtix0hyXZPpDSDq9UEp5gIeAL2qt24dY5jXRHcfMlNBa3wHcAXDyySfLTAoxJbWb5Z1cKe+MilKKp7+4DktcPCrLcfHmwZYUtiq9JZXpK6XsGAH/Hq31w+bh+mjZxvzeYB4/CkyPe3olUDM2zRVicuk0R+9kO6W8M1o2qwWLJS7o57rwdYcIhHpT2Kr0lczoHQX8Htiptb4t7q5HgevN29cDf487/jFzFM8awBctAwkh+otu6O2yy+jpsVLidQJQJyN4EkomvXgPcB3wrlJqs3nsm8CPgQeUUp8EDgMfNO97ArgY2Ad0AZ8Y0xYLMYkEQkbQd1gl6I+VstzorNwAs4qyU9ya9DNs0NdarydxnR7g3ASP18BNx9kuIaaEYLgXm0Vhk6A/ZmRW7tDkL02IFAqGIzht8jIcSyU5fZm+OJb8tQmRQsFwr2yHOMZyXDay7FbqfLLoWiIS9IVIoUBIMv2xppSiLNdFfYdk+onIX5sQKRQMR3BKpj/mSnOcsv7OICToC5FCwVCvZPrjQJZiGJz8tQmRQpLpj4+yHBcN7UGMwYQingR9IVIoGJZMfzyU5rjo6Y3Q2hVKdVPSjvy1CZFC0pE7PmKbqUhd/xjy1yZEChnj9KW8M9bKco2lGGSs/rEk6AuRQsY4fXkZjjXZNnFw8tcmRAoFQ5Lpj4fSHBcOq4VDTZ0ABEK9dPfIqpsgQV+ICbGztp2V33+WTYdb+x0PhntxSqY/5uxWC/NKPOyobQfg6w9t5YY/vZXiVqUH+WsTk0Ikkt5D857bUU9LZw9fvH9zv2GEQenIHTeLy3PYWdsBwNuHW9l61CdDOJGgLyaBf2ytZfUPn2dHTXuqmzKoPQ1+AKqau2js6FsTJhiOyNo742TJtBya/EEON3dxpKWbjkCYNhnCKUFfZLZguJcfPrGTJn+QL/91S6qbM6jt1T6imzvVmsMIIxFNT69k+uNlcZmxafrj7/Zt3HeouTNVzUkb8tcmMtqr+5qobuvmjPlF7KhtT8tx2R2BEAeaOjl/SRkAtb5uAHp6jQ1UpCN3fBSbO2htONC3X25Vc1eqmpM2JOiLjPbGwRbsVsVnz5wLwJajbbH7esytCFNtY5XReXvRMiPo17QZb0zRPVwl0x8f0c3mNx1uxW5VKCWZPkjQFxnuzYMtnFiZx8qZ+VgtineP+gB4bEsNC771JIdTkNlprWn299XtX9vXhMNq4fwlZThtltjY8b79cSXTHw85ZtDvCIQp8jiZlpslmT4S9EUGO9LSxbtHfZw6uwCX3cqCUi/P7Kjj3aM+fvbcHgBeP9A0oW1q6+rhn7saWPWfz/G/L+3n75ureWZHPStn5pHlsFKe66KmzSjvBEPR8o68DMeDy26N/W7z3Q5mFLipkkw/qY3RhUg7kYjmy3/dgstu5cOnzgDgU2fM5luPbOPS29fHHrf5SBtXnzJj3Nrx0NtH+dOGKt4zt5C1c4v46O/fiN33oyd3AWBR8Bmz/FSW64r1OwTDZnlHxumPm9wsOw0dQfKz7cwocPPM9vpUNynlJOiLjHTXa4d442ALP33/iVTmuwG4amUl5y0p5YG3jvDMjnpqfd3c9+YRlk/PG9PAHwz3orUxCuff/rqF6QVZ/Pal/fz6xf2xx5w0PY8vnjefirwsZha6Y521lflunt5Wx4FGPwEz03dJR+64iQV9t4OZhdk0d/bQHgiR47KnumkpIymGyDj7G/385KldnLOohA+eXNnvvhyXnRvOmMMDnz6NG8+YA8B3/r59TCfl3HTPJk75z+e4Z0MVAL+6diWvff1cvnHRIi5canTWzi3O5uyFJSwo9fYbnXPjujnYbRauuWMDO+uMeQWS6Y+faGduQbaDWYVGcpCKfp50In9tIuPc/XoVSsGPr1qGUmrQx1132iy+e+kSguHImC28dbCpk+d21tMRDPO79QcBmJbroizXxafPnMutHzqJS0+axhfOnZ/w+QtKvdz3qTX0RjRfe2grFgUVeVlj0jZxrGjQj2b6ICN4JOiLCdPsD47JcgnVbd3MLMimxFxJcSgnVOQCxto3Y+GeDVXYLIpVM/MBsFsVRR5n7H6P08avrl0RCzCJLCzz8pcb17CsIpdbP3gSc4o9Y9I2caycuEx/ppnpT/URPBL0xYToCUdY9Z/PcdO97xz3uep8Acpyhw/4AIvMWZnvHm0/7hJPd08vf337KBecUMbq2QUAFHucWCyDf9oYzPxSL49+7nSuWlk5/IPFqMUy/WwHboeNYq8ztvLmVCVBX0yIanOY4pPb6ni7qjWpAFzfHuDuDVW0dfX0O17XHqAsiSwfwOuyM7PQzc+e28Oibz/FBT97mZbOnuGfmMBjW2vwdYe4bs1MZpuZvCzfld5imb7bAcCsQjdVLVM705fRO2JCHI57ob3/N69xQkUOXz5/IY0dQVbOzGduXImjrauHK/7nVQ6ZH8N/9MROPrx6Bp88YzZFHidN/mDSmT7A7deu5PUDTeyq7eDhTdVsr/FxxvziEV/DnzdUsaDUw6mzC7Ca2X10Vq1IT32ZvvF9ZmE2r+xtTGWTUk6CvpgQh83Os+e+dCavH2jmjpf38//u20RHIIzXaePd710AQEN7gEe31PQF/KuW8ebBFu587RB/fP0Qnzt7PlozoqC/rDKXZZW5HGnp4uFN1bHJUSOxp76DrUd9fO+ypSilmGVm+vnZjhGfS0ycRWVevE4blXlGPX9WoZsH3w7S1RPG7Zia4W9qXrWYcFXNXThtFuYWZzOvxMjqv/3INgA6gmFCvRHqfAEu/59XaenswWGzsOs/LsRiUVy7egZfeu8Cvv7w1thM25EE/aiyXBcWBdWtyQX9QKiXtq4QZbkudtcZ67KfOseo5Rd5HHzrksWcu7h0xO0QE+c984piCQUQ62A/3NLForKcVDUrpaSmLybE4ZYuZhS4Y0Msl1fm9bv/+Z0NfOpPGwmZ69FcfEJZvw7S6QVu/ve6k2P/TramH89utVCa46K6Lbnhm1/+6xau+J9XAWLT92cUGBmjUoobzpjD7KLBR+mI9BP9/zvSMvJPe5OFZPpiQhxq7oy94MAYtuiwWSjMdhDq1Xzu3neIaM2dn1hNRV4WJTnOY87hcdr42dUn8Yvn9saG343UtLwsHnrnKMun53LdabMGfdy2ah+Pb60FoDMY5lBzF6U5zilbEpgsvC7j/68zGE5xS1JHMn0x7pr8QfbU+1lpjm0HcNgsvG9ZOR9YVckXzptPOKL55sWLOXNBMfNKPINOk79yRSUvfuXsUQffUvPN5HuP7aB1iFE8tz6zO3a71hegqrlzyLH3IjNkOYzZ0d1JdsBvq/bxtQe3pv12nCMhaYsYd+v3GitdnjG/qN/x265eDhhLEb9nbuGElEr8QePFHo5onthWy0dOndnv/gONfg40dvLi7kbOXljMC7sbqfMFONTcxdkLRz7iR6SXLHMZ666e5IL+3zdXc//GI3ztokUUTJJOe8n0xbh7YXcD+W47J0zLTXi/Uoo5xZ4hl1QYK1+9YCGfeM8s5pV4uPPVQ7GVLsGYQHbOf7/EDX/aSG6Wna9ftBiAzUdaaewIMkvq9xkvmuknO9R2l9mB39UzecpBEvTFuGrr6uGpbXVctKx8VDNXx9oJFbl899Kl3HLJYvY1+PndKwdj971zuDV2+1uXLI71G/z2pQNYLYr3LZs24e0VY8thtWBRxuzqZOypjwb9yTMfQ4K+GFd3vXaIYDjCRweUUVLt7IUlnDG/iHs2VNEb0Ty6pYZr7tgAwJbvnM8HT56Oy26lMNuBPxjmiuUVzBhl57FIH0opsuzWpGr6bV091LcbO6BJ0BciCS/taeSXz+/lkhPLWTIt/cZEX7t6BjW+AC/vbeTPrxvLJK+eXUCuu68TuTzPhVLwr2fPTVUzxRjLctiSCuJ76v2x25OpvCMduWJcHGj087l732FBqZefvv/EVDcnofMWl1KY7eAvbx6mtr2btXMLuf3DK/s95orlFZyzsKTfMhEis2U5LEnV9HebpR1IvhyUCYbN9JVSf1BKNSiltsUdW66U2qCU2qyU2qiUWm0eV0qpXyql9imltiqlVg5+ZjFZRSKaT9/9Nnarhf/72MlkO9Mzt3DYLLx/VSXP72zgaGs3p84uPGaExg1nzOFL5y9MUQvFeMiyW5MK4nvq+oJ+51QK+sBdwIUDjv0U+J7WejnwHfPfABcB882vG4HfjE0zRSbxdYfY2+Dn0+vmML0gvevgV58ynXBEozXMLZHROVNBlsNGV5KZfrm53Ef3JCrvDBv0tdYvAy0DDwPRIm0uUGPevhz4kzZsAPKUUuVj1ViRGfzmbMd8d/qPa55b7ImtjR9dE0hMbll2C4FBMvdX9jbyx9cOobVmT30Hy6cby4VMpo7c0X7u/iLwtFLqVow3jrXm8QrgSNzjjprHageeQCl1I8anAWbMGLtNq0XqdZpZkceVnmWdgT539jxuZx9ziiToTwVuh43GjmDC+677/ZuAMbqrrSvEihl5PLmtblIF/dGO3vkscLPWejpwM/B783iigdgJ5y9rre/QWp+stT65uFhmOk4m/oAR9NO1lj/QugXFPPDp03DYZDDbVJBltw47Gue+tw4DxrwOq0VNqtE7o/0rvx542Lz9V2C1efsoMD3ucZX0lX7EKD2yqZoP/OY1wr2RVDclKdHyjsdpTXFLhDiWy24lEEr8WlpYamyvederh2L/dtutkuljBPIzzdsuHg99AAAdA0lEQVTnAHvN248CHzNH8awBfFrrY0o7InkN7QG+/fdtbKxq7TeELJ11muvbeJyJF00TIpXcjuEnZ3WHeinyOCj0OMlyJDfaJ1MM+/lbKXUfcBZQpJQ6CnwX+BTwC6WUDQhg1uaBJ4CLgX1AF/CJcWjzlPIfj++I/cFtOtzG0kHWr0kn/mAIgGzJ9EUaynIMXt7xxy253GuurJnttE2qIZvDBn2t9bWD3LUqwWM1cNPxNkoYXtjdwONba7n5vAXcvaGKdw638tE16bWcQSLRlSy9kumLNBQt70Qi+pj1oDoCIa5YPo1HNtewaqYxqssY1z95avqZ0dM2BWmt+fdHtzO3OJvPnDWHbTU+Nh1uS3WzkhLdoEIyfZGO3OZKm8FwJLbqJhivOX8wTGW+m2duXhfbktPtkJq+mACtXSGqmru4dvUMnDYrK2fkc7Cpc8iNP9KFPxjGabNgs8qfl0g/0TX1B9b1A6EIEW2UcxaUemMb+bidya3VkynkVZkCwXAvd7y8n/ZAaNDHRDfvrsw3ZrSumGFMEtl0pHXQ56QLfzAc25ZOiHQTDfrRocVRHWZf1MD5Je4khnhmkikX9H1dIX6//iDba3wpa8M/ttbywyd28aX7Nw/6mOq2aNDPAuDESqMD91/u2shT29J7QFRnMJwxY/TF1DPXnHl9490b+22DGH0T8A7423U7rLERaZPBlAv6X35wC99/fAdffXArRr/zxHt+ZwMAz+1s4LZn9yR8TDToT8szgr7bYYstF/D1h9/F1z34p4Sxcqipkw/+9jV21raP6Hn+QBiPBH2RplbNzOerFy5kV10Hte2B2PFoYB+YsMwt8VDd1s2Rlq4Jbed4mXJBf0eNEcC217Szfl/ThP/8QKiXF3c38IFVlZy/pJTb/7mXUIJJVzVt3WTZreTHre1+1ydO4aHPnkZbV4g/b6ga97a+ur+Jtw61ctEvXhnRxDC/ZPoiza2Yng/A/oa+NfNj5Z0Bf7uXnWTsmPbIpuoJat34mlJBP9QbodbXzY3r5jCjwM3XHtw64R2jr+9vprOnl0tOLOecRSVENNTHZRtR1a3dTMtz9ds31u2wsWpmAWvmFPCXtw73+2g6Hqqa+zKblq7kf0+dPZLpi/QWXVxvX1zQj5V3BtT0pxe4WT27gL9tqk5ZdWAsTamgX+cLENEwr9jD7R9eQaM/yFce3DKh/5HP7Kgj22Fl7dzCWOmm1mcE/e01Pn71/F72NXRQ3dZNRX7iZYk/fOpMjrR0j/snlQONfS+Itq7kyknBcC9NHT0S9EVaK/I4yM2ysy/ubzy6UGCiT6nvX1nBgaZOthxNXV/gWJn0Qf/xrTW8vr8ZgCOtRuZamZ/FiZV5fPPixTy3s4HP3buJbdXj/5/ZG9E8u6OesxaV4LRZmZZnjAPefLiNr/x1C+/71Xr++9k9XPXr19jX4GdOUeL13S9YWkq+2859bx4e1/YeaOqMZT3JBv3/fHwnde0BzllUMp5NE+K4KKWYV+KJZfrba3zcfP8W4NjyDsBFy8pxWC08ta1uQts5HiZ1Otbd08vn79tERMOVKypYYC6mFB0G+fG1s9h4qJV/vFvLkdYuHv3c6ePans1HWmny93DB0jIAynONTP8HT+zEblXccPps5pd4+epDWwEG3VfWabPygVWV3PnqIRo6ApR4XWPe1nBvhMPNXaydV8TLexppTbK8s7u+g9WzCrhiRcWYt0mIsTSv2MNzO+sBuO2ZvgEViYYb57jsFHkcNPkTL8mcSSZ1pr+j1kdEwzmLSnh8aw0/eWoXFkVspp1Sits/vILzFpf0q1+Pl6e312O3Ks5aaCwlHf8x8juXLuWWS5Zw1qK+ZaaXDrGZ+DWrZxCOaP668ei4tPX36w8SjmjWzDFGDPmSzPQ7ZYy+yBDzSjw0d/bw1qEWnt9lDK741bUrcNkTzyT3uux0DDG3JlNM6qD/rll/+9FVy3jyC+t4z7xC1swp7LduulKKVTML8HWH+i22NB42HmphxfT82Ey/eO9dXApAiddFZX4Wdqtifol30HPNLfawZk4B//X0bn761K4xbef/vXyAHz25i0tOLOcjq421ftq6k8v0u3p6cUs9X2SA6PaYt/ztXVx2C9+4aBGXmiN1EvG4bHQEMn+S1qQO+lurfRR7nZTmuJhX4uGeG9Zw76fWHPO4CnMCVHQW7HipbutmRmH/ztnVswpw2iyxTx8A5y4q4dTZhcNu6nHbh5ajFGPaofvnDVX84ImdXHJiOb+4ejk5WTbsVkVrkpm+Pxgm2yFr7oj0N6/YSKr21Pv50MnTKfQ4h3y812Ub98RwIkyalOxPrx+itTPEp9bNxu2wEYlo3jjQEtvjcijRWa/VbV0sLBs8uz4ePeEIDR1BKswRO1H3fOrU2BKuUd+7/ISkzjktL4urVlTy+v6xCfpHW7v4wT92cuaCYn5x9fLY2jm5WY6kO3K7ZIy+yBAV+Vk4bRZCvRFuOH3OsI/3uuwTUgYeb5Pi1am15mfP7qG1K8T9bx3maxctAozM+qsXLhz2+ZVmID46jpl+nS+A1n2fKqLsVguDlBCTUux10uTvQWvdb0z/aNzzxmFCvRF+cOUJ/RZLy3PbaUuiIzcS0XSFeiXTFxnBalGcOqeQ8hzXMZ/AE/E4bZOipj8pgn59e5DWrhAfOrmSrUd9fOEvxpo2HqeN85eUDfv8Io8Th9UyruWdo23mcNEBmf7xKvI46OmN0N4dJtc9+vXrt1X7eKeqlSXTcmKjm6Ly3fakMv3uUC9aZ87euEL88ROnJP3YnElS058Ur87o2jAfWDWdH165jDcPttDQEWR6gbvfetmDsVgUFflZY5Lp763v4N43D/ONixb3q8lH31CmjXHQL/YadchGfzAW9KMrArodif97tdYcau5itjkPYF+Dn/f9aj0A1yXYpCU3yxFbC2go0ckt0pErMsVIPh17XTaC4Qg94Ui/1/a+hg6mF7hx2jLjE+6k6MjdYQb9ReVebFYLa+cVccWKClbNzE/6HBV5WRxNIrAN5543DnPnq4f44RM7+62pEw2a5XljO6a+2Ox8auzoGz988/2b+fx9g6/geduzezj71hepau4E6LeQ1LLKY7djzHPb8SVR3umKLlgl5R0xCXnNUXfxJZ46X4DzbnuZHz0xtiPoxtOkCPpvHGxhRoE74VDIZFXkZY1JecdpN36ld712iNN+9E9++tQujrR0sau2g+kFWWOeDRSZmX78pJFt1e0cbPIP9hT+96UDQN8bRY2v77rXzi085vEep42OJEYt+IODT2MXItNFZ+rGl3iiVYYdI1yJNpUy+tVZ1dzJ3a9X8fKeRm4+b8FxnasyP4smf5BAqHfQyRnJaO8OUZjt4NYPnsQ9bxzmty/t57cv7Sei4QOrKo+rjYkUefoH/WC4lxpfN3lZid8Au3t66TE/gTSbi83VtgWwWhS7vn8h9gS7XXmcNjqD4WE7i6O7C2UPUlYSIpNFJx36zddCIBSJBfux7qsbTxn96tx8pI3frT+Ix2njutOOb8Pw2Fj9tm7mFntGfZ727jB5bjtnLyrh7EUl1LR1s/bH/wTgtDnHZtHHKy/Ljs2iYln7kZZutIa27hC9EY11wMbPO2r71hhqMYN+ja+bUq8zYcAHI3OPaGM7uaH6SGRvXDGZRcs7jR1BPvaHNznY1MnicmPWfCSDVt/M6KB/ybJyTptTiM1qoSDbcVznio5Yuemed7jvU2vIH+X5fN0hcuOy7Gl5WVx/2kz++HoVa+eNfdC3WBRlua5Yn0G0Tq81tHb1xD4JRFW39S3j3BKX6ZcPkal4zCDuD4aHDvpDrFIoRKaLZvpfe2grDWaSFR38MRGbGo2VjK7p26wWSnJcxx3woS/T31XXwV/eOjLq87QHQuQMKK1899KlvPSVs2ILrI212UXZHGwygn2/NfAT7BVQF1e/b/abQd/X3W9G8EDRIN45TF0/2pHrlo5cMQlFg35DR5D/vKJvAqXNomjPoKGcGR30x1J5jotrV88A4Hlz5b3RGJjpg5GNzyxMvEzyWJhb7OFAYyda61imD31BPV5NWwCP08b0gixaOoN0BsPU+AJMSyLoDzcFPXq/rKUvJqPSHBcLSj18/4oT+Oiamdz58VP47UdXcv7S0ozK9OXVabJYFD+6ahklXie//OdemvzBY0ojyWjvDh3XKKLRmF2UjT8YptEfpKqlC5fdQiAUSZjp1/q6Kc914XbaaO7s4b+e3k2oN8KFJ5QPen5Pspn+MPMDhMhkLruVZ24+M/bvs809I17a05hRQV8y/QHeu6QUreGfuxpG/FytNe2B8DGZ/niLTrI60NhJVXMXJ1YY6w21dB679netz6jfF2Y72HrUxx9fP8TH1swcck5Dspl+Z08vDqtl2IXihJhMclx2CfqZbOm0HKblunh2x8hLPJ09vfRGNDlZE5vpRoP+/kY/R1u7WD7DCPrNCTL9mrYA5WY/iK87xLTcLL5y4aIhzx/fkTuUtq6eCb92IVItJ8tOTzhCINSb6qYkRYL+AEopzltSyit7G+nuGdl/YvTdfqIz/dKcvm0XQ72aucXZ5Lhsx9T0A6FemvxByvNcseUbfnjVsmFr8H0duUP/Pho7ghSPwy5eQqSz6Ou9PUOyfQn6Cbx3SSmBUIRXR7hOffQ/faJr+g6bhTy3nberWgGYUZDN7GIPW6t93Pr07tgG57HlKspyuP60Wdxx3SrOXFA86Hmjkh29YwT9kfeDCJHJokE/mvR96YHN475/9fGQoJ/AqbML8TptsRJPOG4NnaGkKtMHYw2eA+awzVlFbk6YlsOWI23c/sI+Lrv9Vf6xtZbNh9sAWDEjj7JcF+cvHX4FUuibYTtceaexIxhbC0iIqSI+6Id7Izz8TjXfePjdFLdqcBL0E3DYLJy9qISnd9Rx9+uHmHfLk7xd1TLs86JLIRR4jn/ewEhFM2yHzUKp18UJFX0Lp80v9XDTve/w6xf3UZbjipWDkmW1KLLs1iEzfa01jX7J9MXUM6swG4uCBzYe4VAGbLIiQX8QV66ooK0rxLf/vh2AQ03D/2dGF2wbuDvWRIgOL51Z4MZiUbFN1V12C/ffeBqfPH02Tf4eVswYfiexRLKdttiM20R83SFCvZoSCfpiiplR6OZfz5rHAxuP8usX9qW6OcOSoRaDOGN+EXarItRrrKnRNUTAi6pp6ybHZYut0TGRohn2THMHoEVlOZwxv4ibzp6Hw2bh2+9bwiUnllM+xCSsoXicVvxDdORG1/6RTF9MRZ8/dz4v7mng4U3VgLHxULqSTH8QNquF9V87h7duOQ9gyIAXVd3WPeabpCSrL+gbwzcdNgt3f/JU1sQt8rZyRv6ol4LwuGxsOdLG+r1N6ASLSzVI0BdTmMNm4edXL8dpzlEJhpPrB0wFCfpDKM1xUeRxYFHJZfpHW7tjm6xPtFh5J4m9Pkfj42tn09UT5qO/f4NLb1+Pb8D2ifXtxkJuEvTFVDWvxMtvPrqSEypy6OrppSdNA78E/WEopch22IYduQJGeSdVmX60bBOdqDXWPrCqkvVfO4dvXbKYbdXtvLq//3DWF3c3kptlZ3r++LzpCJEJzllUytUnTwfSd+VNCfpJyDY3ERlKRyBEeyCckk5cMNbq/81HVvKeuUXj9jNcdisfPtVYlG5/g599DX72N/rpCIR4ensdl55ULkswiCkv122M3vN1D7/FaCpIR24Ssp3WYWej7q7rAMYv0x6OxaK4aNngi6aNFbfDRkVeFm8fbuW/n91Dlt3Kv1+2hGA4wvtXjv3OYEJkmui4/bauDM30lVJ/UEo1KKW2DTj+/5RSu5VS25VSP407/g2l1D7zvgvGo9ETLds5fHnnncPGbNiVI9iMPVPNKc7mxd2NAHSHern/rSPMKcpm+fTRDQcVYjLJGzBDN90k81n8LuDC+ANKqbOBy4ETtdZLgVvN40uAa4Cl5nN+rZTK+B01sh22YTty36lqY0aBe1TLMWeaLHMP4eiaPe8cbuP9qyqH3D9XiKkiz53hmb7W+mVg4HTUzwI/1loHzcdE1yG+HPiL1jqotT4I7ANWj2F7U8LI9PvKO6HeCJFI/2GLm460snKUE58yzeXLKwC4/cMrAFAKrlhRkcomCZE2ouWd1q70rOmPttdtAXCGUuoNpdRLSqlTzOMVQPxeg0fNY8dQSt2olNqolNrY2Ng4ymZMDI+zbwkCrTXzb3mSf39se+z+Zn+Q+vZgv6UPJrNLTixn/w8v5oz5xWTZrZw2pzBlHdhCpJsclx2rRWVupj8IG5APrAG+AjygjM/2iT7fJ9wmXmt9h9b6ZK31ycXFw6/0mEruuNE7gZAx9vZPr1fF7t9Tb6xiubDMO/GNSxGrRWG1KH79kZX8x+UnDP8EIaYIi0VRkO2IrcWVbkY7euco8LA2pma+qZSKAEXm8elxj6sEao6viannievI7Qge++69u85Ysnhh6dQJ+lHRLeOEEH0K0zjojzbTfwQ4B0AptQBwAE3Ao8A1SimnUmo2MB94cywamkrZDhvBcIRwbwR/gl3vd9f7yXPbZTaqEAIwZqY3+dOzpj9spq+Uug84CyhSSh0Fvgv8AfiDOYyzB7jezPq3K6UeAHYAYeAmrXVm7CE2hGxzu8DOnt6EQzf31HewoNQro1eEEICxLMpBc3+LdDNs0NdaXzvIXR8d5PE/AH5wPI1KN/E7R3XEZfqBUC9Om4U9dR0yekUIERMt72it0y4ZlDnzSYguk9rQEewX9Bvag9T6AnQEwyyYQp24QoihFXmdBEIRuobZZ/uvG49Q6+ueoFYZJOgnITrL9rX9Tf3KO/UdAXbXG8svTMVOXCFEYtFJmgM7c+OXJX/jQDNffWgr//vSgQltmwT9JJR4XSwq87J+bxP+QN/onTpfgD3mmjsLSj2pap4QIs0UmlumxnfmNnYEmf2NJ3ji3Vp8XSFuvn8zMwvcfOWChRPaNgn6SVq3oJiNh1pjm4WAMSlrd30HpTlO8twTvy+uECI9FWUbmX5zXKYf7dj96oNb+eYj79LQEeQX16yI9RlOFAn6STpjfhE9vRGe39mA3apQClo6e2Ijd4QQIionywjk7XF9gNEJnv5gmH9sreXm9y7gpBQsUihBP0mnzCrAYbOwu76D3Cw7+W4Hjf4ge+v9LJJOXCFEnOg+2R1x5eA2c339PLedG06fzWfOnJuStsl6+kly2a2cOruAV/Y24XHasFktbDrcRjAckUxfCNGP12WE1vjRftG1eF74t7PIz05dOVgy/RE4Y76xK5XHZaMg28EusxN3Kq25I4QYnt1qwWW39Mv0o+vr55ircKaKBP0ROH2esTCc12mn0HynVgrmlcjIHSFEf16X/ZhM3+uyYbWkdrKWBP0RWFTmpcjjJDfLHhuSNbsoG7dDqmRCiP68Llu/oO/rDsU2WEkliVYjYLEo/u9jq/C67Dy6xVg8dHF5TopbJYRIR16Xnfb4jtyuHvKyUj+0W4L+CK2YYczOjX5Cq5TNQ4QQCeQkyPRzU1zPBynvjJoy94uZK/V8IUQCRnknfshmiFwp72SuT62bjddl4ypZXVMIkYDX2b8j19cVIi8NMn0J+qPkdtj4l9Nnp7oZQog0Fd+Rq7VOm/KOBH0hhBgHXped7lAvod6IsfNeRMvoHSGEmKyis3L9gTCdPUbGL6N3hBBikorOvG3rDtFlBv106MiV0TtCCDEOlphzeN6uasVnrruTDjV9CfpCCDEOojP4X9nbSJu57k461PQl6AshxDiwWBTr5hfxyt4mWjrNZZXToKYvQV8IIcbJGQuKaOns4fX9zYCUd4QQYlKLrsz7/K56HDZjueVUS30LhBBikir2OllSnkMgFCEvy45SqV1WGSToCyHEuFq3wMj206ETFyToCyHEuFpn7riXDvV8kKAvhBDjatWsfLLs1rQJ+jIjVwghxpHTZuV7ly2lPM+V6qYAEvSFEGLcfeiU6aluQoyUd4QQYgqRoC+EEFOIBH0hhJhCJOgLIcQUIkFfCCGmEAn6QggxhUjQF0KIKUSCvhBCTCFKa53qNqCUagSqRvn0IqBpDJuTCpPhGqLkWtLXZLqeyXQtMPrrmam1Lh7JE9Ii6B8PpdRGrfXJqW7H8ZgM1xAl15K+JtP1TKZrgYm9HinvCCHEFCJBXwghppDJEPTvSHUDxsBkuIYouZb0NZmuZzJdC0zg9WR8TV8IIUTyJkOmL4QQIkkTHvSVUtOVUi8opXYqpbYrpb5gHi9QSj2rlNprfs83jy9SSr2ulAoqpb484Fw3m+fYppS6TymVcJcCpdT15nn3KqWujzv+A6XUEaWUP4Ov4Sml1BbzHL9VSlkz+FpeVErtVkptNr9KMvFalFLeuGvYrJRqUkr9fCTXkk7XYx6/Wim11TzHTzPkWp5SSrUppR4fcPxzSql9SimtlCoa6bWMw/V8wbyW7UqpLw7xMy80Xx/7lFJfH/X1aK0n9AsoB1aat73AHmAJ8FPg6+bxrwM/MW+XAKcAPwC+HHeeCuAgkGX++wHg4wl+XgFwwPyeb97ON+9bY7bHn8HXkGN+V8BDwDUZfC0vAidPhr+tAY97G1iXqdcDFAKHgWLzcX8Ezk3nazHvOxe4FHh8wPEVwCzgEFCU4r+1E4BtgBtjU6vngPkJfp4V2A/MARzAFmDJaK5nwjN9rXWt1vod83YHsBPjP/JyjD8mzO9XmI9p0Fq/BYQSnM4GZCmlbBi/tJoEj7kAeFZr3aK1bgWeBS40z71Ba12b4dfQHnceBzCiTpp0upbjlY7XopSaj/GCfyWDr2cOsEdr3Wg+7jng/Wl+LWitnwc6EhzfpLU+NJL2j+P1LAY2aK27tNZh4CXgygQ/cjWwT2t9QGvdA/zF/Fkjvp6U1vSVUrMw3qXeAEqjAdj8PuRHe611NXArRgZSC/i01s8keGgFcCTu30fNY2MiHa5BKfU00IDxB/7gKC8lLa4FuNMsiXxbKaVGeSnpci0A1wL3azMlG60UX88+YJFSapYZaK8ARr3/3wRdy4Q5nuvByPLXKaUKlVJu4GIS/27HLI6lLOgrpTwY5YgvxmWrI3l+PsY73WxgGpCtlPpooocmODYmQ5bS5Rq01hdgfNx0AueMtB1mW9LhWj6itV4GnGF+XTfSdphtSYdriboGuG+kbRjQnpRej5n1fxa4H+MTyyEgPNJ2mG2ZqGuZEMd7PVrrncBPMD5VPYVRtkn0ux2zOJaSoK+UsmP8ou7RWj9sHq5XSpWb95djZK5DOQ84qLVu1FqHgIeBtUqpU1VfB9plGO+I8e+clQzycTCTr0FrHQAexfzIl4nXYmZx0Y/L92J8pM3IazF/1kmATWv99kivI92uR2v9mNb6VK31acBuYG+aX8u4G6PrQWv9e631Sq31OqAF2Gt2FEev5zOMYRxLxegdBfwe2Km1vi3urkeB6GiB64G/D3Oqw8AapZTbPOe55jnf0FovN78eBZ4GzldK5ZtZwvnmsYy/BqWUJ+4PzIbx0XBXhl6LLTrywHwxvQ/jo2/GXUvcea7lOLL8dLoeZY6kMo//K/C7NL+WcTWG1xP/u50BXAXcp7U+Enc9vwXeAuYrpWYrpRwYnyBHd516lCMlRvsFnI7xsWQrsNn8uhhjhMDzGBnE80CB+fgyjHe5dqDNvB0dsfI9jCC3DbgbcA7yM/8Foy65D/hE3PGfmueLmN//PZOuASg1/xi2AtuBX2Fklhn3/wFkY4xyiV7LLwBrJl5L3H0HgEWT5LVyH7DD/BrRCLEUXssrQCPQbT7/AvP4581/hzGy5d+l+HpeMX+vWxhiVJR5/j0Yo3huiTs+ouuRGblCCDGFyIxcIYSYQiToCyHEFCJBXwghphAJ+kIIMYVI0BdCiClEgr4QQkwhEvSFEGIKkaAvhBBTyP8HBt8N1OLavvoAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "## load data from quandl API\n", "import quandl\n", "quandl.ApiConfig.api_key = 'jou3Hy9N_sKPZxy9mgxt' ## replace with your own key of quandl account from https://www.quandl.com/account/profile\n", "AAPL_price = quandl.get(\"EOD/AAPL\", start_date=\"2018-01-01\", end_date=\"2018-12-31\")\n", "\n", "## OR import from url address by Pandas package read_csv\n", "# import pandas as pd\n", "# url = \"https://raw.githubusercontent.com/dlu-umich/dlu-umich.github.io/master/friday-workshop/AAPL_price.csv\"\n", "# AAPL_price = pd.read_csv(url)\n", "\n", "## plot the daily close price of AAPL stock\n", "import matplotlib.pyplot as plt\n", "plt.plot(AAPL_price.Adj_Close)" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "# calculate return from price time series\n", "ret = np.log(AAPL_price.Adj_Close) - np.log(AAPL_price.Adj_Close.shift(1))\n", "ret = ret[1:]" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "If you buy 1 share of AAPL on 2018-10-03 at price 230.27\n", " then sell it on 2018-12-21 at price 150.09\n", "Portfolio will have PnL : -45.43%\n" ] } ], "source": [ "## apply maxDrawdown function to AAPL return time series\n", "start_ind, end_ind, MDD = maxDrawdown(ret)\n", "\n", "# get date and price from index, and shape them in good format\n", "start_date, end_date = AAPL_price.Adj_Close.index[start_ind].date(), AAPL_price.Adj_Close.index[end_ind].date()\n", "start_price, end_price, MDD = round(AAPL_price.Adj_Close[start_ind], 2), round(AAPL_price.Adj_Close[end_ind], 2), round(MDD, 4)\n", "\n", "# print out maximum drawdown trading info\n", "print('If you buy 1 share of AAPL on '+ str(start_date) + ' at price ' + str(start_price))\n", "print(' then sell it on ' + str(end_date) + ' at price ' + str(end_price))\n", "print('Portfolio will have PnL : '+ str(MDD*100) + '%')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Reference:\n", "\n", "1. [Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)\n", "2. [Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)\n", "3. [Kadane's Algorithm to Maximum Sum Subarray Problem](https://www.youtube.com/watch?v=86CQq3pKSUw)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**2.3 Substring matching** : Given two strings $S$ and $T$, how to determine if $S$ is a substring of $T$? \n", "\n", "#### Example: \n", "S = \"abc\", T = \"ahbgdc\" \n", "Return True\n", "\n", "#### Implement your algorithm here:" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [], "source": [ "def isSubstring(s, t):\n", " i = 0\n", " j = 0\n", " \n", " while i < len(s) and j < len(t):\n", " if s[i] == t[j]:\n", " i += 1\n", " else:\n", " j += 1\n", " \n", " return i == len(s)" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "## test 1\n", "s = \"abc\"\n", "t = \"ahbgdc\"\n", "isSubstring(s,t)" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "## test 2\n", "s = \"axc\"\n", "t = \"ahbgdc\"\n", "isSubstring(s,t)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Reference: [is-subsequence](https://leetcode.com/problems/is-subsequence/)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3. Crack" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "3.1 Two Sum closest to target:\n", "\n", "Given an array nums of n integers, find two integers in nums such that the sum is closest to a given number, target.\n", "\n", "Return the difference between the sum of the two integers and the target." ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": [ "## Example: Given array nums = [-1, 2, 1, -4], and target = 4.\n", "## return The minimum difference is 1. (4 - (2 + 1) = 1).\n", "\n", "def twoSumClosest(nums, target):\n", " \n", " ## sorting an array with length n takes O(nlogn) time\n", " nums.sort()\n", " \n", " i = 0 # start with the smallest element\n", " j = len(nums) - 1 # start with the largest element\n", " minDiff = abs(nums[0] - target)\n", " \n", " while i < j:\n", " \n", " diff = nums[i] + nums[j] - target\n", " \n", " if diff == 0:\n", " return 0\n", " \n", " elif diff > 0: # move downwards to a smaller element\n", " j -= 1\n", " \n", " else: ## diff < 0 # move upwards to a larger element\n", " i += 1\n", " \n", " minDiff = min(minDiff, abs(diff))\n", " \n", " return minDiff" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1\n" ] } ], "source": [ "# test\n", "nums = [-10, -5, 1, 5, 10, 12, 13]\n", "target = 4\n", "print(twoSumClosest(nums, target))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Reference: [Two Sum Closest](http://leancodingnow.com/two-sum-closest/)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "3.2 Based on a [Citadel interview question](https://www.glassdoor.com/Interview/You-are-given-an-array-of-integers-A1-A2-An-including-negatives-and-positives-and-another-integer-S-Now-we-need-QTN_168340.htm):\n", "\n", "You are given an array of integers, A1, A2, ..., An, including negatives and positives, and another integer S. Now we need to find three different integers in the array, whose sum is closest to the given integer S. If there exists more than one solution, any of them is ok. Is there an algorithm to find the three integers in O(n^2) time?" ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2\n" ] } ], "source": [ "def threeSumClosest(nums, target):\n", "\n", " nums.sort() ## sorting takes O(nlogn) time\n", " minDiff = abs(sum(nums[:3]) - target)\n", "\n", " for i in range(len(nums)-2):\n", " j = i + 1\n", " k = len(nums) - 1\n", "\n", " while j < k:\n", " newTarget = target - nums[i]\n", " diff = nums[j] + nums[k] - newTarget\n", " if diff == 0:\n", " return 0\n", " elif diff < 0:\n", " j += 1\n", " else: ## diff > 0\n", " k -= 1\n", "\n", " minDiff = min(minDiff, abs(diff))\n", " \n", " return minDiff\n", "\n", "nums = [-2,-3,4,-1,-2,1,5,-3]\n", "target = 12\n", "print(threeSumClosest(nums, target))" ] } ], "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.6.6" } }, "nbformat": 4, "nbformat_minor": 2 }