Reflection

Today is the last day of classes for this semester and that means the last day of this course. I felt that this course was a challenge. The course material was difficult to understand when newly introduced and took alot of time to wrap my head around and fully grasp which was something that I was not really used to. This course made me reflect on how I learn and how to learn in the future as I had to adjust in grasp the concepts.   

Overall I feel that this course has a great learning experience both in terms of the material in my future cs career but also in terms of how to learn material.

Last Week

This week was very hectic as it was the last week of classes this semester. Had been working on both the 148 project as well as assignment 3 for 165. I felt assignment 3 went fairly well as I felt confident in my answers. I had some questions about the material as I was completing the assignment but I feel that I got enough experience and help with the topics that I was able to complete them.

I approached the questions about big Oh and Omega by looking over the lecture notes as well as the tutorial handout on the subject. Furthermore I felt that using graphing software to illustrate the functions ,as Professor Heap  advised, was extremely helpful.

Penny Piles

For my problem solving episode I decided to attempt to solve the Penny Piles problem.

Step 1: Understanding the problem
Given two drawers, left and right with the left drawer holding n pennies(n being a positive integer), what combinations of pennies in either drawer can be reached using the following operations?

Left:If there are an even number of penny in the left drawer, half may be transferred to the right drawer. Otherwise the pennies in that drawer must be left alone.

Right:If there are an even number of penny in the right drawer, half may be transferred to the left drawer. Otherwise the pennies in that drawer must be left alone.

In this problem solving episode the unknown is the number of integers than can be found by executing the above functions on the drawers with the left containing n pennies.

Step 2: Devising a Plan
My first approach to this problem was to utilize brute force so I could observe a pattern.
I decided to use tree diagrams as I felt that the problem fit the criteria of a tree data structure.

Step 3: Carrying Out a Plan:

After drawing these tree diagrams I compiled a table.

N	Numbers found	Total number not including 0
1	0,1	1
2	0,1,2	2
3	0,3	1
4	0,1,2,3,4	4
5	0,5	1
6	0,3,6	2
7	0,7	1
8	0,1,2,3,4,5,6,7,8	8
9	0,9	1
10	0,5,10	2
11	0,11	1
12	0,3,6,9,12	4

The rows highlighted in red are numbers of n where n values where found.
Values of n that are of base 2^x produce all integers in their range([0,...n])
Odd numbers only produced themselves as they are not divisible by 2.
Even numbers with prime factors other than 2 produced 2 numbers, themselves and their other prime factor.
I still could not find a pattern so I decided to automate by production of further results using Python.


def penny_piles(L):
    numbers_found = [L[0],L[1]]
    if L[0] % 2 == 0:
        left= L[0] // 2
        right = L[1] + left
        numbers_found += penny_piles([left, right])
    if L[1] % 2 == 0 and L[1] != 0:
        right = L[1] // 2
        left = L[0] + right
        numbers_found += penny_piles([left, right])
    elif L[0] % 2 == 1 or L[1] % 2 == 1:
        return L
    numbers_found = remove_duplicates(numbers_found)
    return numbers_found

def remove_duplicates(L):
    L.sort()
    for x in L:
        if L.count(x) > 1:
            y = L.count(x)
            while y > 1:
                L.remove(x)
                y -= 1
    return L

As confirmed by graph, numbers n that are of 2^x produce n numbers and  odd numbers produced 1 number.
As for even numbers; numbers that are even and only have the prime factors 2 and another prime produce only 2 numbers.
However I was not able to produce a pattern for even numbers.

Step 4: Looking back
I was not able to create an algorithm for predicting the