Graphs

• Abstract data type
• Used to represent relationships or connections between objects (nodes/vertices) using edges (links).
• Weighted Graph: A graph in which each edge has a numerical value (weight) representing cost, distance, or time associated with that connection.
• Unweighted Graph: A graph in which edges do not have any weights; all connections are considered equal.
• Directed Graph (Digraph): A graph where edges have a direction, indicating a one-way relationship from one node to another.
• Undirected Graph: A graph where edges have no direction, indicating a two-way or mutual relationship between nodes.
• Uses of Graph
  • Pathfinding and Navigation
  • Network Analysis
  • Resource Optimization
  • Decision Making
  • Problem Solving: Model puzzles, mazes
  • Machine learning and AI
• Dijkstra’s Algorithm: Finds the shortest path from a starting node to all other nodes in a weighted graph.
• A* Algorithm: Finds the shortest path using both the cost so far and a heuristic¹ estimate to the goal.

Dijsktra’s Algorithm

• Give the starting node a distance of 0, and other notes to infinity.
• Put all nodes in a list, ordered by their current distance.
• Repeat while the list is not empty:
  • Take the node with the smallest distance from the front of the list.
  • Mark this node as visited.
  • Check each unvisited neighbour of this node.
  • Calculate the new distance:
    New distance = current node distance + distance to neighbour
  • If the new distance is smaller than the neighbour’s current distance
    • Update the neighbour’s distance.
    • Reorder the list so the smallest distance is at the front.
• Continue until all nodes have been visited or the destination is reached.

A* Algorithm

• Popular and efficient pathfinding and graph traversal algorithm
• Used to find the shortest path between a start node and a goal node
• Uses heuristic h(n) along with distance
• A* chooses the next node to explore based on the lowest total cost function: f(n) = g(n) + h(n)
• Performance depends heavily on the heuristic.

Steps

1. Start at the start node
   1. Write it in your table, g = 0, h = given value, f = g + h
2. Pick the node with smallest f
   1. Look at all nodes in your table
   2. Choose the node with lowest f value - this will be the next node to expand
3. Find its neighbours
   1. For each neighbour of the node
      1. Calculate new g: Add the step cost from start to that neighbor
      2. Calculate f = g + h
   2. Write these neighbours and their values in your table
4. Mark the current node as done
   1. You don't need to expand it again later
   2. You can note its parent (the node from which you reached it)
5. Repeat
   1. Again, pick the node with the lowest f
   2. Expand it, update table and continue
6. Stop
   1. When the goal is chosen for expansion - Path is found
   2. Trace back using the parent column to see the full path
7. Repeat
   1. Again, pick the node with lowest f
   2. Expand it, find its neighbors, update table
8. Stop or Continue
   1. If the goal node is chosen for expansion - Path found
      1. Trace back using the parent column
   2. If not yet at goal, go back to step 2 and keep repeating

Artificial Neural Networks (ANNs)

• Inspired by the human brain.
• Consist of layers of interconnected nodes (neurons).
• Help AI systems learn patterns and relationships from data.
• Each input node has a weight; the weighted inputs are summed, and an activation function determines the output.
• This process is repeated across layers, enabling reinforcement learning and pattern recognition.
• 3 Layers
  • Input Layer
  • Output Layer
  • Hidden Layers
    • Enable deep learning by processing complex patterns
    • Allow the network to make decisions independently
    • Help increase the accuracy of the output

Machine Learning & Deep Learning

Machine Learning (ML)

• A field of Artificial Intelligence (AI) where computers learn from data and past experiences
• Computers improve their performance on tasks without being explicitly programmed with rules
• Example: Email spam detection, Predicting house prices or stock trends, Recommendation systems

Deep Learning

• A subset of ML that mimics the decision-making and data processing abilities of the human brain.
• Handles very large datasets effectively.
• Can work with unstructured data such as images, audio, or text.
• Able to discover hidden patterns within the data.
• Example: Image and speech recognition, Self-driving cars detecting objects and pedestrians, Natural language processing

Machine Learning Categories

Supervised Learning

• The computer is provided with labeled training data
• It identifies patterns that explain why each data point has a specific label
• These learned patterns are then used to predict labels for new, unseen data
• Example: Teaching a computer to recognize fruits by showing labeled pictures of apples, bananas, and oranges.

Unsupervised Learning

• The computer is provided with unlabeled data.
• It identifies patterns or groupings in the data on its own.
• These patterns are used to organize or cluster the data for insights, without pre-defined labels.
• Example: Giving a computer a bunch of unlabeled fruits and letting it group them by color or size.

Reinforcement Learning

• The computer (agent) learns by trial and error.
• It receives rewards for good actions and penalties for bad actions.
• Over time, it learns the best actions to maximize rewards.
• Example: Teaching a child to read: if the child reads a word correctly, they receive smiles and praise; if incorrect, they receive disapproval from the parents.
• Examples: Training robots to perform tasks, Game-playing AI

Regression & Backpropagation

Regression

• The process of finding a mathematical function that best models past data, allowing us to predict future values based on previous results.
• Example: Predicting house prices, stock trends, or temperature.

Backpropagation of Errors

• A technique used in neural networks to adjust weights.
• Errors from the output layer are propagated backward through the network.
• Helps improve accuracy by minimizing the difference between predicted and actual outputs.
• Example: Backpropagation is like kicking a ball toward a goal: if it misses, you adjust your aim and strength based on the error and repeat until it consistently hits the center