首页 >
> 详细

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.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-21:00
- 微信：codinghelp

- 代写 Lab 2: Threads 2022-05-10
- 辅导assessment 1. Present Your Client ... 2022-05-10
- 5Cce2sas辅导、Python，Java程序辅导 2022-05-10
- 代写brae Webb编程 2022-05-09
- 辅导csci 3110 Assignment 1 2022-05-09
- Mth2222 Assignment 2代写 2022-05-09
- Cse3bdc Assignment 2022辅导 2022-05-08
- 辅导cis 468、辅导java，Python编程 2022-05-08
- Comp Sci 4094/4194/7094 Assignment 3 D... 2022-05-07
- Cs 178: Machine Learning & Data Mining... 2022-05-07
- Data7703 Assignment 4 2022-05-07
- 讲解assignment 2: Databases 2022-04-25
- 辅导ait681 Static Analysis 2022-04-25
- Cse121 & Cse121l 编程辅导、辅导c++程序语言 2022-04-25
- 辅导iti1120 Bject-Oriented Programming 2022-04-25
- Cmt304语言辅导、辅导c++，Python编程 2022-04-25
- 辅导comp/Engn4528 Computer Vision 2022-04-24
- 辅导fin 2200 Bloomberg Investment Proj... 2022-04-24
- 辅导bism 7255 Uml Assignment 2022-04-23
- 讲解comp202 Programming Assignment 2022-04-23