1. YSC2229 Lecture Notes, Week 01

• 1.1. Introduction
  • 1.1.1. About this course
  • 1.1.2. What problems are solved by algorithms?
  • 1.1.3. Data structures
  • 1.1.4. What is analysis of algorithms?
  • 1.1.5. Useful Resources
  • 1.1.6. Exercise 1
  • 1.1.7. Exercise 2
• 1.2. Exercises
  • 1.2.1. Mandatory exercises
  • 1.2.2. Recommended exercises
• 1.3. Correctness of Recursive Algorithms
  • 1.3.1. Warm-up: finding a minimum in a list of integers
  • 1.3.2. Reasoning about termination
  • 1.3.3. Exercise 3
  • 1.3.4. Reasoning about correctness
  • 1.3.5. Exercise 4
• 1.4. From Recursion to Imperative Loops
  • 1.4.1. Loop variants
  • 1.4.2. Loop invariants
  • 1.4.3. Exercise 5
  • 1.4.4. Exercise 6
• 1.5. Sorting Lists via Insertion Sort
  • 1.5.1. Insertion sort implementation
  • 1.5.2. Correctness of sorting
  • 1.5.3. Exercise 7
  • 1.5.4. Sorting invariants
  • 1.5.5. Exercise 8
• 1.6. Exercises
  • 1.6.1. Mandatory exercises
  • 1.6.2. Recommended exercises

Supplementary materials

• Code from Week 1: finding minimums and sorting lists.
• Intro slides