Week 8: Big Oh and Big Omega and Penny Piles

Hello Rod here,

Big Oh and Big Omega
This week we continues on Big Oh and Big Omega. Tutorial helped out a lot this week when we went over counting steps in the algorithms we were given. Also the proofs for prooving the upper bound or lower bound of a equation is slowly becoming more clear. I'm still a little rough on this topic and I plan on looking over the course notes this weekend, because most of the concepts there are explained pretty well.

Penny Piles
This week I decided to do my upload my problem solving episode of Penny Piles.

Understanding the Problem:
When we were given the problem it was not clear at first so me and my partner began by reading the rules of the problem and what needed to be solved. In this case penny piles we were not convinced that you can get to every possible number (above zero, less than 64) by using the rules to divide 64. So we began by choosing numbers using the rules to get to that number. Eventually we found out that this was working for all the numbers whether odd or even.

Devise a Plan:
Once we noticed that we can get odd or even numbers we made a tree of possible results of following the steps, which helped us visualize the problem.

Carry out the Plan:
I figured to carry out the plan I wanted to write some python code, that takes as input the number of pennies you want to have in atleast one drawer and it outputs the steps you need to take in a list (this program assumes that all 64 pennies start off in the right drawer). This program is not the most efficient it could be simplified but this was the best I could get it too.

def penny_piles(pennies):
   
    steps = []
   
    operator = 'l'
   
    starting_pennies = 64
   
    while pennies != 64:
       
        if pennies > 32:
           
            pennies = 64 - pennies
           
            if operator == 'l':
                operator = 'r'
            elif operator == 'r':
                operator = 'l'
       
        pennies = pennies * 2
       
        steps = [operator] + steps
   
    if steps[0] == 'r':
        for i in range(len(steps)):
            if steps[i] == 'r':
                steps[i] = 'l'
            elif steps[i] == 'l':
                steps[i] = 'r'
   
    return steps
     
Look Back:
When writing the code I realized a lot of things that were flawed with my understanding of the problem. Such as the proper order of the commands. At first i got the program to work with returning the number of steps it took to solve the problem, then from there I modified it to return the actual steps needed to get the result.

P.s the last little block of code deals with the commands that start with command 'r'. It flips all the commands in order to get the same result but suffice that the first command has to be 'l' because all 64 pennies start in the right drawer.

Something I could also do is make it so that the user can input how many pennies they want to start off with, and i can make that a input variable rather than having it preset to 64.