Exam Prep Session

We have covered the following topics:

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.  

Stack, Queue, and Priority Queue ADTs

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.

Sorting

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  

Recursion

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

Graph Traversals

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?

Heaps

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.

Binary Trees, BSTs, Balanced BSTs

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

Graph Implementation

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?

Dictionary ADT, Hash Tables

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?