Week 11 - Problem Solving Exercise and Halting programs

Week 11

During the first two lessons, we worked on solving halting problems in programs. This chapter allowed me to understand the basics of computability theory, something that I will learn in great depth during CSC236. I was also given an insight on proof by induction although we did not go through the proof in great detail. A program halts if it does not get stuck in an infinite loop and returns some value, whereas a program that does get stuck in an infinite loop does not halt. This part of the course particularly interested me since my tutorial TA mentioned that determining whether a program halts can be used to create a program that can be used to debug another program which can speed up the process of coding. 

On Friday, we focused on working on a problem solving exercise, which involved finding the number of squares a diagonal passes through provided the dimensions m and n.

Before tackling this problem, I broke the problem into smaller instances. For Example, in the example above, I decreased the problem size from m = 6 to m = 4 to m = 4 to n = 2.

Following this, I concluded that m and n are related in a way such that m + n - 2. Thinking, I was done with my proof, I did not check the case where m and n are not multiples of 2 although I did know that it is in the form of n + m - k, where k is some constant. After consultation with my other group members and I discovered a pattern that k is always the greatest common denominator of m and n. I finally concluded that number of squares = m + n - gcd(m, n). This conjecture is valid as it works for every possible combination of m and n provided that m and n must obviously be natural numbers.

Week 9 and 10

In these two weeks, we begun analysing worst, best and average cases of a program. In week 9, we were introduced to big oh notation, and counting the number of steps in a program, which we later defined as the running time. We typically compared the running time of different sorting algorithms. In tutorial of the same week, we discussed how to find the total running time of programs and discovered that the total worst case running time of a program can be formulated by sigma notation. We also discovered that running time depends on the the length of the list of which we want to sort.

This allowed us to transition into our main topic for the week, which is Big oh proofs. We spoke about this briefly during earlier weeks of this course but it was more formally introduced this week. In our Tutorial exercise, we were given problems to work on which involved proving that a function is inside big oh provided that it satisfies the given definition.

In addition to big oh, we were also introduced to big omega proofs which computes the worst case of an algorithm. Both have similar definitions but with slight variations in inequality signs.

Overall, this week has been fairly challenging, however, I have been able to understand the basic structure of the proof and how it can be applied in different ways to various applications. I have a somewhat understanding of the theory behind proving big oh but I hope to further improve my understanding of big oh notation prior to the final exam.

Week 8

This week by far was the most demanding week as we transitioned from proofs into Big Oh analysis. I found it hard to cope up but managed to consolidate lecture notes and office hours to clear up my understanding. We learnt about the formal definition of big-Oh analysis. We learnt that through big-Oh we will be able to count the number of steps in a program execution. We also learnt about the idea of a worst case in a program, which is a case in which a program takes the most amount of steps in execution. The number of steps in a worst case can be calculated if the program takes the most amount of steps.

In tutorial, I finally cleared my understanding of proofs as our tutorial exercise included proofs.  This week overall was enjoyable and did not seem very tedious, as I managed to understand the concepts completely.

Week 7

This week, we were introduced to proof by cases. This includes breaking the argument into different cases and proving true for each case. We see this a lot in conjunction or disjunction statements. It is also used in proving absolute values of statements. This is because, the proof of an absolute value inequality can be simplified to -b < x - a < b where the original statement is | x - a | < b. This proof method seemed less complex than previous proofs because I fully understood the Professor's explanations and examples.

In this week, we were also introduced to counting steps in an algorithm, which exposed me to the concept of Big Ohs. We learnt about the efficiency of algorithms and how the number of steps which is measured as "running time" can be formulated into expressions. This lecture was straight forward as counting the number of executions in a program did not seem very demanding for me. This was one of the most enjoyable lectures for me since I have always wanted to learn about efficiency in programs.

Week 6

In this week, we were introduced to proving something false and negations of statements. This week really allowed me to increase my understanding of proving complex statements. It gave me the understanding of going from the antecedent to the consequent of the proof by assuming the antecedent and proving the consequent. We were also introduced to proving floor functions by using their definition. This week was another hectic week for me as the concepts at first seemed extremely difficult to comprehend.

One extremely difficult concept, I found was proving the limit of a statement. I was not able to find the proof of limits but I hope to clear my understanding soon.

However, during tutorial, my confusion from last week cleared up as our TA went through many examples of proofs and explained each step carefully. We were also introduced to proof by negation. This allowed me to take the negation of a statement and proving the negation. Upon successful disproval, we have successfully disproven a statement.

Week 5

This week was extremely busy for me as exam preparations were already following the assignment were underway. The exam overall did not seem hard as the questions were similar to the practice paper Professor Heap linked us. I have also practiced with various practice papers from previous course offerings, therefore I was prepared for the exam. In addition, in order to facilitate my learning, I had also read  through the book "How to prove it" from the recommendation from Professor Heap.

During Tutorials, we were also introduced to proofs and proving algorithms. We also went through the basic syntax of proofs including comments and indentation. Much of the material covered also linked to my other CS class, CSC148 since the syntax was very similar to Python. It allowed me to connect both subjects and I was ultimately able to find that writing python programs were very similar to writing structured proofs in mathematics. It provided me a lead in to the world of proofs and created a foundation of my understanding of proofs.

Week 4

During the fourth week of the course, I have continued working on my assignment and clarified my concerns with Professor Heap. This week has been a great learning experience for me because I am finally starting to understand my errors in the assignment. Towards the end of the week, I have fixed these errors and provided appropriate explanation. In the end, I have managed to finish the assignment with my group partner and submitted it on time.

During this week, we also learnt about proofs and how they can be proved. We went over the step by step procedure on how to appropriately structure the proof with explanations. We also learnt how different laws can be used to prove a statement and provide explanations. In addition to this, we have learnt about Implications and how a statement can be represented with mixed quantifiers. Hence, by the end of this week, I am now able to differentiate between statements that use the existential quantifiers and statements that use the mixed quantifiers. One aspect of the course content however, that was difficult to understand was limits. Although Professor Heap was able to explain it thoroughly, the notation that he used was confusing. I hope to fix my understanding this weekend in order to prepare me for next week's mid-term exam.

Week 3 Slog

During the third week of CSC165, Professor Heap introduced us to Conjunctions, Disjunctions and Negations. We learnt the different notations used to signify conjunctions and injunctions. Throughout the week, I also improved my ability of transferring english statements to mathematical symbols and have improved overall. In addition to this, we learnt how negation has the ability to change symbols. Hence, we were introduced to DeMorgan's Laws.

We often use conjunctions when combining two statements with an "and". This therefore symbolises that both the original two statements are true. Let us take an example, when making the statement, "There is a pen and telephone" we can therefore use a conjunction since the statement uses the word "and". Disjunctions on the other hand are different from conjunctions since they are joined together in order to prove that either one of them is true. It however does not prove that both are true. When negating a statement we put a "not" operator at the front in order to prove that the opposite of that statement is true. Hence, as an example, not(True) returns the opposite of the boolean value True, hence False. This therefore leads us to discuss DeMorgan's Laws. DeMorgan's Laws prove that when one negates an entire statement, every other element in the statement also turns into a negative statement.

As seen above the not operator is applied to s(1) as well as s(2). In addition, the Disjunction operator also changes to the the Injunction operator. Professor Heap taught us how this can be proven through Sets. This therefore not only increased my understanding of the theory behind this but also allowed me to understand how one can use this.

In order to illustrate implications and symbolic statements, we were introduced to truth tables which really allowed me to gain a better understanding of implications, conjunctions and disjunctions.

Lastly, we were also introduced to some simple terminology namely Tautology, Satisfiability and Unsatisfiability. One makes a judgement that a statement is satisfiable when the premises leads well into the conclusion. However, the opposite of this would mean that the statement is not satisfiable since there is a contradiction if one of our test cases fail. A Tautology is  when one explores various test case values in order to come to a conclusion.

Overall, this week really allowed me to gain a better understanding of using Logic in Computer Science. I believe that truth tables really allowed me to gain a better grasp on the subject material.

Week 1 and 2

In the first week of the course, Professor Heap went over the basics of set theory which are the basic fundamentals of Mathematical reasoning in Computer Science. We were introduced to the method of solving Mathematical problems which is common in both Computer Science and Mathematics. Firstly we must understand the problem at hand and analyse the situation thoroughly. We must be able to familiarise ourselves with any relevant given values and understand which variable we are required to find. In order to make the problem simpler, one must restrict the language and therefore strive for clarity. This therefore, allows us to reach precision in our answer. Next, one must be able to generate an effective plan to tackle the problem at hand. The plan must include ways in which we can use given values in the question to carry out a series of steps to generate an answer. Next, we must carry out the plan in order to find our solution. The final step, allows us to review our answer to match with the accepted answer. If such solution matches, we can conclude that our answer is correct, otherwise we must check our plan to verify there we had gone wrong. We therefore practiced this procedure on numerous problems, many involving Python code. I found this part of the lesson particularly useful as it gave me a headstart into problem solving in Mathematics. It also allowed me to find the relationship of this to Mathematics. Further on this week, we learnt about representing sets in diagrams which allowed me to understand how sets are represented in graphical form. This also appeared in our tutorial exercise which I found fairly straightforward to understand.

In the second week, we learnt about implications, converses and contrapositives. An implication is relates to a cause and effect, or in mathematical terms P(x) -> Q(x). This is mainly found in conditional statements. The opposite of this  is known as the converse, which is mainly known as Q(x) -> P(x). Furthermore, the contrapositive is known as not(P(x)) -> not(Q(x)). I have found this section of the course particularly challenging but hope to reach full understanding of the course material by the end of this week. However, due to the rigour of the material, this part of the course was by far the most enjoyable in CSC165