[Solved] DataStructure Assignment #3

Chapter 3

10 points

1. Linked lists and arrays:
2. What are some advantages of linked lists versus arrays?
3. What are some advantages of arrays versus linked lists?

15 points

2. What is the Big-O running time of the following code fragment? Assume lst1 has N items, and lst2 is initially empty.

public static void add( List<Integer> lst1, List<Integer> lst2)

{

for ( Integer x : lst1 )

lst2.add(0, x); // add to front

}

2. If an ArrayList is passed for lst1 and lst2. Explain your answer.
3. If a LinkedList is passed for lst1 and lst2. Explain your answer.

15 points

3. What is the Big-O running time of the following code fragment?

public static void erase( List<Integer> lst )

{

Iterator<Integer> itr = lst.iterator();

while ( itr.hasNext() )

{

Integer x = itr.next(); itr.remove(); }

}

1. If an ArrayList is passed for lst. Explain your answer.
2. If a LinkedList is passed for lst. Explain your answer.

15 points

4. What is the Big-O running time of the following code fragment? Assume lst1 has N items, and lst2 has N items.

public static int Count( List<Integer> lst1, List<Integer> lst2)

{

Iterator<Integer> itr1 = lst1.iterator();

int count=0;

while ( itr1.hasNext() )

{

Integer x = itr1.next();

Iterator<Integer> itr2 = lst2.iterator();

while ( itr2.hasNext() )

if ( x.equals( itr2.next()) ) count++;

}

return count;

}

2. If an ArrayList is passed for lst1 and lst2. Explain your answer.
3. If a LinkedList is passed for lst1 and lst2. Explain your answer.

15 points

5. What is the Big-O running time of the following code fragment?

public static int calc( List<Integer> lst )

{

int count = 0; int N = lst.size();

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

{

if (lst.get(i) > 0) sum += lst.get(i); else

sum += lst.get(i) * lst.get(i);

}

return sum;

}

1. If an ArrayList is passed for lst. Explain your answer.
2. If a LinkedList is passed for lst. Explain your answer.

15 points

6. Suppose a Java method receives a List<Integer> and reverses the order of the items it contains by removing each item from the front of the list and pushing it onto a Stack<Integer>, and then popping the items from the stack and inserting each item to the end of the list.

What is the expected Big-O running time if:

1. If an ArrayList is passed. Explain your answer.
2. If a LinkedList is passed. Explain your answer.

15 points

7. Show each step of converting a+b*c+(d-e) from infix to postfix notation, using the algorithm described in the textbook that uses a stack.

Submit to eLearning: hw3.doc (.doc can be .txt, .jpg, etc.)