EECS2011A-F21: Fundamentals of Data Structures
Assignment 1
Due: October 18, 2021 @ 9:00pm
Problem 1 [1+3+3+3 points]
Provide justifications, for the following statements using the original definitions of order notation.
Refer to section 4.3 in the book for sample justifications.
1. 6n
4 + 4n
3 + 3n + 8 is O(n
4
)
2. Pn
i=1 log(i) is O(nlog(n))
3. n
2
(log(n))k
is Ω(n
2
) for (1 < k < 2)
4. n
2
n+log(n)
is Θ(n)
Problem 2 [4+3+3 points]
For the following code:
1 public void function2 ( long input ) {
2 long s = 0;
3 for ( long i = 1; i < input * input ; i ++)
4 for ( long j = 1; j < i * i ; j ++) {
5 s ++;
6 }
7 }
1. Estimate the running time (RT) by counting the number of operations and then express the obtained
RT in big-O notation?
2. Then, implement and run the program on your computer to obtain the experimental RT measurements
for the following table and record the RTs for each input.
3. Depict the experimental measurements and the theoretical function that you obtained in big-O analysis
for the same inputs. How well does the RT analysis match the experimental RT measurements? Discuss!
Hint: You may use System.currentTimeMillis() in Java to obtain the System time. You can use Excel
or any other software at your choice to do the plotting. Include the table and graph in your submission.
Submit your Java program separately as problem22.java. Note that no third-party libraries are allowed.
input 1 10 20 30 40 50 60 70 80 90 100
RT
Table 1: Experiments
1
Problem 3 [5+5 points]
For each of the following functions, give a tight (i.e., big Θ) asymptotic runtime bound with respect to the
input. You need to describe the steps that you took to calculate the final answer.
1 public void function31 ( int n) {
2 for (int i = 1 , s = 1; s <= n; i ++ , s += i)
3 System . out . println (" The value of s is: " + s);
4 }
Listing 1: Code Segment 1
1 public void function32 ( double n) {
2 int x = 0;
3 for (int i = 1; i < Math . ceil ( Math . log ( n)); i ++)
4 for (int j = 1; j < i; j ++)
5 for (int k = 1; k < 10; k ++)
6 x ++;
7 System . out . println (" The value of x is: "+x);
8 }
Listing 2: Code Segment 2
Problem 4 [4+11 points]
An evil king has n bottles of wine, and a spy has just poisoned one of them. Unfortunately, they do not
know which one it is. The poison is very deadly; just one drop diluted even a billion to one will still kill.
Even so, it takes a full month for the poison to take effect. Design an algorithm, i.e., provide the pseudocode,
for determining exactly which one of the wine bottles was poisoned in just one month’s time for each of the
following scenarios:
1. If you have O(n) taste testers.
2. If you have only O(log(n)) taste testers.
Submission
Deliverables:
In eClass, submit one zip file named as Assignment1.zip including 2 files: 1) assignment1.pdf
which includes your answers to the questions and 2) problem22.java which is your implementation
for question 2 part 2.