Week 8 - Penny Piles

~~~~~~WEEK 8~~~~~~

Today’s outline:

• Formal definition of O, Ω
• Worst-case analyses of two algorithms
• Problem solving session

I completed the survey that was given to us and I feel the course has been very good so far. Thank God for the extended office hours because I used those for getting help on the second assignment.

We started off the class by recapping O(n²) then by learning the formal definition of O(n²). I understood the formal definition as it is very simple and straightforward. I think the biggest help in understanding it was the graph that was given to us and the chicken and turkey example. We then went on to learning about Ω(n²) which I did not understand at first. Fortunately the examples cleared up the misunderstanding.

We were then introduced to algorithms, the first one was, “insertion sort.” It took me a while to understand the code and finally understand it. We then went onto doing a code which involved maximum slice which would calculate the maximum difference between any numbers in the list in the correct order. The coding was hard to understand and I asked the professor questions and he helped me out and told me about them. I learned that we needed a loop guard for this function. I am taking CSC108 which helped me understand the coding behind this code. I don’t think I would have understood this function if I had not taken CSC108.

We were given a problem called, “Penny piles.” We were given two drawers and 64 coins in one of them and the other empty. We can only transfer money from one drawer to the other only if the initial drawer has an even number of coins in it. Our task was to find how many moves it took to get 48 coins in one drawer. Furthermore, we were asked to find numbers which could not be obtained. We used the method of tracing backwards and going to the number we want to achieve. Ex. I wanted 48 I started from 1 63 then 2 62, 4 60, 8 56, and finally 16 48. Our group did the same for each number we were trying to get. I used a similar technique to this but backwards: http://kevin-au-csc165.blogspot.ca/2014/12/week-7-worksheet-penny-piles.html

This week’s tutorial exercise was extremely helpful as it gave me an introduction to the definition of floor and proofs according to floors.

I have the assignment due next week along with 2 other major assignments and CSC165 mid-term which I have to study hard for this time around. I felt that the assignment should have been due on the 31 October because we would have completed the assignment before that day and our work would be done instead of all work in once place..