Description
Written Assignments (40 points)
1. (15 points) Suppose T1(n)= O(g(n)) and also T2(n)= O(g(n)). Which of the following are true? Explain your
answer.
(a) T1(n)+ T2(n)= O(g(n))
(b) T1(n)/T2(n)= O(1)
(c) T1(n)= O(T2(n))
2. (15 points) Show whether that the following equalities are correct or not:
a) 5
– 6n = Theta(
)
b) 33
+ 4
= O(
)
c) 33
+ 4
= O(
)
d) 10
+ 9 = O(n)
e) 10
+ 9 = O(
)
3. (10 points) Order the following functions by their asymptotic growth rates.
n!
n
log n
Programming Assignment (60 points)
4. (60 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.
All submitted source codes will be passed to Stanford MOSS (http://theory.stanford.edu/~aiken/moss/) for
detecting software plagiarism. You are NOT supposed to copy and paste online solutions nor your collegue’s
solutions.
What to turn in:
Include your name and A number at the top of each file (PDF and two programming files).
Compress the three files (i) your answer note for questions 1, 2, 3 and 4 (the table) in PDF file format
(ii) your fibonacci1.cpp; and (iii) fibonacci2.cpp.
Name the compressed file as hw01_FIRSTNAME_LASTNAME.zip. For example, if your name is
John Smith, name the file as hw01_John_Smith.zip. Submit the compressed file to Canvas.
Make sure all your programs are fully commented, and compile and run correctly.
This is an individual assignment, but you may discuss general strategies and approaches with
other members of the class (refer to the syllabus for details of the homework collaboration
policy). If you discussed an assignment with your colleague, explicitly report the colleague’s name and
what you discussed in your submission.
Follow Code of Conduct (refer to the syllabus for details).
