Unit 6 - Activity 2 Introduction to Search Algorithms

Activity Overview

This activity builds upon students’ understanding of computational pathfinding, introducting the concept of search algorithms and teaching students about the two most commonly used search algoirhtms and how they are used in the real world.

Key Terms and Concepts

  • PATHFINDING is the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes.
  • GRAPHS are sets of vertices connected by edges, where the edges may have a direction associated with them.

    • Key Takeaways:

  • Search enables people to find things in large information spaces, and computer scientists must design algorithms which find desired information efficiently.
  • There are many free, publicly available computer science learning resources available which can enable us to continue to grow our computational problem-solving skills independently.

    • Driving Questions:

  • If we don’t care about how long it takes, what is an algorithm to find a goal node in a graph?
  • If we could explore multiple paths at once, what is an algorithm to find a goal node in a graph?
  • How are these common search strategies used in the real world?
  • How can we continue to learn about computer science outside of school?

    • Materials and Preparation:

    MATERIALS

    1. Computer and Projector
    2. (Optional) Computer Science Resource Brochures or Flyers
    PREPARATION

    Educators should plan to prepare a list of free, fun, and safe resources for students to continue to learn about computer science following the workshop (printed brochures or handouts are recommended for sharing with parents/guardians). Please refer to the Additional Resources section for a list of preliminary online resources recommended for students and their families.

    Please refer to this brochure of computing resources which was created and distributed to our workshop participants for additional resources.

    Activity Instructions

    1. Introduction to Algorithms (15 minutes)
      2.
      • Have students reflect on and review the major points from the previous exercise of transforming the map game into a graph representation.
      • Explain that in computer science, the concept we use to describe the way we think about traversing (or searching) graphs and capturing those strategies with a set of steps is called an “algorithm” which is:
        • a self-contained sequence of actions to be performed
        • like a recipe, or list of steps
        • used for accomplishing a task
      • We consider the map pathfinding strategies we identified before as search algorithms.
      • Define the general “rules” that students will be using to discuss map search algorithms:
        • We always begin at the START node
        • We can only move one level at a time
        • When we list out the order of the nodes we traverse, we don’t repeat any nodes
        • When there is a tie, we will choose the leftmost node first
    2. Breadth-First Search and Depth-First Search (20 minutes)
      3.
      • The breadth first search (BFS) and the depth first search (DFS) are the two most commonly used algorithms used for traversing and searching for a goal node in a graph.
      • When we design search algorithms, it’s important to consider what constraint we care about the most (e.g.: do we have lots of time? vs. do we have lots of computing power?)
      • ASK: If we don’t care about how long it takes, what is an algorithm to find a goal node in a graph?
      • Explain that if we don’t care about how long it would take us and used the Depth-First Search (DFS) algorithm, we would:
        • traverse paths one by one
        • go as far as we can on each path
        • repeat
      • As a method for remembering the algorithm, remind students that “depth” is like “length,” and in this algorithm, we want to go for as long as we can do until we have reached the goal.
      • For example, if we used the DFS algorithm on the following graph, we would visit the root node and then its children nodes until we reached the end node:
      • Explain that this is a simple approach, but is not a good algorithm for “efficiency” (e.g.: in the case of a huge number of nodes), which describes the rate or speed at which an algorithm enables accurately and successfully completing a task.
      • Explain that DFS is a good example of a “brute-force” approach, which is a very general problem-solving technique that consists of:
        • systematically enumerating all possible candidates for the solution
        • checking whether each candidate satisfies the problem's statement
      • ASK: If we could explore multiple paths at once, what is an algorithm to find a goal node in a graph?
      • Explain that if we could explore multiple paths at once (not possible in the map game, but we are just considering this in theory) and used the Breadth-First Search (BFS) algorithm, we would:
      • traverse all possible paths “in parallel” from the start node, level by level
      • continue until the level of the goal node has been reached
      • As a method for remembering the algorithm, remind students that “breadth” is like “width,” and in this algorithm, we are going “wide” by traversing all nodes for whatever given level we are on.
      • For example, if we used the BFS algorithm on the following graph, we would expand 3 levels before reaching the goal node:
      • Explain that Breadth First Search (BFS) is basically used to find a shortest path between any two nodes in a graph.
      • Provide a few example graphs and have students traverse the graph using both DFS and BFS to check for understanding of how these algorithms work and the pros/cons of each.
      • ASK: How are these common search strategies used in the real world? Explain that graphs can be used to represent a large number of real life problems such as road networks, computer networks, social networks such as facebook etc. and have students brainstorm ideas for representing information using graphs and how BFS/DFS could be used in those networks.
      • For example, the following ideas were shared by users to a Quora post about real-world BFS/DFS applications:
        • GPS Navigation systems: Navigation systems such as the Google Maps, which can give directions to reach from one place to another use BFS. They take your location to be the source node and your destination as the destination node on the graph. (A city can be represented as a graph by taking landmarks as nodes and the roads as the edges that connect the nodes in the graph.) BFS is applied and the shortest route is generated which is used to give directions or real time navigation.
        • Computer Networks: Peer to peer (P2P) applications such as the torrent clients need to locate a file that the client (one who wants to download the file) is requesting. This is achieved by applying BFS on the hosts (one who supplies the file) on a network. Your computer is the host and it keeps traversing through the network to find a host for the required file (maybe your favourite movie).
        • Facebook: It treats each user profile as a node on the graph and two nodes are said to be connected if they are each other's friends. Infact, apply BFS on the facebook graph and you will find that any two people are connected with each other by atmost five nodes in between. To say, that you can reach any random person in the world by traversing 5 nodes in between. (I did not run BFS on facebook graph, it is a well known fact). What do you think is the new facebook "Graph Search"? (It is not directly BFS, but a lot of modifications over classic graph search algorithms.)
        • Web Crawlers: It is quite an interesting application. They can be used to analyze what all sites you can reach by following links randomly on a particular website. (Even if you are mildly interested, look into it. It is fun).

    3. Resources for Exploring Computer Science (10 minutes)

      • Have students reflect on the major learnings from all of the previous concepts, activities, and discussions covered.
      • Have students ask any questions they are still curious and/or confused about, and have a group discussion about the topics they found most interesting.
      • ASK: How can we continue to learn about computer science outside of school?
      • Explain that there are free and publically available resources designed to connect students of all ages, parents/guardians, and teachers to science and technology learning opportunities both in-person and online. Encourage students to continue exploring computer science using these free online and in-person resources and try to identity in-person mentors with whom they can follow up and discuss these interests.
      • You can find a brochure containing free information and learning resources related to computer science education online here: http://bit.ly/2vGPeEd
      • For example, you may consider emailing a local college or university’s computer science department to see if there are any students, researchers, and/or professors willing to connect with your learning group for mentorship or even tours. Additionally, there are many technology companies which organize volunteer opportunities for community groups and may be willing to sponsor a field trip to provide a guest speaker.
      • Consider posting resources to a website, sharing them via email with parents/guardians, and/or printing out a hard-copy brochure or flyer for students to take home which include information about free computer science learning resources.

    © MIT Imagination, Computation, and Expression Laboratory 2017.
    This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 United States License.