Graphs Heuristics Undecidable Problems Kahoot

Heurisitics

Lesson on Heuristics

• 2 min read

Teaching Heuristics

Introduction to Heuristics

Heuristics in computer science are problem-solving techniques that provide “good enough” solutions when optimal ones are too complex or costly. They are essential for solving computational problems efficiently, especially with large data sets or when optimal solutions are expensive to compute.

In the AP Computer Science Principles (AP CSP) curriculum, heuristics help students tackle complex problems where traditional algorithms may be inefficient. Here’s a guide to how the College Board defines and teaches heuristics:

College Boards Definition of a Heuristic

“A heuristic is an approach to a problem that produces a solution that is not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical.” — AP Computer Science Principles Course and Exam Description, College Board

Exclusion Statement (AAP-4.A.9): “Specific heuristic solutions are outside the scope of this course and the AP Exam.” — AP Computer Science Principles Conceptual Framework, College Board

  • Meaning they are not required to learn specific heuristic algorithms fo the AP CSP exam

Examples of Heuristics in Coding

1. Nearest Neighbor Heuristic

Used in problems like the Traveling Salesperson Problem (TSP). The algorithm picks the closest unvisited location at each step. It’s fast, but not always optimal.

2. Greedy Algorithms

These algorithms make the best immediate choice at each step. A common example is the Greedy Coin Change algorithm, which picks the largest coin first. It works well in many cases, but not all.

3. Heuristic Search Strategies

In pathfinding problems, estimates like Manhattan Distance or Euclidean Distance help search algorithms (like A*) find solutions faster by guessing which path is best to try next.

Heres a flowchart of a Heurisitc Algorithm

Heuristic Search Flowchart

Image

Source: View on ResearchGate

Setting up the Greedy Coin Change Algorithm

Greedy Coin Change

🪙 Greedy Coin Change Algorithm

🔄 Popcorn Hack: Reverse the Greedy Strategy!

You’re looking at a greedy algorithm that picks the largest coin first. Try flipping it!

  • 🔁 Change coins = [25, 10, 5, 1] to [1, 5, 10, 25]
  • 🧠 See how it affects the number of coins used
  • 📊 Reflect: is it more or less efficient? Is it perfect? Is it good enough?

AP CSP Concepts: Algorithm, Abstraction, Efficiency

Click below to reveal the code:

def greedy_coin_change(amount, coins=[25, 10, 5, 1]): change = [] for coin in coins: while amount >= coin: amount -= coin change.append(coin) return change # Example usage: amount = 63 result = greedy_coin_change(amount) print(f"Change for {amount}¢: {result}") print(f"Total coins used: {len(result)}")

Sorting Algorithms

Heuristics help decide which sorting algorithm to use. For example:

  • Insertion Sort is chosen when dealing with small datasets, as it is simpler and faster for small inputs.
  • Merge Sort or Quick Sort is better for larger datasets as they have better time complexity.

Homework Hacks

Wrap-Up: What Did You Learn About Heuristics?

Take a moment to reflect or turn and talk:

  • How did changing the order of coins affect the result?
  • Which algorithm used fewer coins?
  • Where might greedy algorithms work well? Where might they fail?
  • What is one thing you changed, and what did it show you?
  • Write a 2-3 Sentence Summary of all these questions.