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

Notes

  • Different code that all completes the same task can have different amounts of times to run
  • This amount of run time shows varyihg levles of polynomical efficiency
  • Sometimes requirements that have to be met are very complex, and ideally it would be good to meet all of those requirements perfectly
  • However, it may be hard or take too long to meet those perfectly, a Heuristic approach is when we sacrifice optimal solutions to improve efficiency and easy of programming, by using solutions that are "good enough" to have a satisfactory outcome

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
    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.5004549026489258 seconds
  • Decreased to ~ 0.5 seconds
  • I found that using an else statement instead of elif in line 11 dramatically cut down the time.
  • This is because with the previous elif statement, it actually had to check if the statement requirements were met. This takes time.
  • On the other hand, with the else statement, it doesn't need to check for anything further than the inital if statement, which takes a lot less time.
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):
    upper = (len(array)-1)
    lower = 0
    while upper > lower:
        middle = (lower+upper)//2
        if middle == value:
            return True
        elif middle > value:
            upper = middle - 1
        else:
            lower = middle + 1
    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') 
0.39867186546325684 seconds
  • Decreased to ~ 0.4 seconds
  • This is the binary search method that we were suggested to implement in class

3.18 Undecidable Problems

Notes

  • Decidable problems always have an answer such as True and False
  • Undecidable problems have multiple answers, no answer, can't get to the answer in time, etc
  • There are problems that computers can't solve
  • Contradicotry statments within the code can cause it to not work correctly

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
    }
}

My thought process for this was to make a route based on the shortest time of each location. So for example at each stop, you would see which would be the next closest and go to there.

# start from the "start" school, recursively go to the next school, until all schools have been passed and reach start0
def findBestRoute(start, schools, route, total_time):
    global min_total_time, best_route, route_count, start0
    for loc, time in schools[start].items():
        if loc not in route:
            saved_route = route.copy()    # do not use saved_route = route, that is not list copy!!
            saved_total_time = total_time
            route.append(loc)
            total_time += time
            # start from the loc, recursively go to the next school, until all schools have been passed and reach start0
            findBestRoute(loc, schools, route, total_time)
            # resume
            route = saved_route
            total_time = saved_total_time
            if total_time >  min_total_time:  # time is already too long, no need further check
                return
        if len(route) == 5 and loc == start0:
            route_count += 1
            route.append(loc)
            #print(route_count, route, total_time)
            if total_time < min_total_time:
                best_route=route.copy()
                min_total_time=total_time
            return

min_total_time=10000
start0 = 'DelNorte'
route=[start0]
best_route = []
total_time = 0
route_count = 0

findBestRoute(start0, dataset, route, total_time)

#print ("Total checked route # is "+str(route_count))
print("Best Route:", best_route)
print("Drive Time:", min_total_time, "minutes")
Best Route: ['DelNorte', 'Westview', 'Poway', 'RanchoBernardo', 'MtCarmel', 'DelNorte']
Drive Time: 85 minutes

Grading:

Challenge Homework
.15 pts for attempt .65 for attempt
.20 pts for complete .70 for complete
.25 pts for above and beyond .75 pts for above and beyond