How can you teach computer science algorithms to middle school students?

This is second part of my article about teaching computer science at Community Montessori School, Tampa. In previous article , I shared what I taught about computer science and software engineering job. In this article, I will write about how I taught computer science algorithms to 7 to 9th grade students.

How I prepared?

I introduced flowcharts to them so that they could learn to represent algorithms.

I wanted to teach them a simple and most practical algorithm. I figured search algorithm would be best choice. I easy to explain sequential search. Then I can show them how it can be improved by using binary search algorithm.

To make it fun, I used guessing number game problem and demonstrated how binary search logic can be applied to guessing number game.

Transcript

Here is the complete transcript of the talk.

What is Search Algorithm?

A search algorithm is the step-by-step procedure used to locate specific data among a collection of data.

Search Algorithm Examples in computers

We do search in computers for many things. For eg. We search for products to buy in Amazon, we look for movies in Netflix. We use google to search across everything on the internet.

What is a Flowchart?

A Flowchart is a type of diagram used to represent algorithms.

These are most commonly used shaped to draw a flowchart

• A Oval shape is used to represent a terminal instruction like Start or Stop.
• A parallelogram shape is used to define data. For eg. Reading a input data from user.
• A rectangular shape is used for describing instructions or actions.
• A diamond shape is used to representing a logical decision.
• Arrows are used to connect them to illustrate the flow.

Operators

There are few differences between mathematical and computer operators.

• Since mathematical multiply symbol X can also mean alphabet X, a asterisk ( * ) is used for multiplication.
• Instead of percent ( % ) , a forward slash (/) is used for division.
• % is used for reminder operation.
• Since single equals sign ( = ) is used for assignment, double equals sign ( ==) is used for checking equality.
• For “greater than or equals” and “lesser than or equals” comparisons a equal sign is placed next to greater than ( > ) or lesser than ( < ) symbols.

What are variables?

A variable associates a name to a value or result of an operation.
``Examples: ``
``A = 10 ``
``x = x + 1``

How to Represent collection of Items?

The Array is the simplest way to store a bunch of items in computer memory.

``Examples: ``
``Array primes = [2, 3, 5, 7, 11,                13, 17, 19, 23, 29,                31, 37, 41, 43, 47,                53, 59, 61, 67, 71,                73, 79, 83, 89, 97]``

How to Look up values in Array?

Values in array can be looked up using index operator `variableName[index]`

``primes[0] = 2primes[1] = 3....primes[24] = 97``

In computer science, index always starts with 0

Problem: Check if a number is Prime

Let’s say we have all prime numbers less than 100 stored in a array primes Given any number N between 1 and 100, tell if the number is a prime by searching the array primes.

Sequential Search Algorithm

• We read the input number to check to variable `N`.
• We use variable `i` to track current position. We initialize it’s value to `0`.
• We check if the number in primes array at current index position `primes[i]` is equal to number we are looking for `N`.
• If yes, we declare `N` is prime.
• If no, we move to the next position by incrementing position tracker `i`.
• We repeat the steps until i becomes greater than size of array ( 25 ).
• If we exit after `i > 25`, then we didn’t find the number, so we say `N` is NOT a prime.

This algorithm works, But can you think of better solution? Is there a way we can minimize number of repetitions we have to do ?

Binary Search Algorithm

• We read the input number to check to variable `N`.
• We use two variables `start` and `end` to track boundaries. We initialize their values to `0` and `24` respectively
• We compute the current position `i` as middle value between `start` and `end`
• We check if the number in primes array at current index position `primes[i]` is equal to number we are looking for `N`.
• If yes, we declare `N` is prime.
• Else if `primes[i]` is smaller then `N` , we can discard all the numbers below `primes[i]` , so we move `start` to next position. i.e `start = i + 1`
• Else if `primes[i]` is greater then `N` , we can discard all the numbers above `primes[i]` , so we move `end` to previous position. i.e `end = i — 1`
• We repeat the steps until `start` and `end` cross each other i.e `start` becomes greater than `end`
• If we exit after `start > end`, then we didn’t find the number, so we say `N` is NOT a prime.

This is efficient, we are able to discard half of the numbers in the array on each iteration. So on an average binary search algorithm need to do less work than sequential search algorithm.

In school I used index cards with numbers & markers for demonstrating like below

Limitations of Binary Search

The binary search will work only if collection is pre-sorted. If numbers are in random order, we can’t apply binary search.

Other Techniques for Search

• Indexing like in books or dictionaries is another technique to make searching faster. The google search uses a very complex indexing algorithm.
• Categorizing For e.g. organizing library books in various shelves for fiction, non-fiction, language etc. would help find things things faster.

Basically, if you have better organized your stuff, searching will be come easier!.

Guessing Number Game

1. Think of a number between 1 and 100.
2. Computer will make a guess and you will answer whether the guess is correct or low and higher than the computer’s guess.
3. Computer will make next guess based on the information and you will respond again with correct or low or high.
4. Repeat this until computer makes right guess.

Can you come up with an algorithm for computer to solve this?

Guessing Number Game Algorithm

We pretty much use the same logic we learnt in binary search to solve the guessing number game.

• We initialize the variable `low` and `high` to boundary values `0` and `101`
• Computer will make a `guess` as middle number between `low` and `high`.
• We read user’s response to variable `answer`.
• if answer is ‘y’ , we say “Well done!, the number you though is `guess`
• Else if answer is ‘l’ (i.e your number is larger than computer’s guess), so you update `high` to `guess` . So that in next try, computer can make smaller guess.
• Else if answer is ‘s’ (i.e your number is larger than computer’s guess), so you update `low` to `guess` . So that in next try, computer can make larger guess.
• This will repeat until computer can figure out your number.

References

Computer Science Distilled Book

In the next part, I have written about how I taught programming using python.