CSC165 concepts in other classes

CSC165 concepts have been appearing my other classes.

In CSC148, it was no surprise to see some of the ideas of improving code efficiency in our first-year programming class. It is a large part of our final project to improve efficiency for our programs. It is helpful to have a theoretical definition of big O when making these improvements.

I was surprised to find concepts of computability in PHL240: Persons, Minds and Bodies, a metaphysical class with a focus on human identity and consciousness, a course I am taking solely to fulfill a breadth requirement. In this class we learned there is a theory of mind called functionalism. Using concepts of computability from Alan Turing, functionalists believe that our mind is like a Turing machine, and operates much like a computer program. Our mind is in various mental states at any time, and any mental state can be explained by what inputs cause such a state, and what mental states and outputs are caused by such a state. This is likely the closest this abstract, metaphysical class will be relatable to someone studying computer science.

proofs

Last week I posted here that I was understanding the proofs. That appears to be an understatement because I found out this week that I got 100% on the 2nd assignment and the 2nd term test!!

Calculate big-O and big-Omega on N are just more proofs but they require some practice. I struggled with the quiz this week, seemingly unable to keep the inequalities straight in my head. Luckily my TA, Timo, was able to stay after tutorial and talk me through it. He gave the helpful advice that if you're trying to prove f < g, you need to find f' and g' such that f < f' < g' < g. This will help me keep things straight in head.

Next week is the halting problem. I got a glimpse of it when I was in CSC240 at the beginning of the semester before dropping down. The halting problem was part of why I dropped down, it is pretty mind stretching, but I trust Danny will present it in a way we can digest.

Thoughts on the penny piles problem

This week we were introduced to the penny piles problem. In class my partner and I drew a tree to see if there were any numbers from 0 to 64 that were not included in a tree where left branches represented the L operation and right branches represented the R operation.

We made some interesting discoveries. Firstly, any number you pick in this range can be achieved by performing these operations because they were all in the tree. Secondly, every new step introduced numbers that had not yet been introduced and would not be introduced again. That is, if you were able to achieve a certain number of pennies by making 3 operations, you could not achieve that number by making less than 3 or more than 3 operations. We also found that the leafs in the tree (nodes where the amount of pennies in each drawer was odd) had a depth of 6 (it took 6 operations to get to an odd number), and we mused that since 64 = 2 ^6, this may not be a coincidence.

Obviously we used Hint 3 by drawing a picture, but I also like Hint 1, which was to work backwards. It would be interesting to devise a Python program that would prove that for any number you inputted, you could work backward until you get back to 64 in one drawer, which would prove that every number is in the tree. To see if this tree worked for any amount of pennies to begin with, not just 64, I would make a program that took two parameters, the amount of pennies you hope to achieve in one of the drawers, and the total amount of pennies you begin with (64 in this case). My prediction is that if you entered any number of total pennies such that the total could be expressed as 2^ x where x is a natural number, and the amount of pennies you hope to achieve in one of the drawers is a natural number between 0 and the total, the program would return 'True.'

problem solving episode?

I can't believe I'm actually getting good at proofs. The sample solutions for Assignment 2 were posted and I believe my partner and I were on the right track for all the statements we were to prove or disprove. This is a good sign because it sounds like the Term Test this week will be along the same lines.

In class we're continuing with algorithm analysis which is more difficult, but I'm just trying to see it as more proofs, which like I said in the previous paragraph, I seem to have a good handle on.

For this blog we're supposed to do a problem solving episode. The Free Lunch problem looks interesting but it seems that on the problem-solving Wiki, the answer is right there. Am I supposed to read the answer? What is the main purpose of doing a problem solving episode?

Transition Week

This week in CSC165 feels like a transition week because we're making the switch from proofs to algorithm analysis. In my courses I usually like to read ahead in the textbook before lectures because I learn better when lecture is more of a review rather than seeing concepts presented for the first time in lecture. I tried to read ahead on Chapter 3 but I found it very difficult to understand. I also saw that I'm going to need to get over this irrational fear of deltas and epsilons very quickly.

Yesterday I met with the professor after class to pick up my midterm and go through Question 2 which I had trouble with. He helped me by using different variables rather than epsilons and deltas (I like 'a' and 'b') and talked me through the reasoning. He suggested I grab a first year calculus book and go through the definition of a limit again (I'm currently taking MAT235.)

My partner and I are having no trouble with the assignment. I like to play with the numbers until I get the proof and my free thought can get kind of erratic on the page, and my partner helps me set it straight in proper proof structure. We've gone through all but one of the six proofs, and next week we type it up.