CSCE 3110 Data Structures
Assigment 2 
Total: 80 points
Issued: 02/16/2006
Due: 03/02/2006
................................


1. (15 points) Given an array A of size N-1 that contains all numbers 
from 1 to N except one, design and implement a linear algorithm that 
finds the missing number. Save the program in a file called findNumber.cpp.

2. (15 points) Write the pseudo-code (or C++ code) for the enqueue and dequeue 
operations in a queue implemented using two stacks. 

3. (15 points) Design a data representation mapping a stack s and a queue q
into a single array M. Write algorithms (pseudo-code or C++ code) to add and 
delete elements from these two data objects. What is the running time for 
each such operation?

4. (20 points) Two binary trees are similar if they are both empty or both 
non-empty and have similar left and right sub-trees. Write a function to
decide whether two binary trees are similar. What is the running time of
your function? Save the program in a file called similarTrees.cpp.

5. (15 points) Given a binary tree, write a function to find the depth 
of a given node. What is the running time of the algorithm? Save the program
in a file called findDepth.cpp.

Submission instructions:  
   - write a README file including the answers to the questions, and a 
     detailed note about the functionality of each of the above programs, 
     and complete instructions on how to run them.
   - make sure you include your name in each program and in the README file.
   - make sure all your programs are fully commented, and compile and run 
     correctly on the CSP machines.
   - submit your assignment by the due date using the 'project' program.
     class code is 3110s002, project HW2.