Chapter_02_Getting_Started/exercises_2.1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1 Insertion sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1-1\n",
    "\n",
    "> Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array $A = \\left \\langle 31, 41, 59, 26, 41, 58 \\right \\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $A = \\left \\langle 31, 41, 59, 26, 41, 58 \\right \\rangle$\n",
    "* $A = \\left \\langle 31, 41, 59, 26, 41, 58 \\right \\rangle$\n",
    "* $A = \\left \\langle 26, 31, 41, 59, 41, 58 \\right \\rangle$\n",
    "* $A = \\left \\langle 26, 31, 41, 41, 59, 58 \\right \\rangle$\n",
    "* $A = \\left \\langle 26, 31, 41, 41, 58, 59 \\right \\rangle$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1-2\n",
    "\n",
    "> Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of nondecreasing order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(a):\n",
    "    for j in range(1, len(a)):\n",
    "        key = a[j]\n",
    "        i = j - 1\n",
    "        while i >= 0 and a[i] < key:\n",
    "            a[i + 1] = a[i]\n",
    "            i -= 1\n",
    "        a[i + 1] = key"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1-3\n",
    "\n",
    "> Consider the __searching problem__:\n",
    ">\n",
    "> __Input__: A sequence of $n$ numbers $A = \\left \\langle a_1, a_2, \\cdots, a_n\\right \\rangle$ and a value $v$.\n",
    ">\n",
    "> __Output__: An index $i$ such that $v=A[i]$ or the special value NIL if $v$ does not appear in A.\n",
    ">\n",
    "> Write pseudocode for __linear search__, which scans through the sequence, looking for $v$. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def linear_search(a, v):\n",
    "    for i in range(len(a)):\n",
    "        if a[i] == v:\n",
    "            return i\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1-4\n",
    "\n",
    "> Consider the problem of adding two n-bit binary integers, stored in two n-element arrays $A$ and $B$. The sum of the two integers should be stored in binary form in an $(n+1)$-element array $C$. State the problem formally and write pseudocode for adding the two integers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_binary(a, b):\n",
    "    n = len(a)\n",
    "    c = [0 for _ in range(n + 1)]\n",
    "    carry = 0\n",
    "    for i in range(n):\n",
    "        c[i] = a[i] + b[i] + carry\n",
    "        if c[i] > 1:\n",
    "            c[i] -= 2\n",
    "            carry = 1\n",
    "        else:\n",
    "            carry = 0\n",
    "    c[n] = carry\n",
    "    return c"
   ]
  }
 ],
 "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
}