Chapter_02_Getting_Started/exercises_2.3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.3 Designing algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3-1\n",
    "\n",
    "> Using Figure 2.4 as a model, illustrate the operation of merge sort on the array $A = \\left \\langle3, 41, 52, 26, 38, 57, 9, 49\\right \\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $A = \\left \\langle3, 41, 26, 52, 38, 57, 9, 49\\right \\rangle$\n",
    "* $A = \\left \\langle3, 26, 41, 52, 9, 49, 38, 57\\right \\rangle$\n",
    "* $A = \\left \\langle3, 9, 26, 38, 41, 49, 52, 57\\right \\rangle$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3-2\n",
    "\n",
    "> Rewrite the MERGE procedure so that it does not use sentinels, instead stopping once either array $L$ or $R$ has had all its elements copied back to A and then copying the remainder of the other array back into $A$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_sort_sub(arr, l, r):\n",
    "    if l >= r:\n",
    "        return\n",
    "    mid = (l + r) // 2\n",
    "    merge_sort_sub(arr, l, mid)\n",
    "    merge_sort_sub(arr, mid+1, r)\n",
    "    arr_l = [arr[i] for i in range(l, mid+1)]\n",
    "    arr_r = [arr[j] for j in range(mid+1, r+1)]\n",
    "    i, j = 0, 0\n",
    "    for k in range(l, r+1):\n",
    "        if j == len(arr_r) or (i != len(arr_l) and arr_l[i] <= arr_r[j]):\n",
    "            arr[k] = arr_l[i]\n",
    "            i += 1\n",
    "        else:\n",
    "            arr[k] = arr_r[j]\n",
    "            j += 1\n",
    "\n",
    "\n",
    "def merge_sort(arr):\n",
    "    merge_sort_sub(arr, 0, len(arr) - 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3-3\n",
    "\n",
    "> Use mathematical induction to show that when $n$ is an exact power of 2, the solution of the recurrence\n",
    ">\n",
    "> $T(n)=\\left\\{\\begin{matrix}2 & \\text{if}\\; n = 2 \\\\ 2T(n/2)+n & \\text{if}\\; n = 2^k, \\text{for}\\; k>1\\end{matrix}\\right.$\n",
    ">\n",
    "> is $T(n)=n\\lg n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $T(2) = 2 = 2 \\lg 2$\n",
    "* Assume that $T(2^k)=2^k \\lg 2^k$, $k > 1$, then $T(2^{k+1})=2T(2^k) + 2^{k+1}$ $=2^{k+1}\\lg 2^k+2^{k+1}$ $=2^{k+1}(1 + \\lg2^k)$ $=2^{k+1}(\\lg2 + \\lg2^k)$ $=2^{k+1}\\lg2^{k+1}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3-4\n",
    "\n",
    "> We can express insertion sort as a recursive procedure as follows. In order to sort $A[1..n]$, we recursively sort $A[1..n-1]$ and then insert $A[n]$ into the sorted array $A[1..n-1]$. Write a recurrence for the running time of this recursive version of insertion sort."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$T(n)=\\left\\{\\begin{matrix}1 & \\text{if}\\; n=1 \\\\ T(n-1)+n-1 & \\text{if}\\; n>1\\end{matrix}\\right.$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3-5\n",
    "\n",
    "> Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence $A$ is sorted, we can check the midpoint of the sequence against $v$ and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is $\\Theta(\\lg n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(a, v):\n",
    "    l, r = 0, len(a)-1\n",
    "    while l <= r:\n",
    "        mid = (l + r) // 2\n",
    "        if a[mid] == v:\n",
    "            return mid\n",
    "        elif a[mid] < v:\n",
    "            l = mid + 1\n",
    "        else:\n",
    "            r = mid - 1\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$T(n)=T(n/2)+C$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3-6\n",
    "\n",
    "> Observe that the while loop of lines 5-7 of the INSERTION-SORT procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray $A[1..j-1]$. Can we use a binary search (see Exercise 2.3 - 5) instead to improve the overall worst-case running time of insertion sort to $\\Theta(n\\lg n)$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No, still has to move the elements for $\\Theta(n)$ in each iteration."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3-7 $\\star$\n",
    "\n",
    "> Describe a $\\Theta(n\\lg n)$-time algorithm that, given a set $S$ of $n$ integers and another integer $x$, determines whether or not there exist two elements in $S$ whose sum is exactly $x$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sort the elements then:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def two_sum(a, x):\n",
    "    l, r = 0, len(a)-1\n",
    "    while l < r:\n",
    "        if a[l] + a[r] == x:\n",
    "            return True\n",
    "        elif a[l] + a[r] < x:\n",
    "            l += 1\n",
    "        else:\n",
    "            r -= 1\n",
    "    return False"
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}