Week 8

This week, we started looking at algorithm analysis and asymptotic notation. We looked at big O, which provides the upper bound for the growth rate of a function, as well as big Ω, which provides the lower bound for the growth rate of a function. It was interesting to learn that in terms of complexity, constants are ignored.

A function with a constant time complexity that doesn't depend on the size of the input is O(1). One example if this is the average time complexity for search, insertion, and deletion for a hash table data structure. Hash tables are used because they are very efficient in that keys are mapped to a value so that only one key has to be looked up. This is the reason why they are used very commonly. We can compare this to the linked list data structure, which takes O(n) on average for searching, since it has to go through each item sequentially until it finds the item it is looking for.

Another interesting thing I learned this week was the formula for summing up the integers from 1 to n. The story of Gauss coming up with this solution when he was young also makes this easier to come up with.

This is sort of unrelated, but I came across a very interesting video of the visualization and "audibilization" of 15 sorting algorithms. I think it is a great introduction to sorting algorithms you may not have seen before. Perhaps the most beautiful is the bogo sort.

The second assignment was harder than expected but I eventually figured them out and next week is the second midterm but I am not as worried as the first midterm since I did well on the first one but hopefully this one goes just as well!

An interesting SLOG post I found is here: http://csc165.peet.io/big-o-notation/ (this blog also has a very nice, responsive design). This student writes about the penny puzzle that I previously also wrote about and gives an analysis of the algorithm in big O notation. I think this a very good post because it brings up the importance of run-time when writing programs. When I usually write a program, there is very little thought that goes into thinking about the program's running time but this is something that can have a large effect on your program depending on size of your inputs.

Week 7

This week we finished proofs and started learning about algorithm analysis and asymptotic notation. In computer science, big O notation is used for classifying algorithms and is one of the most important topics in computer science so I am very excited to learn about this topic. We also looked at a few different sorting algorithms. Another sorting algorithm that I found quite interesting is bogosort. According to Wikipedia, "if bogosort were used to sort a deck of cards, it would consist of checking if the deck were in order, and if it were not, throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted." This algorithm has an average time complexity of O((n+1)!).

Penny Piles Puzzle

We were also given another puzzle to solve in class this week.

Given two drawers, with the left containing 64 pennies and the right containing none, can you arrange things so that one of the drawers has 48 pennies using the following operation on the two drawers:

If a drawer has an even number of pennies, you can transfer half of them to the other drawer. If the drawer has an odd number of pennies, you may not perform this operation.

Let's see what the steps you would have to take to get 48 pennies.

(64,0) # Starting off with 64 and 0 pennies

(32,32) # Move half (32) from left to right

(48,16) # Move half (16) from right to left

That was easy enough. Let's try it with an odd number. Say 25. It looks difficult to get from 64 to 25 so lets try working backwards.

(25, 39) # Starting off with 25 and 39

(50, 14) # Try performing the reverse action, double the left drawer

(36, 28) # Since we can't double the left drawer, double the right drawer

(8, 56) # Double the lower number (28) to get 56

(16, 48) # Double the lower number (28) to get 56

(32, 32) # Double the lower number (16) to get 32

(64, 0) # Finally, double the lower number (32) to get 64

So it seems that by working backwards, we can see that the pattern to get to 64 is to double the lower number between the two drawers and take the pennies from the other drawer, and keep performing this until you get back to 64 pennies in a drawer.

The following is my general solution written in Python. It takes two parameters, the first is the starting number of pennies in a drawer, which has to be a power of 2, and the second is the desired number of pennies to end up in a drawer, which has to be between 0 and the first number.

def penny_piles(pennies, number):
    """ (int, int) -> NoneType

    Prints the sequence of moves to get to desired number of pennies.

    Parameters:
    - pennies: the starting number of pennies in one drawer, must be a power of
    2
    - number: the number of pennies to end up with in one drawer
    """
    left = number
    right = pennies - number
    sequence = []

    # Check that the number of pennies is a power of 2
    if not (pennies != 0 and ((pennies & (pennies - 1)) == 0)):
        print("Number of pennies must be a power of 2.")
    elif number > pennies or number < 0:
        print("Number of pennies in one drawer cannot be larger than initial "
              "number of pennies or less than 0.")
    else:
        sequence.append('[' + str(left) + ',' + str(right) + ']')
        while left != pennies and right != pennies:
            if left < right:
                right -= left
                left *= 2
            else:
                left -= right
                right *= 2
            sequence.append('[' + str(left) + ',' + str(right) + ']')

        for step in reversed(sequence):
            print(step)

You can try it out here: http://repl.it/2St/1

This week we received the second assignment and it is all proofs and some of them look difficult so I have some work to do. We also received our Assignment 1 marks back and I got perfect on that so hopefully I can do the same with this assignment. Thanks for reading.

Week 6

There were no lectures on Monday which meant no tutorial this week as well. I hope everyone had a great thanksgiving. This week we learned more about proofs. One thing I find frustrating about proofs is that they can seem so obvious when looking at the solution, but when I am trying to figure it out for the first time, I can sometimes get lost. One example is this proof below:

By selecting B = 100, it makes the inequality much easier to work with and is actually very simple when looking back at it. I think the key is to do enough practice problems so that if you do get a difficult one, it will be one that you have seen before.

We also received our midterm marks back this week and I managed to get perfect on the first test (humblebrag). My other midterms this week also went well so everything has been good so far. I hope to keep it up for the rest of the year. Thanks for reading once again.

Week 5

I had fun studying for my 2 midterms this week. My cheat sheet is completely filled up and actually looks like a work of art. I did put a lot of proofs on the sheet but I don't think they will show up on the midterm. I am feeling pretty good about both of these midterms so hopefully I will be able to do well. This week's tutorial was on proofs and it definitely helped understand how to structure proofs properly and how to introduce quantifiers and operators.

Here as an example of the structure of a proof.

Whenever we make an assumption, we indent the next line, and once we have proven our conclusion, we can unindent and start introducing the operators and qualifiers that were assumed. Something new I learned this week is that the closure of sets can be very useful for use in proofs. For example, real numbers are closed under addition, subtraction, and multiplication and natural numbers are closed under addition and multiplication.

Post midterms:

So both midterms that I had went well. The one for this course was very similar to the previous year's test and did not end up using my cheat sheet but it did help me learn. Proofs were not on it so I will be looking forward to those on the second midterm. For the very last question, creating a truth table was useful for coming up with sets that would make one statement false and the other true. Another 2 midterms coming up next week but things look to be calming down after that. I also started my work-study this week. Hoping to get some relevant work experience and see if it is related to what I want to do in the future. So far it has been very fun and enjoyable. Thanks for reading once again.

Week 4

This week's tutorial was helpful as usual. I think our TA definitely does an amazing job at explaining the material. The quiz was once again very similar to the tutorial questions, but I think having weekly quizzes forces me to keep up with the material and this will help me when preparing for the midterms and exam. The first assignment was a pain to type out in LaTeX, especially the Venn diagrams, but I am glad I did because it turned out very well.

This week, we started looking at proofs. I think this will be one of the most important topics we learn from this course that will carry on to other courses. I haven't done proofs like this before so it is definitely something new. The professor also mentioned that we will get a cheat sheet for the midterm so that will make things much easier.

Another course I am currently taking is PHL245 - Modern Symbolic Logic. There is a lot of material overlap with CSC165. I initially took the course to fulfill a breadth requirement, but it was a good elective to take because I have taken things that I learned from one course and applied it to the other. Even though the notation used is different, we also happen to be starting proofs in this course and use a lot of the rules that we use in this course. Next week is the first midterm so I definitely have some studying to do this weekend. It just so happens that the midterm for PHL245 is right before this midterm so hopefully I can manage that as well.