CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL

Algorithms (Python)
Coding with Kids > Level 3

Objectives Resources:
● Students will learn about algorithms and how they are used ● Simple Sort - ​https://goo.gl/GKh79F
in real life. ● Bubble Sort - ​https://goo.gl/uhYh8U
● Students will learn how to create and use sorting algorithms ● Merge Sort - ​https://goo.gl/AEtFgI
in Python. ● Leaderboard - ​https://goo.gl/pv9JCS
● Students will be able to explain how a sorting algorithm
works to sort a list of randomly generated numbers.

Pacing:
● 1 class.

Overview
● Concept Review - Lists
○ Discuss how we will use lists when we are sorting and why we use lists as opposed to variables of some other type.
○ (Optional)​ Have students do a list warm up to practice working with lists before moving on to the lesson.
● Introduction to Algorithms
○ Part 1: Talk about algorithms. What are they? What do they solve?
■ Sorting algorithms. Leaderboard.
■ Graph searching (finding a route on a map)
● Mini-Project - Simple Sort
● Mini-Project - Bubble Sort
● (Advanced) Mini-Project - Merge Sort

Notes about Concept

Timing and exercises selection:
● You should expect to spend two classes on this lesson. It is important that in the first lesson students become interested in the
topic, learn the basics and want to learn/practice more.
● The second lesson must serve the purpose of refreshing the student about the topic and making them practice more.
● A good way to approach this lesson is to introduce students to the idea of algorithms and get them interested, then complete the
basic simple search algorithm. After completing the basic simple search, move onto new concepts and return to algorithms in a
month or two to revisit the concept and do more complex algorithms.
WARNING:​ This is a lesson about algorithms. If not presented correctly, it could be really boring to the kids! Please, make sure you do
present this lesson in a fun and engaging way!

Background
In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed. Algorithms perform
calculation, data processing, and/or automated reasoning tasks.

An algorithm is an effective method that can be expressed within a finite amount of space and time and in a well-defined formal language
for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when
executed, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final
ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms,
incorporate random input.

Concept Review - Lists

● It is very important that students who are being taught this lesson have a very good grasp on list usage and knowledge, specifically
how to access specific elements and change elements in a list given an index location.

© 2016 CODING WITH KIDS - www.codingwithkids.com

May not be reproduced or distributed without written permission from Coding with Kids
 CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL

Algorithms (Python)
Coding with Kids > Level 3

● A good warm up would be to create a list of names and an index variable, then loop through the list of names and print/say each
one by accessing the correct item in the list using the index variable.

Possible Issues Introduction to Algorithms in Python

● Experience Level​ - Talk about algorithms. What are they? What do they solve?
algorithms are a difficult ● What is an algorithm?
concept and require a ○ First we will talk about what an algorithm looks like in the real world, how they are used in
certain skill level of
our everyday lives and why they are important.
students, both with lists
■ You can look at the list of algorithms from the WiKi page (or elsewhere) and bring
and conceptually
understanding how both up algorithms that you are familiar with or that they could be familiar with (some
lists and looping through examples follow).
lists works. If students are ○ Sorting algorithm to create a leaderboard in their favorite game? Do they realize that
having a tough time, there are different sorting algorithms and some are slow and some can be fast?
bring everyone back ■ If the list is 10 players, it does not matter. But if it is hundreds of thousands of
together and work players, it is important to implement a very fast algorithm.
through the process
○ Finding the closest server to connect to in a game?
together, explaining each
■ This requires an algorithm to determine which of the available servers is the best
step.
● Interest​ - if not presented to join and may require figuring out:
correctly or ● Which is the least populated (fewest people).
entertainingly, algorithms ● Which has the lowest latency (travel time for information to get from
can become a very boring the data to your game system).
lesson for students to ● Which is physically closest to you (generally reduces latency).
learn. This is why it is ● Which has players that have a low latency to you (so that neither they
incredibly important to
nor you lag when playing together).
link the idea of
● There could be many more...
algorithms to real world
usage of algorithms such ○ Graph searching to find a route on a map (GPS navigation)? Do they know that finding the
as GPS, leaderboards, absolutely optimal path is virtually impossible?
creating randomized ■ (As a background for you, this type of graph searching is an NP-complete
worlds (such as in problem, which means there is exponential complexity and with relatively small
Terraria or Minecraft), number of “nodes” it is computationally impossible to find the optimal route.
etc. With today’s computers it could take longer than the age of the universe to find
the best route. Thus, any solution requires some simplification and the route you
get is not necessarily the best.) You can discuss with the students how the
algorithms may work to find a solution.
○ So what is an algorithm?
■ It is a sequence of operations or instructions (each one being called a “step”),
performed in a specific order, designed to carry out some task.
○ For what are algorithms used?
■ They are used to solve problems (GPS route), perform calculations (Euclidean
algorithm), and more.
■ They are used all throughout our world in anything from computer games to
medical records software to financial management software to school records on
students.
● Now we can discuss ​how ​to use algorithms in the real world.
● Show students the leaderboard project and discuss what is happening in the project and how
sorting is necessary to keep the leaderboard organized from highest score to lowest.

© 2016 CODING WITH KIDS - www.codingwithkids.com

May not be reproduced or distributed without written permission from Coding with Kids
 CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL

Algorithms (Python)
Coding with Kids > Level 3

Mini-Project - Simple Sort

● The simplest sorting algorithm is aptly named as simple sort, and works by swapping element item in the list with the smallest
remaining number in the list, then moving to the next element.
○ The simple sort algorithm starts at the beginning of the list, finds the smallest number in the list, and swaps the first
element with that smallest element.
○ Then it moves onto the second element in the list and finds the second smallest number in the list, and swaps the second
element with the second smallest element.
○ This process is continued until all of the elements have been correctly swapped, and the list is fully sorted.
● Have students start by creating a function that can generate a list of 10 random numbers between -1000 and 1000 and return that
list, it should be called create_list.
● Now talk to students about the idea of swapping two items in a list. ​How can this be done? What do we have to be concerned
with?
○ We cannot simply assign the first value to the second value’s location in the list because we would lose the value of the
second item, and the same would happen if we flipped which one we swapped. How can we keep track of the value we
are replacing so that we do not lose it?
■ We can create a temporary variable (I generally recommend using ​temp​) that we will store the value at the
second location we are swapping, then copy the value at the first location to the second location, and finally copy
the value held in temp to the first location, thus swapping the values!
○ Have students create a new function called swap that takes a list and the 2 indices (list positions) to swap in that list. They
should implement swap as discussed previously.
● Now we can create the simple_sort function which will take a list as a parameter. How can we loop through the list and swap each
item with the next lowest value in order to sort it?
○ First we need a for loop that will loop from 0 to the length of the list (use a range).
○ Inside the loop we keep track of the index which holds the smallest number (in the example it is named mini). At the start
of each loop, ​what index should that be?
■ The current index in the loop, because it could be the smallest number in the list.
○ Now we need to make a second for loop that loops from the current index to the end of the list, because we do not want
to swap the positions in the list which we have already sorted. (Use range between current index and length of list).
○ Inside the nested for loop, we will need to check whether the element held in the location specified by the inner index (j)
is smaller than the element held at the location specified by mini (the index of the smallest number that has been found
so far).
■ If this is true, we want to set mini to the inner index variable (j).
○ After the inner loop ends, we know that we have found the smallest remaining element, and thus it should be swapped
into the location specified by the outer index variable (i). Therefore we want to swap the element at index mini with the
one at index i.
● Print out the list before sorting and after sorting to ensure it works as expected.

Finished Code
import random

#create a random list of numbers

def create_list():
nums = []
for i in range(10):
nums.append(random.randint(-1000, 1000))
return nums

#swaps two elements in a given list.

def swap(lst, i1, i2):
temp = lst[i1]
lst[i1] = lst[i2]
lst[i2] = temp

© 2016 CODING WITH KIDS - www.codingwithkids.com

May not be reproduced or distributed without written permission from Coding with Kids
 CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL

Algorithms (Python)
Coding with Kids > Level 3

#sorts a random list of numbers using simple sort.

def simple_sort(lst):
for i in range(len(lst)):
minimum = i
for j in range(i, len(lst)):
if lst[j] < lst[minimum]:
minimum = j
swap(lst, minimum, i)

#main function that runs the simple sort.

def main():
rlist = create_list()
print(rlist)
simple_sort(rlist)
print(rlist)

main()

Mini-Project - Bubble Sort

● The second algorithm discussed here is bubble sort, named because it “bubbles” up (or down) a list, swapping an element until it
reaches its correct position.
○ The bubble sort algorithm works by starting at the beginning and checking neighboring pairs of elements (starting with
element 2 and element 1) and swapping them if element 2 is less than element 1.
○ Then it continues following the element it is currently on (element 2) and checking its lower neighbor (in the list), if the
neighbor is smaller, it swaps them.
○ This process continues until the element is in the correct location, then the algorithm sets the next element as its current
(element 3) and does the same process.
○ This continues until the entire list is sorted.
● This process is continued until all of the items have been correctly swapped, and the list is fully sorted.
● Have students start by creating a function that can generate a list of 10 random numbers between -1000 and 1000 and return that
list, it should be called create_list.
● Now talk to students about the idea of swapping two items in a list. ​How can this be done? What do we have to be concerned
with?
○ We cannot simply assign the first value to the second value’s location in the list because we would lose the value of the
second item, and the same would happen if we flipped which one we swapped. How can we keep track of the value we
are replacing so that we do not lose it?
■ We can create a temporary variable (I generally recommend using ​temp​) that we will store the value at the
second location we are swapping, then copy the value at the first location to the second location, and finally copy
the value held in temp to the first location, thus swapping the values!
○ Have students create a new function called swap that takes a list and the 2 indices (list positions) to swap in that list. They
should implement swap as discussed previously.
● Now that we have the helper functions set up, we can create the bubble_sort function that takes a list as a parameter. ​How do you
think we should set up the outer loop if we start by comparing the second element with the first element?
○ We create a for loop that runs in the range 1 to the length of the list.
● We need a second index variable which we will call j. ​What should j be set to inside of the outer loop?
○ J should be set to i - 1 because it is the element below i.
● Now we need to continue looping through the neighbors below i until we reach the first element. ​How can we set up a loop that
does this using our second index variable j?
○ With a while loop! The condition will be while j >= 0 (the first location in the list).
● How can we now tell whether we should swap the elements as we examine each? ​Note​: students should use j ​only​ for this inner
loop, as i does not change with j.
○ If the element at index j + 1 is less than the element at index j, swap them!
● What should j change by each time the inner (while) loop executes?

© 2016 CODING WITH KIDS - www.codingwithkids.com

May not be reproduced or distributed without written permission from Coding with Kids
 CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL

Algorithms (Python)
Coding with Kids > Level 3

○ It should change by -1 so that it examines the next lower neighbor in the list.
● Print out the list before and after sorting it to examine the result and ensure that it works correctly.

Finished Code
import random

#create a random list of numbers

def create_list():
nums = []
for i in range(10):
nums.append(random.randint(-1000, 1000))
return nums

def swap(lst, i1, i2):

temp = lst[i2]
lst[i2] = lst[i1]
lst[i1] = temp

#bubble sort a given list of numbers

def bubble_list(lst):
for i in range(1, len(lst)):
j = i - 1
while j >= 0:
if lst[j + 1] < lst[j]:
swap(lst, j+1, j)
j -= 1

#main function that runs the program.

def main():
rlist = create_list()
print(rlist)
bubble_list(rlist)
print(rlist)

main()

(Advanced) Mini-Project - Merge Sort

● Merge sort is the most complex of the sorting algorithms we will discuss in this lesson plan, as it involves a lot more functions and
is a completely different idea than the other two sorting algorithms.
○ Merge sort works by separating a list up into 2 lists, one containing the left half and the other containing the right half.
○ This separation, often called splitting the lists, continues until the lists we are looking at only contain one element (they
have 1 single value in them).
○ At this point, the sorting starts occurring. The next function, merge, performs merging of two halves, sorting each element
into the original list by comparing the value gained from each half to the other values in the list and correctly placing it
into sorted position.
● This algorithm is not noticeably faster when working with small sets of numbers, however it becomes quite a bit faster than either
simple sort or bubble sort when the set becomes large (in the millions, billions, and higher).
● Have students start by creating a function that can generate a list of 10 random numbers between -1000 and 1000 and return that
list, it should be called ​create_list​.
● Now they can start creating the split function, which splits a given list into two halves. Split is a recursive function, meaning it calls
itself, which is how it manages to continue splitting until it is looking at lists of length 1. Recursive functions always need a stopping
condition, ​what do you think might be the stopping condition for this function?
○ We stop if the length of the list is 1 or less.

© 2016 CODING WITH KIDS - www.codingwithkids.com

May not be reproduced or distributed without written permission from Coding with Kids
 CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL

Algorithms (Python)
Coding with Kids > Level 3

○ In this case, the we will create an if statement that does the opposite: if the length of the list is greater than 1, split the list
into 2 lists. ​How can we split the list into two lists?
■ By using list splicing in Python. List splicing can be used to get only certain elements in a list and assign that
subsection to a new list variable. We want to split the list into halves, so first we need to find the midpoint, ​how
can we get the midpoint of the list?
● By dividing the length of the list by 2. Unfortunately, this stops working if the list is not of an even length.
However, this can be fixed by using two divide signs (​//​) which will automatically round the result into
an integer or whole number.
● This value should be stored into a variable, we can call it middle.
■ Now that we have the middle we can split our list into two: we will create two variable, left and right. Left will be
assigned to the first half of the list ​[:middle]​, and right will be assigned to the second half of the list ​[middle:]​.
○ How can we continue splitting the lists that we have just created?
■ By running split recursively with the new lists. This means we run split(left) and split(right).
○ The last thing that needs to be done is to merge the two halves together. This can be accomplished by using the merge
function (which we will create next). For now, put a comment that specifies this point is where we will merge the lists.
● Now we need to merge the split lists together and copy the values into the original list at the correct location so that it will be
sorted.
● Students should create a new function called ​merge​ that will take 3 parameters, each being a list: the original list and the right and
left halves we are currently trying to merge.
○ This merge function will need 3 variables to keep track of:
■ The index we are at in the left list, we will name it ​i​.
■ The index we are at in the right list, we will name it ​j​.
■ The index we are at in the original list, we will name it ​k​.
■ Each of these variables should be set to 0 at the start of the merge function.
○ Next we are going to loop through the two lists and compare elements from each list, finding the smaller one and placing
it into the original list.
■ This first loop will continue while ​i ​is less than the length of the left list and while ​j​ is less than the length of the
right list.
■ What should happen if the value at left[i] is less than the value at right[j]?
● The smaller value (left[i]) should be copied into the original list at the location specified by ​k​.
■ What should happen otherwise?
● The smaller value (right[j]) should be copied into the original list at the location specified by ​k​.
■ After the if-then-else has happened, we have successfully copied the smaller number into the original list at index
k​, so we need to increase ​k​ by 1 so that we put the next smallest element into the next location.
○ After this list, we have 3 possibilities:
■ The list could be sorted and the contents of both lists have correctly been copied into the original list.
■ The left half has been completely copied into the original, but the right half has not.
■ The right half has been completely copied into the original, but the left half has not.
○ What should we do if the left half has not been completely copied?
■ We need to continue looping through the left half and add each of the remaining items to the end of the original
list.
○ How can we accomplish this?
■ With another while loop! Inside this one, we copy left[i] to original[k], then increase both ​i​ and ​k​ by 1.
○ What if the right half has not been completely copied?
■ Another while loop, this one copies right[j] to original[k], then increases both ​j​ and ​k​ by 1.
● After all three of these loops have finished executing, the left and right halves will be merged and copied into the original list.
● Now we have to make sure to call the merge function inside the split function, where should it be run?
○ It should be run right where we put the comment! After the two halves have been split.
● What should we pass the merge function as parameters?
○ Original, left, and right: the 3 lists that we have access to in the function.

Finished Code
import random
#create a randomly generated list of numbers.

© 2016 CODING WITH KIDS - www.codingwithkids.com

May not be reproduced or distributed without written permission from Coding with Kids
 CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL

Algorithms (Python)
Coding with Kids > Level 3

def create_list():
nums = []
for i in range(10):
nums.append(random.randint(-1000, 1000))
return nums

#merges the right and left lists together and places their elements into the original list in
sorted order.
def merge(original, left, right):
i = 0
j = 0
k = 0
#while both of the lists have elements left, place them in sorted order into the original
list.
while i < len(left) and j < len(right):
if left[i] < right[j]:
original[k] = left[i]
i += 1
else:
original[k] = right[j]
j += 1
k += 1
#if i < len(left) then there are still elements in left that have not been sorted into the
original.
while i < len(left):
original[k] = left[i]
i += 1
k += 1
#if j < len(right) then there are still elements in right that have not been sorted into the
original.
while j < len(right):
original[k] = right[j]
j += 1
k += 1

#splits the list into 2 halves, then splits each half in half. Continue until only 1 element
remains in each half list.
def split(alist):
if(len(alist) > 1):
#find middle of list.
middle = len(alist) // 2
left = alist[:middle]
right = alist[middle:]
#split apart the halves
split(left)
split(right)
#merge the halves back together
merge(alist, left, right)

def merge_sort(a):
split(a)

def main():
rlist = create_list()

© 2016 CODING WITH KIDS - www.codingwithkids.com

May not be reproduced or distributed without written permission from Coding with Kids
 CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL - CONFIDENTIAL

Algorithms (Python)
Coding with Kids > Level 3

print(rlist)
merge_sort(rlist)
print(rlist)

main()

© 2016 CODING WITH KIDS - www.codingwithkids.com

May not be reproduced or distributed without written permission from Coding with Kids