2. YSC2229 Lecture Notes, Week 02

• 2.1. Arrays and Operations on Them
• 2.2. Insertion Sort on Arrays
  • 2.2.1. Tracing Insertion Sort
  • 2.2.2. Insertion Sort Invariants
  • 2.2.3. Termination of Insertion Sort
  • 2.2.4. Exercise 1
• 2.3. Selection Sort
  • 2.3.1. Tracing Selection Sort
  • 2.3.2. Invariants of Selection Sort
  • 2.3.3. Termination of Selection Sort
  • 2.3.4. Exercise 2
  • 2.3.5. Exercise 3
  • 2.3.6. Exercise 4
  • 2.3.7. Exercise 5
• 2.4. Exercises
  • 2.4.1. Mandatory exercises
  • 2.4.2. Recommended exercises
• 2.5. Complexity of Algorithms
• 2.6. Order Notation
  • 2.6.1. Big O-notation
  • 2.6.2. Properties of Big O-notation
  • 2.6.3. Little o-notation
  • 2.6.4. Proofs using O-notation
  • 2.6.5. Hierarchy of algorithm complexities
  • 2.6.6. Complexity of sequential composition
  • 2.6.7. Exercise 6
  • 2.6.8. Exercise 7
  • 2.6.9. Exercise 8
  • 2.6.10. Exercise 9
• 2.7. Sums of Series and Complexities of Loops
  • 2.7.1. Arithmetic series
  • 2.7.2. Geometric series
  • 2.7.3. Estimating a sum by an integral
  • 2.7.4. Big O and function composition
  • 2.7.5. Complexity of algorithms with loops
  • 2.7.6. Exercise 10
  • 2.7.7. Exercise 11
  • 2.7.8. Exercise 12
• 2.8. Exercises
  • 2.8.1. Mandatory exercises
  • 2.8.2. Recommended exercises

Supplementary materials

• Code from Week 2: basic array sorting.