95-771 DSA Review for midterm Topics 1-13

1. Preconditions, postconditions, procedural abstraction, and class invariants
2. Big O, Big Omega, Little o, and Big Theta
3. Linked Lists
4. Stacks and queues and alternative representations
5. Tree terminology (degree, depth, height, complete, full)
6. For complete trees:
    Given height, compute number of leaves
    Given the number of leaves, compute the height
    Given the height compute the number of internal nodes
    Given the height compute the total number of nodes
    Given the total number of nodes, compute the height
7. Tree traversals: Preorder, inorder, postorder, levelorder
8. Trees represented in arrays
9. Heaps (max or min) and reduce key
10. B-Trees (insert and delete) Red Black Trees (insert) B+ Trees (insert)
11. Graphs and their alternative representations
12. Graph traversals (BFS,DFS)
13. Graph coloring
14. Graph algorithms (Dijkstra, Prim, Floyd-Warshall)
15. Implementing Dijkstra in O((n+e)lg n) and O(n^2)
16. Branch and Bound and TSP
17. Searching (serial, binary)
18. Hash tables (O-A Hashing and chained hashing)
19. Knuth's approach to double hashing
20. Tough school boy hashing
21. DST and Radix Tries