Educational Wealth: analysis and desighn of algorithm(3466)

<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="separator" style="clear: both; text-align: center;">
</div>
solved Assighnments
<br />
<div align="center" style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="clear: left; float: left; margin-bottom: 1em; text-align: left;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg631E3T38WKi1W79dg5QQuomT_lo3ySCSL2VeLMtINqVYHOsJ3lZz6tlQ4K2Qxy9Jk2bmGBrx8mAxXfhqiu_Ql67g3Wqqo90qVL5n63vRka_4zCgqdVyDcq_zllACNrBxwsMky59sa8k8/s1600/allama.png" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" loading="lazy" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg631E3T38WKi1W79dg5QQuomT_lo3ySCSL2VeLMtINqVYHOsJ3lZz6tlQ4K2Qxy9Jk2bmGBrx8mAxXfhqiu_Ql67g3Wqqo90qVL5n63vRka_4zCgqdVyDcq_zllACNrBxwsMky59sa8k8/s1600-rw/allama.png" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">AIOU<br />
<br />
<br /></td></tr>
</tbody></table>
<div align="center" style="line-height: 100%; margin-bottom: 0in;">
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhPutIOtjo1PTtE4-1eB2SgOGD-9ZFu7L82BlBoReQEnhiZJ-43H5cNpIULwmdKJR1vlKrSGA3SR53IyiWKfx6bMeey9Wwd8mH-ZWURIdzQsot9jIIcWPVe0S3l-dlwaXxf9MLbyrC1ank/s1600/DSC_0001.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="640" loading="lazy" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhPutIOtjo1PTtE4-1eB2SgOGD-9ZFu7L82BlBoReQEnhiZJ-43H5cNpIULwmdKJR1vlKrSGA3SR53IyiWKfx6bMeey9Wwd8mH-ZWURIdzQsot9jIIcWPVe0S3l-dlwaXxf9MLbyrC1ank/s640-rw/DSC_0001.jpg" width="480" /></a></div>
<br /></div>
<div align="center" style="line-height: 100%; margin-bottom: 0in;">
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiucj49bgVJsCls6hByKL7POd1qwtKAj965a9iPxcH0Kg0KNgfJuC_wJu5exXq2b7IJOWxwYWhMul-RAktgGB-LB4D8BDxz-2wi5F1RStXZt7AzYYpfNTEyhWfUCXNWH334dMxmXsHkRYM/s1600/DSC_0004.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="640" loading="lazy" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiucj49bgVJsCls6hByKL7POd1qwtKAj965a9iPxcH0Kg0KNgfJuC_wJu5exXq2b7IJOWxwYWhMul-RAktgGB-LB4D8BDxz-2wi5F1RStXZt7AzYYpfNTEyhWfUCXNWH334dMxmXsHkRYM/s640-rw/DSC_0004.jpg" width="480" /></a></div>
<br /></div>
<div align="center" style="line-height: 100%; margin-bottom: 0in;">
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIS6IQDyzBS1dFeSMrDX8GnfrF0zdt_zEFfABd_LigV4YmNO25EtvaT9nq4pj0aNL6O47PobV1l-_IZsoxT3Zp-lZnXUKZ5rkEOYsHFuoIfivC7zPrYvPWKoNKQCOv4t56cUyq8kXa8a0/s1600/DSC_0005.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="640" loading="lazy" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIS6IQDyzBS1dFeSMrDX8GnfrF0zdt_zEFfABd_LigV4YmNO25EtvaT9nq4pj0aNL6O47PobV1l-_IZsoxT3Zp-lZnXUKZ5rkEOYsHFuoIfivC7zPrYvPWKoNKQCOv4t56cUyq8kXa8a0/s640-rw/DSC_0005.jpg" width="480" /></a></div>
</div>
<br />
<div align="center" class="western" lang="en-GB" style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div class="western" lang="en-GB" style="line-height: 100%; margin-bottom: 0in;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1ri1pxa7ma1xlJvtu0vBrH4OlDeSV0cm20-Z9Y89snOjwBtMcpy2ooNGMC3Y7Ec6MjVTxtaQ4SVeeyjbFD1kmmFxQJHczJ4GUtxr13nCIONXQh4a6NuCMKaS593pKxUkackJDH_pj1hY/s1600/DSC_0006.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="640" loading="lazy" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1ri1pxa7ma1xlJvtu0vBrH4OlDeSV0cm20-Z9Y89snOjwBtMcpy2ooNGMC3Y7Ec6MjVTxtaQ4SVeeyjbFD1kmmFxQJHczJ4GUtxr13nCIONXQh4a6NuCMKaS593pKxUkackJDH_pj1hY/s640-rw/DSC_0006.jpg" width="480" /></a></div>
<br /></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
</div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgdjcijKswNi8NlTcNlr3vLX4ZqGsVmgCCI1vlLzqnxOZGLWsDS6Qr1JDhIEos59BNCxOCbcHUuvbg7LbkRrBGXoTRGFCIVyAbXB2unahVSZrcK597C3gFSn8tiuAKmtBFh4tOWrUoPtZ8/s1600/DSC_0007.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="640" loading="lazy" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgdjcijKswNi8NlTcNlr3vLX4ZqGsVmgCCI1vlLzqnxOZGLWsDS6Qr1JDhIEos59BNCxOCbcHUuvbg7LbkRrBGXoTRGFCIVyAbXB2unahVSZrcK597C3gFSn8tiuAKmtBFh4tOWrUoPtZ8/s640-rw/DSC_0007.jpg" width="480" /></a></div>
<br /></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjFa72B8rPe01Ubi533Rl4U6P4Hsu4lrlq9YgMnqIoFLabnWnc0SDpAkv8xHrr6_j0uzvNZqUvuBARgXHOERddJ192NexjhCquxR0oCc4BYjLWWByOri0XPXyT-aTNwdqoiL-AD8OCvyZk/s1600/DSC_0008.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="640" loading="lazy" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjFa72B8rPe01Ubi533Rl4U6P4Hsu4lrlq9YgMnqIoFLabnWnc0SDpAkv8xHrr6_j0uzvNZqUvuBARgXHOERddJ192NexjhCquxR0oCc4BYjLWWByOri0XPXyT-aTNwdqoiL-AD8OCvyZk/s640-rw/DSC_0008.jpg" width="480" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjLnm-RJ1xKYxLHcLYGplR8VDjNZei-unhWdhUf3S3m_froCMjHq2UHwYIE3j58_gVE2khT_sin1MXmSxrrTn71XBSfsyYxO0WjBOikRkj1eS-pyx_jyncmyN1_dfRck7X5-fgOX9hwwmo/s1600/DSC_0009.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="640" loading="lazy" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjLnm-RJ1xKYxLHcLYGplR8VDjNZei-unhWdhUf3S3m_froCMjHq2UHwYIE3j58_gVE2khT_sin1MXmSxrrTn71XBSfsyYxO0WjBOikRkj1eS-pyx_jyncmyN1_dfRck7X5-fgOX9hwwmo/s640-rw/DSC_0009.jpg" width="480" /></a></div>
<br /></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjcauhj3fniJrEEaAlwDVsc0XoPpZ9hGU48GngwzyTmnD9l2AuqBG3LrbZL2pDuKZQdP_4yyo1j_T8hxXsX1UPsE41401J3Pu0KRWUeyV3cne7rRMbUZtCrn1YrnLFVI3Fo-5a2c62Dd-k/s1600/DSC_0010.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="640" loading="lazy" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjcauhj3fniJrEEaAlwDVsc0XoPpZ9hGU48GngwzyTmnD9l2AuqBG3LrbZL2pDuKZQdP_4yyo1j_T8hxXsX1UPsE41401J3Pu0KRWUeyV3cne7rRMbUZtCrn1YrnLFVI3Fo-5a2c62Dd-k/s640-rw/DSC_0010.jpg" width="480" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj0BxVkhdMd5t8xdfvlJba-gxHhegcc8lJY4iuKwIBwKH_BfJ1tGHJBTCa8ldQs0GnSHuiczHPp1W1FE_JaB-3boCTGLJTreOt7DybdY2NKe9hu_EDD0it3LhbPPTzNDYcmqqgHbUeotvo/s1600/DSC_0011.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="640" loading="lazy" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj0BxVkhdMd5t8xdfvlJba-gxHhegcc8lJY4iuKwIBwKH_BfJ1tGHJBTCa8ldQs0GnSHuiczHPp1W1FE_JaB-3boCTGLJTreOt7DybdY2NKe9hu_EDD0it3LhbPPTzNDYcmqqgHbUeotvo/s640-rw/DSC_0011.jpg" width="480" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjBeY4KYgIUkLcrkuz7c_X8wCh5BJyta9sgvSicgOTeimYxJ8mpjhov1q7zCbxrGBYY9wKTiegFPjVcmRxJ93BZf_-N-xofWzOMkR8InvyqzjUPx_jND16ko6foxgAn9_OIAz2UvyU-25M/s1600/DSC_0012.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="640" loading="lazy" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjBeY4KYgIUkLcrkuz7c_X8wCh5BJyta9sgvSicgOTeimYxJ8mpjhov1q7zCbxrGBYY9wKTiegFPjVcmRxJ93BZf_-N-xofWzOMkR8InvyqzjUPx_jND16ko6foxgAn9_OIAz2UvyU-25M/s640-rw/DSC_0012.jpg" width="480" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8QSizcQ79vNlL3JoXUz_DCuJF7EruCLa4tQQSVeruNfWhgFbMFCNIPzOG0lyLYU6gsSP9lBnXzgc4fyECHt7mUAcUtlhZ7Auv4YaGicKG0dcII9WmSX9FXgzZTnEut5c8fXW9k_DJYP4/s1600/DSC_0012.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="640" loading="lazy" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8QSizcQ79vNlL3JoXUz_DCuJF7EruCLa4tQQSVeruNfWhgFbMFCNIPzOG0lyLYU6gsSP9lBnXzgc4fyECHt7mUAcUtlhZ7Auv4YaGicKG0dcII9WmSX9FXgzZTnEut5c8fXW9k_DJYP4/s640-rw/DSC_0012.jpg" width="480" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEguEvnW_moB8tY1eStmFPzTFw6653OLewslcR00ZZeLTVKMG-hprjm4SD7gSVg7CwXDAZvVK4A6KuxKhokRV_L7vIn25zy_T0N1YHknjUG0JbJuU6Zgc0p327L85ycFyi9RZdCjcjrfebk/s1600/DSC_0013.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="640" loading="lazy" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEguEvnW_moB8tY1eStmFPzTFw6653OLewslcR00ZZeLTVKMG-hprjm4SD7gSVg7CwXDAZvVK4A6KuxKhokRV_L7vIn25zy_T0N1YHknjUG0JbJuU6Zgc0p327L85ycFyi9RZdCjcjrfebk/s640-rw/DSC_0013.jpg" width="480" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgCoELImed6T8GHkNarnrBUoDhqyz1Evg6rpQ6lPvs5-YUO30XbGp6A3Q7mJjq6SrM9eQsvgcSYRtou0IUCUQhS75liOlJeqZv2KRnT9BPr9jPyNZPxW_QqQ_RsNGtWaXR5AX8ikKIHfa8/s1600/DSC_0014.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="640" loading="lazy" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgCoELImed6T8GHkNarnrBUoDhqyz1Evg6rpQ6lPvs5-YUO30XbGp6A3Q7mJjq6SrM9eQsvgcSYRtou0IUCUQhS75liOlJeqZv2KRnT9BPr9jPyNZPxW_QqQ_RsNGtWaXR5AX8ikKIHfa8/s640-rw/DSC_0014.jpg" width="480" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<br /></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>Course: Analysis &
Design of Algorithms (3466) Semester: Autumn 2015</b></span></div>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>Level:
BS (CS) Total Marks: 100</b></span></div>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>Credit:
Half Credit Pass Marks: 50</b></span></div>
<div align="center" class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: medium;"><b>ASSIGNMENT No. 1</b></span></div>
<div align="center" class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>Units: (1 – 4)</b></span></div>
<div align="center" class="western" style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;"><i><b>Note:</b></i></span><span style="font-size: x-small;"><i>
 </i></span><span style="font-size: x-small;"><i><b>All
questions are compulsory. Each question carries equal marks.</b></i></span></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in; margin-left: 0.75in; text-indent: -0.75in;">
<span style="font-size: x-small;">Q. 1 a) Let c(n) and d(n) be
asymptotically positive functions. Prove or disprove each of the
following conjectures; </span><span style="font-size: x-small;"><b>(20)</b></span></div>
<ol type="a">
<li>
<div align="justify" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;">c(n) = θ(c(n/2))</span></div>
</li>
<li>
<div align="justify" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;">c(n) = O((c(n))</span><sup><span style="font-size: x-small;">2</span></sup><span style="font-size: x-small;">)</span></div>
</li>
<li>
<div align="justify" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;">c(n) = O(d(n)) implies d(n) =
 Ω(c(n))</span></div>
</li>
</ol>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;"> b) Prove that Pr{A | C} +
Pr{</span><sub> <img align="bottom" border="0" height="20" loading="lazy" name="Image1" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAkAAAAUCAYAAABf2RdVAAAACXBIWXMAAA7GAAAOxQHB+J5RAAAA3UlEQVR4nLWRMQ6DMAxFv6UcpSxVT1BOkHbvylZGWNgY2ViaEY7AAZoTwAkqBshdXANSqRAVUtV6SBzr+duxFTNjy9QmMUBEtCmlpBz9ptz3kDPsezEOd0ahQauQzWM0ch8+KtmQs/0dt+MJVecAvVtCjk0GpLUG2g89OROgTWtEAFmAVyDLeXVBUs+Rpu3lfCtnwxNK6bakeHhOKtd3Jfly9rih50jyQFPIZ6/q4KBZjc0GMpOUX8DSVEgeysHLDBId8QjKGLx4mFSDwJyhCllwsUzVBTHP0X8veGFPhwxR6Q/pMkgAAAAASUVORK5CYII=" width="9" />
 </sub><span style="font-size: x-small;">
| C} = 1.</span></div>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;">Q.
2 a) Give examples of relations that are: </span><span style="font-size: x-small;"><b>(20)</b></span></div>
<ol type="a">
<li>
<div style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;">Reflexive
 and Symmetric but not Transitive</span></div>
</li>
<li>
<div style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;">Reflexive
 and Transitive but not Symmetric</span></div>
</li>
<li>
<div style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;">Symmetric
 and Transitive but not Reflexive</span></div>
</li>
</ol>
<ol start="2" type="a">
<li>
<div style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;">Illustrate
 the operation of counting sort on the array A = [6, 0, 2, 0, 1, 3,
 4, 6, 1, 3, 2].</span></div>
</li>
</ol>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;">Q.
3 a) Let A and B be finite sets, and f : A −> B be a function.
Show that: </span><span style="font-size: x-small;"><b>(20)</b></span></div>
<ol type="a">
<li>
<div style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;">If
 f is injective, then |A| ≤ |B|</span></div>
</li>
<li>
<div style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;">If
 f is surjective, then |A| ≥ |B|</span></div>
</li>
</ol>
<div class="western" style="line-height: 100%; margin-bottom: 0in; margin-left: 0.38in;">
<span style="font-size: x-small;">b) Show that any connected,
undirected graph G = (V, E) satisfies |E| ≥ |V| - 1.</span></div>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;">Q.
4 a) </span><span style="font-size: x-small;"><span style="letter-spacing: -0.3pt;">Illustrate
the operation of Heap sort on the array A = [5, 13, 2, 25, 7, 17, 20,
8, 4]. </span></span>
</div>
<ol start="2" type="a">
<li>
<div style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;">What
 is the running time of heap sort on an array A of length n that is
 already sorted in increasing order? What about decreasing
 order?</span><span style="font-size: x-small;"><span style="letter-spacing: -0.3pt;"> </span></span><span style="font-size: x-small;"><b>(20)</b></span></div>
</li>
</ol>
<div style="line-height: 100%; margin-bottom: 0in; margin-left: 0.63in;">
<br /></div>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;">Q.
5 Write notes on the following topics: </span><span style="font-size: x-small;"><b>(20)</b></span></div>
<ul>
<li>
<div style="line-height: 100%; margin-bottom: 0in;">
<a href="https://en.wikipedia.org/wiki/Quicksort" target="_blank"><span style="font-size: x-small;">Quick sort</span></a></div>
</li>
<li>
<div style="line-height: 100%; margin-bottom: 0in;">
<a href="https://en.wikipedia.org/wiki/Probability" target="_blank"><span style="font-size: x-small;">Probability</span></a></div>
</li>
<li>
<div style="line-height: 100%; margin-bottom: 0in;">
<a href="https://en.wikipedia.org/wiki/Tree_%28graph_theory%29" target="_blank"><span style="font-size: x-small;">Graph and trees</span></a></div>
</li>
<li>
<div style="line-height: 100%; margin-bottom: 0in;">
<a href="http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap10.htm" target="_blank"><span style="font-size: x-small;">Medians and order statistics</span></a></div>
</li>
</ul>
<div align="center" class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: medium;"><b>ASSIGNMENT No. 2</b></span></div>
<div align="center" class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>Units:</b></span><span style="font-size: x-small;">
(</span><span style="font-size: x-small;"><b>5 – 8)</b></span></div>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>   Total
Marks: 100</b></span></div>
<div align="right" class="western" style="line-height: 100%; margin-bottom: 0in;">
<a href="https://www.blogger.com/blogger.g?blogID=4540382126610807499" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"></a><span style="font-size: x-small;"><b>Pass Marks: 50</b></span></div>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;"><i><b>Note:</b></i></span><span style="font-size: x-small;"><i>
 </i></span><span style="font-size: x-small;"><i><b>All
questions are compulsory. Each question carries equal marks.</b></i></span></div>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<a href="https://www.blogger.com/blogger.g?blogID=4540382126610807499" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"></a><br /></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in; margin-left: 0.38in; text-indent: -0.38in;">
<span style="font-size: x-small;">Q. 1</span><span style="font-size: x-small;"><b> </b></span><span style="font-size: x-small;">Give
and explain each step with graph example for the trace of following
graph traversal algorithms: </span><span style="font-size: x-small;"><b>(20)</b></span></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;"> a) <a href="https://www.khanacademy.org/computing/computer-science/algorithms/breadth-first-search/a/the-breadth-first-search-algorithm" target="_blank">Breadth first search</a></span></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;"> b) <a href="https://en.wikipedia.org/wiki/Depth-first_search" target="_blank">Depth first search</a></span></div>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in; margin-left: 0.75in; text-indent: -0.75in;">
<a href="http://i.imgur.com/w8mnlsg.jpg" target="_blank"><span style="font-size: x-small;">Q. 2 a) Demonstrate theinsertion of the keys 5, 28, 19, 15, 20, 33, 12, 17, 10 into a hashtable with collisions resolved by chaining. Let the table have 9slots, and let the hash function be h(k) = k mod 9.</span></a></div>
<ol start="2" type="a">
<li>
<div align="justify" style="line-height: 100%; margin-bottom: 0in;">
<a href="http://i.imgur.com/BdQhBMl.jpg" target="_blank">For the set of keys {1, 4, 5, 10, 16, 17, 21}, draw binary search trees of height 2, 3, 4, 5, and 6. (20)</a></div>
</li>
</ol>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
<a href="http://i.imgur.com/2mrJF9g.jpg" target="_blank"><span style="font-size: x-small;">Q. 3 a) Prove that thefractional knapsack problem has the greedy-choice property</span></a><span style="font-size: x-small;"> </span><br />
<br />
<div style="line-height: 100%; margin-bottom: 0in; text-align: left;">
<a href="http://i.imgur.com/oEsfI7a.jpg" target="_blank"><span style="font-size: small;">  a: 1   b : 1   c : 2   d : 3   e : 5   f : 8   g : 13   h : 21 </span></a><br />
<span style="font-size: small;"> </span>
</div>
<a href="http://i.imgur.com/Pb5bACv.jpg" target="_blank"><span style="font-size: small;">b:What is an optimal Huffman code for the following set of frequencies, based on the first 8 Fibonacci numbers? (20)\</span></a></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: small;"> </span></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: small;"> </span></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in; margin-left: 0.38in; text-indent: -0.38in;">
<span style="font-size: x-small;">Q. 4 Execute the following
algorithms for the given graph. Analyze the difference between the
order of nodes or edges visited for the two algorithms: </span><span style="font-size: x-small;"><b>(20)</b></span></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;"> a) Prim’s algorithm</span></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
<span style="font-size: x-small;"> b) Kruskal’s algorithm</span></div>
<div align="center" class="western" lang="en-US" style="line-height: 100%; margin-bottom: 0in;">
</div>
<div class="western" style="line-height: 0.21in; margin-bottom: 0in; margin-left: 0.38in; text-indent: -0.38in;">
<span style="font-size: x-small;">Q. 5 Write notes on the
following topics: </span><span style="font-size: x-small;"><b>(20)</b></span></div>
<ul>
<li>
<div style="line-height: 0.21in; margin-bottom: 0in;">
<a href="https://www.cs.cmu.edu/~adamchik/15-121/lectures/Stacks%20and%20Queues/Stacks%20and%20Queues.html" target="_blank"><span style="font-size: x-small;">Stack & Queue</span></a></div>
</li>
<li>
<div style="line-height: 0.21in; margin-bottom: 0in;">
<span style="font-size: x-small;"><a href="https://en.wikipedia.org/wiki/Hash_table" target="_blank">Hash Table</a> and <a href="https://en.wikipedia.org/wiki/Hash_function" target="_blank">Functions</a></span></div>
</li>
<li>
<div style="line-height: 0.21in; margin-bottom: 0in;">
<a href="https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm" target="_blank"><span style="font-size: x-small;">The Bellman-Ford Algorithm</span></a></div>
</li>
<li>
<div style="line-height: 0.21in; margin-bottom: 0in;">
<a href="http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap23.htm" target="_blank"><span style="font-size: x-small;">Elementary Graph Algorithms</span></a></div>
</li>
</ul>
<div class="western" style="line-height: 100%; margin-bottom: 0in;">
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br /></div>
<div align="justify" style="line-height: 100%; margin-bottom: 0in;">
<b><span style="font-size: small;">Analysis
and Design of Algorithm (3466/3503) Credit Hours: 3(3+0)</span></b></div>
<div align="justify" class="western" style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div align="justify" class="western" style="line-height: 0.19in; margin-bottom: 0in;">
<span style="font-size: x-small;"><i><b>Recommended Book:  </b></i></span></div>
<div align="justify" class="western" style="letter-spacing: -0.2pt; line-height: 0.19in; margin-bottom: 0in;">
<span style="font-size: x-small;"><i>Introduction to Algorithms
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest</i></span></div>
<div align="justify" class="western" style="letter-spacing: -0.2pt; line-height: 0.19in; margin-bottom: 0in;">
<br /></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>Course Outlines:</b></span></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>Unit No.1: Introduction</b></span></div>
<div align="justify" style="line-height: 0.18in; margin-bottom: 0in; margin-left: 0.5in; text-indent: 0.5in;">
<span style="font-size: x-small;">Introduction to Algorithm
Analysis and Design </span>
</div>
<div align="justify" style="line-height: 0.18in; margin-bottom: 0in; margin-left: 0.5in; text-indent: 0.5in;">
<span style="font-size: x-small;">Growth of Functions,
Summations Formulas and Properties</span></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<br /></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>Unit No.2: Recurrences and
Sets</b></span></div>
<div align="justify" style="line-height: 0.18in; margin-bottom: 0in; margin-left: 0.5in; text-indent: 0.5in;">
<span style="font-size: x-small;">Substitution, Iteration and
Master Methods</span></div>
<div align="justify" style="line-height: 0.18in; margin-bottom: 0in; margin-left: 0.5in; text-indent: 0.5in;">
<span style="font-size: x-small;">Sets, Relations, Functions,
Graph and Trees, Counting and Probability</span></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<br /></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>Unit No.3: Sorting
Algorithms</b></span></div>
<div align="justify" style="line-height: 0.18in; margin-bottom: 0in; margin-left: 0.5in; text-indent: 0.5in;">
<span style="font-size: x-small;">Heaps, Maintaining the Heap
Property, Heap Sort algorithm,</span></div>
<div align="justify" style="line-height: 0.18in; margin-bottom: 0in; margin-left: 0.5in; text-indent: 0.5in;">
<span style="font-size: x-small;">Quick Sort, Performance and
Analysis of Quick Sort</span></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<br /></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>Unit No.4: Sorting in
Linear Time and Order Statistics</b></span></div>
<div align="justify" style="line-height: 0.18in; margin-bottom: 0in; margin-left: 1in;">
<span style="font-size: x-small;">Lower bounds for sorting,
Counting sort, Radix and Bucket Sort, Medians and order Statistics</span></div>
<div align="justify" style="line-height: 0.18in; margin-bottom: 0in; margin-left: 1in;">
<br /></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>Unit No.5: Elementary Data
Structures</b></span></div>
<div align="justify" style="line-height: 0.18in; margin-bottom: 0in; margin-left: 1in;">
<span style="font-size: x-small;">Analysis of Stack, Queues and
Linked List Algorithms, Hash Table and Functions, Binary Search Trees</span></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<br /></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>Unit No.6: Dynamic
Programming</b></span></div>
<div align="justify" style="line-height: 0.18in; margin-bottom: 0in; margin-left: 1in;">
<span style="font-size: x-small;">Matrix Chain Multiplication,
Longest Common Subsequence, Optimal Polygon Triangulation</span></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<br /></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>Unit No.7: Greedy
Algorithms</b></span></div>
<div align="justify" style="line-height: 0.18in; margin-bottom: 0in; margin-left: 1in;">
<span style="font-size: x-small;">An activity selection problem,
Huffman Codes, A Task Scheduling Problem, Amortized Analysis</span></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<br /></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>Unit No.8: Graph Algorithms</b></span></div>
<div align="justify" style="line-height: 0.18in; margin-bottom: 0in; margin-left: 1in;">
<span style="font-size: x-small;">Elementary Graph Algorithms,
Breadth first search, Depth first search, Minimum Spanning Trees</span></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<br /></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in;">
<span style="font-size: x-small;"><b>Unit No.9: Single Source
Shortest Paths</b></span></div>
<div align="justify" class="western" style="line-height: 0.18in; margin-bottom: 0in; margin-left: 1in; text-indent: -1in;">
<span style="font-size: x-small;"> Shortest Paths and
Relaxation, Dijkstra’s Algorithm, The Bellman-Ford Algorithm,
Introduction to NP-Completeness</span></div>
<div align="center" class="western" style="line-height: 100%; margin-bottom: 0in; margin-left: 0.5in; text-indent: -0.5in;">
<br /></div>
<div align="center" class="western" style="line-height: 100%; margin-bottom: 0in; margin-left: 0.5in; text-indent: -0.5in;">
<br />
assginment No 1</div>
<br />
<div style="text-align: left;">
</div>
<br /></div>

Analysis & Design of Algorithms(3466)-solved assighnments.aiou autumn 2015

solved Assighnments AIOU Course: Analysis & Design of Algorit...

Attention! Ad blocker Detected!

Educational Wealth

[PastPapers] Analysis and Design of Algorithms - 3466/3506 -AIOU BS(CS)

Analysis & Design of Algorithms(3466)-solved assighnments.aiou autumn 2015

Popular Posts

Tags

Blog Posts