3. YSC2229 Lecture Notes, Week 03

• 3.1. Complexity of Simple Recursive Algorithms
  • 3.1.1. Complexity of computing the factorial
  • 3.1.2. Method of differences
  • 3.1.3. Recurrence relations
  • 3.1.4. First-order recurrence relations
  • 3.1.5. Inhomogeneous recurrence relations
  • 3.1.6. Exercise 1
  • 3.1.7. Complexity of recursive matrix determinant
  • 3.1.8. Exercise 2
  • 3.1.9. Exercise 3
• 3.2. Exercises
  • 3.2.1. Mandatory exercises
  • 3.2.2. Recommended exercises
• 3.3. Generating Arrays
  • 3.3.1. Simple random generators
  • 3.3.2. Measuring execution time
  • 3.3.3. Randomised array generation and testing
  • 3.3.4. Exercise 4
• 3.4. Searching in Arrays
  • 3.4.1. Linear Search
  • 3.4.2. Exercise 5
  • 3.4.3. Binary Search
  • 3.4.4. Exercise 6
  • 3.4.5. Binary Search Invariant
  • 3.4.6. Exercise 7
  • 3.4.7. The Main Idea of Divide-and-Conquer algorithms
• 3.5. Merge Sort
  • 3.5.1. Merging two sorted arrays
  • 3.5.2. Invariant of merge
  • 3.5.3. Main sorting procedure and its invariants
  • 3.5.4. Exercise 8
  • 3.5.5. Exercise 9
  • 3.5.6. Exercise 10
• 3.6. Exercises
  • 3.6.1. Mandatory exercises
  • 3.6.2. Recommended exercises

Supplementary materials

• Code from Week 3: binary search and merge sort.