Assignment Set 7 (Uploaded on October 7, 2015)
Clarification deadline date: October 9,2015
Submission deadline date:  October 16, 2015


Problem 1: [Threaded binary tree]

(a) Implement a threaded binary tree as discussed in class. 

(b) Write routines for inorder, preorder and postorder traversals 
using the threaded binary tree. 

[Marks: 30 + 10x3 + 20 {Good programming habits} = 80]


Problem 2: [Kd tree and range search]

(a) Take a positive integer n as input from the user and read from the user 
a set of n points on the plane with real coordinates. Let this set of points 
be P. 

(b) Implement a Kd tree for P as discussed in class.  

(c) Let R=[x:x']x[y:y'] be a rectangle on the plane. Find the set of 
points in P that lie within R by using the range search technique 
discussed in the class.   

[Marks: 10 + 45 + 45 + 20 {Good programming habits} = 120]

-------------------------------------------------------------------------
[Make your program multifile and write a proper makefile to compile your 
program. Name your makefile as make15xx, where xx is your roll number. 
Your makefile should be such that we can automatically run your makefile
with the make command.]
-------------------------------------------------------------------------

Naming conventions for program files. xx is your roll number: 

For Problem 1: 
The name of the src file for problem 1 of assignment 7 should be  
``cs15xx-assign7-src-prog1.c''. 

The name of the app file for problem 1 of assignment 7 should be  
``cs15xx-assign7-prog1.c''. 

The name of the include file for problem 1 of assignment 7 should be  
``cs15xx-assign7-prog1.h''. 


For Problem 2: 
The name of the src file for problem 2 of assignment 7 should be  
``cs15xx-assign7-src-prog2.c''. 

The name of the app file for problem 2 of assignment 7 should be  
``cs15xx-assign7-prog2.c''. 

The name of the include file for problem 2 of assignment 7 should be  
``cs15xx-assign7-prog2.h''.
-----------------------------------------------------------------------

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: 
--------------------------------------------------------------------*/