CL3: Algorithmic Thinking
Contents
CL3: Algorithmic Thinking¶
Welcome to the third coding lab!
In this CodingLab we will be thinking and working on functions and algorithms.
The first part is more abstract - thinking about algorithms and functions, and sketching out some pseudocode.
After that, we’ll move to more practice with functions.
PseudoCode¶
First, let’s briefly consider the idea of pseudocode.
Pseudocode is an informal, ‘high-level’ sketch or description of a program or algorithm.
It will typically resemble the structure of a program, but the details to make it actually run have not been fleshed out.
Pseudocode Human Language¶
Some pseudocode is written in human level language, in a way that sketches out the tasks and general control flow.
This highly abstract pseudocode is often not specific to any particular programming language.
# PseudoCode for checking if a student got full credit on assignment
function that takes a list of student ids with student grades
create an output object to collect full credit
for student in list of grades
if grade of student is equal to max grade
add to list of full credits
return list of students who got full credit
Pseudocode in Python format¶
You can also write pseudocode, that is much closer to Python, including Python syntax, but that is more of a template / outline.
PseudoCode like this is sometimes just a work-in-progress that is just not yet finished.
Note the use of the pass keyword - pass is just a placeholder keyword, that does nothing.
# PseudoCode for a function to email a list of emails, and return a log of what was sent
def sent_emails(list_of_emails):
emails_sent = {} # Define an output variable for the logging
for email in list_of_emails:
# Send email to current student
pass
# Add logging information that email was sent
email_sent[email] = True
return emails_sent
Computation & Algorithms¶
Both computers and humans are good at some things, and bad at others. However, it tends to be different things that computers and humans are good at.
Here is a list of possible tasks that a human and/or computer could try and do:
Given a list of 100K values, find the average and range of the list
Sort an array of randomly generated numbers from smallest to largest
Recognize the saddest part of a movie
Recall specific facts, like answering ‘which day of the week was the 1st of June, 1997
Identify the likely country of origin of a person from their accent
Create a meme
Sort a list of 10,000 names alphabetically
Rank memes in order of how funny they are
Given two locations, figure out the best route to drive to get between them
Recognize the emotional state of a person
Flexibly change strategy, based on cues in the environment
Write and perform a winning rap battle
Learn and be able to understand a human language
Learn and be able to understand a programming language
Play tic-tac-toe
Write a review of a movie
Play chess
Play PACMAN
Instructions¶
For the tasks above, we want to try and decide whether it is a task that computers would be better at, that humans would be better at, or if it would be a tie.
In small groups (2 or 3 people), pick 3 or 4 examples from the list of tasks above, have a quick discussion about the task and hand and try to answer the question of who (computers and/or humans) this task would be easier for.
For each task, try to imagine how you might try and do this in Python.
Use pseudocode to sketch out an outline of the procedure.
If you think it is something computers can do well, your pseudocode should roughly cover the whole process.
If you think think it is more of a human thing, try to identify which part of the process, in particular, is difficult to specify within a formal algorithm.
As you work through a few examples, make sure you talk through at least one of each of ‘computer better’ and ‘human better’ task.
Note: as a rule of thumb, computers can do, and are good at anything we can write down an algorithm to complete.
So one way to think of this task is to think through if and how you can think of writing an algorithm to complete this task.
Below is an example, with an answer for the first listed task.
Example: Given a list of 100K values, find the average and range of the list¶
This is a task that is easier for computers because we can write down a clear set of steps to complete this task (we can write an algorithm).
Humans would not be good at completing this task, as there are a lot of steps to complete, and it would be slow, and we might not have the memory to do it.
# Pseudocode for array statistics
def array_statistics():
# Find the mean of the array.
pass
# To do so:
# Find the total sum of the array
# Find the number of elements in the array
# Divide the sum by the number of elements
# Find the range of the array.
pass
# To do so:
# Find the maximum value of the array
# Find the minimum value of the array
# Calculate range by subtracting the max from the min for the array
# Return the mean and range of the array
return None
## Make some notes & write some pseudocode for you chosen tasks here
Functions¶
Functions are a way to organize code into a procedure that we can repeat and use whenever we want.
Function Questions¶
Write a function that takes one input, multiplies it by two and returns the result¶
This function has been started for you, with the name mult_two.
Add some more code to finish this function.
def mult_two(input_number):
# YOUR CODE HERE
# Check that you can use the function
mult_two(2)
# Check this function returns the correct outputs
assert mult_two(2) == 4
assert mult_two(3) == 6
Write a function that takes two inputs, adds them together, and returns the result¶
Call this function add_two.
def add_two(_FILL_IN_INPUTS_):
# YOUR CODE HERE
# Check that you can use the function
add_two(2, 2)
# Check this function returns the correct number
assert add_two(2, 2) == 4
assert add_two(3, 2) == 5
Write a function with a conditional inside it¶
You can decide what this function does.
It could, for example, take a boolean, and print out a status if the input is True.
# YOUR CODE HERE
Write a function with a loop inside it¶
You can decide what this function does.
It could, for example, take a list of numbers, and add 1 to each element, and return the new list.
# YOUR CODE HERE
Write a function with a loop and a conditional inside it¶
You can decide what this function does.
It could, for example, take a list of booleans, and count how many elements are True, returning a count of True values.
# YOUR CODE HERE