EECS2011A编程辅导、辅导Java语言程序

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!

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.

请加QQ：99515681 或邮箱：99515681@qq.com   WX：codehelp