8th week journal

This week, we learnt the algorithm of insertion sort. We derived the exact form of the W(IS) and determined the upper bound and lower bound. We learnt how to prove the time complexity of the insertion sort. First, we need to analyze the sorting method and define the worst case. 'O' is the upper bound and the 'Omega' is the lower bound.

We need to get familiar with how the sorting methods works and practice a lot of proofs. I found that analyzing the steps that we are going through the sorting methods are hard. But once I get familiar with the sort and the knowledge with the 108 of python code, I think it will become easier. And proofs need a lot of practice. I think after I finish the assignment 2, I will get more familiar with the techniques that I can use in the proofs.

7th week journal

This week, we learnt more techniques for proofs. Proofs by cases are sometimes handy when I am stuck at certain proofs. The cases are required to cover everything in the sets, and start proving it using the given definitions. We also learnt the introduction rules and the elimination rules. And it comes to an end to the proofs and we get to touch on some more complicated materials--algorithms. Running time is the most important factor when computer scientists decide which algorithm to use. 

For proofs, I need to do lots of practices and start from finding certain pattern. I can use the rules to keep trying. This will make me get closer to the target. After two weeks of proofs, I found proofs are not as hard as I thought before, maybe because I practice a lot and I learnt more techniques for the proofs. For algorithms, this is important in computer science. We can sort a list using different algorithms. Like bubble sort and merge sort. Different sorting algorithms take different amount of time. Some have more steps than the others. Once we have a super long list, we would want to use the algorithms with less steps, because that will save lots of time. I need to get familiar with how each algorithms work before analyzing it.

6th week journal

This week, we learnt proofs. Proofs require lots of thinking. We learnt how to prove a non-boolean statement, how to disprove a statement, and proof about limits. A non-boolean statement is usually likes a function. Not a equation that returns true or false. A typical non-boolean function is the ‘ the floor of x’. We cannot apply quantifiers to this non-boolean function.  And to disprove a statement, we just need to prove the negate form of that statement. To prove a limits, the order of quantifiers matter a lot. I can always think that given such statement, how I can choose a statement to win the statement.

The proofs are challenging, especially the proofs about limits. The proofs have specific formats, so I think the first thing I need to do is to get familiar with the formats. The most important thought about proofs is that I have to understand the statement clearly and need to believe the statement is true. By following the format, then I need to practice a lot to improve the thinking. There are many ways to prove a statement, so practice will help a lot. And I believe there are some patterns for proofs. Like proving an implication, while choosing the arbitrary numbers or functions, we can also do the latter part first then come back to this function. Because it’s easier and more accurate that way. 

5th week

This week, we get to proofs! We have different approach for different proofs. For proving universal, some proofs are easier to prove using contradiction, others are easier using contradiction. Because to prove a universal, we cannot have any counter examples. For existential, we need to find out at least one example to prove it.

Proofs seem like the most challenge material for this course. It requires lots of thinking. We have to believe the statement and understand the statement in order to prove it. The thinking part comes from practice. So doing lots of practices will help me to think faster. And I think the very important thing for me to do is to get familiar to the math definition. Since I forgot those math terms, it will trouble me a lot. Like prime numbers, R set, N set, etc.

And for the midterm, the most challenge thing to me is the time, because I am not a fast-thinking person. So in that short amount of time, when I was nervous, it made me think even slower. But after all, I finish all my questions. I think the lectures, assignments and tutorials are important, because this course is more towards understanding than memorizing.  And lectures, tutorials and assignments help me understand the materials well. 

4th week journal

The materials are getting harder and harder. This week, we learnt mixed quantifiers, bi-implication, transitivity and the basic proofs. From mixed quantifiers, I knew that the domain of a set is really important. The order of the quantifiers matter a lot, when there are a combination of universal quantifiers and existential quantifiers. For transitivity, this is important for proofs. Same as math, if a>b and b>c, then a>c. For proofs, we learnt the format for writing the proofs, and the starting steps when we first see a proof.

The proofs seem troubles me a lot, because I didn’t understand the example that was given out in the lecture today. I will try to understand it or ask it through piazza. Other than the new materials, we finished our first assignment. This assignment is harder than I thought it would be. Because I studied the materials before doing the assignment and I thought I understood everything. However, when I was doing the assignment with my group, I found that I didn’t know the materials that well. Especially when it comes to venn diagram and the existential statement. I will focus more on these materials while I am studying for my term test.  After doing this assignment, I found myself have a better picture of how everything we learnt links to each other. Doing the assignment in a group is better than doing it individually, since everyone will give out their own opinions and discuss. This is more interactive and I learnt a lot from my group mates. 

We also did a problem solving problem in class this week. It is called folding. We first need to understand the problem. So the purpose for this problem is to predict the sequence of ups and downs for any number of times that we carry out the folding operation. The ups and downs were accounting the creases point vertex up or down. Second, we devised a plan. We decided that one of people would do the folding and the other two would do the recording, so that we could compare our records and avoid mistakes. From our knowledge, we know that the paper can be only folded 5 times. Then we started doing the folding after all the planning. The first 4 could be easily read, but when we folded the paper the 5th time, the ups and downs are hard to distinguish and we checked it over and over again. After we got all the data, we started finding the pattern, since we could not fold the paper again. First, we counted the total number of each fold. The total numbers of ups and downs are 1, 3, 7, 15, 31 accordingly. And we found that the total number of each fold was different by 2 to the n powers. Then we were stuck when finding the patterns of ups and downs. Danny then told us to flip over the paper to look at the hints. After looking at the hint 1, asking that ' is one pattern somehow 'contained' in the other, we suddenly realized that the 2nd fold actually contained the sequence of 1st fold, and the 3rd fold contained the sequence of 2nd fold as its last portion of sequence, and so on. After looking at the second hint, suggesting that we could organize the fold patterns symmetrically. We looked back and carefully rewrite the patterns symmetrically. We finally found the pattern! This was actually a fun problem and following the problem solving steps made the thinking process more organized and clear.