In this notebook, I will be showing my coding solutions to the exercises from Khan Academy, in their Algorithms course created by Dartmouth college professors Tom Cormen and Devin Balkcom. Their exercises and solutions are in Java, and so I will attempt to complete their exercises in python, adding my own notes and research as I go along.
It is designed to 'teach introductory computer science algorithms, including searching, sorting, recursion, and graph theory'.
Access it here.
A simple search for an element in a sorted list of size $N$ can take $O(N)$ with a brute force method of checking every element. However, as the list is sorted, you can take the median element, compare to the object, and eliminate the half of the list that excludes your object. Eliminating half the list at each iteration is called the binary search.
#use list of primes as example list
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]
Khan academy example uses a while loop and notes that since the list is already sorted, we can simply use array indices in the comparisons.
def bin_search(user_guess, array):
"""
Conduct a binary search of list array for object user_guess, and prints results.
"""
min_i = 0
max_i = len(array) -1
n = 1
while min_i <= max_i:
guess = (max_i + min_i) //2 #integer division always rounds down
if array[guess] == user_guess:
print("Number is a prime!")
print("It is the %i th prime" % (guess+1))
print("It took %i iterations to find" %n)
break
if array[guess] < user_guess:
#user number is in the upper half
min_i = guess +1
else:
#user number is in the lower half
max_i = guess -1
if n == len(array):
# go to error and break if search longer than linear search, should never occur
print("Search failed, exceeded allowed iterations")
break
n = n+1
else:
print("%i is not a prime" % user_guess)
bin_search(8, primes)
Keep in mind that the exit case of the while loop is when the min index of the interval is greater than the max index. Convince yourself that this is the case, due to the way the algorithm updates the intervals.
If an array is sorted and of length N, then the order of the binary search is at most O($log(N)$), and max number of iterations is $log_2(N) + 1$, when the object is not in the array.
In the above section, we were dependent on the list already being sorted, but what if the list was unsorted? Then we need an efficient algorithm to sort it to ascending order.
The basic idea for each element $i$ is to:
Note: To sort the list into descending order, we simply need to mirror the list with N/2 calls of swap, or create a copy of our smallest sub-element function, but find the biggest instead.
We will now make a function to the first step, finding the index of the smallest value in the array
def min_value(array, startindex):
"""
Create a function that finds the index of minimum value of a subarray, beginning at
a start index
"""
min_test = startindex #initialise with the first index
for i in range(startindex+1, len(array)):
if array[i] <array[min_test]:
min_test = i
return min_test
#Run some tests to ensure it is working
array = [3,-2, 10,40,0,4,10]
print(min_value(array, 2)) #should be 4, array[4] = 0
print(min_value(array, 5)) #should be 5, array[5] = 4
Now we will make the function to swap values in an array.
def swap(array, ind_1, ind_2):
"""
Swap values of array at ind_1 and ind_2
"""
temp = array[ind_1]
array[ind_1] = array[ind_2]
array[ind_2] = temp
#no return as array (a pointer in python) is fed into function
Combining the two functions, minimum value and swap, allows us to do the selection search
##now combine swap and min_value to do selection sort
array = [3,-2, 5,40,0,2,10.2]
def selection_sort(array):
for i in range(len(array)):
min_index = min_value(array, i)
swap(array, i , min_index)
selection_sort(array)
print(array)
The algorithm has two primary loops, the outer most loop of running through each element and putting the next smallest item there in selection_sort, and the inner loop of finding the smallest element in min_value.
Swapping elements in swap is constant time, as no loops or complex functions occur in that function, only assignment and references.
The outer loop is simply $\Theta(N)$, as we need to go through every element. The inner loop with function min_value has $N$ loops for the first element, and then one less at each iteration of the outer loop. So this is also $O(N)$.
Combining these two means that the total complexity is $O(N^2)$
Khan academy subtitles this section as another way to sort that is simple, but not very efficient.
It is similar to selection sorting, only instead of examining an ever decreasing subarray and moving the smallest value to the left, you have an ever increasing subarray and move the value into the correct position.
Insertion sort is analogous to having an ordered set of cards in your hand, the dealer giving you a new card, and moving the new card from right to left to find the right place to sort it.
In pseudo code:
Assume the array from position 0 to $i-1$ are sorted.
Need to consider the fringe cases:
We will now make an insertion sort algorithm, starting with the comparison and insert function.
def insert(value,array,rightindex):
"""
Function that takes in an array pointer, inserts the value into the array up to and including
the rightindex at the correct ascending position.
Assumes array up to rightindex is already sorted.
returns null
"""
for n in range(rightindex+1):
if value > array[rightindex-n]:
array[rightindex-n+1] = value
return
#shift items to the right at every iteration, unless iterations break
array[rightindex-n+1] = array[rightindex-n]
##for loop has proceed to the end with no assignment
array[0] = value
#test fringe case of being greater than whole subarray
test = [2,3,5,11,13,-1,5]
insert(test[4], test,3)
print(test)
#test insertion of smallest value
insert(test[5],test,4)
print(test)
#test insertion of normal case
test = [2,3,5,11,4,13,7,5]
insert(test[4],test,3)
test
def insertsort(array):
"""
Implements insertion sort on an unsorted array
"""
for n in range(1,len(array)):
insert(array[n], array, n-1)
array = [3,6,1,6,-2,0,-1.1,5,80]
insertsort(array)
array
This algorithm again has two primary loops, once in the insert function and once in the insertsort function, which calls the insert function.
The insert function will compare the current key to at most all elements in the subarray, which will eventually reach $n-1$ for the last element in the whole array. This is then an $O(n)$ operation.
The insertsort functions loops over every element in the array, which is $O(n)$, and calls the insert function each loop, which we have already determined is $O(n)$.
The order of the whole process is then the multiplication of the two orders, $O(n^2)$.
Note: the best case scenario, calling insertsort onto an already sorted list, will be $\Theta(n)$, as it will always loop over each index.
Khan academy draws comparisons between recursion and nested Russian dolls, where I think a better comparison is long multiplication or division. The problem, like 245 times 57, is too large to compute on face value, but when broken down into long multiplication, is straight forward.
245
x 57
_______
1715
12250
______
13965The first exercise requests us to make a factorial function that is iterative. Note that python already has an inbuilt function for the factorial in the math package.
import math
math.factorial(6)
def ifactorial(n):
"""
Function that returns the factorial of n.
"""
i=1
#Note that in python, if n=0, the range function will cover this case for us
for j in range(1,n):
i = i*(j+1)
return i
ifactorial(6)
Now Khan academy asks us to try making a recursive factorial function, where to solve n!, we try to solve n*(n-1)!.
def rfactorial(n):
"""
recursive function that returns the factorial of n.
"""
#base case to prevent indefinite repetition
if n==0:
return 1
#recursion
else:
return n*rfactorial(n-1)
rfactorial(6)
A crucial step to the above is the base case, as without it the recursion will not stop. Also note that the above function is poorly written, as if the input is a non-integer or negative, it will never reach the base case.
Note: Python will automatically stop calling recursive functions after some number of calls, based on implementation. To prevent this, you need to amend the function, as in below.
import sys
print(sys.getrecursionlimit())
x=rfactorial(3000)
def rfactorial(n):
"""
recursive function that returns the factorial of n.
"""
assert isinstance(n,int), "Input is not an integer"
assert n>=0, "Input must be a positive integer"
import sys
sys.setrecursionlimit(4000)
#base case to prevent indefinite repetition
if n==0:
return 1
#recursion
else:
return n*rfactorial(n-1)
The lesson raises a good point in this example, in that it considers the fringe cases. Here, they determine that a single letter string is indeed a palindrome, and that an empty string is also a palindrome. These fringe cases are important to consider whenever implementing algorithms, particularly for production! You must have an idea of how it will be used and what the expectations are.
In case it wasn't obvious yet, to determine if a string is a palindrome, we can use recursion! The following pseudocode will be our template:
def isPalindrome(text):
"""
Takes a string text and returns True is text is a palindrome and False otherwise
"""
if len(text)<2:
#string is empty or one character
return True
else:
if text[0] == text[-1]:
#If ends are equal, trim off ends and feed into function again
x = text[1:-1]
return isPalindrome(x)
else:
return False
assert isPalindrome('a') == True
assert isPalindrome('') == True
assert isPalindrome('abcdcba') == True
assert isPalindrome('12xde') == False
The function at best terminates at the first letter when it is not the same as the last, or it is empty or only one letter. This would then be $\Theta(1)$.
The worse case scenario would then be to cycle through all $n/2$ letters on one side of a string of size $n$, comparing them to the other sides $n/2$ letters. This would be $\Theta(n)$.
In summary, the function is $\Omega(1)$ and $O(n)$
The next example is reasonable straight forward and is similar in principle (at least in regards to recursion) to the above example, so I will simply show the solution without saying much more.
def power(x,n):
"""
Return the value of x^n through recursion
"""
#base case
if n ==0:
return 1
if n >0:
if n %2 ==0:
return power(x,n/2)*power(x,n/2)
else:
return power(x,n-1)*x
else:
return 1/power(x,-n)
power(2,-3)
The next exercise use mutliple recursion to generate art and the Sierpinski gasket.
It may be simpler to draw in Java than python, so at this stage I will skip these exercises.
This appears to be the culmination on the lesson of recursion. Here, we can solve Tower of Hanoi problem using recursion!
Without going to the full explanation here, they use the lessons learnt from earlier examples to build their recursive model to show it is indeed solvable, for any size $n$!
Their thoughts are simply:
In those two examples, it is clear we can move at least 2 disks onto any peg (not necessarily B). If we can move 2 disks onto any peg, then we can also move 3 disks onto any peg, by moving 2 out the way, shifting the 3rd onto the desired peg, and then using our 2 disk mov. If we can move 3 disks, then the 4th also comes naturally, and so on.
Here we can clearly see the recursive nature of the solution play out, when we started out at the base case. All the examples of recursion above have this lesson, start at the base case and work from there.
For more interesting examples of how the Towers have been studied (such as rotating computer back ups and even ants!), see the Wikipedia page.
The challenge in the Khan academy tutorial has us write a function to solve the problem for any $n$ disks from peg $A$ to peg $B$. They do this in Java and depict the solution graphically!
Unfortunately python is not so good at drawing, so I will attempt a solution where each move is printed out as a string.
I will start by defining a class which will represent the Tower scenario, and a function to move a disk from one peg to another, ensuring that the move is legal. This will be the first exercise, mostly due to its abstract complexity, where an Object-Oriented Programming approach makes sense, and gives flexibility to examining the scenario.
Note: The traditional solution in other coding languages involves implementing stacks), which is a data structure based around accessing the values in a Last In First Out (LIFO) manner. Python lists make decent stacks (read more detail here), and for simplicity thats what I'll be doing here. The Tower of Hanoi is not memory intensive, but computationally intensive, so the python list type will be fine in this instance.
class Hanoi:
"""
a class to set up a Tower of Hanoi scenario
pegs: list of peg keys
num_disks: int number of disks involved
startpeg: str key of disk where disks are intially placed
"""
def __init__(self,pegs, num_disks, startpeg):
self.towers = {}
self.pegs = pegs
self.num_disks = num_disks
self.startpeg = startpeg
for n in range(len(pegs)):
self.towers[pegs[n]] = []
self.towers[startpeg] = list(range(num_disks,0,-1))
def showstate(self):
"""
Show state of towers
"""
for peg in self.towers:
print(peg,self.towers[peg])
print("\n")
def diskmove(self, frompeg, topeg):
"""
Move a disk from the top of peg frompeg to peg topeg, where frompeg and topeg are
keys to a dictionary towers, where the items are a list with the disks
arranged bottom to top
"""
assert len(self.towers[frompeg]) > 0, "From peg is empty"
disk_num = self.towers[frompeg][-1]
if len(self.towers[topeg])>0:
print("Illegal move, disk %i is bigger\
than top disk ( %i ) on peg %s" % (disk_num, self.towers[topeg][-1],topeg))
return ValueError
self.towers[topeg].append(disk_num)
self.towers[frompeg].pop()
game = Hanoi(['a','b','c'], 4,'a' )
game.showstate()
game.diskmove('a','b')
game.showstate()
game.diskmove('a','b')
Having set the foundations and checked my implementation of the scenario will be functional and intuitive, I will now redefine the class and create the recursive function that will solve the problem.
The key step in solving the Tower of Hanoi problem, is recognising that if you need to move n disks from peg A to peg B, you first must move n-1 disks to the spare peg C, then move the nth disk to peg B, before repeating your moves for the n-1 disks, but moving from peg C to peg B. Therefore, we will also need a function that will give us what the spare peg will be, given our initial peg and our target peg.
class Hanoi:
"""
a class to set up a Tower of Hanoi scenario
pegs: list of peg keys
num_disks: int number of disks involved
startpeg: str key of disk where disks are intially placed
"""
def __init__(self,pegs, num_disks, startpeg):
self.towers = {}
self.pegs = pegs
self.num_disks = num_disks
self.startpeg = startpeg
for n in range(len(pegs)):
self.towers[pegs[n]] = []
self.towers[startpeg] = list(range(num_disks,0,-1))
def showstate(self):
"""
Show state of towers
"""
for peg in self.towers:
print(peg,self.towers[peg])
print("\n")
def diskmove(self, frompeg, topeg):
"""
Move a disk from the top of peg frompeg to peg topeg, where frompeg and topeg are
keys to a dictionary towers, where the items are a list with the disks
arranged bottom to top
"""
assert len(self.towers[frompeg]) > 0, "From peg is empty"
disk_num = self.towers[frompeg][-1]
if len(self.towers[topeg])>0:
assert disk_num < self.towers[topeg][-1], "illegal move, disk %i is bigger\
than top disk ( %i ) on peg %s" % (disk_num, self.towers[topeg][-1],topeg)
self.towers[topeg].append(disk_num)
self.towers[frompeg].pop()
def solveHanoi(self, frompeg, topeg, numdisks=None):
"""
Solve the tower by moving the disks from peg frompeg to peg topeg, with disks laid
out in self.towers
"""
if numdisks == None:
numdisks = self.num_disks
assert numdisks<= self.num_disks, "Tower does not have so many disks."
def getsparepeg(frompeg, topeg):
"""
return the key of the spare peg
"""
for peg in self.towers:
if peg not in [frompeg,topeg]:
return peg
if numdisks==1:
self.diskmove(frompeg,topeg)
self.showstate()
return True
if len(self.towers[topeg])== self.num_disks:
#already finished
return True
else:
spare = getsparepeg(frompeg, topeg)
#subgame = Hanoi(self.pegs, self.num_disks-1, self.startpeg)
#subgame.diskmove(frompeg,spare)
self.solveHanoi(frompeg, spare, numdisks-1)
self.diskmove(frompeg,topeg)
self.showstate()
self.solveHanoi(spare,topeg, numdisks-1)
game = Hanoi(['a','b','c'], 5,'c' )
game.showstate()
game.solveHanoi('c','b')