Study Plan 7

with notes

• 2 min read

Graphs & Heuristics - Study Plan & Notes

✅ Study Plan

Day 1: Introduction to Graphs

  • Understand what a graph is (nodes + edges)
  • Learn types of graphs (directed, undirected, weighted, unweighted)
  • Real-world applications (social networks, navigation, recommendation systems)
  • Complete Popcorn Hack #1

Day 2: Heuristics

  • Define what a heuristic is
  • Compare brute-force vs heuristic approaches
  • Learn Greedy Algorithm & A* Search
  • Complete Popcorn Hack #2

Day 3: Traveling Salesman Problem (TSP)

  • Understand TSP and why it’s hard
  • Learn about exponential route growth
  • Study heuristic solutions like Nearest Neighbor
  • Complete Popcorn Hack #3

Day 4: Homework

  • Research “Social Network Analysis”
  • Explain how graphs are used in social platforms
  • Give a real-world example

🧠 Notes

1. Introduction to Graphs

Definition
A graph is a data structure used to model relationships between objects.

  • Nodes (Vertices): Entities
  • Edges: Connections between entities

Types of Graphs

  • Undirected Graphs: Edges go both ways (e.g., Facebook friendships)
  • Directed Graphs: Edges have direction (e.g., Twitter followers)
  • Unweighted Graphs: All edges equal
  • Weighted Graphs: Edges have a cost (e.g., distance in a map)

Applications

  • Social Networks
  • Navigation Systems (e.g., Google Maps)
  • Recommendation Engines (e.g., Netflix)

🧠 Popcorn Hack #1

True/False: In a directed graph, an edge from A to B implies an edge from B to A.
Answer: False

3. Heuristics

Definition
A heuristic simplifies problem-solving using practical methods or rules of thumb.

Examples

  • Greedy Algorithm: Take best immediate step
  • A* Search: Uses cost + heuristic to find the shortest path

Real-World Analogy

  • Brute-force: Check every shelf in a library
  • Heuristic: Go straight to the relevant section

Applications

  • Route planning (Google Maps)

🧠 Popcorn Hack #2

True/False: Heuristics always provide faster solutions than exact algorithms but may sacrifice accuracy.
Answer: True

Traveling Salesman Problem (TSP)

Definition
Find the shortest route that visits all cities once and returns to the starting point.

Why It’s Hard

  • Route possibilities = (n-1)!
  • Example:
    • 4 cities → 6 routes
    • 10 cities → 3,628,800 routes
    • 100 cities → more routes than atoms in the universe!

Heuristic Solution Example

  • Nearest Neighbor Algorithm: Visit the nearest unvisited city

🧠 Popcorn Hack #3

True/False: Heuristics like Nearest Neighbor can never guarantee optimal TSP solutions.
Answer: True

📚 Homework Assignment

Topic: Social Network Analysis

Question: How are graphs used to analyze social networks?

Answer Template:

  • Nodes: Represent users
  • Edges: Represent relationships (friends, followers, etc.)
  • Example Platform: Instagram
    • Users (nodes)
    • Follow relationships (directed edges)
    • Graph theory helps suggest new connections or communities