Difference between revisions of "CISC220 F2021 Lab6"

From class_wiki
Jump to: navigation, search
(Created page with "'''NOTE: The lab due date has been changed to Monday, October 27. This is a 4-day extension.''' '''The AVL starter code below has been updated from the original. It correct...")
 
Line 1: Line 1:
−
'''NOTE: The lab due date has been changed to Monday, October 27.  This is a 4-day extension.'''
+
==Lab #2==
  
−
'''The AVL starter code below has been updated from the original.  It corrects some bugs in rotate_right() and rotate_left(), and adds a function setAllBalanceFactors() which traverses the entire tree and writes a new value in balanceFactor at each node.  This function is called automatically after rotations'''
+
The ''Drozdek'' references below are to the textbook.  It shouldn't matter whether you have the 3rd or 4th edition.   
  
−
==Lab #6==
+
The exercises don't make it clear, but "computational complexity" means "big O complexity".  Please write your f function (number of instructions, counting ''assignments'', ''array accesses'', ''arithmetic operations'', and ''comparisons'') as well as your g function.
  
−
I have provided a partial implementation of AVL trees [http://nameless.cis.udel.edu/class_data/220_f2014/code/avl2.tar here] ('''UPDATED VERSION''').  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.
+
===1. Written problems===
  
−
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().
+
* '''(0.75 points)''' Drozdek exercise 2.11.7 about changing the longest subarray algorithm.  Please explain your reasoning.
−
 
+
** '''Note: There is a typo in the modified outer loop code.  "n==i" should read "n - i" '''
−
===1. C++ programming exercises===
+
* '''(0.75 points)''' Drozdek exercise 2.11.8 about the ''k''th smallest integer
−
 
+
* '''(1.5 points)''' Drozdek exercise 2.11.9 (0.5 points for each of adding, multiplying, and transposing)
−
* '''(2 points)''' Update the ''balanceFactor'' values as necessary in each AVLNode of the tree.  Note that as the textbook's pseudocode indicates, this only has to happen along the path from the inserted node to the root (Note: it appears that the pseudocode is only in the 4th edition of the textbook.  There is a scan of it in Piazza [https://piazza.com/class/hz1mqksrq176dz?cid=231 here]).  The ''print_level_and_pretty()'' function prints the keys of each level's nodes in [http://en.wikipedia.org/wiki/Tree_traversal#Breadth-first level order], followed in square brackets by their (a) recursively computed balance factor and (b) balanceFactor variable. (a) is done for you; you are just computing (b) a different way.  You will know you are correct when (a) and (b) 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, and without lines showing the connections) so that you can get a visual sense of its balance.
+
* '''(2 points)''' Drozdek exercise 2.11.10 with four loops (0.5 points per loop).  Show the steps of your calculations.
−
* '''(1.5 points)''' Take care of the "single rotation" case to rebalance the tree. This should work for both the +2/+1 case and the -2/-1 case.  Rotation functions have already been written: ''rotate_right(t)'' performs a right rotation at node ''t'', and ''rotate_left(t)'' performs a left rotation at node ''t''. You just need to do the correct rotation in the correct place.
 
−
* '''(1.5 points)''' Take care of the "double rotation" case to rebalance the tree.  This should work for both the +2/-1 case and the -2/+1 case.
 
  
 
===2. Submission===
 
===2. Submission===
  
−
* 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 <= 8, 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 Project #1.
+
* Make a '''PDF file''' <Your Name>_Lab6_README.pdf with your answers to the written exercises
−
* Create a single tar/zip/rar file out of the top-level and all subdirectories.  This archive file should be named <Your Last Name>_Lab6.tar (or .zip or .rar, etc.).  
+
* No need to compress or archive the PDF, since that's all you're turning in.
−
* Submit it in Canvas by ''midnight at the end of Thursday, October 23''
+
* Submit it in Canvas by ''midnight at the end of Tuesday, October 12''

Revision as of 13:24, 6 October 2021

Lab #2

The Drozdek references below are to the textbook. It shouldn't matter whether you have the 3rd or 4th edition.

The exercises don't make it clear, but "computational complexity" means "big O complexity". Please write your f function (number of instructions, counting assignments, array accesses, arithmetic operations, and comparisons) as well as your g function.

1. Written problems

  • (0.75 points) Drozdek exercise 2.11.7 about changing the longest subarray algorithm. Please explain your reasoning.
    • Note: There is a typo in the modified outer loop code. "n==i" should read "n - i"
  • (0.75 points) Drozdek exercise 2.11.8 about the kth smallest integer
  • (1.5 points) Drozdek exercise 2.11.9 (0.5 points for each of adding, multiplying, and transposing)
  • (2 points) Drozdek exercise 2.11.10 with four loops (0.5 points per loop). Show the steps of your calculations.

2. Submission

  • Make a PDF file <Your Name>_Lab6_README.pdf with your answers to the written exercises
  • No need to compress or archive the PDF, since that's all you're turning in.
  • Submit it in Canvas by midnight at the end of Tuesday, October 12
Retrieved from "http://nameless.cis.udel.edu/class_wiki/index.php?title=CISC220_F2021_Lab6&oldid=2004"