Unit 3.17 and 3.18 Algorithm Efficiency and Undecidable Problems Notes
Vocabulary
- Problem: Description of the task that is looking to be solved
- Decision Problem: Yes or no answer problem
- Organization Problem: Problem where the answer would be the best one possible
- 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
- Took some notes from college board
- An algorithm’s efficiency can be informally measured by determining the number of times a statement or group of statements executes.
- Different correct algorithms for the same problem can have different efficiencies.
- Algorithms with a polynomial efficiency or slower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time. Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.
- Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for solving them. In these cases, approximate solutions are sought.
- A decidable problem is a decision problem for which an algorithm can be written to produce a correct output for all inputs (e.g., “Is the number even?”).
- A heuristic is an approach to a problem that produces a solution that is not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical.
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')
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
else:
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')
Notes
- An undecidable problem may have some instances that have an algorithmic solution, but there is no algorithmic solution that could solve all instances of the problem.
- Some programs are so large or complex that they end up taking a long time to run, making them impractical to use. In order to minimize this runtime, the individual processes that comprise a program can be run on multiple processors simultaneously. Programmers need to evaluate the options of running these processes sequentially or in parallel across multiple processors to optimize the solution time
- The classic example of an undecidable problem is the halting problem, created by Alan Turing in 1936. The halting problem asks that if a computer is given a random program, can an algorithm ever be written that will answer the question, will this program ever stop running?
def divby3(x):
if x % 3 == 0:
return True
else:
return False
print(divby3(21))
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 = { # lot of typos in this dataset
'Del Norte':{
'Westview': 15,
'MtCarmel':20,
'Poway':35,
'RanchoBernardo':50
},
'Westview':{
'Del Norte':15,
'MtCarmel':35,
'Poway':25,
'RanchoBernardo': 45
},
'MtCarmel':{
'Westview':35,
'Del Norte':20,
'Poway':40,
'RanchoBernardo':30
},
'Poway':{
'Westview':25,
'MtCarmel':40,
'Del Norte':35,
'RanchoBernardo':15
},
'RanchoBernardo':{
'Westview':45,
'MtCarmel':30,
'Poway':15,
'Del Norte':50
}
}
def fastestroute(start, data):
drivetime = 0 # sets the starting drive time to 0
order = [] # initialize list to store order of locations visited
while len(order) < len(data): # sets loop to continue until all locations have been visited
mintime = float('inf') # sets minimum time to reach a location to infinity
loc = None
for location, times in data[start].items():
if location not in order: # if the location has not been visited yet
if times < mintime: # if the time to reach the location is less than the current minimum time
mintime = times # update the minimum time
loc = location # update the location reached in minimum time
drivetime += mintime # add the minimum time to the total drive time
start = loc
order.append(start)
order.append(start)
return (drivetime, order)
start = 'Del Norte'
drivetime, order = fastestroute(start, dataset)
print("Total drive time: " + str(drivetime) + " minutes")
print("Order of locations visited: " + str(order))