The End

Inductive proof why I haven't been posting regularly.

P(month, day): It doesn't matter if I blog today (month, day) because I can blog tomorrow!

Base case: month, day = October, 27th. Then it makes no difference if I post that day or the day after and so P(October, 27) holds.

Induction Step: Assume m, n is in natural numbers and P(m, n). 

Then, P(m, n+1) holds until December 5th and then it does make a difference since I can't post on December 6th :(

Semester as a whole and studying for the exam

I approached this class by trying to solve problems first and only seeking lecture notes and course textbook when I was having trouble, and I think this saved me a lot of time. So I think that I will try to study like this for the final exam. Topics I need to focus on because I struggled with: unwinding, proofs of termination on recursive functions, and proving DSFAs. Resources to study off of: quizzes, tutorials, assignments, tests.

Mathematical Problem

Proving correctness and termination of a function which returns whether a tree is a binary search tree.

class Node(object):
    def __init__(self, v):
        self.v = v
        self.left = None
        self.right = None
       
def is_BST(root):
    return _is_BST(root, Integer.MIN_VALUE, Integer.MAX_VALUE)
def _is_BST(root, minim, maxim):
   
    if not root:
        return True
    else:
      if not _is_BST(root.left, minim, root.v) :
            return False
        if not _is_BST(root.left, minim, root.v) or not _is_BST(root.right, root.v, maxim):
            return False
    return True

P(n): is_BST function with a non-empty binary tree of height n returns whether it's a binary search tree

Assume n is in natural numbers, and that P(i) holds for all 0 <= i < n

Case n  = 1 :  then any tree with height 1 is clearly a BST. And P(1) holds since root.v is cannot be lower than the lowest possible integer or greater than the biggest possible integer (in Python), and if not _is_BST(root.left, minim, root.v) if statement is false since root.left and root.right are None (so they return true, and becomes not True or not True)

Case n > 1: then since left and right subtrees have height n-1, P(n-1) hold. And for the same reason as when n=1, if not _is_BST(root.left, minim, root.v) line is false. _is_BST(root.left, minim, root.v)  returns whether the left subtree is a BST, and _is_BST(root.right, root.v, maxim) returns whether the right subtree is a BST. If one of them is not a BST, then the whole function returns false as needed. Otherwise, if statement is not executed, and last line runs and returns true.

Thus, for all n in natural numbers, if P(i) for 0 <= i < n, then P(n)
Then, by complete induction, for all n in natural numbers, P(n)

Test Back

I've had the chance to do some interviews for internships and now I am glad that CSC148, CSC165 instructors taught the things they did because all the material taught were highly relevant to the technical questions I received. I am glad that I had paid attention in those classes. It makes me now want to pay more attention to CSC236.

I got my test back and did very well, but got a mark off because I didn't put induction hypothesis as a comment in the first question. I feel lucky that I put it in 2nd and 3rd question.


edit (Dec. 5th): I think I changed the date on this post but don't know how to change it back?

Quizzes and Repeated Substitution

I've been doing bad on the quizzes because it's difficult to stay on top of the material all the time.

Repeated substitution sounds complicated but I guess this just means substitute the formula until you see a pattern.

If T(n) + 2T(n/2) + n + 1

Then, T(2^k) = 2 T(2^k-1) + 2^k + 1

= 2 ( 2T(2^k-2) + 2^k-1 + 1) + 2^k + 1
= 2^2 T(2^k-2) + 2^k + 2 + 2^k + 1
.
.
.
= 2^kT(2^k-k) + k2^k + 2^k - 1
= n + n logn + n - 1
= nlogn + 2n - 1

Finished First Assignment and First Test

Reactions on first assignment. I thought that while it was significantly harder than 165 assignments, it was fair. The last question I got the answer after staring at it for 5 hours while also doing other stuff. That's a problem that I have which is that if I am stuck on a CS/math question, I am literally stuck for eternity. Fortunately, I didn't get stuck on the first test, so I finished it very fast.