Entertainment: cs502

Showing posts with label cs502. Show all posts

CS502 Assignment no 02 Solution

<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjggS24yRc759bOeYhXOkZZ-JmeOx5SG99C0ZU1oJ-XcNbykuWougesIxQCVMMUMiZX8wjHAqLmIrpw7hd1K-PBYn4_rBf66xj_weVMs7gQtqUCXRMjj-ZHqeA-7KWOrpNauWnqe3693fo/s1600/images.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjggS24yRc759bOeYhXOkZZ-JmeOx5SG99C0ZU1oJ-XcNbykuWougesIxQCVMMUMiZX8wjHAqLmIrpw7hd1K-PBYn4_rBf66xj_weVMs7gQtqUCXRMjj-ZHqeA-7KWOrpNauWnqe3693fo/s1600/images.jpg" /></a></div>
<br />
solution<br />
<br />
<br />
<div style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-size: 16px; line-height: 20.8px; margin-bottom: 5px; margin-top: 5px; outline: 0px; padding: 0px; vertical-align: baseline;">
Denoting <code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Monaco, 'Courier New', Courier, monospace !important; font-size: 13px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">S(n)</code> the sum of the first <code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Monaco, 'Courier New', Courier, monospace !important; font-size: 13px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">n</code> cubes, <code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Monaco, 'Courier New', Courier, monospace !important; font-size: 13px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">S(n)</code> must be a polynomial of the fourth degree in <code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Monaco, 'Courier New', Courier, monospace !important; font-size: 13px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">n</code>, let</div>
<pre style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-left-color: rgb(225, 225, 225); border-left-style: solid; border-width: 0px 0px 0px 2px; font-family: Monaco, 'Courier New', Courier, monospace !important; font-size: 13px; margin-bottom: 20px; margin-top: 20px; outline: 0px; padding: 0px 0px 0px 10px; vertical-align: baseline;"><code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Monaco, 'Courier New', Courier, monospace !important; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">S(n) = an^4+bn³+cn²+dn.</code>
</pre>
<div style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-size: 16px; line-height: 20.8px; margin-bottom: 5px; margin-top: 5px; outline: 0px; padding: 0px; vertical-align: baseline;">
This is because</div>
<div style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-size: 16px; line-height: 20.8px; margin-bottom: 5px; margin-top: 5px; outline: 0px; padding: 0px; vertical-align: baseline;">
1) <code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Monaco, 'Courier New', Courier, monospace !important; font-size: 13px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">S(0)= 0</code>, so there is no independent term,</div>
<div style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-size: 16px; line-height: 20.8px; margin-bottom: 5px; margin-top: 5px; outline: 0px; padding: 0px; vertical-align: baseline;">
2) When computing <code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Monaco, 'Courier New', Courier, monospace !important; font-size: 13px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">S(n)-S(n-1)</code>, which must equal <code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Monaco, 'Courier New', Courier, monospace !important; font-size: 13px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">n³</code>, you get a polynomial of the third degree, by cancellation of the quartic term:</div>
<div style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-size: 16px; line-height: 20.8px; margin-bottom: 5px; margin-top: 5px; outline: 0px; padding: 0px; vertical-align: baseline;">
</div>
<pre style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-left-color: rgb(225, 225, 225); border-left-style: solid; border-width: 0px 0px 0px 2px; font-family: Monaco, 'Courier New', Courier, monospace !important; font-size: 13px; margin-bottom: 20px; margin-top: 20px; outline: 0px; padding: 0px 0px 0px 10px; vertical-align: baseline;"><code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Monaco, 'Courier New', Courier, monospace !important; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">S(n)-S(n-1) = a(n^4-(n-1)^4)+b(n³-(n-1)³)+c(n²-(n-1)²)+d(n-(n-1)).</code>
</pre>
<div style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-size: 16px; line-height: 20.8px; margin-bottom: 5px; margin-top: 5px; outline: 0px; padding: 0px; vertical-align: baseline;">
Developing and simplifying,</div>
<pre style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-left-color: rgb(225, 225, 225); border-left-style: solid; border-width: 0px 0px 0px 2px; font-family: Monaco, 'Courier New', Courier, monospace !important; font-size: 13px; margin-bottom: 20px; margin-top: 20px; outline: 0px; padding: 0px 0px 0px 10px; vertical-align: baseline;"><code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Monaco, 'Courier New', Courier, monospace !important; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">a(4n³-6n²+4n-1)+b(3n²-3n+1)+c(2n-1)+d = n³. </code></pre>
<div style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-size: 16px; line-height: 20.8px; margin-bottom: 5px; margin-top: 5px; outline: 0px; padding: 0px; vertical-align: baseline;">
Let us identify the coefficients:</div>
<pre style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-left-color: rgb(225, 225, 225); border-left-style: solid; border-width: 0px 0px 0px 2px; font-family: Monaco, 'Courier New', Courier, monospace !important; font-size: 13px; margin-bottom: 20px; margin-top: 20px; outline: 0px; padding: 0px 0px 0px 10px; vertical-align: baseline;"><code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Monaco, 'Courier New', Courier, monospace !important; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">n³:  4a        =1 
n²: -6a+3b     =0 
n:   4a-3b+2c  =0 
1:   -a +b -c+d=0
<span style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">Solving this triangular system is straigthforward:</span></code></pre>
<pre style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-left-color: rgb(225, 225, 225); border-left-style: solid; border-width: 0px 0px 0px 2px; font-family: Monaco, 'Courier New', Courier, monospace !important; font-size: 13px; margin-bottom: 20px; margin-top: 20px; outline: 0px; padding: 0px 0px 0px 10px; vertical-align: baseline;"><code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-family: Monaco, 'Courier New', Courier, monospace !important; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">a=1/4 
b=1/2 
c=1/4 
d=0.</code></pre>
<div style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; font-size: 16px; line-height: 20.8px; margin-bottom: 5px; margin-top: 5px; outline: 0px; padding: 0px; vertical-align: baseline;">
<br /></div>
<br />

CS502 Assignment no 02 Solution

solution Denoting S(n) the sum of the first n cubes, S(n) must be a polynomial of the fourth degree in n , let S(n) = an^4+bn...

+ Read more »

CS502 - Fundamentals of Algorithms Assignment No. 01 Solution Fall 2015 Due Date November 25, 2015

<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhPR5GQg_TcGomUFXDyDsCQth4tyztrzAEhboKQ0_CBrHMHouO1-psJF_sO8cQLHo_nELmWv6GiQ8g_3iP_u67xJEqmm7x5nfmD8FiPm9QbXm85T3Y0pm0mSusLVOCNOs3QONF6Jv25jL4/s1600/images.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhPR5GQg_TcGomUFXDyDsCQth4tyztrzAEhboKQ0_CBrHMHouO1-psJF_sO8cQLHo_nELmWv6GiQ8g_3iP_u67xJEqmm7x5nfmD8FiPm9QbXm85T3Y0pm0mSusLVOCNOs3QONF6Jv25jL4/s1600/images.jpg" /></a></div>
<table border="1" cellspacing="0" style="background: rgb(255, 255, 255); border-collapse: collapse; border-spacing: 0px; border: none; color: black; font-family: 'Times New Roman', Times, Palatino, Georgia, serif; font-size: 16px; font-weight: bold; line-height: 20.8px; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline; width: 104%px;"><tbody style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<tr style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;"><td colspan="2" style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;" valign="top" width="51%"><div align="center" style="background: transparent; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">Assignment No. 01<br style="font-size: 1em; position: static !important;" />Semester: Fall 2015</b></div>
<div align="center" style="background: transparent; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">CS502: Fundamentals of Algorithms</b></div>
<div align="center" style="background: transparent; border: 0px; font-size: 1em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<br /></div>
</td><td style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;" valign="top" width="29%"><div style="background: transparent; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">Total Marks: 20</b></div>
<div style="background: transparent; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<br /></div>
<div style="background: transparent; border: 0px; font-size: 1em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">Due Date:25/11/2015</b></div>
</td></tr>
<tr style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;"><td colspan="4" style="background: transparent; border: 0px; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;" valign="top" width="100%"><div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<br /></div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">Instructions</b></div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">Please read the following instructions carefully before submitting assignment:</b></div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">It should be clear that your assignment will not get any credit if:</b></div>
<ul style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; list-style: none; margin: 0px 0px 1.5em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<li style="background: transparent; border: 0px; font-size: 1em; list-style: square; margin: 0px 0px 3px 2.5em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;"><b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">The assignment is submitted after due date.</b></li>
<li style="background: transparent; border: 0px; font-size: 1em; list-style: square; margin: 0px 0px 3px 2.5em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;"><b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">The submitted assignment does not open or file is corrupt.</b></li>
<li style="background: transparent; border: 0px; font-size: 1em; list-style: square; margin: 0px 0px 3px 2.5em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;"><b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">Solution is copied from any other source.</b></li>
</ul>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;"><u style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">Objective</u></b></div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
The objective of this assignment is to;</div>
<ul style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; list-style: none; margin: 0px 0px 1.5em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<li style="background: transparent; border: 0px; font-size: 1em; list-style: square; margin: 0px 0px 3px 2.5em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">Learn and practice Algorithm running time analysis</li>
</ul>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;"><u style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">Assignment</u></b></div>
<div align="right" style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<br /></div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
In this assignment, you are provided with sample code of two sorting algorithms<b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">Insertion_sort.cpp</b> and <b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">Quick_sort.cpp</b>. The code is self explanatory. Inside both programs, we define an array of size ‘n’ and fill it with random values generated by some seed value. Afterwards, we apply sorting algorithm to sort the array elements. You can find in code that we record the system time before and after sorting operation in order to get the total time taken.</div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;"><u style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">Your Task</u></b></div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
You are required to execute the given programs in Dev-C++ and get the running time for various array sizes and seed values. You shall record your results in the excel sheet <b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">Results.xls</b> provided along with this assignment. You need to get running time for array size of 10000, 30000…50,000 for both Insertion and Quick sort programs and report your values in given excel file by replacing the zero values in table for Experimental results accordingly. You shall also mention the seed value you use for these results.</div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
After performing all experiments, you need to make a graph (visual representation) for each algorithm to see its growth in running time w.r.t. input size of array as shown for theoretical results. <b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">You also need to discuss the results graph in your own words.</b></div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<br /></div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; margin-bottom: 1.5em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;"><u style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">Submission</u></b></div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
You are required to submit your solution through LMS as <b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">MS Excel document which contain your calculated running time and discussion on results as desired.</b></div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;"><br /></b></div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<i><u><span style="font-size: x-large;">SOLUTION</span></u></i></div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<i><u><span style="font-size: x-large;"><br /></span></u></i></div>
<div style="background: transparent; border: 0px; font-family: 'Times New Roman'; font-weight: normal; line-height: 20.8px; margin-bottom: 5px; margin-top: 5px; outline: 0px; padding: 0px; vertical-align: baseline;">
First understand seed:</div>
<div style="background: transparent; border: 0px; font-family: 'Times New Roman'; font-weight: normal; line-height: 20.8px; margin-bottom: 5px; margin-top: 5px; outline: 0px; padding: 0px; vertical-align: baseline;">
<strong style="background: transparent; border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">Hint! The "seed" is a starting point for the sequence</strong></div>
<div style="background: transparent; border: 0px; font-family: 'Times New Roman'; font-weight: normal; line-height: 20.8px; margin-bottom: 5px; margin-top: 5px; outline: 0px; padding: 0px; vertical-align: baseline;">
If you need just a random sequence of numbers and don't need to reproduce it then just use current time as seed... <strong style="background: transparent; border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">for example with:</strong></div>
<div style="background: transparent; border: 0px; font-family: 'Times New Roman'; font-weight: normal; line-height: 20.8px; margin-bottom: 5px; margin-top: 5px; outline: 0px; padding: 0px; vertical-align: baseline;">
<strong style="background: transparent; border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">srand(time(NULL));</strong></div>
<div style="background: transparent; border: 0px; font-family: 'Times New Roman'; font-weight: normal; line-height: 20.8px; margin-bottom: 5px; margin-top: 5px; outline: 0px; padding: 0px; vertical-align: baseline;">
Then run both programs of *.cpp files and note the reading and put in the respective rows as per the Arrays.</div>
<div style="background: transparent; border: 0px; font-family: 'Times New Roman'; font-weight: normal; line-height: 20.8px; margin-bottom: 5px; margin-top: 5px; outline: 0px; padding: 0px; vertical-align: baseline;">
The result graph will be developed same as experimental graph</div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<br /></div>
<div style="background-attachment: initial; background-clip: initial; background-color: transparent; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-image-outset: initial; border-image-repeat: initial; border-image-slice: initial; border-image-source: initial; border-image-width: initial; border: 0px; font-size: 1em; min-height: 1em; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;">
<b style="background: transparent; border: 0px; font-size: 1em; margin: 0px; outline: 0px; padding: 0px; position: static !important; vertical-align: baseline;"><br /></b></div>
</td></tr>
</tbody></table>

CS502 - Fundamentals of Algorithms Assignment No. 01 Solution Fall 2015 Due Date November 25, 2015

Assignment No. 01 Semester: Fall 2015 CS502: Fundamentals of Algorithms Total Marks: 20 Due Date:25/11/2015 Instructions ...

+ Read more »

Subscribe to: Posts ( Atom )