Syllabus for Test4

  1. The modified master method of solving recurrence.
  2. The interation method or recursion-tree method of solving recurrence (page-67).
  3. The substitution method of solving recurrence (page-63).
  4. Sorting algorithm basics (terminology, like in-place, stable, etc.).
  5. Binary heaps (page-127).
  6. Operations in binary heap (Hepify, Buildheap, HeapFindMax, HeapExtractMax, HeapIncreaseKey, HeapInsert).
  7. The Heapsort algorithm (page-135).
  8. Priority Queues (page-138).
  9. Description of Quicksort (page-145).
  10. Performance (or running time) of the Quicksort (page-149).
  11. A randomized version of the quicksort (page-153).
  12. Lower bounds for sorting (page-165).