CSCE 3110 Data Structures
Assigment 1
Total: 60 points
Issued: 01/29/2006
Due: 02/09/2006
................................


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

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

2. (5 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) Fibonacci numbers. Implement in two separate files, 
called fibonacci1.cpp and fibonacci2.cpp, the iterative and the 
recursive methods for computing Fibonacci numbers. The programs 
should read from the standard input the value of N, and output the 
corresponding Fibonacci value. Write down in a table the time 
(according to your system clock) that it takes for each program to 
complete, for each of the following N values: 1, 2, 4, 8, 16, 32, 64. 

4. (10 points) Textbook, problem 3.9 (ed.2: 3.9, ed.3: 3.4). Save the 
program as intersection.cpp

5. (10 points) Write a function to add two polynomials. Do not destroy the 
input. Use a linked list implementation. If the polynomials have N and M 
terms, what is the time complexity of your program? Save the program as 
pAddition.cpp

6. (10 points) Write a nonrecursive function to reverse a 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-3, 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 HW1.