List of Topics for Finals

• Analying Algorithms: Big-O notation (including Theta et al.)
  
• List ADT: Linked List, Array Implementation, Doubly Linked List
  
• Java API: Collections (Map/List/Set), Iterators
• Stacks And Queues: ADT, Pointer and array based implementation.
  
• Trees: defination of terms, depth,height path, Infix/postfix/prefix traversals (and expressions)
  
• Binary Search Tree: Find, Insert Delete, Pros and Cons
  
• AVL Trees: Insert, Delete, Single and Double Rotations, Pros and Cons
  
• Splay Trees: Insert, Delete, Zig, ZigZig, ZigZag rotations, Pros and Cons
• Binary Heaps: Priority Queue ADT, Heap order property, Insert, DeleteMin, Percolate Up/Down, Array Implementation
  
• Binomial Queues: Insert, DeleteMin, Adv over Binary Heaps
  
• Hashing : Direct Access Table, Hashing Schemes, Choosing the Hash function, Collison (resolution), Load Factor;; Poisson distribution analysis
  
• Graphs: Terminology, Handshake Theorem, Graph Representations  (Adj List/Matrix), 
  
• Topological Sort: Definition, Queue and Stack implementation
• Depth First and Breadth first Traversals.
  
• Single source shortest path: Dijkstra's algorithm  Bellman Ford Algo (Idea, correctness, implementation,  Run time analysis)
• Flow graphs; maximal flow algorithm.
  
• All-pair Shortest Path: Floyd Algorithm  (Idea, correctness, implementation,  Run time analysis)
• Minimum Spanning Tree: Problem, Kruskal's Prims algorithm (Idea, correctness, implementation,  Run time analysis), Kruskals vs Prim
  
• Disjoint Union/Find: Equivalence classes, Union heuristics (height /rank), Path Compression, Array implementation,
  
• Sorting: Bubblesort, Selection sort, Insertion sort,
  
• ShellSort: (inversions), gap sequences
  
• HeapSort: in-place technique.
  
• MergeSort; constrast with Quicksort
  
• QuickSort: choosing pivot; worst/best/average case examples and complexity
  
• External Sort: disk vs memory issues; runs, merges, using a heap, replacement selection (lightly)
• General sorting issues: comparing algorithms, stability, suitability for various contexts, etc.