Homework 3.17 - 3.18
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
Algorithmic Efficiency:
Algorithmic efficiency is the measure of how effectively an algorithm solves a given problem, in terms of the amount of resources (time and space) the algorithm requires to complete the task.
Algorithms can be judged on the basis of their time and space complexity. Time complexity refers to the amount of time taken by the algorithm to complete its task. Space complexity is the amount of memory or space required by the algorithm to complete its task.
Algorithms with better time and space complexity are considered to be more efficient than those with lesser efficiency.
Algorithms can be further compared on the basis of their algorithmic complexity, which measures the number of steps required to solve the problem.
Different algorithms can be compared by measuring the number of operations they require to solve a problem.
Algorithms can also be evaluated based on their scalability, which measures how easily an algorithm can be adapted for different input sizes.
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):
#--------------------
if value in array:
return True
else:
return False
#--------------------
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
Undecidable Problems
Python Undecidable Problem is a type of problem that can not be solved by any algorithm or set of instructions. It is impossible to determine if a given problem can be solved or not, even with unlimited resources and time.
Examples of undecidable problems include the Halting Problem, which is to determine whether a given program will run forever or not, the Entscheidungsproblem, which is a decision problem relating to the existence of effectively calculable functions, and the Post Correspondence Problem, which is to determine whether two given sequences of symbols can be matched in a certain way.
Undecidable problems are of particular interest in computer science because they serve as a limitation to the power of computers. Even though computers are capable of solving a vast array of problems, there are still some that are impossible to solve.
While undecidable problems can not be solved, there are methods for approximating their solutions. These methods include heuristics, genetic algorithms, and machine learning.
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,
'RanchoBernardo':50
},
'Westview':{
'DelNorte':15,
'MtCarmel':35,
'Poway':25,
'RanchoBernardo': 45
},
'MtCarmel':{
'Westview':35,
'DelNorte':20,
'Poway':40,
'RanchoBernardo':30
},
'Poway':{
'Westview':25,
'MtCarmel':40,
'DelNorte':35,
'RanchoBernardo':15
},
'RanchoBernardo':{
'Westview':45,
'MtCarmel':30,
'Poway':15,
'DelNorte':50
}
}
def fastestroute(start, data):
drivetime = 0
order = [start]
temploc = ""
for i in range(len(data) - 1):
minimum_time = 10000
for loc, time in data[order[(len(order) - 1)]].items():
if time < minimum_time and loc not in order:
temploc = loc
minimum_time = time
drivetime += minimum_time
order.append(temploc)
order.append(start)
return (drivetime, order)
start = 'DelNorte'
results = fastestroute(start, dataset)
for i, location in enumerate(results[1]):
print(str(i + 1) + ".", location)
print("Time:", results[0], "minutes")
#This code finds the fastest route between two locations based on the given dataset. It takes the starting location as an argument and adds it to the order list. The loop then iterates through the dataset, finds the location with the least amount of drive time, and adds it to the order list. The drive time is updated each time a new location is added. The loop ends when the starting location is reached again and the results are printed.