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. BST (insert and delete), B Trees (insert), 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