Day 21 (September 30, 2013)  
Assignment to be done in class and as exercises.

Assignment 1: 
Write codes for the following traversals of a binary tree
(i) inorder, 
(ii) preorder, 
(iii) postorder,  
(iv) level order

Implement the tree using structures. 

Assignment 2: 
Write codes for the following operation on a binary tree
(i) testing equality of two binary trees,
(ii) copying a binary tree,
(iii) SAT evaluation, 
(iv) finding the height of a binary tree.


Assignment 3: 
Write codes for the following operation on a threaded binary tree: 
(i) insertion, 
(ii) deletion, 
(iii) inorder traversal

Assignment 4: 
Write codes for the following operation on a (max)-heap; 
(i) create a heap; 
(ii) insert an element into a heap; 
(iii) delete an element from a heap; 
(iv) extract maximum from a heap, 

Assignment 5: 
Write codes for the following strategies for union find
(i) quick find, 
(ii) quick union, 
(iii) weighted quick union  
(iv) weighted quick union with path compression

Assignment 6:
Write codes for the percolation experiment described in class and 
estimate the vacancy percentage. The implementation should use the 
code written above for union find.

Assignment 7: 
Given a social network containing N members and a log file containing 
M timestamps at which times pairs of members formed friendships, design 
an algorithm to determine the earliest time at which all members are 
connected (i.e., every member is a friend of a friend of a friend ... 
of a friend). Assume that the log file is sorted by timestamp and that 
friendship is an equivalence relation. The running time of your algorithm 
should be MlogN or better and use extra space proportional to N.

Assignment 8: 
Write codes for 
(i) create a binary search tree (BST), 
(ii) insert an element into a BST, 
(iii) delete an element from a BST, 
(iv) searching an element in a BST, 
(v) searching for elements in an interval in a BST, 

Assignment 9: 
Write codes for 
(i) create an AVL tree, 
(ii) insert an element into an AVL tree, 
(iii) delete an element from an AVL tree


------------------------------------------------------------------------
At the top of each of your program files, add the following. If you are 
writing multi-file programs, then each file should have it. 

/*------------------------------------------------------------------
Name: 
Roll Number:
Date of Submission:
Deadline date:  
Program description:
Acknowledgements: 
--------------------------------------------------------------------*/