Unit 3 Sections 17-18 Challenges and Homework
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
Notes
- If a program is more efficient, it can solve a problem in a faster amount of time
- Therefore, the more cycles, the longer time it takes the program to run
- Polynomial Efficiency is better than Exponential Efficiency
- Heuristic Approaches are used when the requirements are complex and multiple
- Heuristic approaches sacrifice optimal solutions to improve efficiency and ease of programming
- Example of an undecidable problem is the halting problem
- Program that calculates whether another program is working
- First program might say error, but second would say no error
- Creates a paradox
- Undecidable problems occur everyday
- Computers have to guess when to stop loading a website because it takes too long
- Internet connections eventually time out because the computer decides it takes too long
- Computers have to guess when to stop loading a website because it takes too long
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):
#--------------------
for i in value:
if i in array:
return True
else:
return False
#--------------------
starttime = time.time()
for i in range(100000):
for i in range(len(valuelist)):
x = isvalue(valuelist,numlist)
endtime = time.time()
print(endtime-starttime,'seconds')
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(data):
start = "Del Norte"
drivetime = 0
order = []
order.append(start)
while len(order) < 5:
dist = 0
for x in data:
for i in data[x]:
if i not in order:
answer = i
dist = data[x][i]
order.append(answer)
drivetime+=dist
x = answer
order.append(start)
print("The drive time is:", drivetime)
print("Order of the drive is:", order)
fastestroute(dataset)