```
1. Lists of Lists; Stack ADT
2. Queue, Priority Queue, and Graph ADTs
3. Graph Traversal: BFS, DFS
4. Dictionary, Set, and Multiset ADTs
5. Sorting
6. Efficiency and Asymptotics: Big-O, Big-Omega, Big-Theta
7. Recursion, Searching
8. List Implementation: Array-Based, Linked-Based
9. Stack Implementation: Array-Based, Linked-Based
10. Queue Implementation: Array-Based, Linked-Based
11. General Trees and Binary Trees: Structures and Traversals (pre-order, in-order, post-order)
12. Heap ADT & impl.
13. Priority Queue impl.
14. Binary Search Tree ADT
15. BST-based impl. of Set and Dictionary;
Hashing for Dictionaries
16. Balanced BSTs
17. Graph Impl.
```

Which ADT could you use do the following and how?

1. Level-order traversal of a tree.

2. Undo and Redo actions.

3. Keep track of orders.

What are the best and worst case running times of the following sorting algorithms:

```
Insertion Sort -- example best case
Merge Sort
Heap Sort
Selection Sort
```

Why write code to solve a problem using recursion as opposed to using iteration?

Consider this graph

What is a possible depth-first traversal of this graph, starting from node **S**?

What is a possible breadth-first traversal of this graph, starting from node **S**?

Suppose we use an array-based implementation for a MaxHeap and after some number of operations, the internal array of a a heap looks like this:

```
[null, 20, 10, 18, 2, 5, 11, 13, 1, null, null, null]
```

Draw the binary tree that is represented by this array.

Then draw the resulting tree and internal array after adding 15 to this heap and then removing the max item from this heap.

Start with this list [3, 2, 1, 8, 7, 6, 5]. Show the resulting heap representation of this list. Using an appropriate number of bubbleDown operations, make this list a valid **max-heap**.

Given the following binary tree:

```
A
/ \
B C
/ \ \
D O P
/ /
T R
```

In what order would the nodes be visited in preorder, inorder, and postorder traversals?

Given the following values in the given order, draw the corresponding AVL trees that would result.

1. 3, 2, 1 [Draw tree]

2. 4, 5 [Draw tree; continue adding to the previous tree]

3. 6

4. 7

5. 16, 15

6. 14

Given the following matrix, draw the directed graph that it represents:

```
A B C D E
A 0 1 1 1 0
B 0 0 1 0 1
C 0 0 0 1 0
D 1 0 0 0 0
E 0 0 1 0 0
```

Is this graph connected? Is it complete? How would you invert the edges of this graph?

Why would you represent a graph using an adjacency list? What of using an adjacency matrix?

Given a dictionary representative of the number of times a word appears in a text file, write a method to print out the relative frequencies (number of times word appears divided by total number of words file) of each word. For example, given

```
{ "hey" -> 5,
"there" -> 5,
"jadrian" -> 3,
"cool" -> 20
}
```

your method should print

```
"hey" : 0.1515
"there" : 0.1515
"jadrian" : 0.0909
"cool" : 0.6060
```

Dictionary Interface DictPair Interface Set Interface

Why is it important to keep the load factor low, especially for hash tables that use open addressing?

]]>But I will be happy to talk to you about any of the following:

```
* Hashing
* Collision Resolution
- Separate chaining
- Open addressing: linear, quadratic, and double hashing
* Hash-based dictionaries
```

]]>First, we will talk about the following operations on BSTs:

```
1. Searching
2. Insertion
3. Deletion
4. Traversal
```

Then we will solve the following problems:

```
1. Write a method to get the minimum value in a BST.
2. Similarly, write a method to get the maximum value in a BST.
3. Write a method to determine if a binary tree is a valid BST.
```

]]>```
1. Heap completeness; the Heap property
2. Heap implementation using Arrays
3. Min, Max Heaps
3. Priority Queue implementation
```

Then, we will attempt to solve the following:

* Which of the following is not a valid max heap?

```
(a) 9
\
2
(b) 4
/ \
9 6
/ \ /
2 7 10
(c) 12
/ \
12 6
/ \ / \
5 8 2 4
/
4
(d) 12
/ \
12 6
/ \ / \
5 8 2 4
/
8
(e) 12
/ \
12 6
/ \ / \
5 8 2 4
/ \
5 84
(f) 12
/ \
12 6
/ \ / \
5 8 2 4
/ \
5 11
(g) 14
/ \
11 15
/ \ / \
5 8 2 4
/ / \
5 2 20
```

For any of the heaps in (1) that is not valid, can you apply any finite number of appropriate number of heap operations (

`bubbleDown`

,`bubbleUp`

, and so on) to make it valid? If so, make it valid by making each subtree -- starting from the leaves -- a valid heap.Perform heapsort on the following arrays clearly showing how the heap changes at each stage:

```
A = [1,9,8,7,6,5,4,3,2]
B = [15,20,1,50,1,2]
```

- Heapsort takes $\Theta(n\log n)$. Mergesort asymptotically has the same runtime. Why would we use one over the other?

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

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();
}
}
}
```

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?

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 --------------
/\ |
| |
|------------------------------
```

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

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

]]>```
1. public Node getNthFromEnd(int i):
Write a method that will return the n-th node from the end of the linked list.
2. public List copy():
Write a method that will copy and return the contents of a linked list.
3. public List cumulativeSum():
Write a method to return a new linked list where each node 'n' contains the cumulative sum of numbers stored in the first node to that node 'n'. For example, {1, 2, 3, 4} should become {1, 3, 6, 10}.
4. public List merge(List l1, List l2):
Write a method to return return a new list containing all the nodes in both 'l1' and 'l2'
```

]]>```
1. Create an array of size 10 and put the following items into the array:
(a) 1,2,3,4,7, 5, 6
(b) "1", "2", "3", "4", "7", "5", "6"
2. Write a method to, given an array, reverse the non-null contents of that array.
3. Write a method to, given an 'item', a number 'n' and an empty fixed-size array, return that array with 'n' copies of 'item'
```

]]>```
- big-O, big-Omega, and big-Theta notation
- proofs
- worst-case analysis
- thinking about recursion
```

Then we will try to solve the following problems using recursion:

```
1. Given a list of integers, write a method to find the minimum value.
2. Write a method to find the maximum value in a list.
3. Given a list of integers, write a method to return the sum of all the integers.
```

Note that the three problems above can certainly be solved using iteration alone. In fact, it is much easier to think about the problem non-recursively. But I think it is good practice on formulating a problem recursively and thinking about both the recursive calls and base cases for a particular recursive formulation.

]]>```
Queues
Priority Queues
Graphs
- Weighted
- Unweighted
- Directed
- Undirected
Breadth First Search
Depth First Search
Sorting
```

Then, we will answer the following:

```
1. Write code to reverse the contents of a Stack using a Queue.
2. Write code to reverse the contents of a Queue using a Stack.
3. Show the BFS and DFS trees obtained by traversing the graph below starting from vertex B.
Assume that vertices in any "neigbors list" are visited in this order: B E A C D F
Clearly show the stack/queue states during the algorithm.
4. Briefly explain the invariants essential for insertion sort and selection sort.
...
```

]]>Write a program that reads in a sequence of characters and prints them in reverse order. Use a stack.

Write a program that reads in a sequence of characters, and determines whether its parentheses, braces, and curly braces are "balanced."

Write a program that reads in a positive integer and prints the binary representation of that integer. Hint: divide the integer by 2.

Write code to reverse the contents of a stack using a queue.

Write code to reverse the contents of a queue using a stack.

```
(a)
List<int> some = new MysteryListImplementation<int>();
(b)
int a = 2;
int b = 3.0 * a;
(c)
public static Integer someStaticMethod() {
return new Integer();
}
(d)
public Integer someNonStaticMethod() {
return someStaticMethod();
}
(e)
public static Integer secondStaticMethod() {
someNonStaticMethod();
}
(f)
public class SomeClass<T> {
...
public SomeClass<T>() {
}
public void someMethod() {
}
...
}
(g)
public class MyInterface {
}
public class SecondClass<T> implements MyInterface {
}
```

- Show the state of the underlying data structure at every step of the algorithm.

```
Stack<Integer> s = new Stack<Integer>();
String someTest = "23*2*8*9*";
int first, second;
for (int i = 0; i < someTest.length(); i++) {
if (someTest.charAt(i) == '*') {
first = s.pop();
second = s.pop();
s.push(first * second);
} else {
s.push(
Character.getNumericValue(someTest.charAt(i))
);
}
}
System.out.println(s.pop());
```

]]>*The list below was given to me to help me prepare practice problems for the prefect session and not as a definite list of topics that will appear on the quiz.*

```
The following list of topics is intended to give you a sense of what I think is important from the course so far, and what I will be thinking of when creating the quiz. It is essentially a more detailed copy of the 'Class Topics' column of our schedule since the beginning of the term.
Please note that this topic list is a guide, not a contract. I may have left something off this list that will end up in a quiz question, and there will definitely be topics in the list that I won't be able to ask about on the quiz.
Java stuff:
- Java types
- The difference between declaration, initialization, and assignment
- Static methods and data, and how they can and can't be used
- The structure of a main method (and the restrictions on it, since it's static)
OO stuff:
- The contents of a class (methods and data, both static and non-static)
- Encapsulation, composition, and inheritance
- Interfaces vs. classes
ADTs: List and Stack. Students should be able to:
- Name the methods of the ADTs, and the inputs, outputs, and actions of those methods
- Trace the state of an ADT through the execution of several operations on it
(That is, given some Java code that creates a stack and does some pushes and pops, what's the state of the stack at various chosen positions in the program?)
```

We will go through the entire list item-by-item. Where appropriate, we will try to solve a toy example illustrative of the particular problem. You will not be asked to write code during the quiz.

]]>Design a

`Room`

class. Suppose we only knew very few characteristics of a`Room`

such as how many people live there, if it's a single or double, and so on. Write the code for this`Room`

class and "test" this class by instanting some`Room`

objects and printing some pretty information about each`Room`

object.Next, design a

`Floor`

class. Suppose a`Floor`

holds a specific number of rooms. Think about other information a`Floor`

can store. Write some "test" code for the`Floor`

class.Finally, write a

`Building`

class. A`Building`

consists of a certain number of floors.

- This program prints numbers 1 through 20. Next, for any given integer x, print numbers 1 through x. When you're done, try using a while loop instead and putting the Java code in a method called printXNumbers.

```
for i in range(1, 21):
print i
```

- This program prints pairs of jazz songs.

```
jazzSongs = ["Strange Fruit", "Lush Life",
"God Bless the Child", "How High the Moon",
"Mack the Knife (in Berlin)", "At Last",
"What a Wonderful World", "My Fun Valentine",
"Girl from Ipanema", "Fever"]
jzLen = len(jazzSongs)
for i in range(0, jzLen, 2):
print "%s <=> %s" % (jazzSongs[i], jazzSongs[i+1])
# for i in range(jzLen / 2):
# print "%s <=> %s" % (jazzSongs[i], jazzSongs[-i-1])
```

- Some more questions possibly made up on the fly...