3.17 Algorithmic Efficiency

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

Extra Notes

  • exponential efficiences take much longer than polynomial because the increase rapidly
  • Heruestic Approach: situation where the list of requirements that must me met with an ideal solution. Sometimes it is easier and less time consuming to reach a less ideal solution. Finding a solution that is 'close enough' to be an acceptable output.

Challenge

Try and fix this ineficcient code! Only change the code between the two commented lines. Fully programmed solution will improve your grade, at a minimum show that you tried.

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') 

0.5466861724853516 seconds

3.18 Undecidable Problems

Notes

  • A decidable problem will always have a definite answer
  • An undecidable problem will either have multiple answers or can not get to the answer in a set amount of time
  • there are problems that can not be solved by computers: ex when there are contradictory statements in the code

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 getdistance(order):
    miles = 0
    x = 0
    y = 1
    for i in range(3):
        current = x
        destination = y
        dist = dataset[order[current]][order[destination]]
        miles = miles + dist
        x += 1
        y += 1
    return miles
    
from itertools import permutations
min = 5000
for combo in list(permutations(['Westview', 'Poway', 'RanchoBernardo', 'MtCarmel'])):
    dist1 = dataset['DelNorte'][combo[0]] 
    dist2 = dataset[combo[3]]['DelNorte'] 
    finaldist = getdistance(combo) + dist1 + dist2
    if finaldist < min: 
        min = finaldist 
        minpath = combo

print('Shortest Distance = ', min, ' miles')
print('Del Norte')
for i in minpath: 
    print(i)
print('Del Norte')

Shortest Distance =  105  miles
Del Norte
Westview
Poway
RanchoBernardo
MtCarmel
Del Norte