AP CSP Vocab
Bits: The smallest unit of data that a computer stores. Include 0 and 1. (Binary)
-
Bytes: 8 bits grouped together. An example is that an IP address consists of four bytes, each separated by a decimal. A decimal number can also be expressed in binary as a byte.
-
Hexadecimal: Uses base 16 Hexadecimal numbers range from 0-9, and the remaining six digits are in letters (A = 10, B = 11, C, D, E, F, etc.)
-
Unsigned integer: Nonnegative integer, while a signed integer can be both positive and negative.
Unsigned integer can be represented in regular binary
To represent a signed integer, add another digit in front of the binary number. The digit is either 0 or 1, with 0 being positive and 1 being negative.
For example, +6 is 0110 in binary, while -6 is 1110
-
Floating point: Decimal numbers are approximated by binary fractions. Many different decimal numbers may share the same binary fraction. Therefore, rounding errors can occur sometimes when performing Python calculations.
-
ASCII: A character encoding (American)
- Unicode: International encoding standard for text
- RGB: Contains views for red, blue, and green, range from 0-255
Lossy permanently deletes certain information, while lossless does not.
- Variables: Abstractions that store values (numbers, boolean values, strings) Variables are categorized based on data type, which typically includes: integer, double/float, string, and booleans.
- List: Contains elements
- Dictionaries: Consist of key value pairs
The homework example above demonstrates the use of lists and variables in Python. The album and song variable takes in a string input which is converted into an integer. The album list consists of lists and tuples, which are used to separate albums and songs.
Python
Variables
Assigning variables: variable name = value
Why use variables?
Variables help to manage complexity by storing values. They can have descriptive names that indicate what the variable does. Furthermore, variables can be reused throughout the program, and if the value needs to be changed, only the variable assignment needs to be changed, while the rest of the code can remain the same.
Lists
Assigning a list to a variable example: myList = [1, 2, 3]
Add elements to a list with: list.append(element)
Dictionaries
Create a dictionary with this syntax: dictionary name = {key:value}
Algorithm: A set of instructions to do a certain task
Selection: Determines which parts of codes are ran based on if they evaluate to true or false. Used with if statements.
Conditional: Different code statements are executed based of if they evaluate to true or false (boolean expressions (See 3.5))
Conditionals
Below is an example of an if else statement that relates to binary
This should be pretty straightforward in demonstrating what an if statement is, so I'm not going to do a code example for an if statement. Check the code cell below the next to see an example of a elif.
binaryString = input("Enter your binary string in 8 digits")
if binaryString[0:1] == 1:
print("Your binary number is greater than or equal to 128")
else:
print("Your binary number is less than 128")
weather = "rainy"
if weather == "sunny":
print("Remember to bring a hat")
elif weather == "windy":
print("Go fly a kite!")
else:
print("Remember to bring an umbrella")
Sequencing: The order in which an algorithm runs.
Selection: Algorithms figure out whether to execute a boolean statement (if statement)
Iteration: Loop (ex: for, while)
See here for a coding example demonstrating sequencing, selection, and iteration.
Coding example
The code below converts a decimal number into binary. This demonstrates sequencing, selection, and iteration.
- Sequencing: First, the binary numbers are appended to the binary list. Next, each binary number is subtracted from the inputted decimal number provided that the input number > the binary number. If that is the case, a "1" will be added to the binary string; otherwise, a "0" will be added.
- Selection: The if statement determines if a "1" or a "0" is added to the binary string.
- Iteration: Two for loops are present; the first adds binary numbers to the list and the second adds a 1 or a 0 to the binary string.
Furthermore, this code segment demonstrates concatenating strings. As you can see in the example below, the output string is either appended to 1 or 0 depending on if the power of 2 fits in the number.
def convert(num):
numOfBinary = 8
binary = [];
output = ""
for i in range(numOfBinary):
binary.append((2**(numOfBinary - 1 - i)))
for i in range(len(binary)):
if num - binary[i] >= 0:
num -= binary[i]
output += "1"
else:
output += "0"
print(output)
convert(25)
Expressions
Expressions are values that can be combined to be interpreted into a new value.
The usual mathematical symbols apply, the main difference is that the symbol for exponents is **, not ^.
The coding example here demonstrates how to use the ** (exponent).
Booleans
Booleans have 2 values: True and False.
Note: All of the code cells on this blog demonstrate boolean expressions and selections. Check a JavaScript version to see boolean expressions and iteration.
Relational Operators
==, !=, >, <, >=, <=
Relational/comparison operators can compare numbers, but they can also be used to compare strings. The later a letter is, the greater its value.
For example, as you can see in the code below, print(b > a) outputs as true, because in alphabetical order, b is after a.
a = "a"
b = "b"
print(b > a)
x = 5
y = 5
z = 3
if x == 5 and y == 5:
print("x and y are equal to 5")
if x == 5 or z == 5:
print("Either x or z is equal to 5")
if not x == 3:
print("x is not equal to 3")
You can create truth tables with logical operators.
A truth table lists all the possible True/False values that two booleans (P and Q is the convention) can take. These True/False values are then used to evaluate a third expression to see if all cases are true.
An example below is an application of DeMorgan's Law.
def checkDeMorgans():
if not a or not b == (not (a and b)):
print("DeMorgan's Law is true")
a = True
b = True
checkDeMorgans()
a = False
b = True
checkDeMorgans()
a = True
b = False
checkDeMorgans()
a = False
b = False
checkDeMorgans()
Strings
Psuedocode: Using common language to write out code. Good for planning purposes and helps other people understand what you intend to do with the code.
Index: Represents the position of an array.
Length: How long something is. For example, the length of a string is the number of characters it has.
Python
Length: len(value you want to find length of)
Substring syntax in Python: string[start index:end index - 1]
In this code, the substring takes an individual character from the binary string and calculates its values based on the base two power place it is in.
This can show specific characters in a string, which are the individual letters/numbers.
Below is an example of traversing through a string.
message = "StRiNG"
for i in range(0, len(message)):
print(message[i])
You can also change a string to uppercase or lowercase with the upper() and lower functions.
msg = "dEfaUlt stRinG"
print(msg)
print(msg.upper() + " now uppercase".upper())
print(msg.lower() + " now lowercase".lower())
num = int(input("Enter a number"))
print("Enter a number: " + str(num))
if num > 0:
print("Your number is positive")
if num > 50:
print("Your number is also greater than 50")
else:
print("Your number is negative")
if num < -50:
print("Your number is also less than -50")
Use iteration to simplify your code and to prevent manually repeating code over and over again.
Iteration:
While loop: while condition:
See the code cell below for an example of iterating through a list using a while loop.
myList = ["apples", "oranges", "bananas"]
i = 0
while i < len(myList):
print(myList[i])
i += 1
break
i = 0
while (i < 5):
print(i)
if i == 3:
break
i+= 1
def addNum(num1, num2):
return num1 + num2
sum = addNum(5, 3)
print(sum)
Lists
- Lists: Collections that store data, can use loops to iterate through them
Python: list name = [element 1 , element 2 ]
- Index: Specify the location where a list element is found, usually starts at 0 Note: In AP CSP, list indexes start at 1
Example: myList = [0, 1, 2]
print(myList[0]) will output 0
Below is an example of using different methods for lists:
myList = [1, 2, 3]
print("Element at index 1 in myList: " + str(myList[1]))
var1 = myList[0]
print("Value of var1 (element at index 0) " + str(var1))
myList.insert(1, 1.5)
print("Inserting 1.5 into list at index 1... " + str(myList))
myList.append(4)
print("Adding the value 4: " + str(myList))
myList.remove(4)
myList.remove(1)
print("Removing element 1 and 4... " + str(myList))
Iteration:
While loop: while condition:
See the code cell below for an example of iterating through a list using a while loop.
myList = ["apples", "oranges", "bananas"]
i = 0
while i < len(myList):
print(myList[i])
i += 1
For loop (iterate through lists): for element name in list name:
Recursive loop: Recursive loops call themselves by calling the function name again
Note: Don't do the code below, will run forever
def recursive_function():
recursive_functionYou can put a dictionary in a list, below is an example:
Note: When you are printing a dictionary by its key, specify the key name in brackets [].
Example: myList = {"myKey":"myValue"}, to print out the value, do: print(myList["myKey"])
myList = [{1: "red", 2: "blue"}, {1: "purple", 2: "green"}]
print("Printing the first dictionary in myList: " + str(myList[0]))
print("Printing the second dictionary in myList: " + str(myList[1]))
print("Printing the second key in the first dictionary in myList: " + str(myList[0][2]))
Procedures
-
Procedure: Programming instructions, can have parameters/return values
-
Parameters: The input value in a procedure/function
-
Arguments: The values of the parameters when they are called.
-
Modularity: Separating functions into many pieces for better organization and to decompose a larger problem so that many parts of the code work to perform one function.
-
Procedural Abstraction: Gives a name (tells you what the task does) but does not show how a task is done. It takes in parameters and may execute different statements (selection) depending on the parameter. It is used to decompose a large problem by providing a solution to a smaller problem.
Calling Procedures
Procedure call interrupts the code and executes the code inside the procedure. After that finishes, the program moves back to where it originally was when it called the procedure.
A procedure may return a value, but it does not need to do so
Calling a procedure: procedure name(arguments)
Developing Procedures
When making a procedure, make sure to do the following:
- Give the procedure a descriptive name
- Note what parameters are needed
- Note any required data
- Determine if the procedure returns a value or just simply does something
JavaScript notes
function name(parameters) {}: Creates a function
-
Library: Allows the user to import methods that can perform functions that would be complicated to code The entire package can be imported or just a single method from the package. To import a single method from a package, type
from package name import method name -
Import a library as a user provided name:
import name as user input name -
To import all methods from a library, type
from name import *
Packages example: numpy, datetime, turtle
from math import *
print("Enter 1st number")
num1 = float(input("Enter 1st number"))
print(num1)
print("Enter 2nd number")
num2 = float(input("Enter 2nd number"))
print(num2)
print("Number 1 rounded up: " + str(ceil(num1)))
print("Number 2 rounded up: " + str(ceil(num2)))
print("Number 1 rounded down: " + str(floor(num1)))
print("Number 2 rounded down: " + str(floor(num2)))
print("LCM: " + str(lcm(floor(num1), floor(num2))))
print("GCM: " + str(gcd(ceil(num1), ceil(num2))))
print("Factorial of num1: " + str(factorial(floor(num1))))
print("Factorial of num2: " + str(factorial(floor(num2))))
print("Square root of 1: " + str(sqrt(num1)))
#print("Number 1 rounded up: " + str())
Below is an example that utilizes the random library
import random
print(random.randint(1, 10)) # prints a random number between 1 and 10
-
Simulations: Abstractions that mimic things that occur in the real world, you can use simulations to calculate things that you can't test in the real world May contain bias because some real world elements can not be factored in Use random number generators to simulate randomness and variability. Applications: Rolling a dice, flipping a coin, spinners
-
Random number generator: You can use the random library:
import random
-
Problem:
- Decision Problem: A problem with yes/no answer
- Organization Problem: A problem with the goal of finding a best answer
- Instance: Problem with specific input
-
Efficiency: How much computing you need for a problem to be resolved
- Polynomial Efficiency (Good): Proportional amount of time (linear) the more work you do
- Exponential Efficiency (Bad): Exponential amount of time the more work you do (ex: double the amount of time)
- Heuristic Approach: Finding a more efficient optimal solution
- Decidable Problem: A decision problem with a solution that always outputs correctly
- Undecidable Problem: A decision problem with no solution