CS251: Homework 1. Midterm Review

Please create a directory hw1 where you will store all your files. Make a copy of this html file and add your answers. Rename this file as index.html and put it into the directory "hw1". You will turn it in before Friday March 21st before 11:59pm. You may scan your answers to questions 5 and 6 and add them as pictures. Include the scanned files in the directory hw1. Include both questions and answers.

To turn in your file: 

1. Login to lore 
2. turnin the hw1 directory
        turnin -c cs251 -p hw1 hw1
3. Verify the files you turned in:
        turnin -c cs251 -p hw1 -v
These are typical questions that you may have in the midterm exam.

1. The following class implements a list of integers. a) write the implementation of insert(int value) that inserts a new element at the end of the list. b) Write the method reverse() that returns a different List object with the same elements but  in reverse order.
struct ListEntry {
  int value;
  ListEntry * _next;
};

class List {
  ListEntry * _header;
 public:
  ... other methods ...
  void insert ( int value );
  void insertBeginning ( int value );
  List * reverse();
};

void
List::insert(int value)
{
   ListEntry * entry = new ListEntry();
   
   entry->value = value;
   entry->_next = NULL;
   
   if(_header == NULL)
   {
      _header = entry;
      return;
   }
   ListEntry * current = _header;
   while(current->_next != NULL)
      current = current->_next;
   current->_next = entry;
}
ryy
List *
List::reverse()
{
   List * list = new List();
   ListEntry * current = _header;
   
   while(current != NULL)
   {
      list->insertBeginning(current->value);
      current = current->_next;
   }
   
   return list;
}

void List::insertBeginning(int value)
{
   ListEntry * entry = new ListEntry();
   entry->value = value;
   entry->_next = _header;
   _header = entry;
}
2. The following class implements a Double-Linked list. a) Write a bubble sort that sorts the list in ascending order. Note: Do the sorting in place. Do not copy the list into an array to do the sorting. b) What is the complexity of the new bubbleSort method with the double-linked list?
struct DLListEntry {
  int _value;
  DLListEntry * _previous;
  DLListEntry * _next;
};

class DLList {
  DLListEntry _head; // Dummy node where _head._next points to first list entry or to tail.
  DLListEntry _tail; // Dummy node where _tail._previous points to the last entry
public:
  ... other methods ...
  void bubbleSort();
}; 

void DLList::bubbleSort()
{
   bool swap = true;
   DLListEntry cur;
   while(swap)
   {
       swap = false;
       cur = _head;
       while(cur != NULL)
       {
          if(cur->value > cur->_next->value)
	  {
             int temp = cur->value;
             cur->value = cur->_next->value;
             cur->_next->value = temp;
             swap = true;
	  }
	  cur = cur->_next
       }
    }
 }
 
(b)
Best-Case: O( n ) its already sorted
Worst-Case: O( n*n ) its in reverse sorted order, therefore you have to go through it n more times, making it n*n
3. Assume the following implementation of a binary tree. a) Write a method samedepth() that returns true if the distance from the root to the leaves is the same for all the leaves, or false otherwise. b) Write a method sum() that returns the sum of all the values of the binary tree. Add any other auxiliar methods you may need.
struct BinaryTreeNode {
  int _value;
  BinaryTreeNode * _left;
  BinaryTreeNode * _right;
};

class BinaryTree {
  BinaryTreeNode * _root;
public:
  ... other methods ...
  bool samedepth();
  int samedepth(BinaryTreeNode node);
   int sum();
  int sum(BinaryTreeNode node);
 };

bool
BinaryTree::samedepth()
{
   if(samedepth(_root) != -1)
      return true;
   else
      return false;
}

int
BinaryTree::samedepth(BinaryTreeNode node)
{
   if(node == NULL)
      return 0;
      
   int left = samedepth(node->_left);
   int right = samedepth(node->_right);
   
   if(left == -1 || right == -1)
      return -1;
   
   if(right == left)
      return (right + 1);
   else
      return -1;
}

int BinaryTree::sum()
{
   return sum(_root);
}

int BinaryTree::sum(BinaryTreeNode node)
{
   if(node == NULL)
      return == 0;
      
   int valueLeft = sum(node->_left);
   int valueRight = sum(node->_right);
   
   return (valueLeft + valueRight + value);
}

4. Write the implementation of the remove(int key) method of the AVL tree that removes the node with that key. You may base your implementation with the one given in class. Also include the implementation of any auxiliar procedures you use.
typedef int KeyType;
typedef char * ValueType;
struct AVLNode {
  int _heigt;
  KeyType _key;
  ValueType _value;
  AVLNode  * _left;
  AVLNode * _right;
  AVLNode * _parent;
};

class AVLTree {
  AVLNode * _root;
public:
  ... Other methods ...
  bool remove( KeyType key ); // Remove a key. It returns OK or false if key is not found.
  void preorder(AVLNode* temp)
};

bool
AVLTree::remove( KeyType key)
{
	AVLNode * current = (AVLNode *)findRecord(key);
	if(current==NULL)
		return false;
	AVLNode * parent = current->parent;
	if(current == parent->right)
		parent->right = current->right;
	else
		parent->left = current->right;
	current->right = NULL;
	current->parent = NULL;
	preorder(current);
	return true;
}

void
AVLTree::preorder(AVLNode* temp)
{
	if(temp!=NULL)
	{
		preorder(temp->left);
		preorder(temp->right);
		addRecord(temp->key,temp->data);
	}
}
5. Starting with an empty tree, perform the following operations in the AVL tree. Indicate the resulting tree after each step. Also show intermediate steps if any.

insert(5);
insert(6)
insert(7);
insert(8);
insert(9);
insert(10);
insert(11);
insert(12);
insert(13);
insert(14);
insert(15);
insert(16);
insert(1);
insert(2);
insert(3);
insert(4)
remove(10);
remove(11);
remove(12)
remove(13);
remove(14);
remove(15);
remove(9);






6. Starting with an empty tree, perform the same operations from question 5. in a (2,4) tree. Indicate the resulting tree after each step. Also show intermediate steps if any.




7. Starting with an empty heap, perform the same operations from question 5. in a Heap. Indicate the resulting heap after each step. Also show intermediate steps if any. The remove() operation has to be interpreted as removeMin().




8. Starting with an empty tree, perform the operations from step 5 in a red-black tree. Indicate the resulting tree after each step. Also show intermediate steps if any.





9. Given the following definition of a red-black tree, write a method bool correctBlackHeight() that returns true if the number of black edges in every path from the root to any leaf is the same.
enum { red=0, black=1 };
struct RBTreeNode {
  int value;
  EdgeColor _color;
  RBTreeNode  * _left;
  RBTreeNode  * _right;
  RBTreeNode * _parent;
};

class RBTree {
  RBTreeNode  * _root;
public:
  // ... other methods ...
  bool correctBlackHeight();
  int countingBlacks(RBTreeNode t, int n);
 };

bool
RBTree::correctBlackHeight()
{
  return countingBlacks(_root, 0);
 }

int
RBTree::countingBlacks(RBTreeNode t, int n)
{
   int right;
   int left;
   
   if(t==NULL)
      return n;

   if(t->_color==black)
   {
      left = countingBlacks(t->_left, n+1);
      right = countingBlacks(t->_left, n+1);
   }
   else
   {
      left = countingBlacks(t->_left, n);
      right = countingBlacks(t->_left, n);
   }
   
   if(left==-1 || right==-1)
      return -1;

   if(left==right)
      return left;
   else
      return -1;
}