4. Chapter 04: Divide-and-Conquer Algorithms

• 4.1. Searching in Arrays
  • 4.1.1. Linear Search
  • 4.1.2. Binary Search
  • 4.1.3. Binary Search Invariant
  • 4.1.4. The Main Idea of Divide-and-Conquer algorithms
• 4.2. Merge Sort
  • 4.2.1. Merging two sorted arrays
  • 4.2.2. Main sorting procedure and its invariants
• 4.3. Quicksort and its Variations
  • 4.3.1. Partitioning an array
  • 4.3.2. Partitioning in action
  • 4.3.3. Sorting via partitioning
• 4.4. Complexity of Divide-and-Conquer Algorithms
  • 4.4.1. Changing variable in recurrence relations
  • 4.4.2. Complexity of Merge Sort
  • 4.4.3. Complexity of Quicksort
  • 4.4.4. The Master Theorem
• 4.5. Generalising Comparison-Based Sorting
  • 4.5.1. Comparator as a parameter
  • 4.5.2. A functor for sorting
• 4.6. Exercises
  • 4.6.1. Exercise 1
  • 4.6.2. Exercise 2
  • 4.6.3. Exercise 3
  • 4.6.4. Exercise 4
  • 4.6.5. Exercise 5
  • 4.6.6. Exercise 6
  • 4.6.7. Exercise 7
  • 4.6.8. Exercise 8
  • 4.6.9. Exercise 9
  • 4.6.10. Exercise 10