Material: Textbook (Goodrich/Tamassia), Chapters 1, 2, 3.1, 3.2, 4.1, 4.3, 4.8, and Chapter 5.

• Complexity Analysis
  
  • Asymptotic notation, concept of big Oh, Omega, etc.
  • Methods to analyze complexity of algorithms.

• Basic Data Structures
  
  • Stacks, Queues, Priority Queues.
  • Priority Queue using Heap; two methods of Heap construction (top down and bottom-up; which one is faster).
  • Tress, binary trees; tree traversal (preorder, postorder, etc.)
  • Dictionaries and Hash functions; chaining methods (separate, open)
  • Binary search trees; insertion and deletion of elements.

• Sorting Algorithms and their Complexity
  
  • Selection sort, insertion sort.
  • Heap sort.
  • Merge sort, quick sort

• Fundamental Algorithmic and Optimization Techniques
  
  • Greedy method, examples; conditions for optimum solutions.
  • Divide and Conquer, examples, sorting algorithms; recurrence equations.
  • Dynamic Programming; Bellman's principle of optimality, examples; recurrence equations.

• Applications to VLSI CAD
  
  • Channel routing, left edge algorithm, conditions of optimality.
  • Channel ordering, topological sorting.
  • Floorplans: slicing, non-slicing, graph representation.

  Good Luck.

  ---