AP CSP Big Idea 3 Resource

AP CSP Big Idea 3

1. Binary Search Algorithm 🔍

   • Purpose: Quickly find an item in a sorted list.
   • Steps:
     • Check middle
     • If target < middle, search left half
     • If target > middle, search right half
   • Efficiency: O(log n) — faster than linear search
   • Requirements: List must be sorted beforehand

---

1. Lists and Filtering Algorithms 📋

   • Lists: Variables that hold multiple items (arrays).
   • Operations:
     • Create: list = [1, 2, 3]
     • Access: list[0]
     • Modify: list.append(4)
   • Filtering: Use loops to extract items based on condition.
     • Example: Keep only even numbers
   • Useful for: Data analysis, search features, dynamic displays

---

1. Random Number Generation & Simulations 🎲

   • Random Numbers: Used in games, simulations, security, and testing.
     • RANDOM(a, b): Gives a random integer between a and b (inclusive).
     • Each run can give different results.
     • Examples:
   • Dice roll: random.randint(1, 6)
   • Coin flip: random.randint(0, 1) - Real-World Uses: - Games: dice, card shuffling, enemy behavior - Simulations: weather, traffic - Security: passwords, encryption keys - Simulations: Imitate real-world systems (don’t always need randomness). - Examples:
   • Traffic lights (fixed pattern)
   • Bouncing ball (gravity and motion)
   • Virus spread or weather (often include randomness)

---

1. Big O and Algorithm Efficiency 🧮

   • Big O Notation: Describes the efficiency of an algorithm in terms of time and space.

Common Big O Notations:

• O(1): Constant time – performance doesn’t change with input size.
• O(log n): Logarithmic time – grows slowly as input size increases (e.g., binary search).
• O(n): Linear time – grows with the input size (e.g., loop through an array).
• O(n log n): Linearithmic time – faster than quadratic, used in efficient sorts (e.g., merge sort).
• O(n²): Quadratic time – performance grows quickly with input size (e.g., bubble sort).
• O(2^n): Exponential time – performance doubles with each input (e.g., naive Fibonacci).
• O(n!): Factorial time – grows extremely fast (e.g., traveling salesman problem).

Analyzing Efficiency:

• Best Case: Fastest time (ideal conditions).
• Worst Case: Slowest time (largest input or worst conditions).
• Average Case: Expected time for random input.

Key Takeaways:

• Big O helps compare algorithm performance.
• O(n log n) is often better than O(n²), especially with large data sets.

---

1. Graphs, Heuristics, and Undecidable Problems 📊

Graphs

• Definition: Graphs model relationships with nodes (vertices) and edges (connections).
• Complete Graph: Every pair of vertices is connected by a single edge.
• Uses:
  • Pathfinding (e.g., Google Maps)
  • Web ranking (e.g., PageRank)
  • Network routing (e.g., data transfer)

Adjacency Matrix vs. Adjacency List

• Adjacency Matrix: 2D array with 1’s and 0’s; represents connections between nodes.
• Adjacency List: Array of linked lists; each list stores adjacent vertices of a node.

---

Heuristics 🧠

• Definition: Approximate problem-solving methods when optimal solutions are too complex or costly.
• Examples:
  • Nearest Neighbor: Used in Traveling Salesperson Problem (TSP) to pick the closest unvisited node.
  • Greedy Algorithms: Choose the best immediate option, e.g., Coin Change problem.
  • Heuristic Search: Helps in pathfinding with estimates like Manhattan or Euclidean distances.

---

Undecidable Problems ❌

• Definition: Problems that cannot be solved by any algorithm for all possible inputs (no guaranteed yes/no answer).
• Halting Problem: Cannot predict if a program will stop or run forever.
• Decidable Problem: Can always be solved by an algorithm (e.g., checking divisibility).
• Real-Life Analogy: Predicting whether a friend will ever stop talking (you can’t know for sure without listening).

Key Points

• Undecidable: Some problems cannot have a complete algorithmic solution.
• Decidable: Problems with algorithms that provide a correct answer for all inputs.

---