Vocabulary
- Problem: a general description of a task that can or cannot be solved algorithmically
- Decision Problem: A problem with a yes or no answer
- Organization Problem: a problem with a goal of finding the best answer
- Instance: a problem with a specific input
- Efficiency: amount of computing needed to solve a problem
- Polynomial Efficiency (Good): more work takes a proportional amount of time (1 job is +2 time)
- Exponential Efficiency (Bad): more work takes an exponential amount more time (1 job is 2x time)
- Heuristic Approach: When optimal solutions are inefficient, look for a possibly optimal solution that is more efficient
- Decidable Problem: A decision problem that has a clear solution that will always make a correct output
- Undecidable Problem: A decision problem with no solution that is not gaurenteed to produce the correct output
import time
def toint(x):
x = int(x)
return(x)
def tostr(x):
x = str(x)
return(x)
def add(x,y):
x = toint(x)
y = toint(y)
z = x + y
z = tostr(z)
return(z)
starttime = time.time()
for i in range(1000000):
x = "1"
y = "2"
answer = add(x,y)
print(answer)
endtime = time.time()
print(endtime-starttime,'seconds')
import time
def betteradd(x,y):
z = x + y
return(z)
starttime = time.time()
for i in range(1000000):
x = 1
y = 2
z = betteradd(x,y)
print(z)
endtime = time.time()
print(endtime-starttime,'seconds')
import time
starttime = time.time()
for i in range(1000000):
x = 1
y = 2
z = x+y
print(z)
endtime = time.time()
print(endtime-starttime,'seconds')
Now am example of both Polynomial, and Exponential Efficiencies:
let's say X is the number of values in a data set. Let's also say that the equations shown are the amount of cycles needed to sort a data set of that length. More cycles = longer time to run
| x | 3x | (2x)^2 | 3^x |
|---|---|---|---|
| 1 | 3 | 4 | 3 |
| 2 | 6 | 16 | 9 |
| 3 | 9 | 36 | 27 |
| 4 | 12 | 64 | 81 |
| 5 | 15 | 100 | 243 |
| 6 | 18 | 144 | 729 |
| 7 | 21 | 196 | 2187 |
| X | Polynomial | Polynomial | Exponential |
| X | Efficient | Efficient | Inefficient |
Heuristic Approach:
Let's say we have these requirements:
- 30 students per class
- 300 students
- 10 classrooms / classes
- 5 classes per student / periods per day
- each student has a different list of 5 wanted classes with 1st, 2nd, and 3rd choices
Thats a lot!
Just imagine how complex it would be to use all of those requirements and make every student as happy as possible. This is when we would use a heuristic approach. This is when we sacrifice optimal solutions to imporve eficcency and ease of programming.
import time
numlist = [1,3,5,7,9,11,13,15,17,19]
valuelist = [0,3,6,9,12,15,18,21]
def isvalue(value,array):
#--------------------
exists = False
while exists == False:
for i in range(len(array)):
if value == array[i]:
exists = True
if exists == False:
return exists
return exists
#--------------------
starttime = time.time()
for i in range(100000):
for i in range(len(valuelist)):
x = isvalue(valuelist[i],numlist)
endtime = time.time()
print(endtime-starttime,'seconds')
def divby3(x):
if x % 3 == 0:
return True
else:
return False
print(divby3(21))
Undecidable Problem: The halting problem
Let's say you have a program that calculates weather another program would error-out given a certain input, then reverse its output. If you fed this program into itself, something weird would happen. Say the first step said the program would have an error, the second step would say no error. This proves the first step was wrong, creating a paradox.
Situations like this happen every day, when a computer must guess when to stop loading a website that might never load. This is why internet interctions will time out if it takes too long.
Video:
Homework!
Make an algorithm that finds the fastest route that hits every location once starting and ending at Del Norte. Make sure to show your thinking. If you are strugling, try using a huristic approach. Remember, what matters more than having perfectly functioning code is that you tried your hardest.
dataset = {
'DelNorte':{
'Westview':15,
'MtCarmel':20,
'Poway':35,
'RanchoBernrdo':50
},
'Westview':{
'Del Norte':15,
'MtCarmel':35,
'Poway':25,
'RanchoBernrdo': 45
},
'MtCarmel':{
'Westview':35,
'Del Norte':20,
'Poway':40,
'RanchoBernrdo':30
},
'Poway':{
'Westview':25,
'MtCarmel':40,
'Del Norte':35,
'RanchoBernrdo':15
},
'RanchoBernardo':{
'Westview':45,
'MtCarmel':30,
'Poway':15,
'Del Norte':50
}
}
def fastestroute(start,data):
drivetime = 0
order = []
#CODE,CODE,CODE
return(drivetime,order)
start = 'DelNorte'
# 'dataset' is the name of the nested key value pair