Penny Piles

On the March 13th lecture, we spent the day working with partners trying to figure out whether we can arrange two piles of pennies in order to get every number in the range of [0, 64]. The way me and my partners did this was by reducing the range to [0, 32]. We knew that if we could create piles of pennies that had every number in this range, than it would be true of the range [0, 64] as well. So we proceeded by using a brute force method and calculated that every number in the range [0, 32] could be created by using a combination of dividing the left and right piles. The simplest way this could be done would be to work backwards. For example, the combination (13, 19) could be created from this progression:

(13, 19), (26, 6), (20, 12), (8, 24), (16, 16), (0, 32). 

First we would divide the pile a few times, then work backwards, and attempt to fill in the gap between the two parts. This does seem like a good approach, but perhaps not the best one. At first I did not think this would be possible for all numbers in the range, [0, 32], but it turns out I was wrong. I also do not really see a different way of doing this, but I do remember different methods being discussed at the end of lecture, I just don't really remember what they were. A tree diagram was also mentioned on the handout, but I just figured that would be a different way to organize the results while still using the brute method approach. Overall, I think this was an interesting problem, and one that I did not expect to be true as well.

SLOG 10

During this week's lecture we began chapter 5, which is about computability theory. This seems to be an interesting part of the course, but I feel it will also be the hardest part. I was confused about the halt problem but I thought it was very cool. Just thinking about how someone would be able to write an algorithm that could determine if another algorithm would have an infinite loop was pretty neat. I mean the only way to truly determine if a program has an infinite loop is to allow it to run infinitely, but what good would that do? Anyway, the halting problem is pretty challenging to understand but I feel this is probably the most interesting part of the course.

It was also Good Friday on Friday this week so we had a day off, which was good because I've fallen behind in basically all my courses, so I need to start catching up. Hopefully this upcoming week goes well and won't be too busy since it is the last, and that the tutorial/quiz goes smoothly as well.

SLOG 9

For the 10th week of class, we continued discussing proofs using big-oh notation, and we also began discussing big-omega notation proofs. All I know is that these are supposed to be the upper and lower bounds of a function, but I'm still confused about what the purpose of a breakpoint and constant is. I guess I'll have to look through the course notes and review the lectures to make sure I understand all of this.

I also did not understand the tutorial handout for this week, but I managed to get a grasp of the material during the tutorial with help from my TA and another student, so I do think I did decently on the quiz this week.

This week we also got back our tests and I did pretty well, it was actually the best mark I have gotten on any piece of work (other than the quizzes). Hopefully the trend continues and I do well on the final as well!

SLOG 8

During this week we continued talking about proofs involving big-oh notation. I was fairly lost at this point, but it's more because I spent my time studying for the upcoming test than because the material is very difficult, but maybe it'll turn out that the material is in fact really hard (but I hope that is not the case). I don't really understand what the whole pick a constant and pick a breakpoint is supposed to signify, or how to manipulate an equation in order to turn it into something that we want so that we can assign values to the constant and breakpoint, but since this stuff is not on the upcoming test, it isn't a priority for me right now.

Me and my partner also submitted the second assignment this week. Hopefully all goes well; the only problem we really had any difficulty with was the last one, but I'm optimistic that we did well.

We also spent an entire lecture trying to solve a penny pile problem. I did this problem with 2 other students, and will make a separate post about this later on.

The test was also this week and I think I did pretty well, despite having to catch up on a lot of the material for proofs.

SLOG 7

First of all, sorry for the late entry, I haven't really been keeping up with the slog part of this course. Anyway, during this week of lecture we continued our discussion of step tracking, and also began looking at proofs using big-oh notation. I found this to be pretty hard to understand at first, and was lost for most of the lectures were we discussed this, but I found that doing the tutorial handouts did help me understand the material a bit better. When we were also looking at the max_sum function, I was completely lost, and I still do not really understand it that well because I have not asked for help yet, even though I should. The i and j accumulators in the loop also made it really confusing. I guess however, that once I start doing assignment 3 this will all start to make sense, as the trend so far in this course has been me being confused about several topics, and then cramming to learn all of it before an assignment is due. Since it's too late to change any of these habits, I might as well just continue doing things the same way and hope for the best.

The second assignment was also due this week. I think it went fairly well, but the last question, the one about proving the gcd(m, n) = gcd(n , m-n) was pretty hard and, unfortunately, I do not think I got the correct solution. I feel I should have gotten more help from the TA's, but oh well.

SLOG 6

The first week back from reading week (which we didn't have any CSC165 homework to do over, which is nice) we continued talking about proofs, and we also learned about different techniques on how to solve proofs, and then began discussing counting the steps of a program. I found this part pretty hard, even on the first day of the new topic, so I can't even imagine how hard the next topic in CSC165 will be. To my understanding, the way to count the steps of an algorithm and calculate the run time is to first determine how many times a line will execute for a set of size n, and then add each line together. The hard part is actually determining how many times each line will execute, as that part can be tricky, especially with nested loops.

Also this week we had our regular tutorial and quiz. I felt pretty confident with the material on proofs, but my structure is quite horrible, which lead me to doing poorly on the quiz this week. I really wish that proofs only required you to do the math to actually prove something, and that all the "assume", "then" statements could be left out. I think this would make it much simpler, but I guess that's not the way it is. 

I also began working on assignment 2 with my partner. Some of the proofs seemed straightforward, but the last two were quite hard. I found structuring my proofs to be a bit challenging. From my perspective the proofs I wrote were fairly good, but they actually were pretty weak. I guess you have to treat proofs as if the person reading it has no knowledge of the math you are using to complete the proof, which requires you to be very detailed and write comments where they are needed. Overall, the second assignment was harder than the first one, but it did give me a lot of practice with proofs, which is a good thing.

SLOG 5

It's been a while since my last post, so I'll try to make a new post for each week of class, that way there will be no massive wall of text to read.

So after the first test, we continued discussing proofs and how to solve them. I found the part about proof about limits to be pretty confusing, and I still don't really understand it quite well. We also learned how to disprove a statement, which requires you to negate the statement. For example, if an existential statement needs to be disproved, you would negate the statement and prove that for all elements of a set, the negation is true.

The tutorial handout that we also did during this week required us to write the proof structure for various proofs and then complete the proofs themselves. I'm not really sure if I did this handout correctly, and I also didn't write the quiz because I missed the class, but I feel the practice I had writing proofs for assignment 2 was a good way to learn the material that I missed and didn't learn.