Syllabus for Test4

  1. The substitution method of solving recurrence.
  2. Sorting algorithm basics (terminology, like in-place, stable, etc.).
  3. A comparative view on all sorting algorithms discussed in the class.
  4. Definition of binary heaps (both max amd min heaps).
  5. Heapify operations in a binary heap.
  6. Buildheap operations in a binary heap.
  7. HeapFindMax operations in a binary heap.
  8. HeapExtractMax operations in a binary heap.
  9. HeapIncreaseKey operations in a binary heap.
  10. HeapInsert operations in a binary heap.
  11. The heapsort algorithm.
  12. Priority queues.
  13. The quicksort algorithm.
  14. Best case and worste case running time of the quicksort.
  15. Lower bounds for comparison based sorting.