Week 12 - End of CSC165 and beyond

This post marks the end of my journey through CSC165H1 at U of T.

As such, I would like to provide a wholesome reflection of the course. — In short, I believe that CSC165H1 differs from the standard offerings at U of T because it has taught me the "joy of learning and discovery".

THE GOOD SIDE:

I understand that some readers may have difficulty empathizing with me — so, let me lament.

I have mostly been blind to the beauty in mathematics. Like the general population, I would associate mathematics to be the antithesis of creativity and expression. In fact, it was ironic that school, the "sanctuary of knowledge",  had reduced my view of mathematics to the tedious, translation and manipulations of $x$ and $y$ on a test paper. As best expressed by mathematician Paul Lockhart in "A mathematician's Lament":

    "Sadly, our present system of mathematics education is precisely this kind of nightmare. In fact, if I   had to design a mechanism for the express purpose of destroying a child’s natural curiosity and love of pattern-making, I couldn’t possibly do as good a job as is currently being done— I simply wouldn’t have the imagination to come up with the kind of senseless, soul- crushing ideas that constitute contemporary mathematics education." - Paul Lockhart

I highly encourage everyone to read it here. Anyway's back to the topic:

 High-school left me with a myopic view of what mathematics represented. Taking CSC165 removed this notion  obliterated this notion: The course, instead of developing the student's already strained computational mindset, CSC165 develops the student's neglected derivation mindset, encouraging the student to derive results. 

My favourite example is the proof of infinite prime numbers, even though the proof is a logically comprehensible but complicated,  most high-schools would exclude such material from the standard maths course based on the "triviality" of the result.

High School Curriculum: Like, of course there are infinite prime numbers - it's common sense.

Me: But can you prove that?

High School Curriculum: *Tries and miserably fails*

In short, I believe high schools only pay emphasis to the usability of the mathematics involved. I liken them to steroid jocks. On the other hand CSC165 helps emulate the process using well defined logic, paying attention to the journey and flow of thought.

THE BAD SIDE:

There is not all that bad to this course, it has greatly improved my logical thinking and capacity for common sense. But I just have one complaint:

Professor Heap, for the love of god, do not use green ink to write during your lectures please.

OTHER NOTABLE SLOGS TO MENTION:

Through the course, I have out come across other SLOGS, here are some I would like to mention:

http://theperfectproofisaworkofart.blogspot.ca

http://165choi.blogspot.ca

http://99bugsbutaglitchaintone.blogspot.ca

http://kelvinxieslog.blogspot.ca

FIN 

Searching Algorithms, Part 2.

This post focuses on Week 8 content.

We can show using big-Oh that a linear search, given the worst case scenario;
when what we are searching for does not exist, is in $\mathcal{O}(n)$

I learn't that this was true using a combination of source material from my CSC108 class,
which is currently covering algorithm complexity, and the tutorial problems, which permit such a method of analyzing algorithms.

Let's us look at the code for a basic linear search:

1    def linear_search(L, value):
2        """ (list, object)-> int
3    
4        Return index for first occurrence of value in list L.
5        If value is not in L return -1.
6    
7        >>>linear_search(['a','b','c','d','c'],'c')
8        2
9        >>>linear_search([1,2,3,4,5],10)
10       -1
11       """
12   
13       for index in range(len(L)):
14           if L[index] == value:
15               return index
16       return -1

Here for an input of size $n$, the amount of steps taken will be proportional to $n$
as we can see from lines 13 of the code:

the number of loops is dependent on the length of list $L$ ( which is $n$). The complexity is independent of the code inside the loop in lines 14, 15.

So, what does it mean for Linear Search to be in $\mathcal{O}(n)$?

It just means it is really, really bad, and that we can do much better.

I personally think it was a pity that the course material did not introduce us to a substantially better
search algorithm. So hence I feel it is my responsibility to introduce to you....*drumroll*

Binary Search!

Here is the code for binary search that I wrote:

def binary_search(L, v):
    """(list, object) -> int

    Return index of first occurrence of v in L.
    If v is not in L return -1.

    Precondition: L is sorted and elements of L can be compared to v.

    >>>binary_search(['a','b','b','c','d'], 'b')
    1
    >>>binary_search([0,1,2,3,4,5],-2)
    -1
    """
    b = 0
    e = len(L) - 1
    
    while b <= e:
        m = len(L) // 2
        if L[m] < v:
            b = m + 1
        else:
            e = m - 1

    if b == len(L) or L[b] != v:
        return -1
    else:
        return b

Binary Search is a search algorithm that finds the specified index of a value within a sorted array
only. In effect it is like trying to find the meaning of a word in a dictionary or a description of an object in an encyclopedia.

The precondition of being sorted creates a distinct advantage that increases the speed of the search.

Let me give an example:

Imagine if you have to search a phonebook of 1,000,000 (one million) entries for the name:
"Sooham Rafiz". Since the phonebook is alphabetically arranged, you know that all the names beginning with "S" will be towards the end.

...you bisect the phonebook and see names beginning with "M",
so here 1 step has allowed us to eliminate 500,000 entries.

...you bisect again to reach "R" names, we have eliminated 250,000 entries with the
2nd step!

This is in contrast to Linear Search where 1 step eliminated 1 entry.

Hence Binary Search, by common sense is: $\mathcal{O}(log_{2}(n))$

Searching algorithms Part 1.

This is the entry for Week 7 and Week 8.

This week t'was a good week, because I finally saw some beautiful code on my lecture slide.

My eyes teared up when I finally saw this piece of beautiful code.

The code above shows a linear search algorithm.  But what is Linear Search anyway?

Let me explain in layman's terms:

Imagine that you have a stack of cards and you want to find a card with a certain rank, for example "Jack", how would you implement that method of search?

Say, you also have gun to your head so that you would search fas.. yeah
I believe I'm overthinking this hypothetical scenario.

How would you do it?

Answer: (Most probably) go through each card one-by-one searching for a Jack.

Me: Hooray! You can do Linear Search!

Linear Search is the most obvious search algorithm: going through a list or array one element at a time, in order. It isn't terribly efficient either...

Given that the course has finally covered enough logical material to cover an algorithm, we have also covered enough material to develop a tool to analyze the algorithm.
That tool is called big-Oh

Big-Oh effectively catalogues functions by their rate of growth.
I personally though such a concept is effective, as it allows us to distinguish functions of different growth rates.

Consider the functions:

$2n^2$, $12n^2 + 100$, $10^6n^2 + 10^{6^6}$

despite the large variance in the coefficients of the functions above, we can prove that
there is a certain point of $n$ beyond which a multiple of the function $n^2$ will out-grow all the functions above.

Hence we say these functions are in $\mathcal{O}(n^2)$

In mathematical presentation $\mathcal{O}(n^2)$ is represented as:

$\mathcal{O}(n^2) = \{f:\mathbb{N}\Rightarrow \mathbb{R}^{\geq 0} | \exists c \in \mathbb{R^+}, \exists B \in \mathbb{N}, \forall n \in \mathbb{N}, n\geq B \Rightarrow f(n) \leq cn^2 \}$

Phew! A lot of notation.

Initially, I found the idea of big-Oh to be absurd, as I found it hard to swallow the fact that even extremely small coefficient quadratic equations and extremely

large coefficient quadratics fit in the

same big Oh, surely $1000000000x^2$ grows faster than $x^2$?

I will talk more about big-Oh in the next post...

floor takes on a new meaning

Week 6

This week we were introduced to a new class of functions, the non-boolean functions.
These are special functions like, for example $sin(x)$, which take an input and give an integer a
real output. This differs from all other functions, which are predicates, returning only True or False.

I felt really excited about how we could incorporate these functions with
our "tool-box of instruments",  to put metaphorically, implications, quantifiers, conjunctions
and disjunctions, to prove a greater range of statements.

The first, arguably special non-boolean function we were introduced to was "floor".

NO! Not that one!

The "floor" function ($\lfloor x \rfloor$)is defined as:

$\lfloor x\rfloor\in\mathbb{Z}\wedge\lfloor x\rfloor\leq x\wedge(\forall z\in\mathbb{Z}, z \leq x \Rightarrow z \leq \lfloor x \rfloor)$

It's simply just taking the largest integer for any real number.

I found that I grasped the concept of floor quickly, as I did a high school research project on the function and it's intrinsic properties. I could say that I enjoyed learning about this function!

I also believe that disproofs also deserve a mention this week, as we have not learn't much about the
formal way of disproving statements. Turns out it is just proving the negation.

Now, I should start work on assignment 2...

A war between proof and intuition - Week 5

Our week 5 material was on proofs and how to rigorously prove
mathematical statements. One example we have seen in class was the direct proof.
Which I personally though was the easiest form of proof.

For example let's try to prove the fact that:
$\forall n\in\mathbb{N}, n \text{ is odd} \Rightarrow n^2$ is odd.

Proof:
Assume $n\in\mathbb{N}$ # $n$ is a typical natural number
    Assume $\exists i \in \mathbb{N}, n = 2i + 1$ # definition of odd.
        Then $n^2 = (2i + 1)^2$  # square both sides
                        $= 2i^2 + 4i + 1$ # Simplify
                 $n^2 = 2(i^2 + 2i) + 1$
        Then $\exists j \in\mathbb{N}, n^2 = 2j + 1$ # $j = i^2 = 2i \in \mathbb{N}$
        Then $n^2$ is odd
        Then $n$ is odd $\Rightarrow$ $n^2$ is ood # implication intro.
Then $\forall n\in\mathbb{N}, n \text{ is odd} \Rightarrow n^2$ is odd.

These are the simplest of proofs. I found the other variations of proofs to be Much harder.
For example I personally struggled with more abstract proofs, like PROOF BY CASES.
Until I finally had to ask for assistance during my professor's office hours.

I also found that preparation for this week's midterm, which went well, also helped in grasping
basic proof structures.

Hopefully practice will resolve the difficulty posed by advanced proofs.
{I'm looking at you proof of infinite primes!}

Comprehending set comprehensions

I was reviewing course material from week 1 to week 4 in order to prepare for my midterm exam.I found the majority of the content on the slides, like the quantifiers, proof structures and predicates
to be easy in nature. I kept on flipping the slides - page by page - until I stopped.

Something weird and alien had caught my eye. I read it again:

for all, one...one for allwhat is the difference between the two claims:

$\forall x \in S1, \exists y \in S2, x + y =  5$
$\exists y \in S2, \forall c \in S1, x + y = 5$

 S1 = S2 = {1, 2, 3, 4}
def forall_exists(S1, S2):    # code snippet 1
    return all(any({x + y == 5 for y in S2}) for x in S1)
def exists_forall(S1, S2):    # code snippet 2
    return any(all({x + y == 5 for y in S2}) for x in S1) 

if __name__ == '__main__':
    print(forall_exists(S1, S2))
    print(exists_forall(S1, S2))

This was from week 4 lecture slides, it was in  week 1 too!
I knew that code snippet 1 was the same as $\forall x \in S1, \exists y \in S2, x + y =  5$
and vice versa ... but I did not know why. I was thoroughly confused...

An accurate portrayal of my reaction when I saw my first set comprehension

CSC108 did not teach me this! So in order to resolve my confusion for the approaching midterm, I had two options. 1) Blindly agree to the facts 2) conduct my own research into the subject (albeit at the cost of time).

I chose the latter, because I was curious. *Opens Google*

Ohhhhhh. That was easier than I thought.

Quick research showed that I was looking at a concept called  "set comprehensions". It can
be used to construct lists in a very natural and easy way, similar to list construction in mathematics.

In maths we write sets as:

$S = \{x^2 : x \in \{0,1,2,3,4,5\}\}$

$V = \{1,2,4, \ldots, 2^{13}\}$

$M = \{x :  x \in S \wedge x = 0 (mod 2) \}$

In python this is the same as:

S = {x**2 for x in range(6)}

V = {2**i for i in range(14)}

M = {x for x in S if x % 2 == 0}

The issue here is that the syntax is quite still quite cryptic, but the output of the mathematical set and
pythonic code will still be the same.

Lets see something simple: Here is code that squares a set of numbers:

squares = set()

for x in range(10):

    squares.add(x ** 2)

This will return the set:  {0,1,4,9,16,25,36,49,64,81}

Well, we obtain the same result with the comprehension: 
square = {x ** 2 for x in range(10)}

Here comprehension iterates over the elements $e$ in  range(10) and returns $e$ ** 2 ($e^2$) for every element.

Now that seems much simpler!

Here I explain some more examples from Week 1:

1. S2 = {x + 2 for x in S}

• The comprehension iterates over every element x in S and makes a list S2 where every element is x + 2.

2. S3 = {x for x in S if x < 3}

• We can even add predicates when making new sets!This comprehension iterates over every element x in S and adds x to S3 if x < 3 is True.

3. S4 = {x ** 2 for x in S if x > 3}

• This is the combination of both 1) and 2). Here we add element $x^2$ to set S4 if element x satisfies the predicate x > 3!

I felt that the research into the topic has allowed me to understand set comprehension deeper than before. Now I am truly ready for the midterm!

logic and paper == brain with paper cuts!

During week 3 of CSC165, we were given a deceptively simple problem to tackle and solve. The problem given to us was...

Take a strip of paper and stretch it so that you have one end between your left thumb and index finger and the other between your right thumb and forefinger. Fold the strip so that the left end is on top of the right end. Repeat this several times, each time folding so that the left end is on top of the right end of the strip. 

When you're done, keep holding the right end and unfold the entire strip. Some of the creases point vertex up, some down. Can you predict the sequence of ups and downs for any number of times you carry out the folding operation? 

Being the recorder (the man who wrote down on all thought, hypotheses and predictions about the problem), I am in a good position to apply G. Polya's problem solving approach to this problem.
Hence, this post will follow a specific structure:

1. I will understand the problem.
2. I will devise a plan.
3. I will carry out the plan.
4. Look back and reflect.
5. Acknowledge when and how I am stuck. 

Let's begin!

Needing some material to work on and evaluate my results, I made the first step of my plan to be:

play and fold the paper.

The other steps of my plan are the following.

1. Play and fold the paper, observe the patterns of the folds.
2. Understand how the variable, number of folds effects the patterns
3. Make a table of the number of folds vs. the pattern generated.
4. Using the observable pattern, try and predict the sequence of folds.

Here is a video of me, folding the paper:

I was only able to fold the paper four times as the paper got thicker and harder to work with...

Nonetheless, I got substantial data.

Num. folds	pattern	pictogram
1	D	$\vee$
2	UDD	$\wedge\vee\vee$
3	UUDDUDD	$\wedge\wedge\vee\vee\wedge\vee\vee$
4	DDUDDUUDDDUUDUU	$\vee\vee\wedge\vee\vee\wedge\wedge\vee\vee\vee\wedge\wedge\vee\wedge\wedge$
5	...	...

Here a 'D' represents a down fold, like a $\vee$ and a 'U' represents an up fold, like a $\wedge$.

I found it very hard to understand the pattern at first, but as I kept searching for any repetition, inverses in the sequence, I realised 3 things.

1.  The pattern builds around a central D, (highlighted in red)
2. Every extra fold adds $2^{n}$ folds, where $n$ is the initial number of folds in the paper.
3. The pattern reverses and inverses around the central D.

Using these properties, I could predict the next sequence! This can be done by adding a sequence of D's and U's in between the already existing sequence.

Confusing? Well, yes. But it is best shown by the illustration below:

Every new sequence just builds on another sequence, like a tree

I am so happy to have cracked this out...

Week 1 and 2 - logic of quantifiers!

I am currently behind on SLOG posts by a week; It is best to rid of this gap before it gets too large. Here are my reflections on the first and second week of the course.

Thus far, I have personally found the course to be tough. I was never taught highly abstract concepts relating to mathematical logic, like quantifiers ($\forall, \exists$), I only knew how to crunch through numbers and equations. 

Sadly, "crunching" through logical claims like:
\[\forall x \in \mathbb {R},\forall y \in \mathbb{R}, x < y \Rightarrow (\exists z \in \mathbb{R}, x < z < y)\]
isn't helpful: Logic needs thought rather than mindless computation.

To increase my comfort with quantifiers, I must first analyse their properties:

Let's take an example and analyze:

1. \[\forall x \in \mathbb{Z}, \exists y \in \mathbb{Z} x < y\]
2. \[\exists x \in \mathbb{Z}, \forall y \in \mathbb{Z} x < y\]

These statements look similar -  the orders of the quantifiers is just switched! These seemed similar to me at first too, but to my shock I discovered that they have very different meanings...

Let's convert them to english:

$(1)$ means that 'for any integer x there is an integer y that will be greater than x'. We can even further simplify this to 'for every integer there is a integer greater than itself'.

This is a True statement (it would be true...unless we broke math)

$(2)$ says ''there is an integer which is greater than all other integers". This is always False.

See the big difference I was talking about? :D

But how did we arrive at the conclusion that (1) is True and (2) is False?

Well, as I learnt from my 165 lectures, to prove a universal ($\forall$) statement True, we need to show that all elements that obey the statement are True. So, if we set $y$ in $(1)$ to $y = x + 1$, (1) will always be True. Conversely, to prove ($\forall$) statement False, we need to show just one counter example.

Existential ($\exists$) statements are different, to prove one True, we just need to show just one example that obeys the statement. It's like saying "There are stars in the sky" -  you just need one star in the sky to make this true. To prove an $\exists$ False, we need to see that all elements in set don't follow the rule. This would happen if there were 'no stars in the sky'.

Here is a table to compare the quantifiers:

Quantifier	True	False
$\forall$	Show all elements are examples	Show one counter example
$\exists$	Show one example in set	Show all elements are counterexamples

And I'm done for the day!

Sooham Rafiz

On my expectations from this SLOG.

 Dear reader,

Welcome to my course log! This is a webpage where I respond to CSC165 course material.

In my first blog post, I aim to convey my personal expectations for this blog. This will not only
set the tone and guidelines for (many!) other posts to follow, but also will serve as a purposeful indicator showing how the blog has evolved throughout the course.

So, what should you expect from this blog?

1.  I will use this blog to convey my personal, subjective feelings on the topics we cover in
     CSC165 in a appropriate manner. I should write about my feelings in a way that is helpful
     and offers advice to other in the same situation.
         
    For example I could discuss why I find mathematical logic to be hard due to my interest in
    the humanities and evaluate the discrepancies / parallels which others can know about and
    how to deal with such discrepancies.

2. I also aim to analyse and critique the course topics or discussions and provide my own objective
   thoughts as a scientist on the matter.

   This type of writing is beneficial to my self-growth because I will have to question my own
   thoughts and opinions; Eventually, I will remove my own doubts and invalid assumptions on a
   topic, turning me into a better scientist.

The two points above are not fixed, they are open to amend as my understanding of the course increases.