Product of Sums Problem Solving

This is a problem solving episode for the 'products of sum' problem presented in class yesterday.
The problem can be found here: 
www.cdf.toronto.edu/~heap/165/W13/ProblemSolving/prodSum.pdf

While in class, I wrote in pencil the following Python program that I believed would solve the problem.

1    def biggest_product_of_sums(pos_integer):
2        products = []
3        products.append(pos_integer)
4        first_num = pos_integer - 1
5        second_num = pos_integer - first_num
6        while second_num <= first_num:
7            products.append(first_num * second_num)
8            first_num -= 1
9            second_num += 1
10      return max(products) 

The while loops runs while second_num <= first_num, because beyond this point, there would only be repeated products being appended to the list.
I soon realized that this function would only work to find the the largest products of a sum made up of only 1 or 2 integers. This is not the problem. For example the largest product of the sum of integers that add to 9 is 3x3x3. But my function would only return 4x5.

I realized recursion would be necessary and only added two lines of code:
After line 5 I added:
first_num = biggest_product_of_sums(first_num)
second_num = biggest_product_of_sums(second_num)

I then ran the program and tested the result. This program was no good, it exceeded maximum recursion depth. I needed a base case and I had the recursion occuring in the wrong spot. After some trial and error, I created a function that works.

Here is the tidy final product:

def biggest_product_of_sums(n):
    '''(int) -> int
    Return the maximum product that can be formed of a list of positive
    integers that sum to n. Precondition: n must be a positive integer.
    '''
    products = []
    products.append(n)
    first_num = n - 1
    second_num = n - first_num
    while first_num > 0 and second_num <= first_num:
        products.append(biggest_product_of_sums(first_num) * biggest_product_of_sums(second_num))
        first_num -= 1
        second_num += 1
    return max(products) 

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.

Reflections on the term test

Today we wrote our first term test. I feel confident I did well. Most the material was straight forward and I feel like I had prepared adequately.

However, the question involving epsilon and delta were beyond my reach. I actually left the 'declare whether the statement or its negation is true or false' questions blank in order to get the 20%. I drew a graph of y = x^3 but was unsure what step to take next to solve the problem. I remember that the professor went over this in class and it had to do with 'you' vs. 'your enemy' and it seemed to make sense during lecture. But as far as being able to go about it myself, I was unsure where to draw the lines on the graph.

When I have my midterm back, I hope to try and go over it again with the annotated lecture notes on this subject and see if I can figure out where to draw the appropriate delta and epsilon lines. If I'm still lost, looks like I'll be headed to office hours.

my switch from CSC240 to CSC165

On Monday I dropped down from CSC240 to CSC165. The decision was one that very difficult for me so I’ll spend my first blog describing the decision-making process.

First, some background. I graduated high school in 2004. Math was always easy for me, so when I went to Western for a Bachelor of Arts degree after high school, I took first year calculus for an easy science credit. This year, I came to U of T to pursue a Bachelor of Science in Statistics and Computer Science. Because I already have a degree, I am considered a second year transfer student and I have credit for MAT135 and MAT136 because of the calculus I took when I was at Western.

When I registered for my courses this year, I made some cocky decisions. I registered for STA257 and STA261 (the most difficult statistics courses) and of course CSC240. In STA257, I learned that theoretical math was not for me. I was doing very well in the calculations aspect of MAT223 (linear algebra) and MAT235 (second year calculus with a focus on applications) but not very well on the proofs. And I was hopelessly lost in STA257. When I realized I should not have taken STA257, it was too late to drop down to another stats course. I made sure to switch into STA248 (statistics for computer science) for second semester, got a tutor and worked really hard to pass STA257 and the results weren’t actually that bad.

On the first day of CSC240 this year, the professor said that we should be in CSC165 if we weren’t just as comfortable with theoretical ideas as we were with concrete examples. My experience with statistics showed me that I need concrete examples in order to understand theoretical ideas. In addition, the professor said we should be in CSC165 if we memorized math and were unable to derive formulas on the spot. Truth be told, I didn’t even know there was a second option to memorizing formulas, a strategy that had always worked well for me. So I decided I should enroll in CSC165. And so I added myself to the waitlist which was 92 students long.

I knew I wouldn’t get in before the waitlist closed, so I threw myself full force into CSC240. I couldn’t guarantee that there would ever be space for me in CSC165, and I didn’t want to be left behind in CSC240. In CSC240, we had online lectures that we had to watch before class so we could learn the new material before our scheduled class time, where we would work through some of the ideas presented in the online lectures. In addition to spending time making sure I understood the lectures, I did all of the recommended reading, which was not in short supply. I found that I was actually grasping the material, and even found a mistake in an MIT textbook, one of our accompanying texts. When it came to the first assignment, I went to office hours, spent probably over 12 hours on my responses, and second guessed myself the entire time. It turns out I needn’t have second guessed myself as much as I did because I managed to get a very good grade.

The turning point came when I couldn’t get through Online Lecture 7 over the weekend. Online Lecture 7 was about infinite sets and the unsolvable Halting Problem. I couldn’t grasp what an ASCII string was, never mind understand why this problem was unsolvable, how to prove something diagonally or how infinite sets can be bigger or smaller than one another. On the same day, Assignment 2 was posted, and I saw that it was likely beyond my grasp. Considering how much time I had spent on the first assignment, I knew it would be likely double that for each subsequent assignment. And also, I saw on the CSC165 syllabus that some of these topics (like the Halting Problem) would also be covered, but not until the end of the semester and I knew the topics would be presented in a more digestible way. First thing Monday morning, I went to my college registrar and made the switch.

This decision was very difficult for me. Should I have stuck with CSC240? I probably could have passed the course. Just because you can do something, does that mean you should? Are we obligated (morally or otherwise) to see how far we can push and challenge our brains? There is someone very important to me who said that maybe I wasn’t giving myself enough credit.

But if I can get the exact same degree with CSC165 and CSC236 and be able to digest the material more easily, is doing so being lazy? Or is it being resourceful? After all, those many, many hours I would’ve spent anxiously labouring on CSC240, I will now be able to use to focus on my other courses and maintain a better cumulative GPA.

I’m looking forward to CSC165. I won’t let this opportunity go to waste.