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)