Problem solving slog

                          Products of sums
   1)Understand the problem
    The problem was stated as following:

    For this question, I interpret it as this: If all the positive integers in a list add up to n( no matter how many elements there is), we need to find a certain kind of way to organize the list so that the product of every elements is maximized. As the example shows in the question, if the integers add up to 2, there are two different lists:[1,1] and [2]. And the second one has a bigger integer so it is the list we are trying to find.

2) Device a plan or two. What is the best case result you expect from the plan?

     For the second part, I come up with a plan. Firstly, I would write down the example with the sum of several small positive integers like 1,2,3,4... For each integer, I would think carefully to write down all possible lists with the sum of that integer.According to the examples I write, I would find out the regular patterns they share and what is similar among all the examples. To make it not a mess, I would write down the lists according to some regulations and orders. For example, every factor in a list must be bigger than 1 and less than the sum number itself. Larger numbers occurs last in a list. And longer list should followed by a shorter one. In addition, I would try to avoid duplicate lists.

    I also make a conjecture.If n is an even number, then the list with the maximum sum should be [n/2, n/2]. And if n is an odd number, then the list with the maximum sum should be[(n-1)/2, (n+1)/2]. This is the best case result I expect for my plan.

3) Carry out and verify your plan.

     To carry out my plan,the first step is to write some examples.

1. n = 1 lists: [1] the expected list:[1]
2. n = 2 lists: [1,1],[2] the expected list:[2]
3. n = 3 lists: [1,1,1],[2,1],[3] the expected list[3]
4. n = 4 lists: [1,1,1,1],[2,1,1],[2,2],[3,1],[4] the expected lists[2,2] or [4]
5. n = 5 lists: [1,1,1,1,1],[2,1,1,1],[2,2,1],[2,3],[4,1],[5] the expected list[2,3]
6. n = 6 lists:[1,1,1,1,1,1],[2,1,1,1,1,1],[2,2,1,1],[2,2,2],[2,3,1],[3,3],[3,1,1],[4,2],[4,1,1],[5,1],[6] expected list[3,3]

......

 From the examples I write above, I figured out one regular pattern. When n is larger than or equal to 4, if n is an even number, then the list with the maximum sum should be [n/2, n/2]. And if n is an odd number, then the list with the maximum sum should be[(n-1)/2, (n+1)/2]. But when n is less than or equal to 4, the list with the maximum sum should be[n].

4) Look back, figure out when and how you become stuck, and what insights represented a breakthrough.

   From the carrying out part, I found out that my original conjecture is partly true.It is true when n is larger than or equal to 4 and false otherwise. Even though it is not totally right, I still gain some confidence for my conjecture is very near the truth. When looking back, I became stuck when I was examine the first four examples since they do not follow the conjecture I made. Which makes me confused. However, there is a breakthrough when I examined the fifth example cause it follows my conjecture. Which is even better is that when n becomes larger and larger, they all follow my version of pattern that if n is an even number, then the list with the maximum sum should be [n/2, n/2]. And if n is an odd number, then the list with the maximum sum should be[(n-1)/2, (n+1)/2].

Conclusion: I have found that this problem solving process is very interesting and challenging. Since I solve the problem finally, it makes me like thinking and want to challenge something more!

     

CSC165 sLOG 9

  As I have already say goodbye to test 2 and chapter 3, I have no reason not to pay more attention on chapter4 regarding algorithm analysis and asymptotic notation. In lecture, pro introduced the upper bound and lower bound for the input with the size of n in worst case. Then he provided us some examples about Wis belongs to big Oh. f(n) belongs to O(g(n)) means there exists a real number c and a natural number B for every natural number n, if n is no less than B, then f(n)less or equal to c times g(n). c is a multiplier ,B is a breakpoint, so that you can go far enough to the right the function is bounded above by cg(n). In terms of limits, this says that as n approaches infinity, f(n) is less than cg(n) once you find the appropriate c.At the beginning, I found the big Oh problem is not easy to do. But after some practices in lectures and tutorials, I become more and more familiar with these kind of problems. It also requires you to be good at writing proof structure. By the way, it is important to remember that for every while loop, we need to execute one more step for the first line!
   Regarding polynomials for big Oh problem, f belongs to O(g) when the highest-degree term of g is no smaller than the highest -degree term of f. Furthermore, logarithmic functions are in big Oh of any polynomials, whereas exponential functions are not in big Oh of any polynomials.When proving some big oh questions regarding exponential functions, it is useful to use the meaning of limit. We also learnt big Omega problems, which is the opposite to big Oh by definition. This time the role of c is to scale g down to below f.

CSC165 Slog 8

   It has been a busy week for my studying for CSC165 cause we have the second midterm this week regarding chapter3: proof. I spent a lot of time doing practices for proof and review the course materials like the course note, the web problems, lecture slides and past tests.Since we have learnt calculus in MAT135 and MAT136, it is not that difficult for us to deal with mathematical problems when proving. However, it was a headache for me to write appropriate comments maybe it is because my first language is not English. So my whole aid sheet I brought to the test was filled with different kinds of comments. We have three questions in test2, the last one is a little bit hard. Even now I am not sure whether I got it totally right and I am eager to know the result. I think I still need to do more practices for proof cause I am not skilled at it.
  Recalling assignment 2, I think the questions are more complicated than that on test 2. Some of them are a little tricky and you have to think about it for a while especially the last question. The great common divisor thing is kind of hard to comprehend and it needs you to be very logic to figure it out. When I see the official answer, I found out that our solution for the gcd question is not good enough even though we tried very hard to prove it. Anyway, I like proofs even though I have to say goodbye to it for now and learn something more complicated-the big O!

CSC165 Slog week7

This week, the professor lead us to study several proof cases. Firstly, we learnt proof about limits. That example make me very confused.From an existential quantification, I am not sure how to pick a number which satisfied the requirement from the question. Then the professor told us to calculate y^2 - pie^2 first and then find out the scope of that number we should pick. Therefore I finally figured it out under professor's guidance. Afterwards we learnt how to prove by cases.The question is: for every natural number n, n^2 + n is even. A natural approach is to factor it as n(n+1), and then consider the case where n is odd, then the case where n is even. Because both cases are proved to be true, the statement is true. Moreover, we learnt some new things like allowed inference and sorting strategies. For inference, I knows how to make conclusions by studying conjunction elimination, existential instantiation... For sorting strategies, I found that the steps required for insertion sort and selection sort on lists of size n were no more than some quadratic functions of n. They are all in O(n^2). When counting costs, we learnt that we should always consider the worst case. To conclude, the professor gave us several examples of counting steps.

CSC165 sLOG WEEK6

  Last week we continue to learn something about proof. I found out that proof is such a big topic which needs a lot of practices to manage it. This week I read the course notes and learn a lot from it.Here are some definations: a lemma is a small result needed to prove something we really care about. A theorem is the main result that we care about (at the moment). A corollary is an easy (or said to be easy) consequence of another result. A conjecture is something suspected to be true, but not yet proven. An axiom is something we assert to be true, without justi cation ( usually because it is "self-evident.") For direct proof of universally-quantified implication, When we assume that x is in D, we are in the "world" where x is a generic element of D. To prove the converse of a statement, you set up the proof of the contrapositive of the converse. I found it is a hard part for example of proving a statement about a sequence. I go through the progress several times and finally figured it out. For multiple quantifiers, implications, and conjunctions, I found that it is not difficult if you have a clear mind and do it step by step.

CSC165 SLOG week5

This week we have a term test for CSC165.Therefore, we only have two lectures. We continued to learn the structure of proof.Generally, there are two steps or phases to creating a proof:1. Understanding why something is true.2. Writing up your understanding. Sometimes these steps can be combined, and often these steps feedback on each other.For the proof outline, when we prove a statement leaded by the universally quantification, we assume the element is a generic one.And we conclude with the whole statement. In the middle, we assume antecedent and then try to prove the consequence of implication. When we prove a statement leaded by existential quantification, we just pick an element from the specific scale, then assume the antecedent and prove step by step until we get the consequence of implication. In the end, we conclude. I found out that writing comments is a good habit.Because if you could not understand one step, comments are very helpful.We also learnt how to prove by using contradiction. It seems that proof is not an easy chapter, we need to do a lot of practices to get to know how to do proof problems better.
  Btw, for the test I felt I did so so. Waiting for the result.

CSC165 SLOG week4

   This week I have learnt a bunch of new things of CSC165. I found that truth table is very useful for evaluating a complicated statement. And I found myself more skillful than before to change my expression for by-implication into the disjunction of two conjunctions.I have learnt the concept of transitivity. It should be well remembered that once the sequence of universal quantifier and existential quantifier has been changed, the meaning of the whole statement would be changed. To make us understand this clearly, the professor drew several graphs to explain this problem. By studying the graphs(such as the graph of approaching infinity) he drew, I gradually understand it. Since one factor is first chosen and another factor is chosen after we now the previous factor, it is not difficult to estimate the scale. Let us put it another way, if one is determined first, another one is going to win.By studying double quantifiers, I knew that there are at least 3 ways to claim that a certain subset of the cartesian product is non-empty. There are also 3 ways to claim that en entire catesian product has some property. In these cases, the order does not change the logic.That is the end of the first two chapters.
   Then we learnt some basic knowledge about proof.It is said that a proof communicates why and how you believe something to be true. Fist you need to understand why you believe the thing is true. Then you need to write it down. We learnt it by studying the example of finding proof of universally quantified implication. A proof outline contains some argument with 'assume' and 'Then'. Moreover, the comments which was leaded by # are very important in the format of proof.