Lesson 3.2 Discovering Algorithms through AI-Enhanced Learning
Lesson 3.2 Introduction to Algorithms
Deep Dive: Types of Algorithms and Applications
Deep Dive: Types of Algorithms and Applications (60 minutes)
Objective: Learn about and explore specific algorithms.
a. Euclid’s Algorithm (GCD)
- The Euclidean algorithm, also known as Euclid's algorithm, finds the greatest common divisor (GCD) between two numbers.
- Example: A 24×60 rectangular area can be divided into grids of square tiles. The largest tile size is the GCD, which is 12.
- 24 = 12 × 2
- 60 = 12 × 5
- Divide the area into 2 × 5 = 10 tiles of size 12 × 12.
- Activity: Use ChatGPT to calculate the GCD of example numbers. Solve a GCD problem together as a class.
b. PageRank Algorithm
- Developed by Larry Page and Sergey Brin in 1996 to rank web pages in search engines.
- Definition: A search engine ranks pages based on their relevance and connectivity.
- Activity: Ask ChatGPT to explain how PageRank works in simple terms. Discuss how search engines like Google, YouTube, and TikTok use similar algorithms.
c. Sorting Algorithms (Bubble Sort, Merge Sort)
- Bubble Sort: Iteratively compares and swaps adjacent elements if they’re in the wrong order.
- Merge Sort: Divides the array into halves, sorts each half, and then merges them using a divide-and-conquer strategy.
- Activity: Use ChatGPT to generate visuals or step-by-step explanations of sorting methods. Students create small arrays and manually simulate sorting them.
d. Heuristic Algorithms
- Definition: Algorithms that focus on efficiency, often offering approximate solutions to complex problems.
- Examples: Traveling Salesman Problem: Optimize a route to visit multiple cities. Sudoku: Solve puzzles efficiently.
- Activity: Use ChatGPT to explore real-world heuristic solutions and discuss their trade-offs.
e. Gale-Shapley Algorithm (Stable Matching)
- Definition: Matches participants (e.g., students and colleges) in a mutually satisfactory way.
- Activity: Simulate a simple stable matching scenario in class (e.g., matching students to favorite subjects). Use ChatGPT to compare the simulated results.