No More Teacher's Dirty Looks

Whadaya know, I learned something in the class

Wow a year of university has flown by so fast and all that other reflective crap. My attitude towards the class has improved quite a bit from the pessimism and doubt I had early on at the start of the year. If I were to make a recommendation to new students who want to know how to do well in the class, my best piece of advice is to go to office hours to seek help whenever you have trouble understanding some ideas. Just sitting on your ass when you have no idea what is going on does not help you do better in the class. Trust me, I know through experience. Some things I really enjoyed learning about were big o notation and the halting problem. I seemed to reach an understanding about them far quicker than other material in the class. I guess I really started to enjoy what was being taught when I was finally able to visualize and understand the concepts that were being presented to me.

And then there was this blog that I had to end up writing once every week. While it may not have been that enjoyable to write about math and logic all the time, I found ways to entertain myself. I also made an effort to actually write blogs because I completely understand why this is an assignment in the first place. Computer Science as a field in general requires lots and lots of interaction with other people, so you'll probably never end up working alone. Therefore communication is key between others; you need to be able to express your ideas and ask for help when you're having trouble understanding something. The almighty Heap in his magnificent glory and wisdom wants us to be better at expressing our ideas and problems to other people. And writing a blog seems like a good way to do so.

Over the semester I had dabbled here and there and looked at other people's slogs. The main thing that comes to mind this is that it is interesting to see how others view the course. Some see it as harder then I do, while others just seem to breeze through the problems that are thrown at them. But overall it is nice to see that the people who make an effort to post are human beings as well. It's good to know that I'm not in a class of robots, seeing that other people get stuck, struggle, and learn reminds me that I'm not the only one having difficulties. Specific examples include:

http://notaslug.blogspot.ca - Nice elaborative blog that explores ideas and problems that are not just contained in the class.

http://captainslog165.wordpress.com - Updates frequently and enthusiastically, seems like a cool person. The categorization of the different types of posts is a nice touch.

http://cs-tah.blogspot.ca - Nice pictures, adds a bit of personality to the blog. And holy cow there's a little pond at the bottom of the blog where you can feed fish, that is so freaking awesome.

Now that I've finished discussing the important stuff that shows what an awesome and well rounded blog this is, I guess I'll try and elaborate on a problem solving episode.

So the problem that I decided to focus on is the Products of Sums problem we talked about earlier in class this week. So first off for understanding the problem, we just need as the handout says to find the maximum product that can be formed using a list of integers that sum to n. I felt that the best way to discover any patterns was to use brute force on the whole thing and find out the largest product for the first few natural numbers. What I found was: 

2 - Largest product set is (2)  

3 - Largest product set is (3) 

4 - Largest product set is (4) or (2, 2)

5 - Largest product set is (3, 2)

6 - Largest product set is (3, 3)
7 - Largest product set is (3, 2, 2) or (3, 4)
8 - Largest product set is (3, 3, 2)

So a pattern that I see that is beginning to emerge is that the largest product sets are the ones that include   2's and 3's. It seems as though we need to reduce the sets to these two numbers. Since 3 is a bigger number it makes sense that we should try to include as many 3's as possible in the set, and finish it off with 2's. Reducing it to something like with 4's doesn't seem to work because 4 can be reduced to (2, 2). Other larger numbers don't appear to work because they are just too big and don't have enough extra numbers to multiply with when it is all reduced.

Also one must consider to eliminate any set with any number of 1's within it. This is because as anything multiplied by 1 is itself, 1 is not necessarily "productive" and should be replaced along with a 3 for (2, 2) (both pairs of values add up to 4). This can be seen in the numbers that are 1 above multiples of 3, such as 4 and 7. It seems as though the first thing one should do for these numbers is take take out a 4, then have the rest of the set consist of 3's.

So the overall idea behind finding the list of integers that adds up to n is reduce to the sums to 2's and 3's. Since the main focus is the number 3, we will consider three cases for the problem.

If 3 fully divides the number, then the largest product of the sums should entirely consist of 3's. With the number of 3's equalling how many times 3 divides into the number.
(Seen with 3 and 6, 9 also works this way as well with (3, 3, 3))

If the number is 1 above a multiple of three, then the largest product of the sums consists of a set with a 4 (or 2, 2), with the rest of the set consisting of the number of 3's that the number - 4 can divide into. (This idea can be observed in 4 and 7, 10 works as well with (2, 2, 3, 3)

If the number is 2 above a multiple of three then the largest product of the sums consists of the number of 3's that the number 2 below this one divides into, in addition to an extra two in the set. (This can be observed with 5 and 8, 11 works as well with (2, 3, 3, 3)

Since I am not very good with deriving equations out of these problems, I will not try to go any further for fear of getting stuck and writing an equation that is horribly incorrect. I am pleased with the results however, as I have actually been able to come out with a solution that considers the multiple possibilities of kind of number is being calculated, which is revolves around being a multiple of 3.

The End Is Nigh

WTF

You gotta love all those assignments due in the last week eh? Now I realize that I should have done that problem solving episode way earlier. Oh well I'll get it done later this week, don't you worry (though I doubt no one is on the edge of their seat waiting for this). I'm just bloody terrible with solving things like the problems we did in class, which is why I am trying to do my best to delay thinking about it. 

Now that we're going to apply the halting problem, I'm really confused as to how we can use it to prove other programs unsolvable. Is it because the questionable program is a part of halt and reaches a contradiction, it is proven to be unsolvable? Also I do not understand the use of function f_prime(x) in the example in the lecture slides. When does it get executed and how specifically does it prove that function initialized is impossible? It seems to me in the example that when the questionable program is in halt, halt itself actually doesn't seem to predict whether a program will halt. It seems that multiple questionable functions coming together multiples the difficulty in the understanding of the solution. 

Assignment 3 is going fairly okay, there have been some snags that I have run into though. I understand whether something needs to be proven or disproven, but I have trouble with manipulating the inequalities to the statements I need to reach. If there is a logical statement regarding a limit that goes to infinity that equals like in the lecture notes, is there one for a limit that goes to infinity and reaches zero? Overall I'm hopeful that I'll get my bearings eventually and be done with my assignments and move on to studying for the final exams. Gosh darnit this never ends.

Whoops

Someday I'll probably think about getting started

I'm at the point where my brain says "I don't want to do work", and my brain responds "alright then, let's not do any work". And then work doesn't get done, which I guess is going to be a problem. I blame the weather for my poor work ethic. I look outside and think to myself "it's too beautiful to do any work today" and then proceed to do nothing while staying inside.

Now that we've started to discuss the halting problem, many of my brain cells have died in an valiant attempt to help me understand what the flip is going on. I don't have a complete understanding of it, and I need some help clearing up a few ideas. Is the reason why navel_gaze(navel_gaze) halts if it doesn't halt (and vice versa) because of the while loop in navel_gaze?

def navel_gaze(f) :

    while H(f, f) : <- this part

        pass

    return 42 (hardy har, don't panic and all those pop culture references and whatnot)

I mean with the possibility of running into an infinite loop in the halt function and an infinite loop in navel_gaze, does the implementation of both ensure that the program will fall into one or the other and fail to run?  If not can the halt function actually run into a infinite loop? Along with questions about the basic halting problem, I have completely no idea how we are able to prove that an algorithm is non computable. It would be nice if we were taught the general formula and way of thinking for understanding and approaching these problems. If we went through a solution slowly that would help as well.

Also with the halting problem, consider the set of programmers that can create such an algorithm ({}). If you have the pleasure of being in the set, you can fly and are ridiculously handsome (and your name also begins with Danny H). Just stating the facts here people.

I'm definitely more optimistic about assignment 3 than I was for assignment 2. I understand the concept behind big o notation and have a good idea of how we can apply what we have learned previously in this course to help our proofs. I think I'm enjoying big o over mathematical proofs because it feels to me that big o is a little more systematic while the mathematical proofs required more creative thinking.

Imma Back!

One of these days I'll get help for my procrastination problem.

Okay guys, now that I've finished all my tests I promise to keep updating my slog. Oh yeah, and I got to do that problem solving blog sooner or later... ehhh not today. Anyways I decided that studying for psych was more important than the slog, and here we are (in the name of Heap I promise to to be more punctual). 

So far I understand big o notation, which is a good because understanding what to do in a class is pretty good. Something that really confused me this week was the discrepancy between big o notation in lecture and the tutorial. The method behind solving a big o problem in lecture was different from the method given in class. The lecture slides proved big o notation in one way, and the tutorial example was proven in another. So I guess that now I'm a little confused about big o notation, which is bad because not understanding what to do in a class is bad. Looking at the website now, the annotated slides for that week are gone now, so yeah... Now I can't prove that the tutorial method and the lecture method are different, but you should totally believe me and not think that I'm crazy. I would definitely like more explanation about solving big o proofs, and would like more specific step by step elaboration about solving those problems. 

So reflecting on the test, I thought it went well. It was easier then I expected, so I think I overstudied. I'm just really glad that the test did not have any concepts that we haven't seen before, otherwise I would have been up really in trouble. A question I have about big o notation right now is that when proving big o, only one part of the inequality is shown and the other side is blank. So then what is the not included side is supposed to have? It might seem a little weird asking this, but I'm quite confused at it. 

Not Again...

Once more with feeling

I feel as though we jumped into big o notation a little too quickly. I understand the main idea behind it, where we need to prove that the best and worst run times for an algorithm, but the actual proving went WAY over my head. I know that there are a lot of people in class that get this sort of thing, but I am not one of them (I'm looking at you, math people). We really jumped right into this topic, I wish there could have been more explanation on the concept of big o, and an approach dealing with simpler algorithms then the ones we did last week. I did not get the thinking behind the individual steps that were taken, and had no idea what the justification was for anything, at all, forever. The proof for the triple nested loop program on friday flew so far over my head it could have been classified as a satellite. I would definitely like to see general tips on how to approach big o notation, as I have absolutely no flippin idea what is being shown to us.

Also on another note, assignment 2 wasn't so hot for me. That learn how to prove proofs thing I was pumped up about didn't go so well... I did end up getting most of the questions right but I still had tons of difficulties. I really didn't end up getting question number 6 right (actually I completely bombed it). Now that I see an example solution for it I am certain that I would never be able to solve something like that by myself. I have never thought like that before when approaching a proof in my short time as a 165 student. It just feels that the level of thought required for the problem goes above and beyond how I am currently thinking, and it is a little frustrating to think that I would never be able to solve something like this if it was posed on a test.

Also speaking about tests, I'm pretty worried about trying to solve proofs I have never seen before on Friday. So I must pose the question. What do? What can I do when after I think long and hard about a proof and come up with nothing? How do I get my mindset onto a topic in a way I've never really thought about before? These are the questions that plague my sleep (actually not really). Good luck on the exam y'all, and may Heap guide you through each step in the proof of life.

Oh Dear, Assignment #2

Wut.

I keep looking at the assignment and my mind is going blank, this week is going to be soooo fun. On another note, I've observed that I'm making posts on later and later days of the week as I continue to delay at a blistering pace. Procrastination is not fun guys, let this be a lesson to all of you. I'd say that I'll try to make them sooner, but lets be honest would I?

Now that I'm working on the assignment, there are definitely tons of questions on my mind (how convenient that they weren't there earlier). One question I have, is if there is a statement that I know a counter example for, can I state the counterexample and reach the conclusion that P(x) -> notQ(x) for all values? Will that be enough to invalidate the entire statement? Also if I have a statement that has a for all assertion in the consequent, what on earth do I do? For example  x in D, P(x) -> ( y in D, Q(y) ^ P(y)), is there anything I can do to solve this or am I completely boned and should view the statement from a different angle? 

What is really irking me right now is the fact that the course notes are mocking me. The two step method it gives to solving proofs seems pretty understandable, but it states in bold IF YOU DON'T UNDERSTAND WHY SOMETHING IS TRUE, DON'T EXPECT TO PROVE IT! In my opinion that little bit of advice is just like saying "if you don't know how to prove it, don't expect to prove it". You don't say? Well then, that'll definitely square me off on my problem solving journey. I cannot expect to fail now that I know that the secret to solving proofs is to understand them.

Scepticism aside, now that I've started looking at other blogs (the few that make an effort of weekly posts, you go giiirl!), it seems that some people are really getting into the groove with these proofs. A lot of people seem to be done with the assignment already, and how they accomplished this Herculean fear was just by sitting down for a few hours and working hard and getting it done. Now it's got me thinking I should have a more optimistic view of the proofs. I just gotta sit down for several hours, enjoy what I'm doing and just power through it. I think I'm going to try really really really hard and make myself drink the CSC 165 kool aid this week. Embrace the proof, and become one with it. 

Good luck on the assignment everyone, may Heap be with you.

Thinking Outside the Box

My one true weakness in math. I guess that explains why I enjoy computer science more than math and logic. With computer science you generally understand all the instruments you have at your disposal when solving problems. As long you understand the commands you can give in your programming language, there won't be any crucial method or tool that you can miss that will prevent you from solving your problem. Computer science is pretty flexible in terms of solutions; while it not be super efficient at least your program can still work. Math for me at least not so much. Sometimes when an answer in given in class, I think to myself "there is no way I could have ever thought of that solution on my own". I just probably haven't even considered thinking that way in terms of solving the problem. For example regarding question 2 on the test, my mind was not analyzing the problem the way that the answer was given (the great Heap has tested me, and I have failed). Assigning delta as a function that uses epsilon never struck me, but I'll definitely catch that in the future. As I've said before, I really need to get into a mathematical mindset and estrange myself from interpreting symbols through language when they only just represent symbols. My main frustration with myself is when I am posed with something new and abstract, I just fall into this state of mind that I can't do it. I can't understand the problem because I'm not viewing from different perspectives or can't remember a useful equation. It's not until I actually see an answer that I perceive I can keep that mentality when dealing with a problem.
 
On the bright side I do believe that I am getting the hang of proofs, there's just a few things that I need to keep reminding myself. Like if the statement of a variable is actually posed in the statement that needs to be proved, one must prove somewhere that the variable is in fact an element of its set. Also it is very beneficial sometimes to bring in extra variables (I don't really understand where it would be useful though), setting up y' can help with proving a statement with y in it. But there are still some things I need help clearing up. If you're supposed to prove something such as  P(x) ^ Q(x), are you supposed to reformat the statement so it becomes an implication? Or are there other ways to directly or indirectly prove such statements?