Question

Exercise 1

Use Top-Down Design to “design” a set of instructions to write an algorithm for “travel arrangement”. For example, at a high level of abstraction, the algorithm for “travel arrangement” is: book a hotel buy a plane ticket rent a car Using the principle of stepwise refinement, write more detailed pseudocode for each of these three steps at a lower level of abstraction.

Exercise 2

Asymptotic Complexity (3 pts) Determine the Big-O notation for the following growth functions: 1. a(n) = 4n 3 + 2n 2 2. b(n) = log(n) + n 2 1000 + n 3. c(n) = 10 log(n) + 3n log(n) + 2 log log(n) 4. (Bonus question: 1 pt) d(n) = n! 100 + n 43 + 4n 5. (Bonus question: 1 pt) e(n) = 2n + n 7

Exercise 3

Consider the following loop.

i ← 0 while(i<n)

helperFunction(...)

i ←i+1

done

1. What is the worst case time complexity (Big-O) of this loop if helperFunction(. . . ) is just a single operation?

2. What is the worst case time complexity (Big-O) of this loop if helperFuncton(. . . ) is an O(n log(n)) algorithm?

3. (Bonus question: 2 pts) What is the worst case time complexity (Big-O) of this loop if helperFuncton(. . . ) is an O(n 2 ) algorithm?

4. (Bonus question: 5 pts) What is the worst case time complexity (Big-O) of this loop if helperFuncton(. . . ) is an O(i) algorithm? (Note that i is the loop counter, so helperFuncton(. . . ) does more work as i increases) Justify your answers and show all your work.

Exercise 4

The following code fragment is a Monte Carlo method for approximating Pi. (for more background, see the link http://mathfaculty.fullerton.edu/mathews/n2003/montecarlopimod.html). Assume that random() is a function that returns a random floating point value in the range from 0 to 1 with uniform density (all values are equally likely); for this question, assume that calling random() is a primitive operation, and requires only one “step.”

i ← 0

count ← 0

while(i<n)

x ← random()

y ← random()

if (x^2 + y^2 <= 1)

count ← count+1 i ← i + 1 done pi ← 4*count/n

1. Use the statement counting approach from the lecture notes to determine the number of operations on each line of the program.

2. Determine the number of primitive operations that will be done in the Worst case as a function of n.

3. Determine the number of primitive operations that will be done in the Best case as a function of n.

4. What is the worst case time complexity (Big-O) of this code fragment? Justify your answers and

show all your work.

Answer 1

Solution:

Note: Exercise 1 and 2 are solved as per the Chegg guidelines, please repost others.

Exercise 1:

The detailed pseudocode is given below:

Pseudocode:

1. Begin
2. decide the location for the trip
3. search for the hotel at the destination
4. book a hotel
5. buy a plane ticket for the destination
6. look for the locations to explore
7. rent a vehicle to explore these locations
8. end

Exercise 2:

1. a(n) = 4n 3 + 2n 2 2. b(n) = log(n) + n 2 1000 + n 3. c(n) = 10 log(n) + 3n log(n) + 2 log log(n) 4. (Bonus question: 1 pt) d(n) = n! 100 + n 43 + 4n 5. (Bonus question: 1 pt) e(n) = 2n + n 7

Let's have a look at Big-O first.

1. a(n) = 4n^3 + 2n^2

4n^3 + 2n^2​​​​​​​<= c*n^3

which means

a(n)= O(n^3)

2. b(n) = log(n) + n^2 1000 + n^3​​​​​​​

b(n)= O(n^3)

3. c(n) = 10 log(n) + 3n log(n) + 2 log log(n)​​​​​​​

c(n)= O(n log n)

4. d(n) = n! 100 + n^43 + 4n^5​​​​​​​

d(n)= O(n^n)

please let me know if I have missed or mistaken on taking the notations in exercise 2.

Please give it a thumbs up if this helped you, also provide your valuable feedback.