Pages

Friday, 17 March 2017

Chapter 2 Exercise 2.1, Introduction to Algorithms, 3rd Edition Thomas H. Cormen


2.1-1 Using Figure 2.2 as a model, illustrate the operation of INSERTION -SORT on the array A=⟨31,41,59,26,41,58⟩.

Solution:

data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAl0AAAJFCAYAAADnB0LdAABQDElEQVR4nO3de4xUxb73/yJ5kJsGgRFhBhUTEIRtgIS9AefIRRAwyAESZlAhAgoqCgECCoKRSwBRmS1kjwoHjihBxcEEOHJEBOSyw2UUA0RQ2GAgOiAgKERuHv/4/Z5PPc/qZ3XTc2G6u1b36vcr6czQ084sq7tXfVbVt6r/1//3vxkAAACk1P8K+gAAAACyAaELAADAAUIXAACAA4QuAAAABwhdAAAADhC6AAAAHCB0AQAAOEDoAgAAcIDQBQAA4AChCwAAwAFCFwAAgAOELgAAAAcIXQAAAA4QugAAABxIKHSNGzfOFBcXJ+tYAAAA0lZeXp4pKyur9n+fUOg6c+aMyc/PN+PHj0/k1wAAAKS10tJSU1RUlNDvSHh6MTc31xQUFCT6awAAAEKNmi4AAAAHCF0AAAAOELoAAAAcIHQBAAA4QOgCAABwgNAFAADgAKELAADAAWeha/v27ebs2bOu/lxG6tevn6lbt25KfjftXznaP1i0f7Bo/2DR/sFKZfv7OQtd3bt3d/WnMlZJSUnKNpql/StH+weL9g8W7R8s2j9YqWx/P6fTizNnzuTJLwftEn6u3tSZqEaNGin/G7R/+Wj/YNH+wXLR/h5qugAAABwgdAEAADhA6AIAAHCA0AUAAOAAoQsAAMABQhcAAIADhC4AAAAHCF0AAAAOELoAAAAcIHQBAAA4QOgCAABwgNAFAADgAKELAADAAUIXAACAA4QuAAAAB0Idun7//XezceNGc+bMGdOpUyfTrl07U7NmzXIfv23bNpOfn1/hY1A9OTk55plnnjFz584t9zGPPPKI2bp1q7l8+bLDIwu39evXm4sXL0b+ffr0aTNmzBhTt27dyH3bt2+3r/1GjRqZHj16mLZt2wZxqKFz5coV8+GHH5rDhw+b1q1bm8cffzyq3eM9fs2aNfY5atWqlX0/IDnOnz9viouLzYwZM8p9jN4rDz74YIXPEW5MVc4/e/futecgGTBggGnRooXz43QptKFLgevZZ5+1Jzs96atXr7adyVtvvXXdY9XhrFy50hw7dsx8+umnhK4UePvtt+0JLV7oUueik2HHjh3NbbfdRuhKkkOHDpn+/ftH3Td06NCoE964cePMtWvXzKJFi8zx48fNkCFD7Ptm7Nixrg83VHQu6d69u6lTp479Xl577TV7UdGsWbPrHq/z06xZs8yECRPMpEmTXB9u6KmjV9vHC10KBmp7df7nzp0jdCVJVc4/kydPtkFs/vz5tp+eNm2avb+kpMTpsboU2tClILV48WJzyy232H8rVC1btsx8++235r777os87uzZs6ZNmzbmrrvuipwckVyjRo0yHTp0iPuzvLw8s2/fPnPkyBEbupA8CxcuNJs2bbIXHp6GDRtGvldHr6t/r6PRRYlOfjpR6j3SrVu3IA47FCZOnGhH2dWmGmWZOnWqPf+oc1+6dGnUY9Xx6FxVWlrKKGMKqN11jomnrKzMtG/f3o4sKnQheSo7/6i9i4qKzE8//WQvRHSbN2+eadmypdm8ebPp1atXEIedcqEMXX/++aft5L3AJb1797Zvvtq1a0c9tnHjxvZrkyZNnB5jttBQsaZ1161bZ0aMGHHdz0+ePGm/EniTS53J/v377ZV9vJEVWbJkiX1+NK3o6dKli/26YMECQlc1qTN59NFHIwFK7avnQeef3bt3Rz1WwVcdj4IYgSv5dF45cOCAnbZ6//33r/u5995o3ry54yMLt6qcfzSyLpp+9x7j9c8afQ+rUIYuTQ/GPtHfffedrddSioY7unIZOXKkvcKHOxo5Ued/xx132GA1ZcoUO+Lop5Odpr/8FBD0+D179rg83FC5++67rxu11flI99WqVStynzqm5557zo72xj43SA5NV7333nvmlVdeCfpQskpVzj/9+vUz9erVMy+99JIdJNG55+OPP7YXHypFCatQhi4/jXppqlFvvDfffDPow8kqM2fOtLVC1Gi5p3oiXS0qPO3cudOMHj3arFq1yg7be7x6IxVw++ssvKn22PtRNf6RQ7+ff/7ZPg+ezz//3E7t9uzZ0xQWFppdu3bZ+zUiPGfOHCfHGmYvv/yyef7553kNB6Aq5x89L7oY1/R6586dbT3piRMnbFF9mJ+zUIcuFdNrCkWFkqIRF80zM9qVehpVVODVGw7uqR7Cq4lQQatOaFu2bLEnOa+YuG/fvram68svv4xaKaeCVq02DfOJzzVvddYLL7wQuU81XKKpSG8UQEFBi03UYWmKF9Wj9taMB1PkwajK+Ue8RSMKXnrda5q9vIuWsAh16FJNl57M8ePH25oidTBaQaTaCqSOOmy1ua7eETwN13/11VfmnnvusTVE3klPI5EabdFqRX1fv359s2PHDvP999/bK08kz/Tp083atWujgqxqXsQ/7aIRLj1OdV6zZ88m+FaDFi5olXqYV8BlkvLOP6IRdW2TorClc5BGxFTnW9HWHpku1KHLoyuewYMH285EaVsjMGwLkTqvvvqqvYovKCiI3KfVQZrO0n2//vqrfR7gjjrvQYMGmeXLl0fu0xWliozfffdd+1ULHoYPH24vTh544IEAjzZcdOGn1YuxdV4KubpAiaXFDBodUKExxfU3Tm2tfRnVwXu0Ovrq1av2vgYNGoR2ZVy6inf+kYcfftjW/apf0M+14EHhS/VeYV3NnhWhy6OlwZpjJnClllaCaurKT0uF9cb7+9//bgu4CV3uKfjGrtLSc+Lfk0tXmirs9k+Dofo0qq4i4XgbnargXu8DFdT7F/543yuU4cZp36cNGzZE3XfhwgVbW6qtPLSFAaHLvdjzj+q7NNKlgCW6CFTdl4rv9ZXQFQI//vij3XEbqRW7IZ6oPkUFwnpDIRiatho4cGC5P9cogEKCpmWY1kqcN9KiDSH9VG+kWqNhw4ZFtpHwjwofPXrUBt/yltqjYtrgOpZGG7VlhAIughF7/tHFt2jmwzvf6DWvemAF57AKZejS9KGWnmqI2SuaV1G9to3Q5o/xeB9VoCFo//5ecMMrnvQvqUf16OpRq0Y1VehdLWq6Sq/x8lbFKQhoeb0Clz8AoHp0Ff/6669Hpms93jSuQpduCmQrVqyIanOttlbtKdzxn/+RmKqefzQboi0jFMa80XatmFato2qCwyqUoUsrf3Ti0lWk9ghR+NI8vgJXbKDSjvQqHvb2JdJqR80zh3VoM92opkVvzscee8z+W52N5v2Zfqw+TaWoDdXZazsCTas3bdo0soLOT3vp6DWvzkbvgbCvHHJBbaorek1nxe5yrk7Gf+GnT8rQKIwWnXTt2tWei1TTEjs6htRQ0b22E9J0lqgeTCPyTD9WX1XPP+qbFbj00Ve6GNG0r6aF9f4I84VfKEOXgpUCl0a3tMNtRTVc2pFeRfa6IXXUsegWS/sUaaWWbkgOXTBcunTJXnHq9V/eNJWuPhUMdFXKdGLyeO1fVd7WEHq++MzL1FAbx9uCQxcZ2raAz7tMnqqef0Th9uDBg3baV4Ml2fA8hDJ0eZgmRDbTlWRFWBmXXip7voBMciOv52yqXwx16AIAAEgXhC4AAAAHCF0AAAAOELoAAAAcIHQBAAA4QOgCAABwgNAFAADgAKELAADAAUIXAACAA4QuAAAABwhdAAAADhC6AAAAHCB0AQAAOEDoAgAAcIDQBQAA4IDT0HXo0CGXfw5IK6WlpUEfQlaj/YNF+weL9k8PzkJXXl6eWb16tb0hvsaNG6fsd+fk5Jhz586l7PeHQSrbX6//oqKilP3+MKD9g0X7B4v2D1Yq29/PWegqKytz9acQxy+//BL0IWQ1Xv/Bov2DRfsHi/ZPH9R0AQAAOEDoAgAAcIDQBQAA4AChCwAAwAFCFwAAgAOELgAAAAcIXQAAAA4QugAAABxIOHTt2rXLFBYWJuNYAAAA0tKpU6cS/h0Jha6CgoKEDwAAACDd5ebmmkmTJiX0OxIOXQQvAACAylHTBQAA4AChCwAAwAFCFwAAgAOELgAAAAcIXQAAAA4QugAAABwgdAEAADhA6AIAAHCA0AUAAOAAoQsAAMABQhcAAIADhC4AAAAHCF0AAAAOELoAAAAcIHQBAAA4QOgCAABwgNAFAADgAKELAADAAUIXAACAA4QuAAAABwhdAAAADhC6AAAAHCB0AQAAOEDoAgAAcCCh0DVu3DhTXFycrGMBAABIW3l5eaasrKza/31CoevMmTMmPz/fjB8/PpFfAwAAkNZKS0tNUVFRQr8j4enF3NxcU1BQkOivAQAACDVqugAAABwgdAEAADhA6AIAAHCA0AUAAOAAoQsAAMABQhcAAIADhC4AAAAHnIWu7du3m7Nnz7r6cxmpX79+pm7duin53bR/5Wj/YNH+waL9g0X7ByuV7e/nLHR1797d1Z/KWCUlJSnbaJb2rxztHyzaP1i0f7Bo/2Clsv39nE4vuvqfykQ1atRI+d+YOXMmb75y0C7hx/mnfC7OP7R/+Wj/YLlofw81XQAAAA4QugAAABwgdAEAADhA6AIAAHCA0AUAAOAAoQsAAMABQhcAAIADhC4AAAAHCF0AAAAOELoAAAAcIHQBAAA4QOgCAABwgNAFAADgAKELAADAAUIXAACAA6EOXefPnzfvvfeeOXHihBkwYIDp1atXhY9fv369efDBB03dunUdHWH2+P333826devMsGHDyn3Mtm3bTH5+vqlZs6bDIwu3Rx55xNSvXz/y7yZNmpjFixeby5cvR+5Tm3fv3t1cvHjRbN261Rw6dCiIQw2dK1eumA8//NAcPnzYtG7d2jz++OMVnlv0+DVr1pjTp0+bVq1a2ecOyaG+oLi42MyYMaPcx3D+Tz61qc4rHr22x4wZE9XGe/fuNdu3b7ffq59u0aKF8+N0KbShS2+yzp07m06dOtknWm+4jh07mq+//vq6x+qFMWvWLPvknzt3jjddCsyfP98cOXIkbuhS2Fq5cqU5duyY+fTTTwldSdK2bVvbnn4ffPBBVOD6xz/+YWrXrm0mTJhgmjdvbj7++GMbyvR+QfXptawgW6dOHfu9vPbaazbUNmvW7LrHr1692p6D9DxMmjTJ9eGGnjp6tX280MX5PzV08da/f/+o+4YOHRrVvpMnT7b9s/oHhbNp06bZ+0tKSpweq0uhDV0fffSR2bNnj2nUqJH9t95UM2fOtIm6W7dukceVlZWZ9u3b2ytLvemQfOr4NdoYz9mzZ02bNm3MXXfdFemckBzqwDW6q5EWz4ULFyLfFxQUmLFjx5rbbrvNBjGdJKdOnWqfr3379pmdO3cGcdihMHHiRLNx40YbfHUBqHZdtmyZPQ8tXbo06rHqeBR0S0tL7eORXGp3vZ7j4fyfOgsXLjSbNm2yo7yehg0bRr5XexcVFZmffvrJXojoNm/ePNOyZUuzefPmSmemMlVoQ1ffvn0jgUueeuopG7pycnKiHudddeoqH8mnk5pGuO6//357pRmrcePG9qumvZA8eXl5tjPRa/7kyZNxH/P000/boKure48uVEQhIfYqFVWjzuTRRx+NBCidhzTCos5/9+7dUY/VCJc6HgUxAlfy6fV94MABO231/vvvX/dzzv+pofP+/v377es+3siuHD9+3H7VRaH3GI26y7Vr19wcaABCG7pi54X1AlCNBCc2d/7880+zfPlyO+KyYsWKoA8nq4wePdpOp+vkp45HU1vq9P10BRp7clMA0+O7dOni8nBD5e6777Zt76dORffVqlUrcp+em+eee84G5FGjRrk+zKyg6SrV9b7yyitBH0pW0citLj7uuOMO2xdPmTLlutd4v379TL169cxLL71kOnToYC9OVN6gPlq1dWEV2tDl59VLfP7550EfSlbRyW7gwIHmlltuCfpQss4///lPO4Kijl7T6RpJGTJkiHnooYcij1Hg0glRJz5/nZemguPdj6rxj7D7/fzzzzYMe3Q+Usjt2bOnKSwsNLt27bL3jxgxwsyZM8fJsYbZyy+/bJ5//nlqtAKgekadXzRyrjIFve5XrVplpw09el7UL2t6XfXXOj/p3KMSoDA/Z6EOXVoNNH78eFvfpc5DaXrDhg3XXYUi+b799ltbRHzfffcFfShZacuWLfYmunLUFaRqJKZPn27mzp1r71enr5quHj162GJiz6233mrrkAhcyeOtznrhhRci96mGSzQV6Y0CKCjo+VGHtWDBAvcHGhJqby3I8dfvwh2da7yaLNWKKlDpfKSQ5V/M4C0aUfDS614Xh+VdtIRFqEOX0rKeRN101a8nVqtY4q1gRPJoewhd1aieCMHTSU+reFU78dhjj0VCl06Aqn185513bE2dVg917drVLmzwRl2QHAq7a9eujbqCV8mD+KddNMKlx+l8NXv27FBf8aeKLhjeeuutUK+AyyS66Pvqq6/MPffcY2ed/KFLpQzaJkV9tPoLjYipBrWirT0yXahDl58Sta4s9aQjtZYsWWLuvffeqNVvp06dMlevXrXbQ9x8882MNjqmUSt15k8++WTkPk1tqdh+5MiRpl27drbgWMXGGv3S84Tk0MWeFibEvua1f1rswh5RPZ2CsgqNqUG9cWprXWT4z/VazKPzj+5r0KBBaFfGpStdPAwaNMjW+Po9/PDDdsWiVlLr51rwoPCleq+w9hFZE7qkd+/ecVfQIbl+++23yCo4j0546vi1/5NWCoX1DZXO1PF4K4Y83nPi0RWnCry13BuJ0+IFlTXE2+hUBfeaclF7+1d4ed/7N7VF1WnfJ5WR+GmrFL3WtZWHFpAQutzTthz+VaKq79JIlwKWaFpRMyQqvtfXsPYRWRW6dCWvwm6kljd95afOXPsWffLJJwEcEURXkRW1v642NdWlom7quRLnjbRoQ0g/b69AbRTsbSOhtvccPXrUrmgsb6k9Kha7IbBotFGjuAq4CIZG2v39r7d/4K+//hqZRtdrXp+QoeAcVqEMXSqgf+ONN8zgwYMjw/Oa59cGeV988UXc/8b7qAKNyMA9f/uz2jExWnmoBSTqZLwNH/U+UIF8eXV2OtFpmF+Biyn4xOkq/vXXXzfDhw+PGknUhZ+mchW6dFMg03Yq/tClqV1t8QF3OP8nj0avFi1aZF/73miVpsvVxv5Vuaon1QpphTGVNIj6btU66vwVVqEMXaLVWOpg9KT36dPHFgorcMUWpnqfz6jhTFE9gJZsM/zshnak37FjR2Q6UvVgmucP69CyCwpXqt3SiUydvzp6bVegZdyx1M7PPPOMXWmqWiL/RqmoHgVdXdFrtDB2l3N1MvrIE48+/kqjMAq7WsSg94LOW7GjY0gNzv/Jp6lc1W7pYkPboahutGnTppEVvB5dHCpwaR9HnaM07atpYb0//BchYRPK0KVgpRWKekOpM6loBZDmkVVkz+edpZZWpfj3KPJoR3qNSOqG5FBHr85dJzVduZe3I71Gv7RZp056TCcmj4LspUuXqvx4b2sIjRB4V/xILrVxvC04OP8nn/f61+tZO8xXNE2ucHvw4EE77attUrLheQhl6PKEfb8PoCKVfZalhvyRPmI/RQPIZDfyes6m+sVQhy4AAIB0QegCAABwgNAFAADgAKELAADAAUIXAACAA4QuAAAABwhdAAAADhC6AAAAHCB0AQAAOEDoAgAAcIDQBQAA4AChCwAAwAFCFwAAgAOELgAAAAcIXQAAAA44DV2lpaUu/xxiHDp0KOhDAALD+SdYtH+waP/04Cx05eXlmaKiIld/LiM1btw4Zb9b7b969Wp7Q3ypbP+cnBxz7ty5lP3+MEj165/zT8Vo/2DR/sFKZfv7OQtdZWVlrv4U4qD9g/XLL78EfQhZjdd/sGj/YNH+6YOaLgAAAAcIXQAAAA4QugAAABwgdAEAADhA6AIAAHCA0AUAAOAAoQsAAMABQhcAAIADCYeuXbt2mcLCwmQcCwAAQFo6depUwr8jodBVUFCQ8AEAAACku9zcXDNp0qSEfkfCoYvgBQAAUDlqugAAABwgdCGUrly5Yq5evWpv165dM3/88Yf9/sKFC/bf+v5//ud/on5+6dKlyH//559/Rr7Xzz16nHdf7dq1I/fXqlUr8r13f82aNSP33XzzzfZr/fr1TZ06dcxNN91kv+qxely9evXsv72f61a3bt0ktwoAIEiELqSt8+fPm9OnT5tz586Zs2fPmosXL9rbb7/9Zs6cOWO///XXX20AUpjybpcvX67y31DYufXWW23I8fgDVLz7/WErXiAThbl493nhr6rH6D8+fVUoa9iwof2q2y233GIaNWpkGjRoYG6//Xb7mCZNmphmzZpVtQkAAI4QuuDcsWPHzMmTJ01ZWZkNVT///LP96t0UqBS0YnkBpGnTppHwcffdd9vvFYQUPLww4h9FysnJsYFJ/06nUaTyRuMUyH7//Xf7vYKlfqYAqvv0GIXO48eP2595QbO89lJbKYypAFRf1RZ5eXk2mKntdEuHtgCAbEDoQtIpVB0+fNicOHHC3n788UcbEvR9bDhQAFAw8EJA586d7fcKCApR3s80mhM2CjvJDDwKZgpkCrQKaAqw+l5triC7b98++1Uh1z/SpnDWvHlz2/5q69atW5s777wzEsrC2PYAEARCF6pFHbw6cYWrI0eOmO+//95+r07eo1EVrzPv1q2bGT58uA1TdOapofbUrUWLFpU+VqNsCsIKYF44ViDTfRs2bLjueWzVqpW59957I4GsQ4cOVfo7AID/h9CFSh06dMjs3r3bHDhwwIYrffVGrPwd8gMPPGDatGljA5W+Mm2VvvTctG3b1t7KoxFLhTF/sPYHMo2Q6Xlv3769DWPt2rUz999/P887AJSD0IUoqrPavn272bNnjx3J2r9/v52K8newAwcOtJ2sRjsYrQovjWTp1qtXr6j7NUr23Xff2deGApm+rl27NhLE9d906tTJThXr1rFjxyAOHwDSDqEry2k0Y9u2bZGbN4qhjlId5ogRI0yXLl0qHBFBdtFIll4fsWFKgV0BTIFdo6GzZs2yQUyBXa8ljYT269ePEAYgaxG6stDmzZvNunXrzOeff25Dl9cpjh492nTv3t389a9/ZYoIN0zbVOj2yCOPRO7T1PTWrVttEFu6dKmZOXOmnZLu0aOH6d27txk0aBCjpQCyBqErS6xfv96sWrXKbNy40Y4+aLRhyJAhNmTFTh8ByeLVjY0dO9b+WyFMYV+jqhMmTLBBv2fPnnbK+rHHHiOAAQg1QleIqYNbvny5ef/9923Qys/PN1OnTrVhi80zEQQvhOlDY1Ub9t///d9m9erV9nU5btw4+1muTz/9NBcCAEKJ0BVC6sQWLVpkdu7caYuaNcrw1FNPEbSQVjSFrZClmwLYmjVrzDvvvGMeeughu3+bRsH02mX0C0BYELpCQp2WOqw333zTFsOrI9u0aRMjBsgICmBDhw61N9UZLl682BQXF5s33njDjBw50kyZMoWLBgAZj9CV4RS21DGpg9LHxjz77LP2xsaVyFR67S5YsMDMnj3bvPvuu2b+/Pn29a1A9tJLL7GSFkDGInRlKG9kSx2SwpaKkidOnMhUDEJDo1+aXtTtgw8+MK+++qr5y1/+YkaNGmVmzJjByBeAjEPoykDLli2zS+/1QceELWQDb+pR4Uuv/Y8++siO6Grki9c+gExB6Mog2il+8uTJZu/evVztIyt54UvTjdp8VStz9T7wtqQAgHRG6MoA2ulbS+p1la89jQ4ePEhdC7KaQtaTTz5p5s2bZ7eaUPjSdDu73QNIZ4SuNKepRE2h1KpVy5SUlNhViQD+T83XnDlz7Kaq48ePt5+koBFg1Tky5QggHRG60pSWzatmZcuWLXYjSa3k4qN5gOtp1FcfbaWRYG0toQ/ffvvtt7lAAZB2CF1pqKioyNap3Hvvvebrr79mygSoAtV66bMcNepVWFho/61Nghn1ApAuCF2Oqf5k8ODBplu3btf9TLVbI0aMsKNbWqGl4AWg6jQarA/WHjBggB0pbteund1o1f8h3AAQFEKXQ6rP0qorfR7i/v37ozYw1dTIM888Y5o3b87oFpAghawDBw7YUa/+/fvbWi+NejFFDyBICYUujdooRODGXL582bRs2TLuz/Qh1SoIBpA8uuDRDQASoc+F1axUdSUUus6cOWPy8/Pt1SQqtmTJEjtt6KcCYG1wqpumQjp16hTQ0QHhpnOVRrq0QEXbTXTt2jXoQwKQYUpLS23NdSISnl7Mzc1llVAltJlpbOASjWppinHPnj1scgqkmMKWNhfWSfO3334z//Ef/8F0IwCnqOlyYMyYMeX+TFfe2mleK60ApJY+SLt79+5m5MiR5m9/+5vdXoIPhwfgCqErxVRHopGuigwbNsyOdMVb0QgguVRkv2/fPru9RJcuXeznOPbq1SvowwKQBQhdKXT+/Hn7gdRVoW0k1BEwzQiknt5nGmF++umnzUMPPWRHwLQJMQCkEqErhfR5iVqpWFUXL14kdAGOqJ5r5cqVpkOHDrbWSxc9+jcApAqhK0U0pViVJepahPDEE0+weSMQEI1waRPVgQMHmn/7t38z69atYxd7AClB6EoR7SxfHm18qo1QH3/8cVZPAWlANV1aDt6nTx/TuXNns2HDBgrsASQdoSsFtGGstoPw04ZqCmK6cTIH0o/2zdP2LV6BvYIXnwwBIJmchS4VrZ49e9bVnwuM6rJUy+XR5rEq1G3Tpo39t+pGdIunX79+KRv5ypb2TwTtH6x0aX8tflm4cKH9ZIh//OMf5vbbb0/JMaWbdGn/bEX7ByuV7e/nLHRpb5xstHPnTnuripKSkpRtNJut7X8jaP9gpWP766POskU6tn82of2Dlcr293M6vThz5kye/HK4aBfav3y0f7Bol/Bz1alloho1aqT8b9D+5XPR/h5qugAAABwgdAEAADhA6AIAAHCA0AUAAOAAoQsAAMABQhcAAIADhC4AAAAHCF0AAAAOELoAAAAcIHQBAAA4QOgCAABwgNAFAADgAKELAADAAUIXAACAA4QuAAAAB0Idun7//XezceNGc+bMGdOpUyfTrl07U7NmzXIfv23bNpOfn1/hY1A9ei7WrVtnhg0bVu5jaP/kU5v++eefkX/rvTBkyJCoNv7222/NgQMHTO3ate17pGXLlkEcaujUq1fPPPbYY6Z169bm8OHD5qOPPjKXL1+u8PEDBw40TZo0MUeOHDHr1693eLThdv78eVNcXGxmzJhR7mPU3g8++KCpW7euwyMLN7XpxYsXI/8+ffq0GTNmTFQb792712zfvt1+P2DAANOiRQvnx+lSaEOXOvlnn33WnvD0pK9evdq0bdvWvPXWW9c9Vh3TypUrzbFjx8ynn35Kp58C8+fPtx1JvNBF+6dGWVmZmTlzZtR9PXv2jGpfvR+uXr1qxo8fbwPZlClTzKBBg8zgwYMdH224qOPYunWruXbtWqQTUdt2797dnDx58rrHFxQU2ECwcOFCU1RU5PpwQ08dvZ6PeKFLwWDWrFm28z937hyhK0kOHTpk+vfvH3Xf0KFDo9p38uTJNoipf1A/PW3aNHt/SUmJ02N1KbShSx354sWLzS233GL/rU592bJl9qr+vvvuizzu7Nmzpk2bNuauu+6ynX660zHqpJ2Xl2dyc3Mz4gShIHXixIm4P6P9U2fVqlVmwYIF5s4774zc16BBg8j3eo/oYsQLus2aNTMTJ060J8JWrVpFvU/SRaa0/5tvvmn69u1rO56cnBzz6quvmlGjRtkQPHr06KjH6jlSKPjb3/5mH4/k0nl/3759cX+mC5P27dvb17tCF5JHFxCbNm2yAx+ehg0bRr5Xe+sC46effrLnHt3mzZtnR9o3b95sevXqFcRhp1woQ5emUzp06BAJXNK7d2/75tMUil/jxo3tVw3pZ4I//vjDflXHo5umJHTsesGmI53UNMJ1//332yvNWLR/aijMHj9+3DzxxBORNo6lK3yFF//7RJ2PKLClY+jKhPbv2LGjbT8vQGn0RGFLoatLly5Rj9UI16RJk2wQI3Aln0K6ps41bfX+++9f93PvddO8eXPHRxZuOu/v37/fjiyW997U+Uk09e49xuufNUIcVqEMXd5Vu993331n64XCVq+iGpEffvjB3tKtA1L4Xb58uZkwYYJZsWJF0IeTEuna/qqfUydeWFhog9Wjjz5qR178U4safaxVq1bUf6cApsfrhJkJ0rH91a6xoyYKiLrPX9Oldn7nnXdsB6ULQiSfpqvee+8988orrwR9KFlFs0x6vd9xxx12el1T67ro8OvXr599z7700kt2kKRRo0bm448/tmVAqq0Lq1CGLj91/JpG0RtPQ/5h5u+ANKWhDkgv5KCozVUY7B9JCbN0an+dxEThSeFLw/gqVtU0lxe8FLgUBlT/6H+OmjZtGvf+dJcu7a+RrXh0POqMPA8//LA9Pk2lqIbFGwX7z//8z+tq8XDjXn75ZfP888+n7RR0mKl2UaNVe/bsMTt37rQjuRr91Wvdo+dFtXQqZ+jcubNd4KMLFp2nwvychTp0qdNYsmRJZBXQyJEj7Txzuo521alTx66yqYiKnqtCJ37v5K8OSFMeLql2Tv8/6ThFVZ4wtb/+nvc3jx49ajtxXXnqStJbzKBgpnD1zTff2JOk58KFC/YK1HXgSnX7B1mzo1F20fnHoxXVoufEG+nS86QpmZtvvtl2Rqgeddy6uOjWrVvQh5KVVI/l1WTpok+BasuWLTZk+RczaGpd9FqfO3euWbp0aaADBS6EOnSp09CTqZVZmm7RkuHXXnstbYfyNZ998ODBpP9edT4vvviinWJ1QWFXVzWZdrUelvaPpYsMjTpq+wKN+nqhS/VeKjDW+8Ib1VIwUR2M65AoqW5/TbUGRR2KVoX6pxdVwC3+85HeM1o5qs5InVNFW0wgPgV3rcoN8wq4TKLpwq+++srcc889duGOP3TpXLNmzRobtrxFJroQrGhrj0wX6tDl0RWPTmTff/+9TduackzHbQl+++03W1hbEV01lDd9EY83zaKvrkKQRhfvvfdeO6zsOXXqlB2lUKevq/ggOvXKhKX949HrvUePHvak51GBvaa7tJfdjz/+aFc5quBYI8NeIHAp1e0fFK1O1C12pE0jivFG9nbv3m07KhV3U1x/46ZOnWpHEf2vdS3m0flH92kFb1hXxqUrTRfqokM1vn6aYteKRb3v9XOdf3SeVL1XOvYRyZAVocujjkRzzOkYuJIp6HoidZ5qZz+d8HTVrlEVdSZhfUNJ0O1fnttvv/26jQc1uuXfk0vhQMevk1+mSqf2V/GwRhPjbXSq+hV1/iqo9+/d5W2volCGG6d9nzZs2BB1n9pS5x9tiaItDAhd7mlltH+VqOq7NNKlgCV6v2qGRMX3+hrWPiKrQpeu5nW1H0bpsnJLNJUSS8PHGlH55JNPAjii1Eun9i+PgrBXRxSPRiEVDqZPn55RBfSSju3vjdp98MEHUfervkujwJryVSjTdir+URmNEmtFY7xNVFE57TsXS2Um2jJC7YpgrF271i6s8mirCPn1118jhfN6/+r9oeAcVqEMXZo+VHGqOhivaF41K6qp0c638XgfVaARmUzpcLyORhvOZfpqD9o/edSxqIZRe9N5r38V06ttR4wYEfe/0cIHBWMFroceesjh0VZfura/aOd/1ZGpox87dmzkfn3MkvaNUujSTYFMtXX+0KXib02RwR3/+QeJ0ejVokWLzPDhwyOjVZomVxvPmTMn8jhtYaP3sMKY9x65cuWKXXGtOuywCmXo0lJVXbWrQFXTKQpfmsdX4Irt0LWJ5I4dOyLTYapH0jxzug5tqpPRUv903o37RtD+yaeO47PPPrMdudpRw/paGaiVc/6pdV2c6GpTI5D6b/yf4JCuMqH91eb/9V//ZY8v9nWsTkX7Enm0qEFTuir61vuga9eudoVX7OgYUkM1dRpx1HSWKOzqwoTpx+rTVK5qt1RKoosPlfVoGxrv8xU96psVuLSPoy5ENO2raWH105XVdmayUIYudRwKXBrd0oqoimq4VEysmpZM+aw5zXunQ63KjdKqlNiPPxHaP/k0uqWTmT5L8aabbip3R3r9XHRVmSl1jpnQ/iqY1xV8VXlbQ6gTUkeF5PMWM8TSa0krRb2tC5A4XWhcunTJjnip/61oyl/hViuWNTqvwZJseB5CGbo86X7VDqRKvE9liOV93hnSQyZ89ihQVbGLdiqSTeehUIcuAACAdEHoAgAAcIDQBQAA4AChCwAAwAFCFwAAgAOELgAAAAcIXQAAAA4QugAAABwgdAEAADhA6AIAAHCA0AUAAOAAoQsAAMABQhcAAIADhC4AAAAHCF0AAAAOOA1dhw4dcvnnEIP2Dxbtj2xWWloa9CFkNdo/PTgLXXl5eWb16tX2hvgaN26cst9N+1eO9g9WKts/JyfHnDt3LmW/PwxS/fovKipK2e8PA9o/WKlsfz9noausrMzVn0IctH+waP9g/fLLL0EfQlbj9R8s2j99UNMFAADgAKELAADAAUIXAACAA4QuAAAABwhdAAAADhC6AAAAHCB0AQAAOEDoAgAAcCDh0LVr1y5TWFiYjGMBAABIS6dOnUr4dyQUugoKChI+AAAAgHSXm5trJk2alNDvSDh0EbwAAAAqR00XAACAA4QuAAAABwhdAAAADhC6AAAAHCB0AQAAOEDoAgAAcIDQBQAA4AChCwAAwAFCFwAAgAOELgAAAAcIXQAAAA4QugAAABwgdAEAADhA6AIAAHCA0AUAAOAAoQsAAMABQhcAAIADhC4AAAAHCF0AAAAOELoAAAAcIHQBAAA4QOgCAABwgNAFAADgAKELAADAgYRC17hx40xxcXGyjgUAACBt5eXlmbKysmr/9wmFrjNnzpj8/Hwzfvz4RH4NAABAWistLTVFRUUJ/Y6Epxdzc3NNQUFBor8GAAAg1KjpAgAAcIDQBQAA4AChCwAAwAFCFwAAgAOELgAAAAcIXQAAAA4QugAAABxwFrq2b99uzp496+rPZaR+/fqZunXrpuR30/6Vo/2DRfsHi/YPFu0frFS2v5+z0NW9e3dXfypjlZSUpGyjWdq/crR/sGj/YNH+waL9g5XK9vdzOr3o6n8qE9WoUSPlf4P2L5+L9p85cyYnv3K4aBfav3w32i4ffPCBWbhwoenTp4+ZM2dOag4KScX5v3wuzv8earoAAJU6f/68KS4utrdz587Z++rXrx/wUQGZhdAFACjXoUOH7KjWsmXLrvvZ6dOnAzgiIHMRugAA11m/fr0NW1u2bCn3MRcuXHB4REDmI3QBAKwrV66Yd9991yxatMgcO3as0scrdGllXE5Ojp1qbNiwoZMVYECmInQBAMyKFSvMyJEjzeXLl6v83+ixsUX49erVM82bNzdt2rQxd955p2ndunWSjxTIXIQuAICdTqyOgwcP2q8qrv/9999tndeJEyfMv/71LzsKtnjx4mQeJpDRCF0AALNgwQL7dc2aNWbnzp039N+2bdu2wp+7XJIPpDNCFwDATgVqH6dJkybZ2q5du3aZzz//3N60grE83vYRACpH6AIARFExfK9evexNI2Dao+vLL780X3zxhdmwYYM5efJk5LF8vAxQdYQuAECFGjVqZEfBvB3NtbJx27Zt9tahQ4eAjw7IHIQuAMANadGihb2NGjUq6EMBMgqhCwAAwAFCFwAAgAOELgAAAAcIXQAAAA6EOnRpr5kPP/zQHD582H4UxeOPP17h54Lp8doYUDsqt2rVyjzyyCMOjzZ8tMz8vffes7tTDxgwwC4/r4h2xH7wwQf57LYU0E7h69atM8OGDSv3MVqJlp+fb2rWrOnwyMJNbfrnn39G/n3mzBkzZMiQqDb+9ttvzYEDB0zt2rVNu3btTMuWLYM41FDTZ0M+88wzZu7cueU+Ruf7rVu33tDHIKFiOqdfvHgx8m/1rWPGjIk6x+/du9d+coGon9ACjTALbejSkmZ9JlidOnUiH9z62muv2TdVs2bNrnv86tWrzaxZs8yECRPs5oBIjAJX586dTadOnewbrbi42HTs2NF8/fXX1z1Wb0y1vd582miR0JV88+fPN0eOHIkbuhQMVq5cad8nn376KaErScrKyszMmTOj7uvZs2dU+7711lvm6tWrZvz48TaQTZkyxQwaNMgMHjzY8dGG29tvv20v6OKFLoWtGTNm2PPTbbfdRuhKEm2o279//6j7hg4dGnV+nzx5su0fdH5SOJs2bZq9v6SkxOmxuhTa0DVx4kSzceNG+/EUCgBTp041y5Yts5370qVLox6rJ16fD1ZaWlrpx1mgaj766COzZ88eu7+PqN3VAemKplu3bpHHqWNq3769HVlU6ELyKUhptDEebWypDya+6667IhcnSI5Vq1bZjUW107unQYMGke8VdnWx5wVdXQzqvKXzkd4P9913XxCHXSG9RrQxal5ensnNzc2ICyRta1HeXmL6/9i3b5+9IFHoQvIsXLjQbNq0KeoDzxs2bBj5Xuf7oqIi89NPP9nXvm7z5s2zI72bN2+udGYkU4UydOnJfPTRRyMBSh2/rmQUunbv3h31WJ309MQriBG4kqdv376RwCVPPfWUDV0a5vfzRh2bN2/u8vCyhkKtOpT777/fjvLGaty4sf3apEkT14cWagqzx48fN0888USkjWNphFed/i233BK5T2FLFNjSMXT98ccf9quCl2716tWzr514swfpQFNVmrLV1PqIESOu+7m3sz4XHMml887+/fttv1vea0PvD1H5j/cYTbHLtWvX3BxoAEIZuu6+++7rrlr0pOq+WrVqRe7TC+O5556zJz42+Uuu2Hl5vQE1jE+wdUe1RMuXL7dT5itWrAj6cLKKOnlNrxQWFtrziy4CdSHin1rU6KP/fCQKYHq83i+ZQFNxP/zwg72lYwDTyMnIkSPtSDvc0cyRBj/uuOMO2xdo2jy2j+3Xr599zbz00kt2JFIX6R9//LHtIzQVHFahDF3+ERa/n3/+2YwePTryb32Qq2qIVGehk6M+4FV0RTRnzhwnx5oNvHo5tTfc0SKGgQMHRo2kwA1vOkvhSeFLo+maWn/11VcjwUuBSyMtWuTgf46aNm0a9/505w9gGtFWACvvXOyCRtYXLVpEjVYAVE+t0SqVmOzcudP2uxq91bShR1PT6hc0na76Xy0w0YWI3ieZMG1dXaEMXfF4qyNeeOGFyH2q4RJdhXop/OWXX7bFlnrBqB4D1afVoCoQVn2XTnzqiPRhudROpJ5WxGkRSTpOUWUDvca91/nRo0dtANCVv67kvcUMej8oXH3zzTe2k/JcuHDBjgC4Dlx6vaj+tSIq+q8KXczqJgpgaguXNZtahauRXnX4cM/7sHTRRYcC1ZYtW2zI0pSjx1u0puClfldlPkEGdReyJnRNnz7drF27NipBe0P4/mFPjXDpcboynT17dqgTd6qp7fQm0k3tqTeWlgvHW8GI5NEIia4qY1fOIRgqDNao42OPPWaL573QpXovFXFrZa83qqVgovqiIC5MVE9z8ODBpP9eha8XX3zRzia4oJCniz1Xfw8V03ThV199Ze655x476+EPXXqta5sm9RE6X2lETBci/seETVaELnX2Wr0YeyKrX7/+dYXd0qVLF5vOVehHDVJy6IpGI4t60yG1lixZYu69996oq/xTp07ZUQp1+jfffDOjjY5pSrFHjx5Rr38V2Kv2Rausf/zxR7vKUfsUqcBeK3pd++2330xBQUGFj9F50RvBqgpvmjHeeTZVNIWrc43//0ULFDSSp/t+/fVXO+oCd3QBrq1QVGPq9/DDD9u6Oz0v+rle/wpfqvcK6zkq9KFLKxY1jB9vo1MV3OvNp4J6f/Gn971CGZKnd+/ecVfQIbnUeaqWwk+BS1O8GlXRStGwntDS2e23337dAhONbvn35FJJgwKKOp9MFXQ9l/62Fi34aasCdfx///vf7Wo5Qpd7Cr7+Veqq79JIlwKW6PWiEXoV3+trWM9RoQ5d3lWlNmTz8/aK0jC/t42E/6pINRhaQZROq3DCQLtuq7AbqRVvA0gN32tE5ZNPPgngiCAKwtosuDwahdQol0ohMqmAXtJp5WLshpyiMKsFUurQEQyV7fjP/wq/opFHr4xHrx/V42nD1LAKbehSin799dfN8OHD7dW9Rx2/9m1R6NJNgUzL6f2hSyc/7V6P6lEB/RtvvGGv4L3pWRXoqn7liy++iPvfeB8VUdVCXSSXv/0zrcNPNxo515YRGtn1PtJHF3Jq23h7RYkWPigYK3A99NBDDo+2+ryg5Y0iZTJvVC52Cw/cOI1eadWo+l5vtErT0jrH+HcF0GikXkMKY2PHjrX3qe9QrbVq8sIqlKFLxahK1JpOiV0xoydZHzng0cefqOZLRZddu3Y1O3bssHPKsaNjuDG6Ylc76k3Xp08fe3JW4Io9OXufz6jhZFHtnTqmsO5GnG60iade8950pOrBVGcR1qF9FxSuPvvsMzvSrnb06om0Q7d/ny6trtPVvkYg9d+ovivdA6/exwommbIbfWU0FapwoEUOoott1R0x/Vh9Wn2rNtRgh7ZjUn2itkHxdhDwaKpdgUv7CGowRDvXa3W7+ufKagszWShDl050ly5dqvLjva0hlNC9xI3q08lYKxQVqNTZVHRy1hWmiuz5vMvU0qog/x51HhVza0SSz/pLHo1uqTPRZynedNNN5e5Ir5+Lruoz5fMu9X7NxCX9urDWLZYWBWhltW5IDq//VX+qFbEVTTnr4lorZjU6rG2asqEfCGXoqq6wf7q5a5l4cgaSwfssxYp4nzcHhNGN9KfZ9D4gdAEAADhA6AIAAHCA0AUAAOAAoQsAAMABQhcAAIADhC4AAAAHCF0AAAAOELoAAAAcIHQBAAA4QOgCAABwgNAFAADgAKELAADAAUIXAACAA4QuAAAABwhdAAAADjgNXaWlpS7/HGLQ/sE6dOhQ0IeQ1Wh/ZDPO/+nBWejKy8szRUVFrv5cRmrcuHHKfjftX7lUt//q1avtDfHR/sFKZfvn5OSYc+fOpez3hwHn/2Clsv39nIWusrIyV38KcdD+waL9g0X7B+uXX34J+hCyGq//9EFNFwAAgAOELgAAAAcIXQAAAA4QugAAABwgdAEAADhA6AIAAHCA0AUAAOAAoQsAAMCBhEPXrl27TGFhYTKOBQAAIC2dOnUq4d+RUOgqKChI+AAAAADSXW5urpk0aVJCvyPh0EXwAgAAqBw1XQAAAA4QugAAABwgdAEAADhA6AIAAHCA0AUAAOAAoQsAAMABQhcAAIADhC4AAAAHCF0AAAAOELoAAAAcIHQBAAA4QOgCAABwgNAFAADgAKELAADAAUIXAACAA4QuAAAABwhdAAAADhC6AAAAHCB0AQAAOEDoAgAAcIDQBQAA4AChCwAAwAFCFwAAgAOELgAAAAcSCl3jxo0zxcXFyToWAACAtJWXl2fKysqq/d8nFLrOnDlj8vPzzfjx4xP5NQAAAGmttLTUFBUVJfQ7Ep5ezM3NNQUFBYn+GgAAgFCjpgsAAMABQhcAAIADhC4AAAAHCF0AAAAOELoAAAAcIHQBAAA4QOgCAABwwFno2r59uzl79qyrP5eR+vXrZ+rWrZuS3037V472DxbtHyzaP1i0f7BS2f5+zkJX9+7dXf2pjFVSUpKyjWZp/8rR/sGi/YNF+weL9g9WKtvfz+n0oqv/qUxUo0aNlP8N2r98tH+wXLT/zJkz6XzK4aJdaP/y3Wi7fPDBB2bhwoWmT58+Zs6cOak5KKQENV0AAKS58+fPm+LiYns7d+6cva9+/foBHxVuFKELAIA0dejQITuqtWzZsut+dvr06QCOCIkgdAEAkGbWr19vw9aWLVvKfcyFCxccHhGSgdAFAEAauHLlinn33XfNokWLzLFjxyp9vEKXVibm5OTYqcaGDRs6WYGH6iN0AQAQsBUrVpiRI0eay5cvV/m/0WNji/Dr1atnmjdvbtq0aWPuvPNO07p16yQfKRJB6AIAIGCaTqyOgwcP2q8qrv/9999tndeJEyfMv/71LzsKtnjx4mQeJhJE6AIAIGALFiywX9esWWN27tx5Q/9t27ZtK/y5iy1ZUDWELgAAAqapQO3jN2nSJFvbtWvXLvP555/bm1YwlsfbPgKZgdAFAEAaUTF8r1697E0jYNqj68svvzRffPGF2bBhgzl58mTksXy8T2YhdAEAkMYaNWpkR8G8T7TQysZt27bZW4cOHQI+OtwIQhcAABmkRYsW9jZq1KigDwU3iNAFAADgAKELAADAAUIXAACAA4QuAAAAB0IdurTXyYcffmgOHz5sPwrh8ccfr/BzqfR4bUynHX1btWplHnnkEYdHGz5a5vzee+/Z3ZEHDBhglz9XRDsyP/jgg3x2WArouSguLjYzZswo9zG0f+pop/B169aZYcOGlfsYrUTLz883NWvWdHhk4aY2/fPPPyP/PnPmjBkyZEhUG3/77bfmwIEDpnbt2qZdu3amZcuWQRxqKKkP1WdCepo0aWJ3yPd/1FHHjh1Nt27d7Pd6j1TlMyczWWhDl544fSZVnTp1Ik/ia6+9ZrZu3WqaNWt23eNXr15tZs2aZSZMmGA3p0Ni1Ml37tzZdOrUyYZYdfh6c3399dfXPVadvdp+7969dqM/Ov3kGzNmjH3txwtdtH/qzZ8/3xw5ciRu6FIwWLlypT1Pffrpp4SuJCkrKzMzZ86Muq9nz55R7fvWW2+Zq1evmvHjx9tANmXKFDNo0CAzePBgx0cbPtolX69nvw8++CAqcGkPMgUxtfutt95q5s2bZ+8vLCx0eqwuhTZ0TZw40WzcuNE+8QoAU6dONcuWLbOdy9KlS6MeO3nyZJu+S0tLK/04BVTNRx99ZPbs2WP3lxG1u06A+iww76pGdGJs3769HVlUp4/k0+t+3759cX9G+6eeOh6N9sajjS31wcR33XVX6K/wXVu1apXt1LXTu6dBgwaR7xV2dbHtBV1djKvfUH+g98N9990XxGFXSK8RbYyal5dncnNz0/oCSQMYmt3QTJPnwoULke91Ea4BDrW7/p90mzZtmjl69KgNx1u2bAnisFMulKFLncejjz4aCVDq+HWFr85n9+7dUY/Vm66oqMgGMQJX8vTt2zcSuOSpp56yoSsnJyfqcd6oY/PmzV0eXtbQSVpTJ5reff/996/7Oe2fWgq1GuG6//777UhjrMaNG9uvutpH8ijMHj9+3DzxxBORNo6lEV6Fl1tuuSVyn8KWKLClY+j6448/7FcvpNSrV8++duLN3gRJ7aqLOZ3z/bvn+9199932q0p/vMdo1FE0QxVWoQxdejKVov30otR9tWrVitynE+Jzzz1nXyBsMpdc2rjPb//+/XZ+n2Drlq4cVVf3yiuvBH0oWUe1RMuXL7dX/CtWrAj6cLKKaoP0eYWaptL5XRfhuhD0Ty1q9NHfH4gCmB6v81Um0FTdDz/8YG/pFMBGjx5t+1v1sbrwU2mPBj38PvvsM1tHran3hx9+2JY26HnS8xbvAiUsQhm6/CMsfj///LN9MXj0QaJ6ojWUqTenPmBURowYYebMmePkWLOBVy+n9oY7L7/8snn++efTegoizBR2Bw4cGDWSAje8j8ZReFInrtkMlTa8+uqrkeClwKURFi1y8D9HTZs2jXt/uvMHMM0oKICV1xem2j//+U/b5l6RvGaStIDhoYceijpeXQxqClgzUKr30sW6arH9dV9hE8rQFY/ecPLCCy9E7lMNlyhdeyNd6qjmzp1rrl27Zl8MqD5dxahAVfVdehPpRKgPa40dhUTy6fWuzsVfPwd3tCJOUyTpOEWVDXSO8c4zqhHSNJfKTj7++OPIYgadjxSuvvnmG9vRe1R3pFEj14FLrxfVH1fEm36rjAYTdBMFMLWFy5pN1WN5NVma3VC7q75r+vTptn/1KJiJ+lqVAGlQxDvusMqa0KUne+3atVFX/d4Qsn9qUSNcepxeDLNnz2aUIAFqO13h6Kb2VIGqVtHFW8GI5NGJW6uySkpKgj6UrKQREtUExa6cQzC0BYRGHR977DFbPO+FLtV7aYGJVlZ7o1oKJpoOC+LCUFtWHDx4MOm/VyHmxRdfDGxFoEYatYpdBfV6DvyhSyNb/fv3t2FLoUt9xe233x71mLDJitClzl6rF2PfSNo/JLawW7p06WJfKCrEpAYpObRKRSOLmmpEaum1rpOcv61VzK2rZN2nFVyV7ZmG6luyZIm59957zc6dOyP3nTp1yra/Ov2bb76Z0V7HNOrbo0ePqPeECuy1al2r3H/88Ue7ylELTlRgryJw13777TdTUFBQ4WPUL93ISJA3zRivn3NJMx0azHjyySej7tfMh+pO9bzo55988okd+NBzEtbV1KEPXSre0zByvI1OVXCvIVAV+/mLD73v/Zu6IXG9e/cOdYFkutC+aDqZ+WnKRCc+LYnXaiFCV+qo89R2KX4KXGp/japopSihyz2NoMQu8NHoln9PLk1zKaAofGWqoOu5yqMLPw1keFRLredDBfWiMDl06FDbH6vkh9CVgbyrGj2Rft5eURpm9raR8F9hqAZAK1jSYRVImGjrAhUWI7ViNyQUjfZqywid0JBa8aZGNG2iq3ddySMYCsIaAS6PRiE1yqVSlEwqoJd0WrlYHgVZ/+tfo8GiTVG9wnnV2Kl/DvMWKqENXZs3bzavv/66GT58uL269Kjj10c9KHTppkCm5dz+0KU3n5a4onpUQP/GG2/YK0hvelZ1Rqqf+OKLL+L+NxcvXrRfq1ooiuSi/YPlb/9M6/DTjS4stGWERta9j/TRhbTaVivT49HCBwVjBS7/Crt05gWthg0bplXtsUavtIBKF3neaJX6AYUrf52jVrOrr9AnAHh9tP6f/vrXv9qa1LAKZejSE60RFaXn2CFKPanaF8Sjj9/QKICKDLt27Wp27NhhXxixo2O4MbpiVDtqGqVPnz725KDAFXty8D6fUYXHonoknRiZ/nKD9g+WNvHUOcebjlQ9mPYsYvqx+hSuNGWlmQ61ozY81crAhQsXRu3TpX3UVNytEUj9N6rvSvfAq/OotrpI593oFa5UuzV27Fg7+KGBDm3X5F8hKlqw8O///u9m0aJFdiBEz4X2UtNHAoW59jeUoUtvtEuXLlX58d7WEHoR6IWCxOhkoBWK6tB1sqvo5KC6AxXZ83mXqaXXeLwtUGh/N7Q6y79HoEfF3BoR5rP+kkejWyrK1mcp3nTTTeXuSK+fi0ZlMuXzLvV+TbdarVga6NDghka8FGbL25FeVFP9l7/8xZbzqK/wtpAIs1CGruqKLbJEYtL95AAgnLzPUqyIfp7ONVCZ7kY+S7SiYBY2hC4AAAAHCF0AAAAOELoAAAAcIHQBAAA4QOgCAABwgNAFAADgAKELAADAAUIXAACAA4QuAAAABwhdAAAADhC6AAAAHCB0AQAAOEDoAgAAcIDQBQAA4AChCwAAwAGnoau0tNTln0MM2j9YtH+wDh06FPQhZDXaH3AYuvLy8kxRUZGrP5eRGjdunLLfTftXjvYPVqrbf/Xq1faG+Gj/YKWy/XNycsy5c+dS9vvDIJXt7+csdJWVlbn6U4iD9g8W7R8s2j9YtH+wfvnll6APAf8XNV0AAAAOELoAAAAcIHQBAAA4QOgCAABwgNAFAADgAKELAADAAUIXAACAA4QuAAAABxIOXbt27TKFhYXJOBYAAIC0dOrUqYR/R0Khq6CgIOEDAAAASHe5ublm0qRJCf2OhEMXwQsAAKBy1HQBAAA4QOgCAABwgNAFAADgAKELAADAAUIXAACAA4QuAAAABwhdAAAADhC6AAAAHCB0AQAAOEDoAgAAcIDQBQAA4AChCwAAwAFCFwAAgAOELgAAAAcIXQAAAA4QugAAABwgdAEAADhA6AIAAHCA0AUAAOAAoQsAAMABQhcAAIADhC4AAAAHCF0AAAAOELoAAAAcSCh0jRs3zhQXFyfrWAAAANJWXl6eKSsrq/Z/n1DoOnPmjMnPzzfjx49P5NcAAACktdLSUlNUVJTQ70h4ejE3N9cUFBQk+msAAABCjZouAAAABwhdAAAADhC6AAAAHCB0AQAAOEDoAgAAcIDQBQAA4AChCwAAwAFnoWv79u3m7Nmzrv5cRurXr5+pW7duSn437V852j9YtH+waP9g0f7BSmX7+zkLXd27d3f1pzJWSUlJyjaapf0rR/sHi/YPFu0fLNo/WKlsfz+n04uu/qcyUY0aNVL+N2j/8tH+waL9g0X7B4v2D5aL9vdQ0wUAAOAAoQsAAMABQhcAAIADhC4AAAAHCF0AAAAOELoAAAAcIHQBAAA4QOgCAABwgNAFAADgAKELAADAAUIXAACAA4QuAAAABwhdAAAADhC6AAAAHCB0AQAAOBDq0HXlyhXz4YcfmsOHD5vWrVubxx9/3NStW7fCx69Zs8acPn3atGrVyjzyyCMOjzZ8zp8/b9577z1z4sQJM2DAANOrV68KH79+/Xrz4IMPVvgcoXr0XBQXF5sZM2aU+xjaP3Vo/2CoTS9evBj5t87tY8aMiWrjvXv3mu3bt9vvdZ5q0aKF8+MMq6q0v9p+27ZtplGjRqZHjx6mbdu2QRyqM6ENXceOHTPdu3c3derUsd/La6+9ZrZu3WqaNWt23eNXr15tZs2aZSZMmGAmTZrk+nBDR51M586dTadOnewbTR1Ox44dzddff33dY/XGVNvr5Hfu3Dk6nRTQiU6v/XidPu2ferS/e4cOHTL9+/ePum/o0KFR7Tt58mR7fpo/f74NB9OmTbP3l5SUOD3WMKpK+48bN85cu3bNLFq0yBw/ftwMGTLEPPvss2bs2LGuD9eZ0IauiRMnmo0bN9rUrAAwdepUs2zZMntyW7p0adRj9cZbvHixKS0tDX3KduWjjz4ye/bssVcvonafOXOmvarp1q1b5HFlZWWmffv2dmRRnQ6ST6/7ffv2xf0Z7Z96tH8wFi5caDZt2mRnOTwNGzaMfK/2LioqMj/99JO9ENdt3rx5pmXLlmbz5s2VjsyjYpW1vwY6dDHuXWio71X4VVC77777ovqJMAll6NKb6dFHH40EKHX8usLUyW/37t1Rj9UTrzeeghiBK3n69u0bCVzy1FNP2dCVk5MT9Thv1LF58+YuDy9raJT3wIEDdtrk/fffv+7ntH9q0f7BUJjdv3+/Pe/Hm9kQjayIyk+8x9SuXdt+1egLqq8q7b9kyRI7levvJ7p06WK/LliwgNCVSe6++247leWnJ1731apVK3KfXhjPPfecycvLM6NGjXJ9mKEWWxehN6Bq5Ai2bmm6RHV1r7zyStCHkpVo/2Bo5kIX33fccYc9F02ZMuW6c3y/fv1MvXr1zEsvvWQ6dOhgO/+PP/7YnqNUW4fqq0r7K+yq/MdPz4Eer1mSsApl6PInZ7+ff/7ZjB49OvLvzz//3A5t9uzZ0xQWFppdu3bZ+0eMGGHmzJnj5FizgVcvp/aGOy+//LJ5/vnnqREKCO0fHNXzarRKnffOnTvteX/VqlV22tCj50XnJZWXqP5U9URa9KMSCJ6zxFSl/b16ay1g87f3XXfdFff+sAhl6IrHW53ywgsvRO5TDZdoKtJL4TpRzp07175gNMSJ6tObZvz48ba+6/Lly/ZqcsOGDdeNQiL59HqvWbNmaIfo0x3tHyzVY3k1WSroVqDasmWLDVn+xQzeoikFL533VWZS3kU7qq4q7a8SFNV0ffnll1E7BWhBg8pQwhi4JGtC1/Tp083atWujnkhNeYl/2FMjXHqc6rxmz54d2ifeBbWdTmK6qT11YtMqrngrGJE8Wjjy1ltvsQIrILR/etF04VdffWXuueceO+ruD10aUdE2QTpHqeZUIzInT56scGsP3Jjy2l/trdkPrVbU9/Xr1zc7duww33//vR15DKusCF3q7LV6MXaERU9ybGG3qJhP6VyFltQgJYeuKDWyqDcdUkuvdW3V4W/rI0eOmKtXr9r7GjRowMqsFKL9048uAAcNGmSWL18edf/DDz9sVywWFBTYn2vBgwKA6r0YkU+eeO2vEUUtMnn33Xft13bt2pnhw4fb0a8HHnggwKNNrdCHLq1Y1LRWvI1OVXCvIU8V1PtXWHjfK5QheXr37m33KkJqad8hTeP6XbhwwU7xaisVLeGm008d2j89aVsO/ypR1RdppEsBSxQCVHek4m99JXQlV2z7i8KYf08ujTRqYZu/DChsQh26vCtNbcjm5+0VNWzYsMg2ErrS8Rw9etQ+8eUtdUX16Gpm4MCBQR9G6H366afX3afRXm1ZoAsMpBbtn55UNuI//2j1nPz666+RMhKd8/Pz821wRnLFtn8s9dfqjzUtH+ayntCGLl3FvP7665HhSo83jKnQpZsC2YoVK6JClz6SQLvXo3pUQP/GG2+YwYMHR6ZnVeeiDSK/+OKLuP+N91ERmoKBe7R/sGj/5NHolXY417nfG61SuYja2L8qXYXc2jJCYcAbbdG5S7W+WgCE6qlq+/tpIETbqyhw+fviMApl6NL+IErUGs6P3eVZbzLteutZuXKlvQrVlhFdu3a1hXya048dHcON0UebqB31puvTp49p0qSJDVyxVzDe5zNqOF9UD6MtO5h+cYP2Dxbtn3yaylXtkC62tR2Qdvxv2rRpZAW7R/tBKXDpo990Ma5pX00Lq38Ie8efSlVtf1H/rE1SdbHh/wSTMAtl6FJHf+nSpSo/3tsaQgk9zJ/55IqClVYoqkPRXiwVDRXrTaYiez7vMrX0Go+3BQrt7wbt7453/tf5XDvMV1QmonB78OBBO+2rbYJ4HhJX1fbX6JcGRjQqFubpxFihDF3VxafLJ1c2XLUASE83cj6nfjf5Kmv/bN0ZgNAFAADgAKELAADAAUIXAACAA4QuAAAABwhdAAAADhC6AAAAHCB0AQAAOEDoAgAAcIDQBQAA4AChCwAAwAFCFwAAgAOELgAAAAcIXQAAAA4QugAAABwgdAEAADjgNHSVlpa6/HOIQfsHi/YPFu0fLNo/WLR/enAWuvLy8kxRUZGrP5eRGjdunLLfTftXjvYPFu0fLNo/WLR/sFLZ/n7OQldZWZmrP4U4aP9g0f7Bov2DRfsHi/ZPH9R0AQAAOEDoAgAAcIDQBQAA4AChCwAAwAFCFwAAgAOELgAAAAcIXQAAAA4QugAAABxIOHTt2rXLFBYWJuNYAAAA0tKpU6cS/h0Jha6CgoKEDwAAACDd5ebmmkmTJiX0OxIOXQQvAACAylHTBQAA4AChCwAAwAFCFwAAgAOELgAAAAcIXQAAAA4QugAAABwgdAEAADhA6AIAAHCA0AUAAOAAoQsAAMABQhcAAIADhC4AAAAHCF0AAAAOELoAAAAc+P8B/S3xOy1eg3wAAAAASUVORK5CYII=

2.1-2 Rewrite the INSERTION -SORT procedure to sort into nonincreasing instead of non-decreasing order.

Solution:

Insertion-Sort(A)

for j = 2 to A.length
    key = A[j]
    // Insert A[j] into the sorted sequence A[1..j − 1]
    i = j  1
    while i > 0 and A[i] < key
        A[i + 1] = A[i]
        i = i  1
    A[i + 1] = key
2.1-3 Consider the searching problem:
Input: A sequence of n numbers A=<a1,a2,...,an> and a value v.
Output: An index i such that v=A[i] or the special value NIL if v does not appear in A.
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.

Solution:

Linear-Search(A,v): 
for i = 1 to A.length
    if A[i] == v
        return i

return NIL

Initialization: Initially the subarray is empty. So, none of its’ elements are equal to v.
Maintenance: In i-th iteration, we check whether A[i] is equal to v or not. If yes, we terminate the loop or we continue the iteration. So, if the subarray A[1..i1] did not contain v before the i-th iteration, the subarray A[1..i] will not contain v before the next iteration (unless i-th iteration terminates the loop).
Termination: The loop terminates in either of the following cases,
  • We have found index i such that v = Ai
  • We reached the end of the array, i.e. we did not find v in the array A. So, we return NIL
In either case, our algorithm does exactly what was required, which means the algorithm is correct.

2.1-4 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 C 1/-element array C . State the problem formally and write pseudocode for adding the two integers.

Solution:

Input: Two n-bit binary integers stored in two n-element array of binary digits (either 0 or 1)
A=<a1,a2,...,an> and B=<b1,b2,...,bn>.
Output: A (n+1)-bit binary integer stored in (n+1)-element array of binary digits (either 0 or 1) C=c1,c2,...,cn+1⟩ such that C=A+B.

Binary-Add(A,B): 
n = A.length
for i = 1 to (n + 1)
    C[i] = 0

carry = 0
for i = n to 1
    C[i] = (A[i] + B[i] + carry) % 2
    carry = (A[i] + B[i] + carry) / 2
C[i] = carry

return C

No comments :

Post a Comment