http://nameless.cis.udel.edu/class_wiki/index.php?title=CISC220_F2021_Lab7&feed=atom&action=historyCISC220 F2021 Lab7 - Revision history2024-03-29T10:47:55ZRevision history for this page on the wikiMediaWiki 1.28.0http://nameless.cis.udel.edu/class_wiki/index.php?title=CISC220_F2021_Lab7&diff=2016&oldid=prevCer: /* 2. Submission */2021-10-13T20:36:26Z<p><span dir="auto"><span class="autocomment">2. Submission</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='en'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 20:36, 13 October 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l16" >Line 16:</td>
<td colspan="2" class="diff-lineno">Line 16:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Include a '''PDF file''' <Your Name>_README.pdf which contains the inputs and outputs of your program, etc.  You should (a) list the input files you tested, (b) show the output of calling ''print_level_and_pretty()'' on the final tree WITH AND WITHOUT calling updateBalanceFactors() if the tree height is <= 7, and (c) show the "statistics" (from the driver() function in main.cpp) for all input files regardless of size, again with and without calling updateBalanceFactors().  Test on at least 3inarow.txt, 5words_doi.txt, partial_alphabet.txt, firstline_wap.txt, and the three cleaned files from Lab #5 (DOI, BTS, and GE).</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Include a '''PDF file''' <Your Name>_README.pdf which contains the inputs and outputs of your program, etc.  You should (a) list the input files you tested, (b) show the output of calling ''print_level_and_pretty()'' on the final tree WITH AND WITHOUT calling updateBalanceFactors() if the tree height is <= 7, and (c) show the "statistics" (from the driver() function in main.cpp) for all input files regardless of size, again with and without calling updateBalanceFactors().  Test on at least 3inarow.txt, 5words_doi.txt, partial_alphabet.txt, firstline_wap.txt, and the three cleaned files from Lab #5 (DOI, BTS, and GE).</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Create a single tar/zip file out of the top-level and all subdirectories.  This archive file should be named <Your Last Name>_Lab7.tar (or .zip, etc.).  </div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Create a single tar/zip file out of the top-level and all subdirectories.  This archive file should be named <Your Last Name>_Lab7.tar (or .zip, etc.).  </div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Submit it in Canvas by ''midnight at the end of <del class="diffchange diffchange-inline">Tuesday</del>, October <del class="diffchange diffchange-inline">19</del>''</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Submit it in Canvas by ''midnight at the end of <ins class="diffchange diffchange-inline">Friday</ins>, October <ins class="diffchange diffchange-inline">22</ins>''</div></td></tr>
<!-- diff cache key my_wiki:diff:version:1.11a:oldid:2014:newid:2016 -->
</table>Cerhttp://nameless.cis.udel.edu/class_wiki/index.php?title=CISC220_F2021_Lab7&diff=2014&oldid=prevCer at 18:02, 13 October 20212021-10-13T18:02:39Z<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='en'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 18:02, 13 October 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2" >Line 2:</td>
<td colspan="2" class="diff-lineno">Line 2:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Lab #7==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Lab #7==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>I have provided a partial implementation of AVL trees [<del class="diffchange diffchange-inline">xxx </del>here].  The AVLTree class is based on BSTree_Fast, but insert(), contains(), and findMax() have been written.  The executable is called "avl" and it expects the name of an input file on the command line.  Try running it on a few files before you start to program.  It will print out information about the (unbalanced) BST that has been constructed.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>I have provided a partial implementation of AVL trees [<ins class="diffchange diffchange-inline">https://drive.google.com/file/d/1u2XX3kbdYxhPbY-96xirobI640JIk51v/view?usp=sharing </ins>here].  The AVLTree class is based on BSTree_Fast, but insert(), contains(), and findMax() have been written.  The executable is called "avl" and it expects the name of an input file on the command line.  Try running it on a few files before you start to program.  It will print out information about the (unbalanced) BST that has been constructed.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>For this lab your job is to fill in as much of the ''updateBalanceFactors()'' function in avl.hh as you can, following Chapter 6.7.2 of the textbook and your lecture notes, so that the constructed trees are actually balanced.  This function is called automatically at the end of each insert().  Don't worry about post-delete() situations.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>For this lab your job is to fill in as much of the ''updateBalanceFactors()'' function in avl.hh as you can, following Chapter 6.7.2 of the textbook and your lecture notes, so that the constructed trees are actually balanced.  This function is called automatically at the end of each insert().  Don't worry about post-delete() situations.</div></td></tr>
</table>Cerhttp://nameless.cis.udel.edu/class_wiki/index.php?title=CISC220_F2021_Lab7&diff=2013&oldid=prevCer: /* Lab #7 */2021-10-13T17:59:47Z<p><span dir="auto"><span class="autocomment">Lab #7</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='en'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 17:59, 13 October 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4" >Line 4:</td>
<td colspan="2" class="diff-lineno">Line 4:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>I have provided a partial implementation of AVL trees [xxx here].  The AVLTree class is based on BSTree_Fast, but insert(), contains(), and findMax() have been written.  The executable is called "avl" and it expects the name of an input file on the command line.  Try running it on a few files before you start to program.  It will print out information about the (unbalanced) BST that has been constructed.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>I have provided a partial implementation of AVL trees [xxx here].  The AVLTree class is based on BSTree_Fast, but insert(), contains(), and findMax() have been written.  The executable is called "avl" and it expects the name of an input file on the command line.  Try running it on a few files before you start to program.  It will print out information about the (unbalanced) BST that has been constructed.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>For this lab your job is to fill in as much of the ''updateBalanceFactors()'' function in avl.hh as you can, following Chapter 6.7.2 of the textbook and your lecture notes, so that the constructed trees are actually balanced.  This function is called automatically at the end of each insert().</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>For this lab your job is to fill in as much of the ''updateBalanceFactors()'' function in avl.hh as you can, following Chapter 6.7.2 of the textbook and your lecture notes, so that the constructed trees are actually balanced.  This function is called automatically at the end of each insert()<ins class="diffchange diffchange-inline">.  Don't worry about post-delete() situations</ins>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===1. C++ programming exercises===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===1. C++ programming exercises===</div></td></tr>
<!-- diff cache key my_wiki:diff:version:1.11a:oldid:2012:newid:2013 -->
</table>Cerhttp://nameless.cis.udel.edu/class_wiki/index.php?title=CISC220_F2021_Lab7&diff=2012&oldid=prevCer: /* Lab #7 */2021-10-13T17:59:19Z<p><span dir="auto"><span class="autocomment">Lab #7</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='en'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 17:59, 13 October 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4" >Line 4:</td>
<td colspan="2" class="diff-lineno">Line 4:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>I have provided a partial implementation of AVL trees [xxx here].  The AVLTree class is based on BSTree_Fast, but insert(), contains(), and findMax() have been written.  The executable is called "avl" and it expects the name of an input file on the command line.  Try running it on a few files before you start to program.  It will print out information about the (unbalanced) BST that has been constructed.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>I have provided a partial implementation of AVL trees [xxx here].  The AVLTree class is based on BSTree_Fast, but insert(), contains(), and findMax() have been written.  The executable is called "avl" and it expects the name of an input file on the command line.  Try running it on a few files before you start to program.  It will print out information about the (unbalanced) BST that has been constructed.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>For this lab your job is to fill in as much of the ''updateBalanceFactors()'' function in avl.hh as you can, following Chapter 6.7.2 of the textbook and your lecture notes, so that the constructed trees are actually balanced<del class="diffchange diffchange-inline">.</del>.  This function is called automatically at the end of each insert().</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>For this lab your job is to fill in as much of the ''updateBalanceFactors()'' function in avl.hh as you can, following Chapter 6.7.2 of the textbook and your lecture notes, so that the constructed trees are actually balanced.  This function is called automatically at the end of each insert().</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===1. C++ programming exercises===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===1. C++ programming exercises===</div></td></tr>
<!-- diff cache key my_wiki:diff:version:1.11a:oldid:2011:newid:2012 -->
</table>Cerhttp://nameless.cis.udel.edu/class_wiki/index.php?title=CISC220_F2021_Lab7&diff=2011&oldid=prevCer at 17:58, 13 October 20212021-10-13T17:58:29Z<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='en'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 17:58, 13 October 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Lab #7==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Lab #7==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>===1. <del class="diffchange diffchange-inline">Written problems</del>===</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">I have provided a partial implementation of AVL trees [xxx here].  The AVLTree class is based on BSTree_Fast, but insert(), contains(), and findMax() have been written.  The executable is called "avl" and it expects the name of an input file on the command line.  Try running it on a few files before you start to program.  It will print out information about the (unbalanced) BST that has been constructed.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">For this lab your job is to fill in as much of the ''updateBalanceFactors()'' function in avl.hh as you can, following Chapter 6.7.2 of the textbook and your lecture notes, so that the constructed trees are actually balanced..  This function is called automatically at the end of each insert().</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>===1. <ins class="diffchange diffchange-inline">C++ programming exercises</ins>===</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* '''(<del class="diffchange diffchange-inline">1 point</del>)''' <del class="diffchange diffchange-inline">What are </del>the <del class="diffchange diffchange-inline">minimum and maximum number of leaves in a binary heap of height </del>''<del class="diffchange diffchange-inline">h</del>'', <del class="diffchange diffchange-inline">where a single-</del>node <del class="diffchange diffchange-inline">tree is height 1? </del> <del class="diffchange diffchange-inline">Show your reasoning.</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* '''(<ins class="diffchange diffchange-inline">2 points</ins>)''' <ins class="diffchange diffchange-inline">Update </ins>the ''<ins class="diffchange diffchange-inline">balanceFactor'</ins>' <ins class="diffchange diffchange-inline">values as necessary in each AVLNode of the tree.  Note that as the textbook</ins>'<ins class="diffchange diffchange-inline">s pseudocode indicates (4th edition only, apparently)</ins>, <ins class="diffchange diffchange-inline">this only has to happen along the path from the inserted </ins>node <ins class="diffchange diffchange-inline">to the root. </ins> <ins class="diffchange diffchange-inline">The </ins>''<ins class="diffchange diffchange-inline">print_level_and_pretty</ins>()'' <ins class="diffchange diffchange-inline">function prints the keys of each level</ins>'<ins class="diffchange diffchange-inline">s nodes in [http://en.wikipedia.org/wiki/Tree_traversal#Breadth-first level order], followed in square brackets by their </ins>(a) <ins class="diffchange diffchange-inline">recursively computed balance factor </ins>and (b) <ins class="diffchange diffchange-inline">balanceFactor variable.  </ins>(<ins class="diffchange diffchange-inline">a</ins>) is <ins class="diffchange diffchange-inline">done for you; you are </ins>just <ins class="diffchange diffchange-inline">computing </ins>(<ins class="diffchange diffchange-inline">b</ins>) <ins class="diffchange diffchange-inline">a different way</ins>.  <ins class="diffchange diffchange-inline">You will know you are correct when </ins>(a) and (b) <ins class="diffchange diffchange-inline">are the same.  It also [http://leetcode.com/2010/09/how-to-pretty-print-binary-tree.html pretty prints] a pseudo-graphical representation of the tree (using only the first character of each key string) so that you can get a visual sense of its balance</ins>.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">* '</del>''(<del class="diffchange diffchange-inline">2 points</del>)'''  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* '''(<ins class="diffchange diffchange-inline">1.5 </ins>points)''' <ins class="diffchange diffchange-inline">Take care of the "single rotation" case to rebalance the tree.  This should work for both the </ins>+<ins class="diffchange diffchange-inline">2/</ins>+<ins class="diffchange diffchange-inline">1 case and the -2/-1 case.  Rotation functions have already been written: </ins>''<ins class="diffchange diffchange-inline">rotate_right</ins>(<ins class="diffchange diffchange-inline">t</ins>)'' <ins class="diffchange diffchange-inline">performs </ins>a <ins class="diffchange diffchange-inline">right rotation </ins>at <ins class="diffchange diffchange-inline">node </ins>''<ins class="diffchange diffchange-inline">t</ins>'', <ins class="diffchange diffchange-inline">and </ins>''<ins class="diffchange diffchange-inline">rotate_left</ins>(<ins class="diffchange diffchange-inline">t</ins>)'' <ins class="diffchange diffchange-inline">performs a left rotation at node </ins>''<ins class="diffchange diffchange-inline">t</ins>''<ins class="diffchange diffchange-inline">.  You just need to do the correct rotation in </ins>the <ins class="diffchange diffchange-inline">correct place.</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">** </del>(a) <del class="diffchange diffchange-inline">Draw the tree after each insertion of the following integer keys into a max heap, both before </del>and <del class="diffchange diffchange-inline">after upheaping: 80, 40, 30, 60, 81, 90, 100, 10.  </del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">* </ins>''<ins class="diffchange diffchange-inline">'(1.5 points)'</ins>'' <ins class="diffchange diffchange-inline">Take care </ins>of the <ins class="diffchange diffchange-inline">"double rotation" case to rebalance the tree.  This should work for both the +2/-1 case and the -2/+1 case</ins>.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">** </del>(b) <del class="diffchange diffchange-inline">Now removeMax</del>() is <del class="diffchange diffchange-inline">called on the tree </del>just <del class="diffchange diffchange-inline">created.  Show the tree after each step of the process of removeMax</del>()<del class="diffchange diffchange-inline">, before and after downheaping</del>.  <del class="diffchange diffchange-inline">Clearly label or mark what is going on for both </del>(a) and (b).</div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* '''(<del class="diffchange diffchange-inline">2 </del>points)''' <del class="diffchange diffchange-inline">Write a C</del>++ <del class="diffchange diffchange-inline">function </del>''<del class="diffchange diffchange-inline">int removeMax</del>()'' <del class="diffchange diffchange-inline">for </del>a <del class="diffchange diffchange-inline">heap that is represented in array form (root </del>at <del class="diffchange diffchange-inline">index 1, etc.).  Assume the array is called H and that </del>''<del class="diffchange diffchange-inline">int leftChild(int i)</del>'', ''<del class="diffchange diffchange-inline">int rightChild</del>(<del class="diffchange diffchange-inline">int i</del>)''<del class="diffchange diffchange-inline">, and </del>''<del class="diffchange diffchange-inline">int parent(int i)</del>'' <del class="diffchange diffchange-inline">functions are defined which return </del>the <del class="diffchange diffchange-inline">array </del>''<del class="diffchange diffchange-inline">index</del>'' of <del class="diffchange diffchange-inline">those nodes given </del>the <del class="diffchange diffchange-inline">index of node ''i''</del>.</div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===2. Submission===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===2. Submission===</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* <del class="diffchange diffchange-inline">Make </del>a '''PDF file''' <Your Name><del class="diffchange diffchange-inline">_Lab7_README</del>.pdf with <del class="diffchange diffchange-inline">your answers to </del>the <del class="diffchange diffchange-inline">written exercises</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* <ins class="diffchange diffchange-inline">Include </ins>a '''PDF file''' <Your Name><ins class="diffchange diffchange-inline">_README</ins>.pdf <ins class="diffchange diffchange-inline">which contains the inputs and outputs of your program, etc.  You should (a) list the input files you tested, (b) show the output of calling ''print_level_and_pretty()'' on the final tree WITH AND WITHOUT calling updateBalanceFactors() if the tree height is <= 7, and (c) show the "statistics" (from the driver() function in main.cpp) for all input files regardless of size, again </ins>with <ins class="diffchange diffchange-inline">and without calling updateBalanceFactors().  Test on at least 3inarow.txt, 5words_doi.txt, partial_alphabet.txt, firstline_wap.txt, and </ins>the <ins class="diffchange diffchange-inline">three cleaned files from Lab #5 (DOI, BTS, and GE).</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* <del class="diffchange diffchange-inline">No need to compress </del>or <del class="diffchange diffchange-inline">archive the PDF</del>, <del class="diffchange diffchange-inline">since that's all you're turning in</del>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* <ins class="diffchange diffchange-inline">Create a single tar/zip file out of the top-level and all subdirectories.  This archive file should be named <Your Last Name>_Lab7.tar (</ins>or <ins class="diffchange diffchange-inline">.zip</ins>, <ins class="diffchange diffchange-inline">etc.)</ins>.  </div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Submit it in Canvas by ''midnight at the end of <del class="diffchange diffchange-inline">Thursday</del>, October <del class="diffchange diffchange-inline">30</del>''</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Submit it in Canvas by ''midnight at the end of <ins class="diffchange diffchange-inline">Tuesday</ins>, October <ins class="diffchange diffchange-inline">19</ins>''</div></td></tr>
</table>Cerhttp://nameless.cis.udel.edu/class_wiki/index.php?title=CISC220_F2021_Lab7&diff=1933&oldid=prevCer: Created page with "==Lab #7== ===1. Written problems=== * '''(1 point)''' What are the minimum and maximum number of leaves in a binary heap of height ''h'', where a single-node tree is height..."2021-08-30T14:42:02Z<p>Created page with "==Lab #7== ===1. Written problems=== * '''(1 point)''' What are the minimum and maximum number of leaves in a binary heap of height ''h'', where a single-node tree is height..."</p>
<p><b>New page</b></p><div>==Lab #7==<br />
<br />
===1. Written problems===<br />
<br />
* '''(1 point)''' What are the minimum and maximum number of leaves in a binary heap of height ''h'', where a single-node tree is height 1? Show your reasoning.<br />
* '''(2 points)''' <br />
** (a) Draw the tree after each insertion of the following integer keys into a max heap, both before and after upheaping: 80, 40, 30, 60, 81, 90, 100, 10. <br />
** (b) Now removeMax() is called on the tree just created. Show the tree after each step of the process of removeMax(), before and after downheaping. Clearly label or mark what is going on for both (a) and (b).<br />
* '''(2 points)''' Write a C++ function ''int removeMax()'' for a heap that is represented in array form (root at index 1, etc.). Assume the array is called H and that ''int leftChild(int i)'', ''int rightChild(int i)'', and ''int parent(int i)'' functions are defined which return the array ''index'' of those nodes given the index of node ''i''.<br />
<br />
===2. Submission===<br />
<br />
* Make a '''PDF file''' <Your Name>_Lab7_README.pdf with your answers to the written exercises<br />
* No need to compress or archive the PDF, since that's all you're turning in.<br />
* Submit it in Canvas by ''midnight at the end of Thursday, October 30''</div>Cer