Final Thoughts

  The semester has come to the end. Like many of my peers, I am busy studying, procrastinating, and squeezing in that extra slog before the deadline. Overall the csc165 experience has been great. The course reconfirms my decision of going into computer science. I have always loved problem solving, and logic is definitely one of my favorite subject and strength.

  Below are some blog posts from my peers that I find interesting. The last one prompted me to do more research on the problem. The poster simplified the problem, and I tried to solve the original question. After finding that it was beyond my capability, I searched online for a solution. This website gives a detailed solution of the question: http://www.geometer.org/mathcircles/indprobs.pdf . Interestingly, it also proved the poster’s simplified solution wrong. In fact you only need two colours to solve the problem.

Guess my love for solving logic problems is here to stay.

Interesting posts:

An example of the halting solution that helped me understand

http://timothylock.me/sLOG/2014/11/30/week-11-halting/

Detailed recording of problem solving process and insights in problem solving

http://165choi.blogspot.ca/2014/11/tackling-assignment-3.html?showComment=1417581724893

Polya’s approach to problem solving, penny piles

http://ryancsc165.blogspot.ca/2014/12/problem-solving-episode-penny-piles.html?showComment=1417582831045#c7538314247665592910

Interesting thoughts on intuition

http://thesnailslog.blogspot.ca/2014/10/its-not-logic-its-intuition.html?showComment=1417583264352#c3351338564767101041

Detailed summary on sorting

http://csc165weeklyslog.blogspot.ca/2014/10/sorting-week-7.html?showComment=1417583589315

A familiar problem….

http://csc165judy2014.blogspot.ca/2014/11/week-11-journal-10-problem-solving.html?showComment=1417583965276#c3698401123937709652

Countability and Induction

    All good things come to an end, including csc165. In our last couple of lectures, we wrapped up with countability and induction. The two topics were very contrasting in terms of difficulty. Having learned in high school and mat137, induction is no foreign idea for me. However, I find the countability and computability sections very abstract. I had trouble understanding in class the concept of diagonalization, knowing only that it shows how there are programs that are incomputable. Going through the tables and lecture notes one more time on my own, I finally realized what Danny meant when he said there is always at least one result that is different in diagonalization. Knowing that computability and induction will not be in the exam is a relief. Yay for slightly less material to study.

Halting problem

    The materials we learned this week were a real challenge to me. We started a new chapter on computability and more specifically, the halting problem. The halting problem is one of supposedly many questions that computer cannot solve. The idea is to write a function that determines whether a function will halt or not. This is proved to be impossible by both Alonzo Church and Alan Turing, independently, in 1936.

    While in lecture, I found the disproof of the halting problem confusing. Admittedly I was lost in the proof and had to review the lecture slides to fully understand it. To disprove the halting problem, we have to create a contradiction. For example the function below solves the halting problem:

def new(f):

while halt(f, f):

pass

return “haha”

    Consider halt(new, new), which tests if the function new halts. If new(new) halts, then halt(new,new) is true and new(new) gets stuck in the while loop then new(new does not halt). The obvious contradiction in the sentence is highlighted in red, and a similar contradiction is shown when we assume new(new) does not halt.

    What is truly interesting about the halting problem is that it is only impossible in the current programming languages that we have. This leads to other provoking questions. Is it possible to invent a new language that makes some ‘unsolvable problems’ in the current languages solvable? As for me, such a language is beyond my imagination, because it will be a whole new way of thinking and a whole new dimension of logic.

Big Omega and General Statements

    This week we wrapped up the Big O session with Big Omega proofs and general Big O statements. The Big Omega proofs are very similar to the Big O proofs. The way I remind myself is this: if I am trying to prove that g(n) <= c*f(n), I will have to manipulate g(n) into a similar expression, say g’(n), that is greater than g(n). This way if g’(n) <= c*f(n), the statement will be true. By the same logic, for f(n), I will have to find a f’(n) that is smaller. Every time I start a proof, I go through this process to see what I am trying to find. This extra process helps me a lot, since I will not have to memorize the steps and possibly get confused by Big O and Big Omega. In terms of general statements of the Big O, I find that it is crucial to understand the relationships between the variables and to utilize the definition of the Big O. This dictates what examples to pick when proving a statement (ie. max, multiplication). 

Big O Continued

  This was an eventful week for csc165. We continued on with the Big O proofs in class and had our second term test on Wednesday. The test went fairly well since the questions are very similar to the assignment questions.

  After some practice in class, I think I am starting to get the hang of Big O proofs with polynomials. The practices also showed how important having a solid understanding in constructing proofs is. With Big O proofs, the numbers we use for c and B can differ, which makes the proofs more diverse and interesting. However, I find myself having problems with proving the negation of the Big O statement, such as the second question in the tutorial 7 problems. I am guessing that n has to be a function involving c and B, and maybe the roof of c since n has to be a natural number. I look forward to the tutorial on Tuesday to see the actual proof of that question.

Big O

    This week we started a whole new chapter involving counting program steps and the Big-O. The concept of Big O is simple as of now, but I expect to see more complicated variations and examples in the near future. I am understanding the ideas of a breaking point, and I find the graphical representation very helpful. However, counting the number of steps the program takes is surprisingly more difficult than I expected.  When trying to find the worst case scenario, I find it confusing when there is a for loop inside another for loop because of the new variable. While loops are similar, but with a restriction to watch out for. I think overestimating the number of steps making it much easier because I get a general idea of the number of steps. Overestimating the steps may actually not be that bad, since it will still work if we are relating it to the Big O.

Penny Piles

In Friday’s class, we were given an interesting exercise, the question shown in the image below.

Like last time, the purpose for this exercise is to help us familiarize with the procedures of problem solving. I will briefly explain how I solved each of the 3 questions, and reflect on how I could’ve done better.

Q1: 64 pennies to start with, sort it so that one drawer has 48 pennies

A1: The solution to this questions is straightforward. I move the pennies twice to obtain 48 pennies in one drawer.

Q2: Find any numbers in range [0, 64] that are impossible to achieve.

A2: First off, I need to find ways to get the numbers from 0 to 32, since any n above 32 exists if its counterpart 64 – n exists. I approached this problem by drawing a tree diagram. It would be unrealistic to draw out all possibilities on the tree diagram, so instead I drew only 5 layers. I then realized, after continuous trials, that I can obtain all number from 0 to 32 in the tree diagram, and thus there are no numbers that are impossible to achieve.

Q3: Starting with a different number of pennies in the left drawer.

A3: First, it is obvious that the number has to be even because the pennies cannot be split if there are an odd number of pennies. I tried drawing sketches of tree diagrams for some even numbers I chose arbitrary, such as 48, 28, 36, 54, 100, and 20. At the same time, I also factorized the numbers into their prime factors, suspecting it would give some related clues. With that many examples written in front of me, I was soon able to see the pattern and hence the solution. One has to start with an even number of pennies, expressing the number as (odd*(2^n)), in which ‘n’ is a positive integer and ‘odd’ is any positive odd integer. The number of pennies one can obtain in a drawer is the multiples of ‘odd’ up until (odd*(2^n)).

Below is a picture of my rough work on the exercise paper. It might be difficult to understand since it is all over the place and there are no explanations or comments included. That, I think, is an area I need to improve upon. I need to be able to present my solution and procedures neatly, and maybe organize my procedures as I solve the problem.

More Proofs

  With two midterms coming up next week, this week’s slog is going to be short.

  This week in class we continued on with proofs. The examples we are tackling are getting consistently more difficult. For example, in Wednesday’s class, we focused on the question with “floor of x”. What caught my attention was when proving the result “floor of x > x - 1”, in one of the steps, we had to use “the contrapositive of the third point of the definition of floor of x”……After reviewing the material, I finally understood what the professor did there. In conclusion, I think I need more practice to be able to “see” what to do in a proof, because these methods, even though understandable, do not come intuitively.

    By the way we also proved the epsilon – delta definition of limits in class, which was a nice review for the upcoming MAT137 term test.

Term Test and Proofs

  This Wednesday we took our first term test. Honestly speaking the term test was not as difficult as expected and surprisingly similar to the practice test

  Now to proofs.

  Doing proofs is like solving mazes drawn on paper. You know where to start and where you want to end, all that is left is the “middle part”. You can work towards the result from the start (implication), or you can work backwards from the end (result). Doing proofs require a much better understanding of the problem and solution, and it is this that differs it from solving computational problems. One proof that we went through in class that I find interesting is Euclid’s proof that there are infinitely many prime numbers. The proof showed creativity with the use of contradiction and demonstrated full understanding of the subject by using the prime property that every integer >2 has a prime divisor. The proof was difficult to understand when reading it the first time, and I can only imagine how difficult it is to construct it from scratch.

Cheat Sheets

    The first term test is coming soon, and I am not sure if I am prepared or not. Luckily, we are allowed a cheat sheet for the test. Naturally, I tried to cram as much as I could on the two sided letter paper. However, I discovered that the act of copying notes on a cheat sheet actually helps the process of studying a lot, since I am summarizing all the notes. It also highlights my weaknesses, such as drawing Venn diagrams for the distributive laws. In fact, the process of making the cheat sheet might actually be more helpful than the cheat sheet itself during the exam. This is why I like math and logical reasoning. Unlike many other subjects, mathematics and logical thinking is a skill that will not be easily forgotten. More importantly, logic cannot be learned by memorization, which is why the cheat sheets are more reliable as a tool for studying than a lifesaver during the upcoming exam. 

PAPER FOLDING!

  During this week’s lectures, we continued our slow tread through Chapter 2: Logical Notation. We learned in Monday about negation and how to move the negation sign further into the expression. We were also introduced to truth tables, which I find much more concise and convincing than Venn Diagrams. We went through logical arithmetic and DeMorgan’s law in Wednesday’s lectures, which were mostly understandable. The part that confuses me is the distributive law. I can see it is true on the Venn Diagrams but still cannot wrap my mind around it.

  The highlight of the week came Friday when we were given an exercise in lecture to find the pattern of the creases when you fold the paper from left to right. The purpose of the exercise was to implement the “problem – solving procedures” we briefly talked about during the first week of class. 

The procedure goes like this:

1    1. Understand the problem

2    2.  Plan a solution

      3.  Carry out your plan

4    4. Review any solution you achieved

  This is almost the same as the procedures I take when I solve a problem, except that I do not always plan a solution. More often than not, I will have a vague idea of a solution in my mind and proceed with it (and improvise as I go along). That had worked for me in the past, but now as I move forward to more difficult problems, I should probably consider this new problem solving strategy…….

  On a side note, I could only fold the paper 5 times when folding it in the same direction continuously, instead of 7 times (paper folding myth).

  On another side note MythBusters folded a piece of paper more than 7 times: https://www.youtube.com/watch?v=kRAEBbotuIE

Vacuous Truth

  Almost two weeks have passed since I stepped in the first lecture of CSC165. I must admit the course is not really what I expected…… and I AM LOVING IT (so far).

  I remember in our first tutorial, our TA jokingly mentioned that there are people who would spend their time debating over logic. Sitting there, I thought to myself, “Well that sounds like something I would do!” As of today, September 18^th, we have covered topics including quantifiers, if-then statements, and converses and contrapositives. Much of the topics discussed overlaps with the syllabus of MAT137, hence sometimes the lectures feel like a review for another class. However, there are several interesting problems I encountered, one of which being the case of vacuous truth.

  At first, I found the idea of vacuous truth very abstract and absurd. How can something that is false (or unrelated) in the first place make a logical if-then statement? However, after going through some examples in my head, the concept of a vacuous truth began to make sense. If the first statement of the implication is false, the if-then statement will always be true, whether the second statement is true of false. In my own interpretation, this is because the first condition of the implication (the if…. part) is false, the implication itself will have no value, and everything implied would be possible, hence true. 

  What really shocked me was the application of this concept in our tutorial questions. In one particular case where we had to draw a Venn diagram of the false case of the statement “some programs (out of 3) pass the test”. I forgot to include a “O” in the region exclusive of the 3 programs. I realized my mistake in the tutorial. The O must be included because in the case where there are no programs all statements are true, hence the application of the concept of vacuous truth.