Today's lab will focus on logical expressions and circuits and absolute paths in the Unix operating system.
Software tools needed: web browser and Python IDLE programming environment with numpy and matplotlib packages installed.
See Lab 1 for details on using Python, Gradescope, and Blackboard.
Last week, we introduced decisions (if-statements). These relied on the "test" which was an expression that evaluated to true or false.
We can build up more complicated logical expressions using built-in operators, and, or, and not. A standard way to summaries these operators is with truth tables. A truth table lists all the possible inputs and gives the output for each combination.
For example, here is the truth table for the and operator:
in1 | in2 | in1 and in2 |
---|---|---|
True | True | True |
False | True | False |
True | False | False |
False | False | False |
It lists all the possible combinations of values for the inputs, in1 and in2 and what and would give as output. For example, if in1 is True and in2 is False, the value of in1 and in2 can be read off the last column of the third line of the truth table as False.
Similarly here is the truth table for or:
in1 | in2 | in1 or in2 |
---|---|---|
True | True | True |
False | True | True |
True | False | True |
False | False | False |
For example, if in1 is True and in2 is False, the value of in1 or in2 can be read off the last column of the third line of the truth table as True.
The not operator changes the input from false to true, or true to false. That is, not True is false and not False is true. We can write this in the table format above:
in1 | not in1 |
---|---|
True | False |
False | True |
These logical operators are useful building complex tests for our if-statements (as well as other control structures that will be introduced later).
As an example of logical expressions, we will use them to estimate the snow pack level in California over the last drought using satellite imagery.
Landsat Satellite Program is a joint program of USGS and NASA that has provided continuous images of the earth since 1972. The data is publicly available through the USGS-EROS site and has been invaluable in mapping changes in the earth. Today, we will use data images from the USGS remote sensing gallery:
http://remotesensing.usgs.gov/gallery/
The snow pack in the Sierra Nevada mountains provide almost a third of the water used by California. As a first estimate of snow pack, the number of pixels that are (nearly) white are counted. How much change has their been in the Sierra Nevada snowpack during the past drought in California? Here are images from before and during the worst years of the drought:
February 2011 | February 2013 | February 2014 |
How much snow is there? We will use the number of pixels that are nearly white as an estimate of the snow. We can add in a new variable, countSnow to keep track of each time a pixel is nearly white. Here's an outline of our program:
When is a pixel white? It's when the red, green, and blue values are close to 100%. In code, we would have:
t = 0.75 #Threshold for almost white-- can adjust between 0.0 and 1.0 ... for i in range(ca.shape[0]): for j in range(ca.shape[1]): if (ca[i,j,0] > t) and (ca[i,j,1] > t) and (ca[i,j,2] > t): countSnow = countSnow + 1Let's translate that into Python. Open up a new IDLE window and copy over the outline. Using the image programs from last lab as a template, fill in as much as possible before looking at the program below:
#Name: CSci 127 Teaching Staff #Email: hunterCSci127help@gmail.com #Date: Fall 2017 #This program loads an image, counts the number of pixels that are # nearly white as an estimate for snow pack. #Import the packages for images and arrays: import matplotlib.pyplot as plt import numpy as np ca = plt.imread('CaliforniaDrought_02232011_md.png') #Read in image countSnow = 0 #Number of pixels that are almost white t = 0.75 #Threshold for almost white-- can adjust between 0.0 and 1.0 #For every pixel: for i in range(ca.shape[0]): for j in range(ca.shape[1]): #Check if red, green, and blue are > t: if (ca[i,j,0] > t) and (ca[i,j,1] > t) and (ca[i,j,2] > t): countSnow = countSnow + 1 print("Snow count is", countSnow)
This program assumes that you have downloaded and saved CaliforniaDrought_02232011_md.png to the same directory as your program.
How can you modify your program to let the user specify the input file? See Programming Problem List.
The logical expressions above are useful not only in designing decisions and selecting data in Python, but the same concept underlies much of the hardware of computers. The and, or, and not can all be simulated in hardware via logic gates. These gates take inputs (usually 0 or 1) and output a value, based on the logical operator it is simulating.
Here is a simulator for circuits. Let's see an AND gate in action:
Try making a circuit with an OR gate:
What is different between the behavior of the OR and AND gates?
Now, let's build a circuit, or collection of gates, that takes majority of 3 inputs, called in1, in2, in3:
Here's a window for building your circuit (if running from home, you may need to allow the browser to run flash-- what the circuit app uses for graphics). Directions (with images) are below:
Build your circuit as you read the instructions below:
Our last gate is an or, so we will write down an or
(lotsOfStuff1) or (lotsOfStuff2)We'll use parenthesis to keep things neat. Now, let's look at the left hand side (lotsOfStuff1). It also has an or, so we can write it down:
((lotsOfStuff3) or (lotsOfStuff4)) or (lotsOfStuff2)Let's keep refining our expressions (lotsOfStuff3) has an AND at the top, so, we will replace it with:
(((lotsOfStuff5) and (lotsOfStuff6)) or (lotsOfStuff4)) or (lotsOfStuff2)(lotsOfStuff5) is just a wire back to the first input, so, we can write that instead:
((in1 and (lotsOfStuff6)) or (lotsOfStuff4)) or (lotsOfStuff2)and similarly, (lotsOfStuff6) is just a wire back to the second input, so, we can write that instead:
((in1 and in2) or (lotsOfStuff4)) or (lotsOfStuff2)That looks better! If look at lotsOfStuff4, we see an AND gate with wires back to the first and third inputs:
((in1 and in2) or (in1 and in3)) or (lotsOfStuff2)Similarly, we can replace lotsOfStuff2 with:
((in1 and in2) or (in1 and in3)) or (in2 and in3)Save this line to a text file (you can use any text editor, just make sure to save it as plain text, with no formatting):
#Name: Your name here #Date: 16 October 2017 #Program #23: Computes the majority of 3 inputs out = ((in1 and in2) or (in1 and in3)) or (in2 and in3)(your expression, preceded by out = ). For the logical expressions homework, you submit just a text file with the logical expressions. The grading script evaluates the expression, testing it with different inputs. See the Programming Problem List.
In addition the AND, OR, and NOT gates, there are several other standard gates. For each, we can build a circuit using just AND, OR, and NOT gates that gives the same output.
What does a NAND gate do?
Toggle the inputs to figure out what the gate does.
Now, build a circuit that has the same behavior as a nand gate (i.e. for the same inputs, both give identical output) using only AND, OR, and NOT gates.
When you have the answer, label your inputs in1 and in2, save the answer in a file:
#Name: Your name here #Email: Your email here #Program: Computes NAND of two inputs, using only AND, OR, and NOT gates out = ...(where ... is replaced by your answer). See the Programming Problem List.
In Lab 3 we looked at Hexadecimal numbers to represent colors.
Another important number system in Computer Science is the Binary Number System. The digital logic design discussed above allows two voltage levels or states: false ≡ off ≡ 0 and true ≡ on ≡ 1, translating naturally into binary numbers.
Each digit in a number has a "position". In the decimal (base 10) system to us so familiar, we know that the possible digits are 0 - 9 and each position is a power of 10. So if we see a 7 in the "ones" position we know it is 7 ones. If we see a 7 in the "tens" position we know it is 7 tens and so on. Thus, the number 77 in base 10 is 7 tens + 7 ones.
In binary (base 2) we have two digits, 0 and 1, and each position is a power of two. In each position we can have either a 0 or a 1, so in the "ones" position we either have a 1 or not. In the "twos" position we either have a 2 or not, in the "fours" position we either have a 4 or not, and so on.
For example, the binary number 11001 has five positions: "ones", "twos", "fours", "eights" and "sixteens" (consecutive powers of two). We have 1 only in the "ones", "eights" and "sixteens" positions, so 11001_{base2} = 1+8+16 = 25_{base10}.
Logic gates thus perform logical operations on binary numbers. We can then combine logic gates to do arithmetic on binary numbers: see programming problem 34.
Last lab, we introduced relative paths for navigating the directories via the shell. Relative paths (e.g. cd ../) used the current location when executing. We can also use absolute paths that are independent of your location. For example,
$ cd /usr/bin $ pwd $ lswill change your working directory to one of the machine's standard bin directories which is filled with programs, or binaries. The next two commands show the path to the working directory and list its contents. These binaries are in a central location to make them easier to find and use.
Since it is nice to be able to return to your default, or home directory, there is a built-in short-cut for home (~). Try
$ cd ~ $ pwd $ lsThe first command will return you to your home directory, no matter where you started.
Next lab, we will introduce scripts, or files of shell commands, that we can execute at the command line.
If you finish the lab early, now is a great time to get a head start on the programming problems due early next week. There's instructors to help you, and you already have Python up and running. The Programming Problem List has problem descriptions, suggested reading, and due dates next to each problem.