Algorithms
Contents
Algorithms¶
What are the sorts of things that we should do with computers? What are things that are easy to compute? Hard to compute? Impossible to compute?
Algorithms¶
If you can write the steps down, you can write an algorithm.
Algorithms are computable.
Computers cannot read between the lines. They are very literal.
Algorithm Example: Making a Sandwich¶
Clicker Question #1¶
Can you write an algorithm to make a ham and cheese sandwich.
A) Yes
B) No
C) I don’t know
Algorithm for making a ham & cheese sandwich¶
Humans are pretty good at making sandwiches. Computers may struggle a bit.
Algorithm Example: Sorting¶
Given a list of numbers, how can we sort it into the correct order?
Y’all Google is really good at sorting.
ranking: rate a site as how related
sort: given a list of good sites, determine order to present to user
…and do this on all the things
# Define a list of numbers
list_of_numbers = [2, 1, 3]
Clicker Question #2¶
array: a collection of items, where each item can be accessed by its index.
Can you write an algorithm to sort an array?
A) Yes
B) No
C) I don’t know
sort_array¶
A version of a selection sort:
loop through current list
find lowest item
put that at the front of your sorted list
remove lowest item from current list
wash, rinse, repeat
def sort_array(array_to_sort):
"""A function to sort an array."""
is_sorted = False # Keeps track of when we are done sorting
sorted_array = [] # A new list that we will use to
while not is_sorted:
lowest = None
for item in array_to_sort:
if lowest == None: # If not defined (first element) set the current element as lowest
lowest = item
if item < lowest:
lowest = item
# these next two lines use new methods
sorted_array.append(lowest) # Add the lowest value to our sorted array output
array_to_sort.remove(lowest) # Drop the now sorted value from the original array
if len(array_to_sort) == 0: # When `array_to_sort` is empty, we are done sorting
is_sorted = True
return sorted_array
Using sort_array¶
# Sort an array of integers
unsorted_array = [12, 7, 19, 12, 25]
sorted_array = sort_array(unsorted_array)
print(sorted_array)
[7, 12, 12, 19, 25]
# Sort an array of floats
unsorted_array = [21.3, 56.7, 2.3, 2.9, 99.9]
sorted_array = sort_array(unsorted_array)
print(sorted_array)
[2.3, 2.9, 21.3, 56.7, 99.9]
Clicker Question #3¶
Using our sort_array function from above, what will the following code snippet print out:
data = ['a', 'c', 'b']
sort_array(data)
['a', 'b', 'c']
A) [‘a’, ‘c’, ‘b’]
B) [‘a’, ‘b’, ‘c’]
C) [97, 98, 99]
D) None
E) This code will fail
How Python evaluates strings¶
'a' < 'b'
True
ord('a')
97
ord('b')
98
Clicker Question #4¶
Using our sort_array function from above, what will the following code snippet print out:
data = [True, False, True]
sort_array(data)
[False, True, True]
A) [False, True, True]
B) [True, False, True]
C) [0, 1, 1]
D) [True, True, False]
E) This code will fail
How Python evaluates Booleans¶
True < False
False
bin(True)
'0b1'
bin(False)
'0b0'
Clicker Question #5¶
Using our sort_array function from above, what will the following code snippet print out:
data = [[1, 4], [1, 2]]
sort_array(data)
[[1, 2], [1, 4]]
A) [[1, 4], [1, 2]]
B) [1, 1, 2, 4]
C) [[1, 2], [1, 4]]
D) None
E) This code will fail
SideNote: sorted¶
# Sort a list, with `sorted`
data = [7, 4, 6]
sorted(data)
[4, 6, 7]
# what about a list of strings?
sorted(['asdf','abcd'])
['abcd', 'asdf']
# Sort different data types
print(sorted(['a', 'c', 'b']))
print(sorted([True, False, True]))
print(sorted([[1, 4], [1, 2]]))
['a', 'b', 'c']
[False, True, True]
[[1, 2], [1, 4]]
Algorithmic Complexity¶
Algorithmic Complexity¶
Things we might care about:
The number of steps it takes to complete our algorithm
Usually defined in relation of the size of the input
The amount of memory it will take to run our algorithm
Properties of our sorting algorithm¶
It will require \(n^2\) steps, where \(n\) is the length of the list
It will require ~double the memory of the original list
Computability¶
Things that computers can do are things that we can write down an algorithm to do.
Things that we can write an algorithm to do are things that we can define a specific set of steps to complete.
Variable Type Checking¶
Note: The rest of the noteook includes notes to answer a student’s in class question. You are not expected to know this, but you are free to learn and use the information!
To check on an input variable’s type, you can use the following approach:
isinstance(object, classinfo)
isinstance() takes two parameters:
object: variable/object to be checkedclassinfo: class, type, or tuple of classes and types
For example, using the string_manipulator function from earlier, note that I’ve added the following two lines:
if not isinstance(string, str):
print("Warning: please provide a string as input")
This checks to see if the input is anything other than a string. If it is, the function prints a warning.
def string_manipulator(string):
if not isinstance(string, str):
print("Warning: please provide a string as input")
else:
output = ''
for char in string:
if char == 'a' or char == 'e':
char = 'z'
output = output + char
return output
# use function with a string
string_manipulator('hello!')
# print warning if not a string
string_manipulator(5)
However, sometimes, you want it to raise an error rather than just print something. Here we use raise instead of print. In this case, an error will be returned (with our specified message) to the user if the wrong variable type is provided:
def string_manipulator(string):
if not isinstance(string, str):
raise ValueError("Please provide a string as input")
else:
output = ''
for char in string:
if char == 'a' or char == 'e':
char = 'z'
output = output + char
return output
# raise error instead of print message
string_manipulator(5)