CSCE 3110 Data Structures
Assigment 2
Total: 80 points
Issued: 02/04/2007
Due: 02/19/2007 (postponed to 02/26/2007)
................................


1. (15 points)
   Show that the following equalities are correct:
   a) 8n^3 + 2n^2 = Theta(n^3)
   b) n! = O(n^n)
   c) 2^n + n log n + 5 = Theta(2^n)
   d) 5 n^3 + 4 n = Omega(n^2)
   e) 33 n^3 + 4 n^2 = Omega(n^3) 

  And show that the following are incorrect:
  f) 10 n^3 + nlog n + 9 = O(n^2)
  b) n^2 log n = Theta(n^2)

2. (15 points) Order the following functions by their asymptotic growth rates. 
log(log n) ; 2^(log n) ; n^2 ; n! ; (log n)! ; (3/2)^n ; n^3; 
2^(2^n); n; n log n; sqrt(log n); log n

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

4. (10 points) Given an array A of sorted numbers from the standard input
and a number p we would like to search, implement the binary search 
algorithm that returns the position of number p if it is in A, and 
returns -1 otherwise. Save the program as binarySearch.cpp. Analyze
the cost of your algorithm in terms of big O (please give detail steps 
to show how you reach your conclusion).

5. (10 points) Write a program to read from standard input two lists of
sorted numbers into lists L1 and L2.  Write a procedure to 
compute (L1 union L2) without the duplicates using only the basic list 
operations. Save the program as union.cpp. The following is a sample 
test numbers from the standard input:
3 12 34 57 67
1 3 12 21 34 57 67 
You program should output:
1 3 12 21 34 57 67

6. (10 points) Write a program to read from the standard input two polynomials.
Write a function to add two polynomials. Do not destroy the input. 
Use a linked list implementation. If the polynomials have M and N terms, 
respectively, what is the time complexity of your program. Save the program as pAddition.cpp
The make it easier to read from the input the polynomials will follow the following 
sample input format:
+2x^7+12.3x^3+23x^2+1x^0
+33x^3-3.3x^2+10x^0

The following link gives a sample program that reads a polynomial. Use it only if it helps you:
 www.cs.unt.edu/~huangyan/3110/sampleProg/polynomial.txt

7. (10 points) Write a program to read from standard input a list of numbers and store
them in a single listed list. Write a nonrecursive function to reverse the singly linked 
list in O(N) time. Save the program as reverseList.cpp

Submission instructions: 
       - write a README file including the answers to problems 1, 2 and 4, 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 3110s001 and the project name is 'list'.