You must complete the pre-reading before each class:

✔️ Pre-reading for Tuesday 2/2
✔️ Pre-reading for Thursday 2/4

---

Pre-Reading for Intro to Analysis of Algos, Tuesday 2/2

Essential Questions

Before attending class, please complete the material below and use the following questions to guide your note-taking:

✔️ Why is time complexity important?
✔️ What are common order-of-growth classifications? ✔️ What are the differences between Big-O, Big-Omega, and Theta?
✔️ What is the process for analyzing the time complexity of an algorithm?

Read/Watch/Review

Before attending class, please complete the material below:

• Read Gaddis 9.6: Introduction to Analysis of Algorithms
• Watch Analyzing Algorithms (15 min)
• Watch Big O Notation (14 min)
• Explore Common Complexities, Graphed
  • When I say explore, I mean zoom in and out, add constants, compare values at small vs large x values, etc.
• Read Asymptotic Notations
• Watch Asymptotic Bounding 101: Big O, Big Omega, & Theta (23 min)

In Class

In today’s class we’ll be analyzing and comparing the time complexity of simple algorithms. We’ll also talk briefly about why we can’t just manually time algorithms, and why asymptotic analysis is important.

---

Pre-Reading for Basic Sorting Algos (Implementation), Thursday 2/4

Essential Questions

Before attending class, please complete the material below and use the following questions to guide your note-taking:

✔️ What’s the difference between stable and unstable sorting and why does it matter?
✔️ How does bubble sort work?
✔️ How does selection sort work?
✔️ How does insertion sort work?

Read/Watch/Review

Before attending class, please complete the material below:

• Read Stable Sorting Algorithms
  • You can ignore section 3.3 “Radix Sort”
• Watch Stable Sort vs Unstable Sort Algorithms (4 min)
• Read The Bubble Sort
  • You can ignore the runtime analysis for now (after the animation)
• Watch Introduction to Bubble Sort (8 min)
• Watch Bubble Sort (1 min)
• Read The Selection Sort
  • You can ignore the runtime analysis for now (after the animation)
  • Note: The reading has you find the largest element each time whereas the videos have you find the smallest element– either approach is fine.
• Watch Introduction to Selection Sort (11 min)
• Watch Selection Sort (2 min)
• Read The Insertion Sort
• Watch Introduction to Insertion Sort (13 min)
• Watch Insertion Sort (2 min)

In Class

In today’s class we’ll be debugging implementations of basic sorting algorithms.