Will be used for sharing code and learning python
To start getting our heads to think more programmatically, we will start with scratch, a free software built to learn the ideas behind coding from the great people at MIT. linked here.
To start, I would advise you to create a project and play around.
If you get stuck, MIT put out a couple tutorial videos here
While playing around, it is advised to use blocks from the control section, this will help you create more powerful animations.
For all systems this tutorial should come in handy if you get stuck.
Before you start, you may want to read up on a bash primer, or just learn the basic commands.
here is a bash reference. Of course you do not have to know all of them, but some of them you will use more then others, such as: cd, ls, mkdir, find.
Python usually comes installed on these operating systems. To check, open your applications and search for terminal. Once it is opened type
python --versionYou should see something like: 2.7.11
If not, you can download python here
Google has put out a setup page for python also, linked here
For mac, a great package manager to have is homebrew, download and instalation is advised.
Before you start, we will be using the command line, so reading up on a command line reference is advised. You don't need to learn all the commands, just some of the more useful ones (such as cd, dir, find, help, md, move, path)
You can test to see if python is install on your machine opening the cmd application and typing: python --version
if you dont get back a version such as: 2.7.11, then you need to download and install it here
Google has put out a setup page for python also, linked here
A text editor is a program that will allow a user to edit text. When you program, you will usually want to use a text editor with a certain text format. For example, when you use microsoft word, the document ends with .doc, you might have seen .pdf, .jpg, .gif or various others, for python we use .py.
Sublime text is a great editor that uses colors and auto complete to make coding easier for the user and better overall experience. You can download it here.
If you have trouble or want another look, here is a tutorial. Otherwise just continue.
After you download sublime (or you can use any text editor) open a new file and save it as: helloworld.py in the documents
On the first line write:
print("Hello World!")Save the file and open your terminal/command line. Using your appropriate commands (for windows and *unix use: cd ), change into the directory where your file is saved.
This:
cd documents Should work, but you might need to use ls/dir to help find the documents folder. Once you changed into the documents directory write:
python helloworld.pyWhich if you have done everything correctly, should write to the screen: Hello World!
- For homework this class, create a scratch project that involves at least three different control blocks, two motion blocks, two event blocks, and two operators blocks.
- Set up python on your machine
- Reading
- Basics of programming
- Python
- Types
- Variables
- [Input and output](#input and output)
- If statements
- Homework
To be familar with the upcoming section, skim through this on basic syntax.
Read through this on variable types.
Skim through this on basic operations.
Read through this on decision making carefully.
When we say carefully, we really mean, try to really understand, the better you understand what is going on, the better you will code, and the less you will debug later.
Optional: Math and numbers, Strings, Boolean Logic,
To understand some of the work that is done here, I write "#" after code sometimes, these are comments. They are english and ignored by the computer. Read them as an english commenter for the line of code or the code your about to read or just read. Try it out in the interpreter.
You can skip this paragraph if you don't want some nitty gritty details, but it is advice to come back at point. As a side note on the difference between python 2.7 or less and python 3 and greater: There are small differences between the versions that will slightly be mentioned throughout the course, it should not matter what version you use at this point. On Mac computers, python 2.7 comes preinstalled (at the time of this writing), so it may be easier to stick with 2.7 for now. In the future you may want to port over to 3.x. On windows, if you downloaded 3.x then you will want to use that versions documentation. The differences will not always effect you, but come important in a couple places. The main differences in the begginning parts of the course are the print and input commands/functions. In 2.7 and below print is a keyword and in 3+ it is a function meaning if you want to print you do: print 5 # < 2.7 and print(5) # 3+. If you do it with parenthesis in 2.7 it will still work, so I advise you get into practice of using parenthesis for when you port your programs in the future. I mention inputting later. Another difference is the division operator, we will talk about that later.
To start running the python interpreter Open either the command line (on windows) or the terminal (on *nix systems such as Mac, Linux, Unix, etc.) and just type python. Play around with some math 5 + 5, 4.0/3, 4*4 (some weird things may happen if you do division based on your version, so don't freak out). You can also use an Online interpreter.
Python is a beginner friendly language that has an english-like sytanx. In Python, the interpreter (the thing that will help the computer understand what you are typing) uses spaces or tabs to seperate commands and understand the flow of the program. In other many other languages semicolons and braces, '{ }', are used, or some mixture. You can use semicolons if you'd like, but generally it is not done. Try and stay close to general python coding practices so that others can understand your code better and you will be able to read theirs as well. As you program in Python you will get a better understanding of this.
Throughout this class, you may want to refer to the references on the bottom of the page, or google, your new best friend.
Reading this on variable types is enough for types now, and I highly suggest that you understand this page. It is essential that variables types are understood for the rest of the course. These will be the tools you use to solve problems. This is one of the only readings I will advise you to go through compleately. Don't worry if you don't understand all of it.
In python you can create a variable easily as long as you don't name it one of the keywords. You can read about the keywords here. A variable does not need to mean anything, it can be compleately arbitrary, the computer does understand. I suggest that you use variable names that mean something to you and can be easily infered what they contain from an outside reader (or you when you read your code in the future).
If you wanted to put a mathematical expression or a sentence or a mixed list you would do it like this:
x = 5 + 12 + 24 + 36
sentence = "I love coding in python"
mixedList = [5 + 23, 0, "Coding is fun", 10.5, "Hello world!"]
this_Is_A_Variable_That_Will_Contain_a_number = 5
number = 10Python is case sensitive, so x and X are different as well as variableName and variablename
To play around with this, open the interpreter (by typing python in your terminal/command line or using an online one here) and try it out.
If we want to output, we use 'print', it does not matter about the internals here at this point, for our sake lets use it as a function like so:
print("Hello World")You may want to skim through this before you continue.
Input in python is simple but is different depending on your version. If you are using python 2.7 or less than you want to use raw_input() if your using python 3 or above, you want to use input(). In the class folder there is a helpFunctions.py file, you can read through it if you'd like. To get the users name:
from helperFunctions import *
name = getString("Please enter a name")and to print it
print(name)or
print("Hello " + name)If statements are a logical way to make decisions based on unknown input. We use if statements in our lives all the time. For example, we say "if I am late, leave without me", "If I don't catch the bus, I'll take a cab".
In programming we use if statements as a form of controlling the flow of the program. The sytanx is pretty straightforward, you can read about it here, only the first section is necessary.
The syntax, taken from the docs:
if x < 0:
print('x is negative')
elif x == 0: #else if
print('x is zero')
elif x == 1: #else if
print('x is one')
else:
print('x is positive and not one') # not less than zero, not zero and not onethe if statement checks if x is less than zero, if it is it will print: 'x is negative', if it is not and if (else if) x is zero then print: 'x is zero', if it is not and if x is 1, print: 'x is one', else in all other cases, print: 'x is positive and not one'
This next example is going to be a bit confusing, I do this, not to confuse you on purpose, but to try and drive home a point.
The inside of an if statement need not be a single command, it can be an if statement itself, in fact it can be any number statements, for example:
x = 25
if x > 10:
if x > 30:
if x > 50:
print("x is really big")
else: # 30 < x < 50
print("x is prety big")
else: # 10 < x < 30
if x > 20: # 20 < x < 30
print("x is big")
else: 10 < x < 20
print("x is nicely sized")
else: # x < 10
print("x is small")I agree there are better ways to write this, but this is just an example of how you can nest code for more complicated control flow.
The last thing we will do with if statements, is boolean logic. In python if you want to test for multiple conditions in an if statement, you can use keywords like and or or. They are very useful and can make reading code really easy.
x = 25
if 10 <= x and x <= 50: # <= means: less than or equal, similar >= would mean: more than or equal
print("x is in the middle")
# another example:
if x < 10 or x > 50:
print("x is not in the middle")A neat cool trick that you can do in python is some regular mathematical inequalities:
x = 25
if 20 <= x < 30:
print("x is in the twenties")As a side note, != means not equal.
Now that you know how to get input from the user, you will do some logic on the users input.
- ask the user for their name
- if they give you name that does not have at least 3 charachters or more than 20, ask one more time.
- if again they do not give you a good name, don't do anything more, you may use
exit()
- if again they do not give you a good name, don't do anything more, you may use
- if they give you name that does not have at least 3 charachters or more than 20, ask one more time.
- If the initial of their first name is before m or m, then tell them "your first name starts at the beginning of the alphabet"
- Otherwise tell the user "Your first initial starts at the end of the alphabet"
Here is some pseudocode to help with your first coding homework:
get name from user
if its less than 3 letters or longer than 20
get name from user
if name is still less than 3 letters or longer than 20
exit
if initial of first name is between 'a' and 'm'
print("your first name starts at the beginning of the alphabet")
else
print("Your first initial starts at the end of the alphabet")
You may and should use the helperfunctions file. There you can find the functions between(charA, charB) use like:
'c' in between('a','d') # True
'C' in between('a','d') # True even though it is capitalized
'f' in between('a','d') # FalseTo include the between function in your code, download the class file and place it in the same directory as the one you are writing the homework's answer in. Then on the top of your code write:
from helperFunctions import *the "*" is a wildcard, like a joker in cards, it tells the computer, I want anything and everything. It is generally better to name the functions you are looking for, this way when you reread your code (or someone reads yours), it will be known why that file/library/module was called in, but for our sake, this is enough. At this stage it is not important for us to delve into the functions that were prepared.
If you would like to do it:
from helperFunctions import betweenYou may see this done differently online or in other examples, we will talk about importing later as well.
This reading on if/else statements from the reading section may come in handy.
If you are having trouble with importing, you can just copy and paste the code on top of your file and then use the function explicitly without importing.
Read through this on loops carefully as well. Skim through this on Lists. Skim through this on tuples. Skim through this on python dictionaries Skim through Control Flow Python, as a general rule on this particular link, the closer the section is to the top of the page, the more important it is at this moment.
In programmaning, arguably the most important concept is looping. Looping alows the user to write a command one time and tell the computer to run it as many times as you'd like. For example, on your calender you may repeat an event every thursday, it would be extremely annoying and time consuming if you had to manually create the same event for every thursday, rather telling the computer one time what your event is and then repeating it every thursday until a set date. This was is fast and convienent.
In python there are two main ways to loop, for loops and while loops, you can read more about them here.
A for loop usually has a set start and end, it is used generally when you know the amount of times you want the loop to run.
A while loop is generally used when you are unsure the amount of times you need the loop to run. For example, you may want a loop to run every day until it rains, here you don't know the amount of days (times) you need it to run, just when to stop.
The syntax is simple:
for loop:
''' program to output the numbers from 1 to 25 ''' # three quotes is also another form of comments
for x in range(1,26): # this runs from 1 through 26 (not including 26)
print(x) # on every iteration x will be set to the next number and then we print it
Try this out on your interpreter.
while loop:
''' An infinite loop program, this program will never stop, so if you try to run it, press control-c to stop your computer at some point. '''
x = 1
while True: # meaning run always
print("x is now " + str(x)) # print the current value of x,
#need to put x in the str() function so that print understands it, don't worry about that for now
x = x + 1 # increment x by 1
Get 10 names and their assoceated ages from the user, print to the screen: the oldest persion and their age.
It is up to you to choose how the user will know what to type and how you store the data.
Get a height from the user and print a triangle (using the at symbol, @) to the screen using that height as the number of @ symbols on the bottom row.
For example if the user enters: 3, the output should be:
@ @@ @@@
If the user enters 5, the output should be:
@
@@
@@@
@@@@
@@@@@
and so on.
Hint: You may want to print the triangle without spaces first. For example, an input of 5 would output:
@ @@ @@@ @@@@ @@@@@
Once you do this, add the spaces in to finish the project.
Read through this on functions carefully. This is a very important concept in programming that will really save you a lot of time.
Skim through this on modules
Read the first answer on the modulo operator here and the syntax in python.
Here we will dive a bit more into loops and their power. Just a quick refersher on the syntax:
for x in range(0,101):
print(x) # will print all numbers from 0 -> 100 (including 100)
x = 0
while True: # will run forever
print(x)
x = x + 1While loops have a similar syntax to if statements, but they will run again and again while the condition is true. So if we wanted to make a while loop work like a for loop it would be simple:
x = 0
while x < 101:
print(x)
x = x + 1If we look at this, it will work exactly like the for loop above, the loop runs while x is less than 101, on each iteration x is incremented, just like the for loop, and it prints it. Try a couple out in the interpreter.
Just like if statements, loops can also be nested:
for x in range(1,11):
print(x)
for x in range(1,11):
for y in range(1,11):
print(str(x) + " * " + str(y) + " = " + str(x*y)) # the str() function turns an object/variable into a string for the print functionYou don't even have to have static nested loops, you can make them a bit more dynamic:
for x in range(1,11):
for y in range(x,11): #start from x and go to 10 (inclusive)
print(str(x) + " * " + str(y) + " = " + str(x*y))If you'd like to break out of a loop you would you the "break" keyword:
for x in range(1,10000000):
print(x)
if x == 10:
break
# or you can use it in a while loop
x = 10
while True:
print(x)
x = x + 1
if x > 25:
breakTry these out and play around with it to get a better feel.
the break keyword only breaks out of loop it currently is in, so a nested loop will not be compleately broken out of, for example
for x in range(1,11):
for y in range(1,11):
if y > 5:
break
else:
print(str(x) + " * " + str(y) + " = " + str(x*y))The last thing we will do is iterable collections
if we have a list we can loop through it as well:
listOfItems = [1,2,3,4, "I like coding", "coding is fun", "yay"]
for item in listOfItems:
print(item)As an exercise try to create a list of lists and iterate through every element and print them all.
Functions in programming allow you to write a piece of code once and use it many times. I'm sure you have seen functions before in your math classes, such as sin,cos,tan, ln, log, etc. Even if you havn't dont worry, the concept isn't hard.
Lets create a simple function, one that calculates the number that is bigger, given two numbers.
We would take two numbers in and will return to the user the larger number.
def largerNumber(firstNumber, secondNumber):
if firstNumber > secondNumber:
return firstNumber
elif secondNumber > firstNumber:
return secondNumber
else: #they are equal
return firstNumber #does not matter since they are equalIn python you use the def keyword to let the intrepreter know that you are "def"-ining a function, you then name it (we named it largerNumber), then you open the parenthesis to allow arguements for the functions, the rest we have seen before. Again, function names need not mean anything, but it is good practice to name them something that explains what the function will do.
To use it, just call it like other functions we have seen:
print(largerNumber(5,10)) # will print 10Let's rewrite some of our previous code in a function so that we can re-use it. Let's print the numbers from 1 through the users input:
def print_from_one_to_the_number(n):
for x in range(1,n+1):
print(x)
print_from_one_to_the_number(20)
print_from_one_to_the_number(30)
print_from_one_to_the_number(40)Here we define a function that takes an argument that we use in our for loop, so that our loop is dynamic. Now every time we want to print out the numbers from 1 -> n, just use this one line call.
Now lets do something a bit more useful, lets start computing, lets sum the numbers from 1 -> 100
currentSum = 0
for x in range(1,101):
currentSum = currentSum + x # on each iteration x will change to the next number, we add it to the current sum
print(currentSum)Now if we functionize it, we can sum the numbers from 1 -> n
def sum_from_one_to_n(n):
currentSum = 0
for x in range(1,n+1):
currentSum = currentSum + x
return currentSumNow if we want to sum from a -> b:
def sum_from_a_to_b(a,b):
currentSum = 0
for x in range(a,b+1):
currentSum = currentSum + x
return currentSumNow that was easy, we know have a function that will sum any amount of numbers, starting from any place.
As an exercise, try and write a function that sums all the squares (x * x) from a -> b
This homework may be a bit more difficult than the previous two, don't sweat it, work through them and you will become a better programmer for it.
Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.
It will be useful to understand the modulo operator, if statements, and looping.
For this homework we will write a program for the caesar cipher.
In the cipher, you will increment each letter by fixed amount (with wrapping so that 'z' + 1 = 'a').
For example if the increment is 5 then 'abcde' becomes 'fghij', if the increment is 3 then 'wxyz' becomes 'zabc'
In this assignment you will print out all the possible values that our encripted value could be.
For example if our encripted code is 'a' then that code could have come from the entire alphabet.
'ab' could have come from 'ab','bc','cd','de', etc.
For a slightly harder problem, try to implement an algorithm that does not have to check every possibility.
For example, if our encripted code is 'z lzm hr z gtlzm' then since we are dealing with the english language, we know that there are only a limited amount of one letter words, decreasing our possibilities to only handful.
Skim through this on exceptions Read through wiki on tower of hanoi as we will be using it a lot this class.
Recursion is the act of a function calling itself. A great example of this is the factorial function in mathematics.
In mathematics, n! (pronounced n factorial) is written as n * (n-1)! where 0! = 1! = 1, so 5! = 5 * 4! = 5 * 4 * 3! = 5 * 4 * 3 * 2! = 5 * 4 * 3 * 2 * 1! = 5 * 4 * 2 * 1 = 120
When we write recursive functions, we usually have a base case of when we should stop, and we want to move towards that base case on every interation of the function.
If we wanted to write a function to compute a factorial, we would write:
def factorial(n):
if n == 1: # our base case
return 1 # return 1 since 1! = 1
else:
return n * factorial(n - 1) # n! = n * (n-1)!As we see here, we have a base case when we stop (when n = 1) and on each interation n gets closer to the base case, assuming the user enters a positive integer.
Take some time to really think through the recursion, it may be best to draw out on a pen and paper the iterations. Recursion is usually one of the hardest concepts for a new programmer to get their head around.
We will spend some extra time on some more examples, feel free to skim over them if you feel that you understand recursion, we will also come back to it throughout the course to make our lives easier.
Let's write a program that will return the number of 5's in a number
def count_fives(number):
if number == 0: # base case
return 0
if n % 10 == 5:
return 1 + count_fives(number // 10) # 1 for the ones place + call the function for the same number without the ones place
else:
return 0 + count_fives(number // 10) # 0 for the ones place + call the function for the same number without the ones placeThe last example we will look at here are the Fibonacci numbers.
The Fibonacci numbers are generated by a recursive relation, where you find the following number by adding the previous two numbers, starting with 1 and 1.
For example the third number is 2, since 1 + 1 = 2, then the next number is 3, since 1 + 2 = 3, etc.
def Fibonacci_number(n):
if n == 1 or n == 2:
return 1 # if its the first or second number we are looking for then the answer is 1
else:
return Fibonacci_number(n-1) + Fibonacci_number(n-2) # to get the next number, we have to sum the previous two
Lambdas are anonymous functions, or functions that dont have names, they are used when you want to write short one line functions.
To see the usefulness of this, we will expand the concept of arguements in functions, and maybe you've realized this already, but functions can take functions as arguements. Lets look at an example where this would be usefule:
def square(x):
return x*x
def cube(x):
return x*x*x
def sum_from_a_to_b(a,b,function):
currentSum = 0
for x in range(a,b+1):
currentSum = currentSum + function(x)
return currentSum
#now lets use it
print( sum_from_a_to_b(1,10,square) ) # will print the sum of the squares
print( sum_from_a_to_b(1,10,cube) ) # will print the sum of the cubesNow what if we dont want to create a new function like cube that we will only use once, well we can just use a lambda:
print(sum_from_a_to_b(1,10, lambda x: x*x*x) ) #will print the sum of the cubesIn the tower of hanoi there are three towers with N rings on the first one (in ascending order). The goal of the game is to move all the rings to the middle tower. The rules are simple, you may only move one ring at a time and a ring can only be placed on a ring that is larger than itself.
Open up the file for this class and play the game on your terminal/command line to get a feel for the game.
Then try to implement solve, an algorithm that will win the game automatically for you (from the starting position).
For a bit more, try to solve it for any starting configuration.
In this cipher our key is not a single number, but rather a word or series of numbers. The code is encripted with by cycling through each letter of the code and key at the same time, using a mini caesar cypher on each letter.
For example if our code is 'abc' and our key is '123' then 'a' gets shifted one place, 'b' two and 'c' three, so we get as an output 'bdf'. If our key is shorter than our code we just wrap around and start again. Again 'z' + 1 = 'a'.
Decripting this algorithm is a bit harder, but not impossible. This problem is a bit more advanced and uses frequency analysis and can be implemented with machine learning. We will not cover that in this class.
Play this game, and get ready to build it.
Read up on this classic game and get ready to build a similar version as well.
The game of fifteen is an easy one to understand and a bit harder to solve. This week we will implement the game on the console and if your ambitious, I urge you to try to come up with a computer algorithm that will solve the board. Be careful though, many permutations are impossible to solve.
This homework will also be offered as a final project, so it is really given here to get you thinking about different searching problems.
We will now solve the game of fifteen.
Before we start, you may want to look into Depth First Search or/and Breadth First Search. You don't have to use these algorithms, but it may give you some ideas and make it easier.
Solving this is not easy, I suggest you write down your psdueo code first on a pen and paper, then dive into the coding after you are finished writing out all the details.
To help you out, try and play the game yourself and see what you as the human do, can you explain why you are trying to do some moves before others. Do you have a general algorithm? If you are having trouble solving the game, then all the more so having the computer solve it will be more rewarding, and maybe scary.
If you get stuck, You may want to read this on (n^2 -1) puzzle and this paper on a more advanced solving technique. Reading through these after you write your own solution would be helpful in the future for similar style problems.
Read through these sorting alogrithms: bubblesort merge sort insertion sort and some others here
Trying to implement these three sorting algorithms yourself would be beneficial. I did not pick these three for any particular reason, there are numerious sorting algorithms, these just happen to be the ones I picked. I encourage you to find algorithms you find easy to understand and even more so, hard to understand, and implement them yourself in Python.
A good place to look would also be here
You can watch a clip here explaining bubble sort. If you look in the class file, three version have been implemented for bubble sort, it would help to look at them and try to understand what is happening.
You can watch a clip here explaining Merge sort.
You can watch a clip here explaining Insertion sort.
Of the bound notation, Big O is arguably the most important. Big O is way to characterize a function and give it an upper bound. This part may get too mathematical for some, so feel free to skim through it, there is no reason to let it slow you down at this point. I do suggest coming back to it at some point as it is asked many interviews. You can skip here to skip the more mathy part.
To find an upper bound on a mathematical function you are tring to find the highest value it will reach, given a set of inputs. This can be easy for certain functions and hard for others. For example, given the function: f(x) = x, well we can see that this function is always as big as the input it is given. So we write that this function is O(n), read as: big oh of n, or sometimes just: oh of n. Other functions are a bit tricker, and we won't boggle ourselves down with the nitty gritty details, the internet is full of exercises.
One of the more important rules is: O(f(x)) + O(g(x)) = O(max(f,g)). For example, if f(x) = x, and g(x) = x^2, then since g > f for x > 1, then O(f(x)) + O(g(x)) = O(max(f,g)) = O(g(x)) = O(x^2)
If your unsure which function will be larger at points, then you need to do some calculus and limits, but this is a bit more advanced then what we will be dealing with.
Lets look at a couple examples. If we want to find an element in an unsorted list what is the big O? linear search
Well, how many operations would we have to do? The answer obviously depends on the size of the list.
We can ask ourselves, in the worst case scenario, what is the largest number of elements in the list we would have to check? Well if the item is not in the list, we would have to check every element, which would O(length of list) or usually written O(n) where n is the size of the input.
What if our list is sorted. Well then it becomes a bit easier, what we do is start at the half way point, if the middle item is larger than the item, then we research the list but only search the first half of the list, otherwise we search the second half of the list. (unless of course we found the item). Well how many searches does this take? In the worst case, the item is not in the list, and we keep halfing until there is only one element left. So the answer to our question is the answer to this question: How many times can we half a number. If you remember from Trigonometry/Algebra 2 the answer is log base 2. Since computers are binary by nature, we use base 2 as our implied base, so we write O(log(n)), read as: "oh of log n". Don't worry if you didn't fully get it, most people don't use big O notation on the regular, but it is a concept you should be somewhat familar with.
Now that we've discussed them, lets code the two examples up:
Linear Search is search through a collection of items, one at a time.
def linearSearch(listOfItems,item_to_search_for):
for item in listOfItems:
if item == item_to_search_for
return True # we found it
return False # if we got this far, that means we never returned true, that means it is not in the listBinary Search only works on sorted lists. This one will be a specific solution to a integer only list, but you can make a more abstract generalization to the binary search algorithm when we talk more about classes.
Look here for another code example and interactive step by step.
def binarySearch(listOfNumbers,number):
length = len(listOfNumbers) # get the length of the list
if listOfNumbers[length//2] == number: # if the middle element is the one we are looking for, return true
return True
if length == 1: # if there is only one item in the list and its not the one we are looking for
# (otherwise we would have returned true one line before this) then return false
return False
elif listOfNumbers[length/2] > number: # if the middle element is greater than our number
return binarySearch(listOfNumbers[:length//2], number) # research but only use the first half of the list
else: # if its less than number
return binarySearch(listOfNumbers[length//2:], number) # research but only use the second half of the listYou can look and play around with the class file on Binary Search to get a feel for it.
You may want to go back and get a better understanding of Lists, tuples, dictionaries in python.
Furthermore, you should skim through Linked Lists and take a look at some of the data structures here (some are less important than others). In general the most important ones are arrays (in python lists), hashtables (in python dictionaries), tuples, linked lists, trees (we will cover in class 9), Graphs, Stacks (Cover in class 10 in sudoku), and Heaps.
The readings here are more for you to skim, there will be more for next week, this is really a primer. Classes overview: tutorialspoint and python-course
magic methods: rafekettler or python-course works fine.
Throughout reading these data structures and afterwards, I would advise you to look at this great cheat sheet on big O for each of these data structures.
Furthermore, this website has a great Visualization of common themes that you might want to look at.
Hashing is a the way of classifiying data into some group based on some property. To be less abstract I will give you an example. If I am a farmer and have three baskets that I want to store all my food in, how would I go about doing this, so that when I want to find, lets say apples, It will be easiest. If I only have three types of food that I farm, then it will be easy, but what if I have 6 or 9 or 100? Well what you want is to find some way so that each basket has around 1/3 of the types of food you produce so that you can find the item you are looking for the quickest possible. One way could be fruits, vegetables and grains. Or if you have a lot of grains and few fruit and vegetables, maybe put half the grain types in one, the other half in another and mix fruit and vegetables. In programming we can do the same thing, and this is implemented with pythons hash() method. You do not need to learn the internals of how hashing works, but you should know that there is some way that the method decideds which numbers (basket) the piece of data you have justed hashed should map towards. This can be really convient if you have a large number of elements that have no apparant order. For instance, if you had 100 items, and could map each item to a number 1 through 100, then put that item into a list at the number the item was mapped to, then to find the item again would only cause one lookup, quickly being able to retrieve that item. In python, dictionaries use hashing to store items and is one of the reasons there does not seem to be an order or have the order in which you placed them. The function that maps them is something that more mathy people may want to look into.
This visualization should be helpful.
A linked list is a list that does not necessarily have an index like an array/list. When a linked list is instantionated, a first node and a last node is created. These nodes are 'pointing' towards the place where the first and last elements of the list are located in the computer. As the list is generated the node that points to the first element (head node) and the one that points to the last node (tail node) continiously change as you add elements. As we add elements, we have a node that holds the data, and then a 'pointer' to the next node. There are different implementations regarding how exactly it is constructed, but the concepts remain the same.
The reason linked lists are useful is that you can add elements anywhere in the list and not have to shift all the other elements over. In an array/list, if you had a = [1,2,3,5,6] and then decided, I should put a 4 between the 3 and 5, and also put a 0 at the beginning, how would you do that, well first you would need to move the 5 and 6 over one place to make room for the 4, then move the rest of them over to make room for the 0. Let's say you were smart and decided to move over the 5 and 6 two places, and the rest 1 place. That would still cost you n moves, where n is the number of elements to the right of the index you are adding (here 5). In a linked list you would not have to move anything over, you can just move the 'pointer' to a different place and then tell this new place to then point to the next element, pretty easy, huh.
Trees are useful for sorted data. What I mean by sorted is that if you can describe the data in some way that if A < B and B < C then A < C. The opposite holds as well. If D > E and E > F then D > F. Furthermore if you would like to search your data with extreme speeds, then a tree might be for you. A tree is a data structure that 'points' to 2 or more nodes. We will deal with a binary tree ('points' to 2 nodes) here. For three and more nodes, the concepts are similar.
When you create a tree you have your root node that has two empty pointers (we will call them left pointer and right pointer). When we add a node, we ask: is this new piece of data less than or greater than the root node, if it is less than, use the left pointer to put the data. If it is greater than, use the right pointer. After we make the first decision, we can ask the same question again, with the exception that we must ask if this point has not been assigned yet, if not put the data here, else ask the question again, is it less than or greater than. You might start to realize that this looks recursive, if not we will go through it in a bit. The case where the data is equal is up to the creator, and can be done either way, in each case you might want something different or not care at all. (maybe a third pointer for the case of equal?)
This is recursive since when we decide to go down one of the paths towards either left or right, we are back where we started, decided if we should stop here, go left again or go right. Needing no knowledge of what happened before. The current node can be seen as a root node itself. It just happens to have a 'pointer' to it from some other node.
Here we will define a little jargon. For line structured data we use the terms FIFO/LILO, LIFO/FILO which are acronyms for first in first out/first in last out and last in first out/first in last out. These mean exactly what they sound like, the first one in, is the first one out or FIFO. The last one in is the first one to come out or LIFO. A queue is a FIFO line, you may have experienced this in the supermarket or at a bank teller. The first one in is also the first one out. Now you may take longer at the checkout/teller so you may not actually be the first one out, but assuming each person takes the same amount of time, you would be.
A stack is the opposite in a sense from a queue in that it is LIFO, or the last person who comes in, is the first person to come out (last in, first out). A good example of this is when you stack items, such as dished, usually the last one to be stacked is the first one you wash. Hence the name 'stack.'
Tuples you may have seen already in this course or while programming, a tuple is a data structure that associated n items together.
This is used differently in different languages, but if I wanted to say a = (1,2,3) then I would have just created a 3-tuple that has 3 items.
Tuples in python are not mutable (immutable), meaning you can not change an item in the tuple, if you want to do that, use a list.
A graph is exactly what it sounds like, some graph with edges and vertices connecting them to each other. This can be implemented in many ways, but a common way is to extend the definition of a linked list to have some list of 'pointers' so that each node can point to as many (or some limit) number of nodes. In this way, a node can have many nodes pointing to it, and many nodes that it points to. If you have a node that is not pointed to by any of the nodes. You would need to create a new list as it is technically in a different graph.
Here is a quick look at pythons types based on mutability
Mutability is the ability to change an item. In many programming languages certain types and data structures are not mutable, we will now discuss which ones are not mutable.
As we have already seen, Tuples are not mutable. Meaning if you said a = (1,2,3) then tried to execute a[0] = 2 as to form the tuple (2,2,3) you would get a TypeError error. Try it. This is because you cannot change the data inside the tuple. But what you can do, is reassign a to a new tuple so a=(2,2,3) would work. Or if you just want to change the first element you can do a = (2,) + a[1:] . It is a bit strange, but as you dive deeper into python and mutability it will start to make sense.
In python if you want to use a variable as a key in a dictionary it must be immutable, to learn a bit more, read here. It talks about classes, so maybe it will make more sense after the next two classes.
Classes are a way to define your own data type and to implement ones you have learned about. To define your own class you use the keyword class. Then you need some method inside the class to tell it what to do when you instantiate the class. For instance, if you wanted to create a class to represent fractions you would need to give it the numerator(top of fraction) and denominator(bottom of fraction). Lets take a look:
class fraction():
def __init__(self, top, bottom):
self.numerator = top
self.denominator = bottom
f = fraction(1,2) # setting f to be the fraction 1/2Lets take a look line by line. class fraction(): just telling the computer I am creating a class named fraction.
def __init__(self, top, bottom): Here I creating the instantiate method, yes you do need the two underscores, we will get to those in class 9. Then we have three arguements: self, top, bottom. self is used for us to reference the actuall item that holds the data. Meaning if we want some to say that this class has this data, or we want to call a class method or access the class data, as long as we are inside the class, we will use self. self must be used as the first arguement in every method in a class. You do not need to use the word self, but it is advised as other programming languages force you to, and it makes reading your code easier. The last two arguements are just what the user inputs.
self.numerator = top This allows us to have every fraction object to have a numerator and set it to the first argument the user calls
f = fraction(1,2) just call it like a function, but will instantiate f as a fraction class.
If you want to obtain a piece of data, we will create a couple more methods.
class fraction():
def __init__(self, top, bottom):
self.numerator = top
self.denominator = bottom
def getNumerator(self):
return self.numerator
def getDenominator(self):
return self.denominator
def setNumerator(self, top):
self.numerator = top
def setDenominator(self, bottom):
self.denominator = bottom
f = fraction(1,2) # setting f to be the fraction 1/2
f.getNumerator() # would return 1
f.setNumerator(3) # would set the numerator as 3, so f is the fraction 3/2
f.getNumerator() # would return 3What we have done here is added methods to get and set the data in the fraction. Try out some yourself. How would you implement a method to add two fractions?
Well we can define a method add(fraction1, fraction2) or we can create a class method so that we can write f.add(f2), the last possibility is to tell computer what it means to use the addition symbol '+' with a fraction class and write f + f2. I will do the second one here and the third way in the next class.
class fraction():
def __init__(self, top, bottom):
self.numerator = top
self.denominator = bottom
def getNumerator(self):
return self.numerator
def getDenominator(self):
return self.denominator
def setNumerator(self, top):
self.numerator = top
def setDenominator(self, bottom):
self.denominator = bottom
def add(self, fraction2):
bottom = self.getDenominator() * fraction2.getDenominator()
top = self.getNumerator()*fraction2.getDenominator() + fraction2.getNumerator()*self.getDenominator()
return fraction(top, bottom)
f = fraction(1,2)
g = fraction(1,3)
h = f.add(g) # should return a fraction 5/6Here we used some math to add fractions, using cross multiplication. We did not simplify the fraction, but we could have. Take a look here for more explanation.
Being able to implement a sorting alogrithm or common data structure is useful but not essential. People have already optimized most data structures and sorting algorithms, so doing it yourself would only be for learning sake. I would suggest you look at the class file and get a better understanding of how classes are creates to create a data structures. Furtheremore I suggest you try and read through the pseudocode for various sorting algorithms on wikiepedia and try to implement them in python. If you get stuck, the internet has the answers.
For this weeks homework you should try and implement a fraction class that has three pieces of data, the whole part, the numerator, the denominator. Meaning that if you add two fractions and it is larger than one, then your whole part should be the integer, and the fraction should always be less than one. You should also create the following methods: get methods (for whole, numerator, denominator), set methods (for whole, numerator, denominator), add, subtract, multiply, divide (make sure you don't divide by zero), printFraction and simplify (which will simply a fraction to its lowest terms).
printFraction can print anything that you think would help the user understand what the fraction is currently at.
By simplify we mean:
f = fraction(4,8) # f = 4/8
f.simplify() # f should now equal 1/2You may want to use a couple functions for your help in some of the functions:
from fractions import gcd #greatest common divisor
def lcm(a, b): # least common multiple
return a * b // gcd(a, b)This one is a bit more mathematical, so if you are unsure how to do this correctly, look here.
Similar to last week, it is hard to give homework without having you do whats already been done, I think it would be more useful to understand the theory here then the exact implementation.
As an aside homework, you can and should start on the final project. There are various options listed below.
- Brick breaker (using pygame), Pygame tutorial
- something with matplotlib
- something with numpy
- something with sympy
- Monte Carlo Simulation
- Greedy algorithms for problems
- Backtracking
- Solve the game of fifteen or any n^2 - 1 game or compliment with A* Then solve it for a board of any size.
- Dijkstra's Algorithm and Enhanced Iterative-Deepening Search*
- Natural Language Processing. This project is very open ended, I suggest just reading through this book and doing it's homeworks.
We will now build a Sudoku solver. This is easier than you think. We will be stupid about it, and I encourage you to try and make the algorithm more effienct in the future. We will brute force it, with some checks for speeding up.
We will be using a backtracking algorithm
The algorithm:
initialize the empty squares to zeros create stack that will keep track of the places we have placed numbers while we are still solving: if the current square we are at is at or below 8 increment the square if the increment was a valid (in terms of row, column and grid) add this position to our stack get the next empty square if none # we solved exit else set square to zero # if it is at 9, then we have made a mistake and must backtrack to the previously placed square go to last placed square and redo
To help wrap your head around the algorithm, I suggest you write it out on pen and paper, starting to iterate through.
There is sample code in the class file.
The homework for this week is to pick a final project and try to do something with it. Some of them are more layed out and some are more open ended. Have fun and pick something that is interesting to you, and doesn't seem to overwhelming, but still challenging.
- Code Like a Pythonista: Idiomatic Python
- Python documentation 3.5.1
- Python documentation 2.7.11
- tutorialspoint
- Free Python Books
- sentdex's website and his youtube channel's playlists
- Online interpreter
- A github page with various information
- consolidation of python tutorials/guides
- Hidden features and tricks
- Natural Language Processing Book
- Python Tricks and Hints
- Decoraters 1, 2, and 3
- Python Decoraters Library
- Descriptors
- A curated list of awesome Python frameworks, libraries and software
- Big O cheat sheet
- Visualization of common themes