Prerequisites

Prereqstraightlines

Algorithms:

An algorithm is a set of instructions that solve a problem or accomplish a goal. In everyday life, you use many algorithms without even realizing it. For example, you can think of a cookbook as a long list of algorithms that tell you how to make specific dishes. Here is how you make oatmeal algorithmically:

  • Pour 1/2 cup of oats into a bowl
  • Pour a cup of milk into the bowl
  • if you are not allergic to peanuts:
    • put 1/2 cup of peanut butter in the bowl
  • Microwave for two minutes

Code is a word that essentially describes instructions that are written in a language that a computer can understand. In my videos I use the Python programming language to implement the featured algorithms. Pseudocode is a word used to describe algorithms written in a similiar style to actual computer code, but is more understandable for people. You can think of the lyrics to my songs as pseudocode. I call my songs musicAlgos because they are musical algorithms.

Variables:

A variable is a name we assign to a particular value. Multiple variables can be set to the same value (but two or more variables cannot have the same name).

Python example of variables:

Say we wanted to add two numbers and store their sum as a variable:

#This prints out the value of x
x = 2+5 #x is a variable storing 2+5
print x

One interesting thing you can do to a variable is reassign it by recursively mentioning itself. Here is what I mean:

#set i = to itself+1
i=7
i = i+1 #adds 1 to i
print i #should print 8
Types:

In Python each variable has a specific data type it is classified as. Based on the way you define the variable, Python will identify what type it is, which is known as implicit typing.

Booleans
A boolean can only take on two values True and False. Certain statements involving logical operators will output booleans. For instance if I wrote 4>5 the output would be False since 4 is not greater than 5, here the operator was > . Here is a list of operators:

  • Greater than, less than, greater or equal to, less or equal: >,<,>=,<=
  • Is equal to: ==
  • The ‘not’ operator will reverse the value of a statement (T->F or F->T): not
  • Is not equal to: !=
#examples of booleans
4 > 4 #False
4 >= 4 #True
5 >= 4 #True
5 <= 4 #False 5 == 4 #False not 5==4 #True not 4==4 #False 5 != 4 #True

Ints and Floats
You can set a variable equal to an integer data type or int for short by setting it equal to a positive or negative whole number. If you set your variable equal to a number with anything after the decimal point even if it’s zero, that is called a float. Here is what I mean:

#examples of int and float
myInteger = 5 #an int
myFloat = 5.0 #a float

So what are the main differences between ints and floats other than that ints can only be whole numbers? Well, you can only do list indexing (see lists) using integers. If you ask for list[0.3], Python won’t know what you are talking about and throw an error. Division also can work differently. With floats division is more straightforward, and basically performs the way you would expect by carrying out the division until it can’t store anymore values past the decimal point. In Python 3, integer division (division among two integer values) can work two ways: with the ‘/’ operator, division may output a float since the answer might not be a whole number. With this operator “//” it will round down to the nearest whole number and the quotient will be an int. In Python 2.7 (the version I use), even the ‘/’ operator will round down for integer division and output an int.

Division in Python 2.7:

Here is an example of how floats and ints interact with each other using division. The comments (followed by #) tell you the output.

#Shows how ints and floats handle division
print 1/2 #will output 0 (an int)
print 3//2 #will output 1 (an int)
print 5/2.0 #will output 2.5 (a float)
print 5//2.0 #will output 2 (an int)
print 5.0//2.0 #will output 2.0 (a float)

The only difference between 2.7 and 3 would be that 1/2 would output 0.5 in Python 3. (And in Python 3 you need parentheses around the values which you want to print i.e. print(5/2).
Strings:

The string data type is a sequence of characters, such as letters, numbers or symbols. In Python, you define a string by putting quotes around it. Some cool things you can do with strings: add them together with the + operator,
and index them (see lists). For example:

#string stuff
string1 = “Hi”
string2 = “I’m Ben”
print string1+string2 #prints Hi I’m Ben
Lists:

A list is composed of a row of cells, where each cell holds a value. We identify the leftmost cell as index 0, the next index is 1, the following one is 2, and so on. Another name for index is position.

List img

Lists in Python:

Let’s create a list containing the values: 10,20,30,40. Say we wanted to see what was at position 0 and then change that value to something else. To see what is at a certain position in the list we specify the position in brackets[ ], if we want to see the entire contents of the list we don’t need brackets. Another use of brackets is to reset a value in the list. Here is what I mean:

#list indexing
myList = [10,20,30,40]
print myList[0] #would print 10
print myList #would print [10,20,30,40]
myList[0] = 25 #reset the value at pos. 0
print myList[0] #would print 25
print myList #would print [25,20,30,40]

Strings which are sequences of characters can be indexed like lists as well, where each letter holds a single position. For example:

#string indexing
myString = “Hello”
print myString[0] #would print H
print myString[4] #would print o
If, Else, and Elif statements:

The code inside an if statement is only executed if a certain condition is met. If there is a following else statement and the if condition is not met then the code inside the else statement will be exectued.

Real life example of an if/else statement:
I am deciding on what to do tomorrow. I’d prefer to go to the beach, but only if it is sunny. If it is not sunny, I will play ping pong:

    if it’s sunny outside:

  • Go to the beach
  • else:

  • Play ping pong

Let’s change it up a bit. Let’s say that my second preference is actually to play tennis, but only if the courts are dry. To represent this, I could use an elif (short for else if), which is executed if no previous if or elif statement before it has been executed:

    if it’s sunny outside:

  • Go to the beach
  • elif the courts are dry:

  • Play tennis
  • else:

  • Play ping pong

Python example if statements:
The following code would print out “17 is greater than 10”

#This prints x is greater than 10
x = 17 #x is a variable storing 17
if x>10:
print x, “is greater than 10”
elif x == 10:
print x, “is equal to 10”
else:
print x, “is less than 10”

The following code would print out “x is equal to 10”

#This prints x is equal to 10
x = 17 #x is a variable storing 17
if x>10:
print x, “is greater than 10”
elif x == 10:
print x, “is equal to 10”
else:
print x, “is less than 10”

The following code would print out x is less than 10

#This prints “x is less than 10”
x = 17 #x is a variable storing 17
if x>10:
print x, “is greater than 10”
elif x == 10:
print x, “is equal to 10”
else:
print x, “is less than 10”
For Loops:

For loops follow the same set of instructions for every item in a given sequence.

Real life example of a for loop:
Say you had to a pay a bunch bills. For every bill you need to 1)write a check, 2)get an envelope, 3)identify address of the recipient, and 4)put a stamp on the envelope (in this order). This can be expressed as a for loop:

For every bill I need to mail:

  1. write a check
  2. get an envleope
  3. identify address of recipient
  4. put on postage

Python example of a for loop:
Say you wanted to print the numbers 0,1,2,3 Like this:

  • 0
  • 1
  • 2
  • 3

In Python you would express this as so:

#This prints 0,1,2,3
for number in range(4):
print number

The range(n) function returns an ‘iterable’ containing the values [0,1,2,…,n-1]. The implied lower bound is 0 and it includes integers up to, but not including n. For each value in this iterable the for loop performs the instruction indented within it (which simply prints out the value). Even though range(n) returns an iterable of integers, you don’t have to say for number in range(4), you could say for elephant in range(4) or for donkey in range(4),…etc. and Python would do the same thing (as long as you also told Python to print elephant or donkey depending on which was used in the for statement). Typically i is the variable used in for loops, which we refer to as a loop counter because it counts which iteration the for loop is at.

#This prints 0,1,2,3 (equivalent to previous box)
for i in range(4):
print i
While Loops:

While loops follow the same set of instructions while a given condition is met. The condition is checked each time the instructions have been completed.

Real life example of a while loop:
Usually this is how my dinners at home go: 1)I eat a serving of the main course and starch, and 2) I’ll eat a serving of vegetables. If I am not hungry after eating the the main entree, starch, and veggies, then I stop eating. If I am still hungry, I’ll take another serving of each…

This can be expressed as a while loop:

while I am hungry:

  1. eat a serving of main course and starch
  2. eat a serving of veggies

Python example of a while loop:
Again, say you wanted to print the numbers 0,1,2,3 Like this:

  • 0
  • 1
  • 2
  • 3

In Python you would express this as so:

#This prints 0,1,2,3
i = 0 #set variable i to store 0
while i<4: print i i+=1 #adds 1 to i

The variable i is initially set to 0. We enter the while loop because i is less than 4. On each iteration of the while loop, the value that i stores is printed out, and we add 1 to i. The loop concludes after four iterations since on the fourth, i was initially equal to 3, and then it was incremented or increased by 1. This caused the condition that i<4 to break, and thus the while loop concluded.

Functions:

A function is a set of instruction(s), which in order to execute must be “called” upon. Functions are useful because they allow us to organize a program such that when one reads it, the program’s main function can give a big picture view of what’s happening, and helper functions can help hide some of the details.

A function may accept input values or parameters from its caller and may return a value to whomever called it (this also makes them reusable in a variety of situations). Code written outside a function will execute automatically, but code inside a function is only executed if the respective function is called.

Real life example of functions:

Here our main() function walks us through the process of making an omelet. First you beat three eggs, next specify and prepare the ingredients, and then cook the eggs and ingredients in a pan. To abstract or hide away some of the nitty gritty details of each step, I declared three helper functions: beatTheEggs(n) takes in a parameter “n”, that indicates how many eggs you want to cook, and yields n beaten eggs, prepareTheIngredients(listOfIngredients) allows you to specify a list of ingredients you would like in the omelet and cuts them up in small pieces, and cookItUp(listOfIngredients,beatenEggs) cooks the ingredients and eggs in a pan.

This is obviously not real code so don’t get hung up with the details. Just understand that the main() function tells the high-level or big-picture story and each helper function hides the details so main() is very readable.

def main():

  1. beatenEggs = beatTheEggs(3)
  2. ingredients = [brocolli, cheddar, onions]
  3. prepIngredients(ingredients)
  4. cookItUp(ingredients,beatenEggs)

def cookItUp(ingredients,beatenEggs):

  1. put a pan on the burner on hi setting
  2. lather the pan up with cooking spray
  3. pour beatenEggs into the pan
  4. For every ingredient:

    1. put it in the pan
  5. wait 5 minutes and then flip one half of the omelet with a spatula and put it on a plate
  6. return omelet on a plate

def prepIngredients(ingredients):

  1. get out a cutting board and kitchen knife
  2. For every ingredient:
    1. cut in up into small pieces

def beatTheEggs(n):

  1. find n eggs in the fridge
  2. For every egg:
    1. crack it and put yoke in a bowl
    2. throw out the shell
  3. add a dash of milk to the bowl
  4. mix eggs in the bowl
  5. return the beaten eggs

main()

A few things to notice though: Again beatTheEggs(n) takes in a parameter n that specifies the number of eggs you want. It also returns a value, n beaten eggs. This function could be used in other situations as well, for example, I could be writing a program that makes a batch of brownies which requires eggs. The function prepIngredients(ingredients) takes in a list of ingredients as a parameter. Even though the contents of the list have been changed (each ingredient has been sliced into small pieces), the list does not need to be returned explicitly, since it is mutable.

A type is mutable if it can be changed outside of the function it is declared in. An immutable type cannot be changed outside of the function it is declared in.

List of some mutable objects: lists,sets,dictionaries

List of some immutable objects: ints, strings, floats,tuples

Python example of functions:
Say you wanted to write a program that finds the median value in a list of numbers (for the sake of ease let’s assume it has an odd number of entries). First it would need to sort the list of values, and then find the middle element in that sorted list.

#This prints “x is less than 10”
def main():
myList = [10,20,11,34,12,45,14]
sortTheList(myList)
middleElement = findMiddleElement(myList)

def sortTheList(yourList):
#sorts the list in ascending order
swapped = True
while swapped==True:
swapped = False
for i in range(len(yourList)-1):
if yourList[i]>yourList[i+1]:
swapped = True
old = yourList[i]
yourList[i] = yourList[i+1]
yourList[i+1] = old

def findMiddleElement(yourList):
middleIndex = (len(list)-1)/2
return yourList[middleIndex]

main()

Logarithms:

Log is short for logarithm. If ab = c then Logac = b and vice-versa (the two statements are equivalent). In other words the log tells you what power its base, a, should be raised, to yield c.

Examples:

  • Log101000 = 3 because 103 = 1000.
  • Log232 = 5 because 25 = 32. (In computer science, a log without an explicit subscript base usually means base 2.)