Final Entry

I am sad to say that the course is over.  CSC 104 is one of my favourite classes this semester, and I would highly recommend taking it. I learned something new every lecture, and I am proud to say that I am no longer computer illiterate. Whether you decide to take the course to fill the breadth requirements or to broaden your horizons, I promise you will not regret it.

Problem-Solving

Problem:

The list of positive integers that add up to 1 is (1), and the product of this list (if you allow unary products) is also 1.

There are two lists of positive integers that add up to 2, and they yield two different products (2) (with product 2), and (1,1) (with product 1).

There are several lists of positive integers that add up to 3, and they yield several different products: (3) (with product 3), (2,1) (with product 2), and (1,1,1) (with product 1).

If n is a positive integer, what is the maximum product that can be formed of a list of positive integers that sum to n?

Hint 1: Organize: Even for a fairly small number n, you will have quite a large list of numbers that sum to n.  Do you have some organizing principle for your lists?

Hint 2: Economize: Are there some list that you can remove from consideration right away?

Understanding the Problem:

Known:

The list of positive integers that add up to some number

 One set of these numbers produces a maximum product

Unknown:

How to find the maximum product that is formed from the list of positive integers that sum to n

Devise a Plan:

Plan 1:

 Write the list of positive integers and products for n=1-7

Make a list of the maximum products

Find an equation that works for all the possible cases (i.e. max. product =???? for all n=1, 2, 3, 4….)

Look Back:

Plan did not work, I got stuck

 Devise a new plan

Devise a New Plan:

 Hint 1 suggested an organizing principle for the list of numbers that sum to n

Plan 2:

Write the list of positive integers and products for n=1-7

Make a list of the maximum products and the numbers they came from

Notice, all of the maximum products contain 2’s and 3’s

Organize list based on number of 2’s and 3’s

Look for pattern relating n and the number of 2’s and 3’s

Product Sums
n	Numbers that Sum to n	Product of the Sums
1	(1)	(1)
2	(1+1) (2)	(1) (2)
3	(1+1+1) (2+1) (3)	(1) (2) (3)
4	(1+1+1+1) (2+1+1) (2+2) (3+1) (4)	(1) (2) (4) (3) (4)
5	(1+1+1+1+1) (2+1+1+1) (2+2+1) (3+1+1) (3+2) (4+1) (5)	(1) (2) (4) (3) (6) (4) (5)
6	(1+1+1+1+1+1) (2+1+1+1+1) (2+2+1+1) (2+2+2) (3+1+1+1) (3+2+1) (3+3) (4+1+1) (4+2) (5+1) (6)	(1) (2) (4) (8) (3) (6) (9) (4) (8) (5) (6)
7	(1+1+1+1+1+1+1) (2+1+1+1+1+1) (2+2+1+1+1) (2+2+2+1) (3+1+1+1+1) (3+2+1+1) (3+2+2) (3+3+1) (3+4) (4+1+1+1) (4+2+1) (5+1+1) (5+2) (6+1) (7)	(1) (2) (4) (8) (3) (6) (12) (9) (12) (4) (8) (5) (10) (6) (7)

Maximum Product Sums
n	Sum	Max. Product
1	1	1
2	2	2
3	3	3
4	2+2	4
5	3+2	6
6	3+3	9
7	3+2+2	12

Solution:

n=1 and n=2 are different than n=3, 4, 5, 6, 7 so I assumed that the rule does not apply to these two values of n.  Values when n is a multiple of 3 (n=3, 6) (the remainder is 0), contain the same number of threes as the quotient of n divided by three.  Values that have a remainder of one when n is divided by three (n=4, 7) contain two twos and the one less than quotient of n divided by three threes.  Values that have remainder two when n is divided by three (n=5) have the quotient of n divided by three three’s and one two.  I put these ideas into a DrRaket function called prod-sum, which is below.

(require picturing-programs)

(define (prod-sum n)

  (cond

   

    ((equal? n 1) n)

    ((equal? n 2) n)

   

    ((> n 2)

 

  (cond

    ((equal? (remainder n 3) 0) (expt 3 (quotient n 3)))

    ((equal? (remainder n 3) 1) (* (expt 3 (sub1 (quotient n 3))) (expt 2 2)))

    ((equal? (remainder n 3) 2) (* (expt 3 (quotient n 3)) 2))))))

Looking Back:

I checked the solution in DrRacket using several different check-expects for values of n greater than seven, and all the tests passed.

From this problem-solving attempt I realized how important it is to truly understand the problem before you start.  I spent a long time on plan 1 until I realized there was a pattern of twos and threes in the maximum products.  Plan 1 would probably not bring me to the correct answer.  If I had understood the problem and the hints I would have spent less time working on the problem. 

Four Day Week!!!!

I am so happy that today is Good Friday.  I am going to get some much needed sleep, and catch up on some schoolwork.

Today I started (and finished) Project #2.  I just turned on the automatic parentheses in DrRacket.  Sometimes, I find them very helpful, because it cuts down on the amount of typing I have to do, but every problem I encountered with the project related to the parentheses.  Sometimes I had too many, and sometimes I did not have enough.   These little mistakes made the project take longer than necessary.  I am still deciding if I am going to attempt the bonus.

On a completely different note, I read Chris Ng’s blog (http://csc104chrisng.blogspot.ca) this afternoon.  Congratulations on a fantastic team finish at the Canadian University Badminton Championships Chris!

One Stressful Week and One Lesson Learned!

This week I had three midterms, two quizzes, and three assignments due.  Everything was going well, until I had to do Wikipedia Part 3.  I had my entire assignment prepared, but when I went to edit the page on Friday night, I realized that the page I wanted to edit was locked and that I did not have permission to write on that page!  I started to panic, because the assignment was due in a few hours.  I read every Wikipedia page possible, and I talked with different users.  After a lot of extra work, I did the best I could to get my assignment submitted. 

After that fiasco was over, I realized why more people don’t edit Wikipedia more often.  It’s hard, and unfair (yes, I know that the world is unfair, but Wikipedia seems a little extreme considering it’s an encyclopedia).  My page was protected because irresponsible people put inappropriate and profane language on the page.  This stops people who have good intentions from adding to the page.  Another problem is, even though one user does a lot of quality work on a page, and provides accurate information, another user, who may know nothing on the topic, can simply delete all that information.  This decreased the value of the page, and Wikipedia (and seems a little unfair), but unfortunately I cannot think of a real solution to this problem.  

If there is one thing I take away from this experience, it is that I now understand why Wikipedia is never a good source, and that it is always important to check the validity of your sources, because anyone can put anything on the Internet.