CSC 148 - Why geeks should write

I am a first-year student in CSC148, which is a course that teaches students how to write solutions for advanced problems, a continuation of the CSC108 course. It also covers concepts from abstract data types to recursion. Some people have also told me that I will be learning about data trees and algorithms, including that for sorting. Overall, this course aims to expand our knowledge in systematic and efficient programming as well as foster good programming skills.

This is just a brief introduction to the course that I will learn a lot in. Now, why should computer scientists write about computer science? This is a good question, as many would expect a computer scientist to program a lot and spend his or her time in front of a computer, not writing blogs. However, I do feel that computer scientists need to keep in touch with concepts that they have learned in their field and also maintain good writing habits. Writing about concepts learnt helps a computer scientist by reminding him/her about what certain aspects of computer science are or how they are supposed to be understood and applied. For example, if there is a definition of a computer science term, such as abstract data type, reading about it will help to understand the concept, but writing down its definition and other notes about it will help a computer scientist better absorb and retain this concept. Similarly, I will now define abstract data type in order to help me remember what it is.

Abstract data type - a data type that specifies a set of operations (or methods) and semantics of the operations (what they do), but it does not specify the implementation of the operations. 
http://openbookproject.net/thinkcs/python/english3e/stacks.html

Basically, it is a data type that specifies a set of methods and what they do, but it doesn't specify how they do what they do. This is an example of my own annotations to make sense of this term. In this, writing helps as well as computer scientists will better understand concepts, especially when they put it in their own words. Furthermore, whenever they are doing a project, assignment, or anything related to computer science, computer geeks can look back at blogs they have written about a particular concept or term if they don't remember it. This way, blogs about computer science will serve computer scientists well in the future. They can serve as an aid to understanding and refreshing one's memory about certain concepts previously learned. As well, they serve as an excellent tool to write about new concepts learnt each time. 

Additionally, computer scientists should write blogs so that others will benefit from their knowledge as well. By reading these blogs, other aspiring computer scientists or people will understand and enjoy the concepts of computer science. As well, if they don't understand a concept or term, they can just refer to these blogs to help understand concepts and in turn, this will help them apply their newly learnt concepts to their existing knowledge of computer science. This way, writing about computer science will not only benefit the computer geek writing it, but also its readers who wish to learn and gain knowledge.

Week 11 and Week 12

In week 11, we learnt a little about the history of algorithms involving two individuals, Alonzo Church and Alan Turing. I found it very interesting to know that they showed that some problems can't be solved by algorithms, anyone or computers. I was surprised, as I thought that computers could solve even the most complicated math or logical problems. As well, I was surprised to know that computer programming languages today can solve as many problems as the old Turing machine. This is because I know that languages and machines have become far more advanced now when compared to the past.

We also learnt the concept of halt, which is a non-computable function that takes an input and returns an output, but we don't know how. As well, a function can halt or not halt, depending on its condition. When it doesn't halt, it enters an infinite loop. The professor also taught us a function which cannot be implemented; it is called the equalizer. This is the code:

                                 def H(f, i):
                                        ''' Return True if f(i) will halt, False otherwise.'''

                                        # Once you've figured out how to implement this, delete next line
                                        return True

As seen, it looks simple but is virtually impossible.

We also learnt about reduction, which is where a program predicting whether x is initialized is written. The general statement for this is:     g computable  ===>   f computable

Furthermore, partly-working halts, other uncomputable functions, and the way to count finite sets were other concepts covered in lecture.

Infinity doesn't equal infinity: this was a very interesting concept for me to learn as I initially thought that infinity always had to equal itself. But in lecture, I was told that I had to think of it in terms of different extremely big values that are approaching infinity. For example, 2**10000 and 7**1000 are not the same and yet, they both approach infinity.

Also, the professor highlighted the concept of counting by 1-1 and onto, and how a set of natural numbers has the same size as its subset, the even natural numbers. One more interesting thing that I found was that diagonalization proved that not all sets are countable.

In our last week of classes, we learnt additional concepts ranging from Cantor's example to writing an inductive hypothesis. One concept that I found interesting this week was the principle of simple induction, where if something is a predicate of natural numbers, that is true for all natural numbers. This is so, provided that if the predicate's first value is true. This way, the truth value is passed from each value to the next. As well, when the notation is given like this:

"n Î ℕ, n ≥ k Þ P(n)

it means that P is true for all natural numbers greater than or equal to k. 

On Friday, the professor conducted another activity involving a rectangular grid with a line passing through it diagonally and shaded squares. The shaded squares were because the line passed through those squares. We had to use various techniques to try and derive the formula for this pattern. It was difficult and I didn't succeed, but I enjoyed doing it very much. This is because this allowed me a chance to apply my critical thinking skills once again in the course.

Personally, the concepts were generally moderate in terms of difficulty. This is why I asked my professor questions during lecture, and he clarified my doubts very well. This is what I intend to do in addition to rereading if I don't understand the lecture material, as it is part of seeking help from others. 

Week 9 and Week 10

These two weeks have been intensive with concepts, ranging from proving more quadratic functions to Big-Omega and Big-Theta. By far, I have seen that the course is progressively more difficult. So, I know that I will have to spend more time rereading my lecture notes and trying to understand the logic hidden in the various problems involved in mathematical reasoning.

One concept I learnt during Week 9 is that of a loop guard. A loop guard is just a step that a part of code takes to move a function along and help it execute. For example, in code, an initialization statement for a variable is a loop guard, as it is run through only once. An example of this is max = 0 or i = 0. I found the proofs about quadratic functions to be quite challenging, so I decided to include the proof for one of the functions.

7n**6 - 5n**4 + 2n**3 Î O(6n**8 - 4n**5 + n**2), it uses the O(n**2) notation to prove it.

Here is the proof:

Choose c = 9/2. Then cÎℝ+.

Choose B = 0. Then BÎℕ

Assume nÎℕ  # typical ℕ

      Then n >= B  # antecedent

             Then 7n**6 - 5n**4 + 2n**3 <= 7n**6 + 2n**3             # 5n**4 <= 0

                                                                        # add 7n**6 + 2n**3 to both sides

                      <= 7n**6 + 2n**6           # 2n**3 <= 2n**6 

                                                               # "nÎℕ

                      = 9n**6 <= 9n**8         # 9n**3 <= 9n**6 x n** 2    "nÎℕ

                         = c2n**8             # c = 9/2

                      = c(6n**8 - 4n**8)        # -4n**8 <= -4n**5

                      <= c(6n**8 - 4n**5)   <= c(6n**8 - 4n**5 + n**2)

                        # add 6n**8 - 4n**5 to both sides of 0 <= n**2

              f(n) <= c(6n**8 - 4n**5 + n**2)

       Then n >= B Þ f(n) <= c(6n**8 - 4n**5 + n**2) 

Then "nÎℕ, "                      # introduce "n                           "

Then $BÎℕ, "                  # introduce $B                               "                 

Then $cÎℝ+, "                                                                       "

------------------------------------------------------------------------------------------------------------------------

This is one of the various proofs that we were and are taught to write for quadratic functions. It is a lengthy process, and it is also confusing. It even confused me as there were so many steps that seemed like they were arbitrarily thought of and included. One of these steps was the changing the degree of a variable so that it will be higher. This is the reason why I know that rereading these proofs and understanding them is important. Furthermore, I know that something like this will appear on the exam, so this is necessary to know, not just important.

In the 10th week, we were taught about the role of logarithmic and exponential functions in proofs. We were also taught how L'Hopital's rule applied into proofs, and I find it amazing that mathematical equations such as these can be expressed through proofs. However, I find it equally frustrating that I do not understand how the proof progresses. I also wonder how quite a lot of people in my lecture session are able to understand this concept and offer the next step to the proofs' solutions. Knowing that this is the first time that we've seen these kinds of proof statements, I wonder how they understand what values to use for variables, for example, and I don't. 

Additionally, we were taught the notation for Big-Omega, Ω(g). It is almost the same as the notation for Big-Oh, except that here, f(n) >= cg(n). In Big-Oh, f(n) <= cn**2. We were also taught about the bound that was formed by combining Big-Oh and Big-Omega. This bound has the symbol Q. As usual, some proofs related to these concepts were taught to us, which looked fairly reasonable for me to understand. However, if I was given a similar question like this, I would most likely not be able to do it. This is why I am rereading my notes and trying to improve my understanding in the course material. 

So far, I have been challenged and intimidated by the course material, despite my efforts to makes sense of the material. As well, I am apprehensive of the material included on the final exam, as well as the level of difficulty of the exam.

Week 7 and 8

In these two weeks, my professor taught us more concepts related to proofs and even the concept of Big-Oh. Firstly, he showed us how to make sure that a claim is true or false before proving so. He also introduced us to some rules of inferences and how they work, some of which we had already covered in detail. These inferences are:

1. Conjunction elimination, where A Ù B, conclude A or B separately
2. Existential instantiation, where $keX, P(k), pick an element with this property, and let k'eX, P(k')
3. Disjunction elimination, where A Ú B, ØA can conclude B
4. Implication elimination, where A Þ B, A can conclude B and ØB can conclude ØA
5. Universal elimination, where "xeX, P(x), aeX can conclude P(a)
6. Implication introduction, where A Þ B 
7. Universal introduction, where "aeD, P(a)
8. Existential introduction, where $xeX, P(x)
9. Conjunction introduction, where A Ù B (if you know A and B)
10. Disjunction introduction, where A Ú B (if you know A)

Furthermore, my professor also mentioned something about sorting algorithms and speed. If I remember correctly, he mentioned that the speed does not depend on the input and hardware the algorithm is running on. He also conducted a "penny piles" activity last Friday, where we were given a situation in which a number of pennies are in either of two drawers. We had to sort them in even numbers according to which drawer they were in. This activity seemed complicated at first, but I slowly came to understand it and had fun doing it, even though I couldn't get the final answer.

Some more concepts that my professor covered in lecture was the running speed of algorithms, and that they could be measured by counting how many steps it takes to reach the output. So basically:

length of algorithms = no. of steps

My professor also showed us how to establish formulas for the number of steps taken to complete a function based on an input. The class also learnt that there are two worst cases: the upper bound and the lower bound. The upper bound means that the program will take no more than a certain number of steps to complete the program. The lower bound means that the program's worst case contains at least a certain number of steps. Upper bound is denoted by: WP e O(U), and lower bound is denoted by: WP e Ω(L). O is for oh, and Ω is for omega, U is for upper bound, and L is for lower bound. Additionally, we learnt the concept of bounding a sort so that WP e O(n to the power of 2) is proven, for example.

As mentioned before, we also learnt the concept of Big Oh of n to the power of 2. This function means that all quadratic functions are roughly the same speed and that the natural numbers are the input and non-negative real numbers are the output. Lastly, we were shown how to prove WP e O(n to the power of 2) and WP e Ω(n to the power of 2).

Overall, the concepts for the first week were relatively easy for me to understand, but the second week's concepts were substantially more challenging. I understood part of it, but if I were given another problem related to it, I would most likely not be able to solve it or write a proof for it. I know that it takes time to understand and absorb the concept of Big Oh, so this is why I am reading over my lecture notes to understand it better. Additionally, if I were to be given an expression and asked to prove it, I would have some difficulty doing so. This proves that I need to work on application of my learnt concepts. By far, this course has continued to be challenging and I know that one can't succeed without practice and hard work. To overcome this difficulty, I aim to continue to read my lecture notes over and over again, do certain lecture problems without looking, and seek help if in doubt.

Week 5 and 6

In the fifth and sixth week, my professor covered how to write proofs for various mathematical statements. This includes formatting them by logically indenting them, commenting them and concluding them with the original statement. Proofs take a lot of time to structure and write because you must consider all possible situations for where the mathematical equation is true or false. Some proofs though, are quick to prove. For example:        $xeR, x ** 3 + 3x ** 2 - 4x = 12
This is an existential, so it is not hard to prove. But you must find the right term to prove it true. This is where it sometimes gets tricky, as you may have to conduct a trial and error method before finding the right term.
So, in this, when x = 2, the existential proves to be true. This is written as:
                                    Pick x = 2. Then xeR    # well known
                                    Then x ** 3 + 3x ** 2 - 4x = 8 + 12 - 8
                                                                                = 12              # sub 2 for x
                                    Then $xeR, x ** 3 + 3x 
This is an example of how a proof is written.

My professor continued teaching us how to write more proofs after this, especially those with floor division of x (ëxû). But, he also reemphasized a limit and its graph and taught us how to write a proof based on limits.
At first, I had difficulty understanding how to write proofs, what conditions to include and how to indent them, but now I have started to understand it. Writing proofs seems simpler for me than it used to because I have learnt that you just have to follow a certain logical order by looking at the mathematical expression.

Week 4

In the fourth week, my professor delved further into the complicated aspects of logic and reasoning. By far, this course has been relatively tough for me. I am constantly introduced to new ways of understanding logic, but I struggle to understand the concept that the professor is outlining and the description in the slides. We learnt about concepts ranging from limits and their graphs to outlining proofs and finding them. One thing I struggle to do is find the difference between two seemingly identical expressions. For example, there are two expressions:     "xeS1, $yeS2, x + y = 5     &                                                                                                                   $yeS2, "xeS1, x + y = 5.
with S1 = S2 = {1, 2, 3, 4}. I could not really see the difference between these 2 expressions except for the fact that their conditions switched places.

One thing that I understood was the definition of a graph of x squared as x approaches infinity. In this case, y approaches infinity. My professor explained that y approaches infinity means that y is moving farther and farther away from zero or becoming larger than zero. He also demonstrated the concept of the graph of x squared for x more than zero. Double quantifiers was another concept that my professor explained. He said that they prove that a certain subset of the Cartesian product N X N (N squared) is not empty and has some properties, in 3 ways. I didn't fully understand this concept either as he covered the material quite quickly and I didn't know what to ask him to clarify my doubt. All I knew was that I didn't understand it. This is why I try and review my notes after class to make sense of the content. As well, I aim to further strengthen my knowledge through the help of teaching assistants and also through the detailed course notes.

I also just completed an assignment that combined whatever was taught until last week. It was very challenging, although I did try my best to understand what I wrote and checked my answers thoroughly. Right now, I am quite nervous about the results of this assignment and look forward to the upcoming material in the course.

Week 3

This week, my professor taught us some more complicated, logical concepts. I learnt about concepts all the way from expressions that restricted domains of items in two sets when they are combined together, until a concept known as De Morgan's Law. The course content is still challenging for me, but I try to understand it by rereading over the information and repeating it to myself. At the extra help sessions, I try to further clarify my doubts with teaching assistants through explanations and diagrams. It has helped me and I am confident that I will succeed in this course if I continue to attend these sessions regularly.

Other concepts that I have learnt this week are conjunction (combining two statements by claiming them as true with the word "and"), disjunction (combining two statements by claiming that at least one of them is true with the word "or"), and negation (reversing the truth values of statements using Ø). Negation involves changing a statement so that true becomes false and false becomes true. It is a very tricky concept to grasp because it involves changing certain conditions to fit the negation statement. For example, there is a statement that implies "for all x belonging to a set of real numbers, P(x) implies Q(x). The statement that says this is "xeX, P(x) -> Q(x). When this statement is negated, we get the statement "for certain x belonging to a set of real numbers, P(x) is true and Q(x) is not true". This is symbolized by $xeX, P(x) and ØQ(x). At first, I was confused at why this happened as I thought that the inverted A could not be changed to a mirror-image of E just because of a sign. However, through extra help and rereading, I was able to make sense of the concept. Furthermore, I was unaware of what the word parse meant, despite it being used several times in class. I researched its definition and I saw that it was just the breaking down of a statement into components to make sense of it.

I also learnt that Venn diagrams were necessary to represent conjunctions, disjunctions and negations in an easier and a more visual way, but there were some limits as to how many predicates or functions the Venn diagrams can represent. This is where truth tables can help. Truth tables are tables that have variables and functions as headers and T and F in the tables to signify if the eventual condition will be true or false. This was one of the concepts that I enjoyed learning the most this week as it was easy to find results of expressions using this way. Other new terms that I learnt this week are tautology (when a statement is true in all cases), satisfiable (when a statement is true in certain cases), and unsatisfiable (when a statement is false in all cases). Lastly, De Morgan's Law states that the roles of "and" and "or" are switched. For example, Ø (P or Q) <-> ØP and ØQ. At first, I couldn't understand this, but later I understood the logic by rereading it: if P or Q cannot be true, it means that both of them will be untrue.

On Friday, my professor conducted a unique activity. He told his students to take a strip of paper and keep folding it into half from the left. Each time we folded, we had to open up the folded paper and record how many times the paper folds pointed upwards or downwards. Then, we were to find some kind of logical pattern as to how the number of upward or downward folds increased. I came up with a math equation for the increment of the total number of folds for every fold leftwards. This was the most interesting and enjoyable activity for me this week as I not only learnt something, but had fun at the same time. At the moment, I am looking forward to and a little apprehensive of the upcoming course material for next week.