Big Idea 3, Simulations and SQLite Lesson Notes
My notes on the lesson by Drew, Vivian, Aliya, Sri and Sreeja
- Review Topics
- Selection
- Introduction to Algorithms
- Iteration and Simulations
- Databases
- Grading
Review Topics
All of the topics below are things that have been heavily covered and used throughout the class. We will mostly be focusing on more complicated uses and mechanics of these topics.
Lists
- What are Lists?
- Lists are an ordered sequence of elements, where each element is a variable
- Unlike dictionaries, lists' keys are all integers that describe the order of the list
Some examples of lists:
- Playlist of songs
- names of students in a class
-
contacts on your phone
-
Each element of a string is referenced by an index (which is a number) and they generally start 0 but for the AP Exam it starts at 1.
- AP Exam: 1,2,3,4 etc.
- Python: 0,1,2,3 etc.
How do lists Manage Complexity of a program?
- We may not need as many variables. For example:
- One Variable that holds all students would be better than having a variable for EACH student
- There can also be a list of test scores so if they need to be curved then the same calculation can be applied to the list (that has all the students) instead of doing the calculations one at a time
Answer the following questions about the code block below:
- Why do you think lists are helpful? What word does College Board like to use to describe the function of lists?
# variable of type string
name = "Sri Kotturi"
print("name", name, type(name))
# variable of type integer
age = 16
print("age", age, type(age))
# variable of type float
score = 90.0
print("score", score, type(score))
print()
# variable of type list (many values in one variable)
langs = ["Python", "JavaScript", "Java", "Bash", "html"]
print("langs", langs, type(langs))
print("- langs[2]", langs[2], type(langs[2]))
print()
# variable of type dictionary (a group of keys and values)
person = {
"name": name,
"age": age,
"score": score,
"langs": langs
}
print("person", person, type(person))
print('- person["name"]', person["name"], type(person["name"]))
grade1 = 10
grade2 = grade1
average_grade = (grade1 + grade2) // 2 #what are these two slashes?
print(average_grade)
num1 = 2
num2 = 4
num3 = 6
num1 = num2 ** num3
num3 = num1 % 5
num2 = (num1 + num3) // 9
print(num1)
print(num2)
print(num3)
Selection
Selection refers to the process of __ in a program based on certain conditions. It is normally done with conditional statements.
Conditionals
What is a conditional?:
- Statement that allows code to execute different instructions if a certain condition is _
- Allows program to make decisions based on data and input
What are the main types of conditional statements?:
- if
- elif
- else
If statements
- The if statement is used to check if a certain condition is true. The condition can be any expression that evaulates to a boolean value, True or False. If the condition is True, then it executes a code block.
- If (condition) then (consequence)
- Example:
x = int(input("Enter a number"))
if x > 0: # if condition, check if this is true of false
print("x is positive") # code that will execute if condition is met
Else
- The else statemnt executes a code block when the if condition is False.
- If (condition) then (consequence A), else (consequence B)
Elif
- The elif statement can check ___ conditions in a sequence, and execute a certain block of code if any of the conditions are true.
-
If (condition) then (consequence A), elif (condition) then (consequence B), else (consequence C)
-
Example adding onto the code from before to take negative numbers and 0 into account
x = int(input("Enter a number, x:"))
if x > 0: # if condition, check if this is true of false
print("x is positive") # code that will execute if condition is met
elif x < 0: # if previous condition not true... elif condition, check if this is true of false
print("x is negative")# code that will execute if condition is met
else: # everything else, in this case it is if x == 0
print("x is zero") # only executes if all previous conditions are not met
x = int(input("Enter a number, x:"))
if x % 2 == 0:
print("x is even divisible by 2")
# only ever checks is x is divisble by 3 if x is even. nested conditional
if x % 3 == 0:
print("x is divisible by 3")
else:
print("x is not divisible by 3")
else:
print("x is odd")
Binary Search
What is binary search and what is it used for?:
- Find and select a specific element in a sorted list of elements
How does binary search work?:
- Repeatedly divides the search interval in half to find the middle element and __ the middle value to the target value, if not the same then it continues on to either the lower or upper half
- Eliminate half of the remaining search interval elements each time
- Efficient way to search for element in large dataset
What is the time complexity and why?:
- O(log(N))
- The maximum number of iterations is the amount of times the list can be divided in half until it reaches 1 number
-
Dividing by 2, so it is log2(N), logarigthm of n base 2
-
You may recognize the example below from the binary lesson last Friday
import random
def binary_search_game():
low = 1
high = 100
target = random.randint(low, high)
while True:
guess = (low + high) // 2
print(f"Is your number {guess}?")
response = input("Enter 'higher', 'lower', or 'yes': ")
# conditional statements to check target number and guess
if response == 'yes':
print(f"I guessed your number {guess}!")
break
elif response == 'higher':
low = guess + 1
elif response == 'lower':
high = guess - 1
else:
print("Invalid input, please enter 'higher', 'lower', or 'yes'.")
binary_search_game()
response = input("Enter 'rock(r)', 'paper(p)', or 'scissors(s)': ")
Introduction to Algorithms
- an algorithm is a __ that describes how to solve a problem or perform a specific task using a computer program.
- It is a precise sequence of computational steps that take an input and produce an output
How do Algorithms relate to data structures?
- Algorithms often rely on specific data structures to __.
- Sorting algorithms require a data structure such as an array or a linked list to store and manipulate data.
- Searching algorithms such as binary search require data structures like ___ to organize and search through data.
Important Terms
What is an algorithm?
- it is a ___ set of instructions that accomplishes a specific task
Sequencing
- means that there is an _ in which to do things
Selection
- Helps to choose _ based off of a decision that the programmer wants to make
Iteration
- Repeat something until the condition is met. (also referred to as repetition)
Calling and Developing Procedures
- A procedure is a ___ that performs a specific task.
- To call a procedure, you need to know its name and any arguments it requires.
- When a procedure is called, the program jumps to its instruction and starts executing it.
- The arguments passed to a procedure can be used within the procedure to __.
- After the procedure has completed its task, it returns control back to the calling program.
def add_numbers(a, b):
sum = a + b
print("The sum of", a, "and", b, "is", sum)
# Call the procedure with arguments 5 and 7
add_numbers(5, 7)
- The result of the procedure can be __, printed to the screen, or used in any other way that is required by the program.
- Procedures can be defined within the same program ___, and can be reused across multiple parts of the program.
- To avoid errors and improve code readability, it's important to define and call procedures with proper syntax and conventions that are appropriate for the programming language you're using.
def calculate_average(numbers):
total = sum(numbers)
count = len(numbers)
average = total / count
return average
# Call the procedure with a list of numbers
numbers_list = [10, 20, 30, 40, 50]
result = calculate_average(numbers_list)
# Display the result
print("The average of", numbers_list, "is", result)
Algorithmic Efficiency
- Algorithmic efficiency refers to the amount of __ needed to execute an algorithm.
- The efficiency of an algorithm can be measured in terms of its __.
- Time complexity refers to the amount of time required by an algorithm to complete its task as a function of its input size.
- Space complexity refers to the ___ required by an algorithm to complete its task as a function of its input size.
- can be analyzed using __, which provides an upper bound on the worst-case time and space complexity of the algorithm.
What is the time complexity of the following code:
- O(N)
- O(N*log(N))
- O(N * Sqrt(N))
- O(N*N)a = 0
for i in range(N):
for j in reversed(range(i, N)):
a = a + i + j
What will be the time complexity of the following code?
- n
- (n+1)
- n(n-1)
- n(n+1)
value = 0
for i in range(n): #iterates "n" times, with "i" taking on values from 0 to n-1.
for j in range(i): # iterates "i" times, with "j" taking on values from 0 to i-1.
value=value+1
- Efficiency can be improved by _ or by using more efficient data structures and algorithms.
- Some common techniques for improving efficiency include reducing the ___, caching results, and ___.
- Understanding algorithmic efficiency is important in software development, as it can impact the performance of applications and their ability to scale with larger data sets.
Iteration and Simulations
Simulations are _ or systems that use mathematical algorithms and computer programs simulate the real behavior and aspects of the subject being modeled.
Simulations are most often used to model __ that would be difficult to test in real life, such as modeling the spread of diseases in certain ecosystems or testing the functionality of a potential product before it is made.
In this lesson, we will be looking at lists, iteration, and random values through the lens of simulations.
PLEASE RUN THE CODE BELOW BEFORE INTERACTING WITH THE CODE SEGMENTS IN THIS SECTION!
class Card:
def __init__(self, suit, val):
self.suit = suit
self.val = val
if val == 11:
self.kind = "Ace"
elif val == 12:
self.kind = "Jack"
elif val == 13:
self.kind = "Queen"
elif val == 14:
self.kind = "King"
else:
self.kind = str(self.val)
#return a formatted string version of a card
def show(self):
return f"{self.kind} of {self.suit}"
#adjust aces to prevent breaking
def ace_adj(self):
if self.kind == "Ace":
self.val = 1
For Loops
For loops are probably the most well-known type of iterative loop used in code. Most of us know about the for variable in list format.
One helpful tool not a lot of people know about is the enumerate() function. When used in conjunction with a for loop, you can always have _ and value of each selected list entry.
numlist = [3, 5, 68, 203]
for key, num in enumerate(numlist):
print(f"This entry's index is {str(key)}, but its value is {str(num)}.")
print(f"The difference between the value and the index is {num - key}.")
QUESTION: How is the key, num in enumerate(list) format similar to the format used when applying a for loop to a dictionary?
Answer: __
List Comprehension
You may also see for loops used within a list like below. We went over this in class fairly recently. In this case, it is used to show the cards in the hand of a player.
player_hand = [] # the player's hand is represented as a list
# because lists are mutable (can change), they can be added to, like drawing a card
# assume the deck below is a a deck of shuffled cards
deck = [Card("Hearts", 3), Card("Spades", 12), Card("Diamonds", 11)]
def draw_card(hand, deck):
hand.append(deck.pop())
#try it out
draw_card(player_hand, deck)
print([card.show() for card in player_hand])
def fibonacci(terms):
if terms <= 1:
return terms
return fibonacci(terms-1) + fibonacci(terms-2)
fibonacci(5)
def build(deck):
for suit in ["Spades", "Clubs", "Diamonds", "Hearts"]:
for val in range(2, 15): #HINT: try replacing this function
deck.append(Card(suit, val))
While Loops
While loops aren't used in the program, but they offer a __ a set of instructions in a program. The procedure below the while [condition] line will occur until the condition is made not true.
Student Interaction: How could this build function be altered to function with a while loop within it?
def build(deck):
for suit in ["Spades", "Clubs", "Diamonds", "Hearts"]:
for val in range(2, 15):
deck.append(Card(suit, val))
#HINT: you may want to make an incrementing i variable
While loops also alter an alternative way to loop a set of instructions forever, until a precise thing occurs to break the loop. See the code below.
import random
i = 0
while True:
i += 1
ch = random.randint(1, 11)
if ch == 10:
print(f"It took {str(i)} random generations to get 10.")
break
49 random generations is a lot more than it would normally take, but it's important for code to be able to model unlikely, yet possible scenarios. Speaking of random values...
Random Values
Because unpredictable randomness occurs in the real world, it's important to have a way to represent it. Simulations are _, which could be in the form of random number generation or other methods like shuffle.
Card decks are a great example of how random values can be used to represent real-world scenarios. In the card simulation, the random module's shuffle function is used to quite literally shuffle the deck, seen below.
def shuffle(deck):
random.shuffle(deck)
Often, random selection methods use functions like ______ or ________ as ways to select certain indexes in lists, or might use the random numbers in some other way.
QUESTION: Without shuffling the card order of the deck, can you think of a way that the aforementioned random module functions could be used to get a random card from the deck? Do so in the code cell below.
import random
#find another random function that could pull a random card from a deck of UNSORTED cards
Simulation Homework
Now that you've learned about simulations and how they're used, it's time to apply that knowledge by creating a (basic) simulation of a real-world scenario. It can be something in nature, like the changes in the wildlife population of a certain area; it can be a game, like Uno (no blackjack though, that's taken); or it can be something completely random and unique.
The simulation must include...
- Use of at least one random value
- At least one list or similar data type (dictionary, set, etc.)
- Efficient use of iteration (must support the purpose of the simualtion)
- Selection (use of conditionals)
Do this in your student copy in the cell provided. This is worth 0.9 (or more with extra credit) out of the 3 possible points.
# (Concert attendance? Wind speeds? Interactions between subjects in large environments?)
# Think about the sort of things that could be saved in lists, dictionaries, etc.
# (Even better if you can take advantage of the specific features of multiple types of data sets!)
# What kind of iteration happens in the real world?
# What occurs repeatedly, even over a long period of time?
# You could model the results of a disease spreading through a population without it taking IRL years.
Databases
We have already gone over databases in this class, but here is a refresher. A database contains data that's __. The information in this database can then be __ from the database and can be used in a program.
Setting Up the Database
Run the code cell below to prepare SQLite to create the database. If your system is struggling with the flask functions, verify that you're in the correct Python environment. REMEMBER: You should only db.init_app(app) ONCE during the process!
from flask import Flask
from flask_sqlalchemy import SQLAlchemy
# Setup of key Flask object (app)
app = Flask(__name__)
# Setup SQLAlchemy object and properties for the database (db)
database = 'sqlite:///sqlite.db' # path and filename of database
app.config['SQLALCHEMY_TRACK_MODIFICATIONS'] = False
app.config['SQLALCHEMY_DATABASE_URI'] = database
app.config['SECRET_KEY'] = 'SECRET_KEY'
db = SQLAlchemy()
# This belongs in place where it runs once per project
db.init_app(app)
import os, base64
import json
from sqlalchemy.exc import IntegrityError
# Define the User class to manage actions in the 'users' table
class User(db.Model):
__tablename__ = 'players' # table name is plural, class name is singular
# Define the User schema with "vars" from object
id = db.Column(db.Integer, primary_key=True)
_username = db.Column(db.String(255), unique=False, nullable=False)
_streak = db.Column(db.Integer, unique=True, nullable=False)
# constructor of a User object, initializes the instance variables within object (self)
def __init__(self, username, streak):
self._username = username
self._streak = streak
# a username getter method, extracts username from object
@property
def username(self):
return self._username
# a setter function, allows username to be updated after initial object creation
@username.setter
def username(self, username):
self._username = username
# a getter method, extracts streak from object
@property
def streak(self):
return self._streak
# a setter function, allows streak to be updated after initial object creation
@streak.setter
def streak(self, streak):
self._streak = streak
# output content using str(object) in human readable form, uses getter
# output content using json dumps, this is ready for API response
def __str__(self):
return json.dumps(self.read())
# CRUD create/add a new record to the table
# returns self or None on error
def create(self):
try:
# creates a person object from User(db.Model) class, passes initializers
db.session.add(self) # add prepares to persist person object to Users table
db.session.commit() # SqlAlchemy "unit of work pattern" requires a manual commit
return self
except IntegrityError:
db.session.remove()
return None
# CRUD read converts self to dictionary
# returns dictionary
def read(self):
return {
"id": self.id,
"username": self.username,
"streak": self.streak
}
# CRUD update: updates user name, password, phone
# returns self
def update(self, username, streak):
"""only updates values with length"""
if len(username) > 0:
self.username = username
if streak > 0:
self.streak = streak
db.session.commit()
return self
# CRUD delete: remove self
# None
def delete(self):
db.session.delete(self)
db.session.commit()
return None
"""Database Creation and Testing """
# Builds working data for testing
def initUsers():
with app.app_context():
"""Create database and tables"""
db.create_all()
"""Tester data for table"""
u1 = User(username="Mr. Cards", streak=5)
u2 = User(username="Kard Kowntre", streak=10)
u3 = User(username="Un Bea Table", streak=15)
users = [u1, u2, u3]
"""Builds sample user/note(s) data"""
for user in users:
try:
user.create()
print(f'Created user with username "{user.username}".')
except IntegrityError:
'''fails with bad or duplicate data'''
db.session.remove()
print(f"Records exist, duplicate email, or error: {user.username}")
def __init__(self, username, streak):
self._username = username
self._score = streak
@streak.setter
def streak(self, streak):
self._streak = streak
@property
def streak(self):
return self._streak
import json
from flask import Blueprint, request, jsonify
from flask_restful import Api, Resource # used for REST API building
user_api = Blueprint('user_api', __name__,
url_prefix='/api/users')
api = Api(user_api)
class UserAPI:
class _CRUD(Resource): # User API operation for Create, Read. THe Update, Delete methods need to be implemeented
def post(self): # Create method
''' Read data for json body '''
body = request.get_json()
''' Avoid garbage in, error checking '''
# validate name
username = body.get('username')
if username is None or len(username) < 1:
return {'message': f'Username is missing, or is less than a character'}, 400
# validate uid
streak = body.get('streak')
if streak is None or streak < 1:
return {'message': f'Streak is missing, or is less than 1'}, 400
''' #1: Key code block, setup USER OBJECT '''
uo = User(username=username,
streak=streak)
''' #2: Key Code block to add user to database '''
# create user in database
user = uo.create()
# success returns json of user
if user:
return jsonify(user.read())
# failure returns error
return {'message': f'Processed {username}, either a format error or a duplicate'}, 400
def get(self): # Read Method
users = User.query.all() # read/extract all users from database
json_ready = [user.read() for user in users] # prepare output in json
return jsonify(json_ready) # jsonify creates Flask response object, more specific to APIs than json.dumps
def put(self):
body = request.get_json() # get the body of the request
id = body.get('id')
username = body.get('username')
streak = body.get('streak') # get the UID (Know what to reference)
user = User.query.get(id) # get the player (using the uid in this case)
user.update(username=username, streak=streak)
return f"{user.read()} Updated"
def delete(self):
body = request.get_json()
id = body.get('id')
player = User.query.get(id)
player.delete()
return f"{player.read()} Has been deleted"
# building RESTapi endpoint
api.add_resource(_CRUD, '/')
This is important particularly in a full flask respository context, but in this case, you'll just need to run the initUsers() function.
initUsers()
An Alternative Method of Making SQLite Databases
In a previous lesson, we went over using the cursor object in SQLite3. Rather than go over all of that here, this lesson goes over it thoroughly. (You may use this method for the homework below.)
Database Homework
For this assignment, we'd like you to make your own database file as instructed above. Remember, the API file isn't necessary in this case; you'll be focusing on making the model and the init function.
Your database must include these things:
- A class with at least four attributes (if not the cursor method)
- Setters and getters for this class (if not the cursor method)
- Each of the CRUD functions
- An
initfunction with at least four entries - A screenshot showing proof that your SQLite file has been created correctly
Feel free to base your database on the model provided above! Ask our group if you have any questions or concerns.
# If you've already run the db.init_app(app) function while in this notebook,
# don't do it again until you've closed it!
Grading
Your submission will be graded based on the following criteria:
- Filling in the blank throughout the lesson and providing code in the given cells when applicable (0.9)
- Simulation homework (0.9)
- Database homework (0.9)
Here are some ideas for ways to increase your score above a 2.7:
- Make a frontend version of your simulation that can be interacted with on your blog
- Connect your simulation to the database you create
- Create a menu that allows a user to make an entry in your database (CRUD functions within it)
- You can establish a relationship between two classes/tables in your database (see the relationship between the User and Note classes in the Nighthawk Coders flask repository)