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.