## 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
```