L1 Slides – Algorithms.pdf

Lesson 4: Linear search Algorithms  Starter activity Searching for a book Think about how you would instruct someone to find a book: On a randomly ordered bookcase in someone’s bedroom In the fiction section at a library Question: Wo...

Lesson 4: Linear search Algorithms  Starter activity Searching for a book Think about how you would instruct someone to find a book: On a randomly ordered bookcase in someone’s bedroom In the fiction section at a library Question: Would the instructions be the same in both cases? Think, write, pair, share.  Objectives Lesson 4: Linear search In this lesson, you will: Identify why computers often need to search data Describe how linear search is used for finding the position of an item in a list of items Perform a linear search to find the position of an item in a list  Activity 1 Searching for an item Whenever there are lots of items, it’s important to be able to find the one you need. For instance, you might need to look through a clothing rail to find an item in your size or search through a pack of cards for a particular card.  Activity 1 Searching for an item Computers need to search through sequences of data all the time, such as trying to find a file with a particular name on your computer. Another example is using a search engine to find websites on the internet that match certain keywords. When faced with a search problem, you will either have to deal with ordered or unordered sequences of data.  Activity 2 Linear search Linear search is an algorithm that involves checking each item in a list or sequence of data one at a time (hence “linear”) to see if it’s the right item. If you have a list that is not in order, a linear search is the only reasonable way to search through it. In the next slides, you will see an example of how to perform a linear search.  Activity 2 Linear search Each number is hidden under a cup. The cups are arranged in a random order. From the cups, the number to find is 126. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 27 358 62 9 412 126 81 175 408 Take a list of data and an item that is being searched for (the search item).  Activity 2 Linear search Each number is hidden under a cup. The cups are arranged in a random order. From the cups, the number to find is 126. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 27 358 62 9 412 126 81 175 408 current Start from the first item in the list.  Activity 2 Linear search Each number is hidden under a cup. The cups are arranged in a random order. From the cups, the number to find is 126. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 27 358 62 9 412 126 81 175 408 current Compare the item at the current position to the search item.  Activity 2 Linear search Each number is hidden under a cup. The cups are arranged in a random order. From the cups, the number to find is 126. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 27 358 62 9 412 126 81 175 408 current If it is not the item you are searching for, go to the next item in the list.  Activity 2 Linear search Each number is hidden under a cup. The cups are arranged in a random order. From the cups, the number to find is 126. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 27 358 62 9 412 126 81 175 408 current Compare the item at the current position to the search item.  Activity 2 Linear search Each number is hidden under a cup. The cups are arranged in a random order. From the cups, the number to find is 126. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 27 358 62 9 412 126 81 175 408 current If it is not the item you are searching for, go to the next item in the list.  Activity 2 Linear search Each number is hidden under a cup. The cups are arranged in a random order. From the cups, the number to find is 126. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 27 358 62 9 412 126 81 175 408 current Compare the item at the current position to the search item.  Activity 2 Linear search Each number is hidden under a cup. The cups are arranged in a random order. From the cups, the number to find is 126. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 27 358 62 9 412 126 81 175 408 current If it is not the item you are searching for, go to the next item in the list.  Activity 2 Linear search Each number is hidden under a cup. The cups are arranged in a random order. From the cups, the number to find is 126. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 27 358 62 9 412 126 81 175 408 current Compare the item at the current position to the search item.  Activity 2 Linear search Each number is hidden under a cup. The cups are arranged in a random order. From the cups, the number to find is 126. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 27 358 62 9 412 126 81 175 408 current If it is not the item you are searching for, go to the next item in the list.  Activity 2 Linear search Each number is hidden under a cup. The cups are arranged in a random order. From the cups, the number to find is 126. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 27 358 62 9 412 126 81 175 408 current Compare the item at the current position to the search item.  Activity 2 Linear search Each number is hidden under a cup. The cups are arranged in a random order. From the cups, the number to find is 126. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 27 358 62 9 412 126 81 175 408 current If it is not the item you are searching for, go to the next item in the list.  Activity 2 Linear search Each number is hidden under a cup. The cups are arranged in a random order. From the cups, the number to find is 126. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 27 358 62 9 412 126 81 175 408 current Compare the item at the current position to the search item.  Activity 2 Linear search Each number is hidden under a cup. The cups are arranged in a random order. From the cups, the number to find is 126. Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6 Cup 7 Cup 8 Cup 9 27 358 62 9 412 126 81 175 408 current If the item at the current position is equal to the search item, then stop searching.  Activity 2 Algorithm for linear search The instructions for performing a linear search can be written as: 1. Take a list of data and an item that is being searched for (the search item) 2. Repeat steps a-c starting from the first item in the list, until you find the search item or until the end of the list is reached: a. Compare the item at the current position to the search item b. If the item at the current position is equal to the search item, then stop searching. c. Otherwise, go to the next item in the list.  Activity 3 Searching shuffled cards You are now going to perform a linear search on a set of cards: 1. Take 10 cards and choose a card to search for 2. Shuffle the cards thoroughly 3. Place 6 of the 10 cards face down in a single row without looking at them 4. Perform a linear search for your chosen card and fill in the table Rules: you can only turn over one card at a time. You must turn it back over after each comparison. Follow the instructions in groups of 2 or 3 and answer the questions on the Activity 3 worksheet.  Activity 4 Performance of an algorithm In the last activity, you may have noticed that the amount of cards you had to compare to your search card wasn’t always the same. In computer science, it is useful to know how long an algorithm may take to complete under different scenarios. The number of steps an algorithm needs to perform depending on the input data can be expressed as the best and worst-case scenario.  Activity 4 Best-case scenario The best-case scenario occurs when the item you are looking for results in the smallest possible number of steps. In the case of linear search, this happens when the item you are looking for is the very first one in the list. Best-case  Activity 4 Worst-case scenario The worst-case scenario takes place when the item you are looking for results in the greatest possible number of steps. With linear search, this happens when the item you are looking for is the very last one in the list or it isn’t in the list at all. Worst-case  Activity 4 Carrying out a linear search Complete the tasks on the Activity 4 worksheet for performing a linear search.  Plenary Best and worst-case scenario Answer the questions below when performing a linear search on these cards: 1. What card would you need to search for the best-case scenario to occur? 2. What card would give you the worst-case scenario? 3. How many comparisons would it take to work out that a card wasn’t in the set of cards?  Homework Homework: Linear search flowchart Create a flowchart for a linear search using the instructions in the homework sheet as a guide. Due: Next lesson  Summary Next lesson In this lesson, you… Next lesson, you will… Identified why computers often need Investigate another searching to search data. algorithm called binary search. Described how linear search is used for finding the position of an item in a list of items. Performed a linear search to find the position of an item in a list.