Question 1. What is the Big-Oh order of the following growth functions? 1. 5n 3

Question

Question 1. What is the Big-Oh order of the following growth functions?

1. 5n3+ 3n2- 3

2. 2n2+ 5n + 17

3. 1000n + 30n2

4. 10n2log n

Question 2. Arrange the growth functions of the previous question in ascending order of efficiency for the fixed problem sizes n=10 and again for n = 1000000.

Question 3. Determine the order of the following code fragments:

1)

for (int i = 0; i < n; i++)

for (int j = 32; j < n; j++)

System.out.println("Nested loops!");  //measure these.

2)

for (int i = 0; i < n; i++)

for (int j = i; j < n; j++)

   for (int k = 1; k < n; k += 2)

System.out.println("Depthly nested loops!");   //measure these.

3)

int i=0, j=0;

do {

do {

     System.out.println("...looping...");  //measure these

        j=j+5;

   } while (j < n);

i++;

} while (i < n);

4)

for (int i=0; i < n; i++)

for (int j=1; j < n; j=j*2)

System.out.println(i, j);  //measure these.

Question 4. Suppose you with had two algorithms, A and B, with growth functions fa(n)=2000n2 and fb(n)=2n4. If you were to do an exact analysis on these growth functions, i.e., not simplify them with Big-Oh, what algorithm would you recommend for which values of n? Explain how you arrived at your answer. (Hint: you should be dividing up the domain of n > 0).

Question 5. Compare and contrast: data types, abstract data types and data structures. Include how they are related.

Question 6. Trace an initially empty Stack (called S) through the following operations:

Stack S = new Stack();

S.push(new Integer(4));

S.push(new Integer(3));

//a) What is the content of the stack at this point?

Integer Y = S.pop();

S.push(new Integer(7));

S.push(new Integer(2));

S.push(new Integer(5));

S.push(new Integer(9));

//b) What is the content of the stack at this point?

Integer Y = S.pop();

S.push(new Integer(3));

S.push(new Integer(9));

//c) What is the content of the stack at this point?

Question 7. Assume you have a stack called S with the following contents, and trace the following operations:

4 (top)

8

2

3

1

System.out.println(S.peek()); //a) What is printed?

S.pop();

System.out.println(S.peek()); //b) What is printed?

System.out.println(S.pop()); //c) What is printed?

System.out.println(S.peek()); //d) What is printed?

//e) What are final the contents of the stack?

Question 8. Explain how the undo operation in a word processor can be supported by the use of a stack. Give specific examples and comment on the contents of the stack after various actions are taken.

Question 9. What would happen to the time complexity (Big-oh) of the methods in an array implementation of the stack if the top of the stack were at position 0? Explain.

Explanation / Answer

Multiple Questions with multiple sub-questions : Answering 1st.

1. 5n3+ 3n2- 3 O(n3)
2. 2n2+ 5n + 17 O(n2)
3. 1000n + 30n2 O(n2)
4. 10n2log n O(n2logn)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.