Quiz #3 Prep

First, we will briefly go over the following topics:

1. Efficiency and Asymptotics: Big-O, Big-Omega, Big-Theta  
2. Recursion, Searching  
3. List Implementation: Array-Based, Linked-Based  
4. Stack Implementation: Array-Based, Linked-Based  
5. Queue Implementation: Array-Based, Linked-Based  
6. General Trees and Binary Trees: Structures and Traversals (pre-order, in-order, post-order)  

Efficiency and Asymptotics

Prove the following:
1. $8n^2+15$ is $O(n^2)$ and $O(n^3)$
2. $15n^4+n^2-n-10$ is $O(n^4)$
3. $5n^2+4n$ is $\Omega(n)$ and $\Theta(n^2)$

In terms of big-O notation and $n$, give the running time of the following code snippets:

for (int i = 0; i < 4; i++) {  
    for (int j = 1; j < n; j++) {
        for (int k = j; k < n; k++) {
            doStuff();
        }
    }
}

Recursion, Searching

What is wrong with the following piece of code? Fix it.

public static int multiplier(n, m) {  
    return n + multiplier(n, m-1);
}

Write a method to return the sum of all the integers in a list using recursion.
Given a random list of integers, what is the most efficient to search for some number? Why?

Linked Lists

Suppose you have a Node class that looks like:

private Node<T> {  
    public T val;
    public Node<T> next;
    public Node(T value) {
        val = value;
    }
}

Write a method to create a circularly singly linked structure that looks like:

A -> B -> C -> D -> E ---------  
/\                            |
|                             |
|------------------------------

Next, remove E, then B so that you have:

A -> C -> D -------------------  
/\                            |
|                             |
|------------------------------

Next, insert G between A and C to get:

A -> G -> C -> D --------------  
/\                            |
|                             |
|------------------------------

Trees

Produce the pre-order, in-order, and post-order traversal results of the tree below:

           A
          / \
         E  B
        /   / \
       H    C  D
              \  \
               I  F
                   \
                    G