#12 More about countable

In the last week's class, we learned more about countability and induction. We talked about the definition as countable for a set of number- basically iff it is listable (which means it can be described as a list for each item in its own position).
There is also a new concept called diagonalization. By using this concept, we can prove that the rational numbers are countable.e.g. The set of infinite number of floats in [0,1] can be put in a large list. Cantor was already proved that at least one number was missed when listing all numbers between 0 and 1, since the increment is keep decresing.
When using diagonalization proof, we add 1 to the tenth digit when digit is less than or equal to 5, minus 1 to the the tenth digit when digit is bigger than 5.And do the same thing to 100th digit and so on.After all, there will be a diagonal line in the matrix of digits.And a new number is created by this step.

#11 Halting Problem

This week we were taught about halting problem. Honestly saying I still find it is hard to tell what exactly it is. Yet there is a question about proving some function is not computable in Assignment 3. I went through the given proof in course note. Here is the question below.
Claim : the function meaning_of_life is non-computable.
Proof by reduction:

For a contradiction, assume that meaning_of_life is computable,i.e. It can be implemented as a python function. So, implement halt(f, n) using meaning_of_life(f, I),

def halt(g, i):

     def meaning_of_life(f, I):

         ...code for meaning_of_life goes here...

     def g_prime(x):

         g(i)

         return 42

return meaning_of_life(g_prime, i)

If g(i) halts, then g_prime(i) will execute the statement return 42, so meaning_of_life(g_prime, i) returns True, so halt(g, i) returns True.

If g(i) does not halt, then g_prime(i) will not execute the statement return 42(no matter what value x has), then meaning_of_life(g_prime, i) returns False, then halt(g, i) returns False.

But there is no python implementation of function halt.

Hence, there is no python implementation of function meaning_of_life.

It just use the property of halting problem(it has no result)

#10 More about Big-Omega

The statement of big-omega is shown below:
∃c ϵ ℝ+ ∃B ϵ ℕ, ∀n ϵ ℕ, n ≥B ⇒ f(n) ≥ cn2 

This is basically the same statement as the big-oh nontaion, except the less than or equal is replaced by bigger than or equal to.

So the cn^2 is the greatest lower bound of the function, it is closest to the running time under best case.

And the proof method is as same as the big-oh, which is using the proof structure.

#9 More about Big-oh

In last week's slog I was given the basic concept of big-oh, this week I got the deeper understanding anout it.

Danny taught us the concept of big-oh notations is f(n) is in O(n^2) iff

                            ∃c ϵ ℝ+ ∃B ϵ ℕ, ∀n ϵ ℕ, n ≥B ⇒ f(n) ≤ cn^2. 

f(n) can be seen as the biggest running time for the worst case of the function.This has to be less than or equal to the bound.

And the rest is same as before, using the proof structure :

Pick c = ________. Then c ϵ ℝ+ #intro- ∃

Pick B = ________. Then Bϵℕ #intro- ∃

Assume n ϵ ℕ #intro-∀

                 Assume n ≥B #antecedent

                #proof body 

                 Then n ≥B ⇒ f(n) ≥ cn2 #intro-⇒

Then ∀n ϵ ℕ, n ≥B ⇒ f(n) ≥ cn2 #intro-∀

Then ∃c ϵ ℝ+ ∃B ϵ ℕ, ∀n ϵ ℕ, n ≥B ⇒ f(n) ≥ cn2 #intro-∃

Now the basic way of solving big-oh Problem is shown.

#8 Midterm test 2 Big-Oh, Big-Omega

Finished the second midterm in this week, and I got 100%,Hureh!
Instead of proof again, new material was introduced this week, that is called big-oh.
Since I've already taken the course CSC148, this is not the first time hearing about this concept.
But I still found it hard when comes to the counting steps part.
Tracing recursive functions i.e. counting-steps is easist under worst-case, which was the mainly case we focus on. Sometimes I couldn't get straight out the counting time under n variables, so I just start from n = 1, then count at n = 2, and then using the induction to get when n is a variable.
 Danny describes the big-oh as the 'turkey size' and the function is the 'chicken size'. Cause the biggest chicken is smaller than the turkey, so big-oh is a special way to describe the upper bound of a function. In contrast, the big-omega is the way to describe the lower bound.

#7 More Proofs

After this week, the learning of proof techniques will almost comes to an end. So I think now is the proper time to sum up main techniques of proofing.

Direct proof : the most common way to carry out a proof,one conclusion followed by another one,just like chains connects together. Straight forward.

Equivalent proof: use contrapositive to prove the original statement. From the truth table, statement and its contrapositive statement hold the same status, i.e. Statement A is true iff contrapositive of A is true.

Proof of existence: useful under disproving the for all... statement or proving the exist statement. Just to find one example.

Proof by contradiction:contains assumption, disprove a statement by proving its negation is true.In personal view, this is the most effective way of proof we've learnt so far. Especially when cannot figuring out whether the statement is true or not.

Proof by cases:divide the antecedent into several parts(all are true) and proof the consequence for each condition. It take times to divide the antecedent.

Most of the times one problem can be solved in multiple ways, if I were writing the proof during exam, I would consider direct proof at first.Then proof by contradiction.

#6 Idea of Proof Sturctures

This week Danny introduced us about the proper proof structures.Danny described the logical/math problems as 'the enemy', and proof structure is the most efficient way to 'defeat' them.
We also attached delta-epsilon proofs, I was not unfamiliar with this theorem since I've seen it from my calculus classes.Yet I never thought a proof can be written as logical sentences,like
assume.....
      let......
          then......
      then exist.......
then for all..... exist......
This kind of structure helps a lot to clarify my thoughts while solving problems, not only in CSC165, but also in math classes as well. And the structure can be used for all mix quantifier problems(for all, there exist....).This means the range of its application could be really wild.
While learning how to write the proof, I didn't find writing the structure hard. It is just a tool to be used, to sort out the steps of proof, yet the real hardest part is still the 'then.....' part. It depends on the problem and usually contains math statements. Will we be given hints during the final exam?

#5 Midterm, Proof by contradiction

In this week of study, we've learnt how to disprove statements.
Disprove means to prove that something is False.In class, Danny introduced mainly on contradition, which is also known as indirect proof. That means assume the statement is True, then find the point which makes contradictions, then the statement is False.
However, the first midterm test was mainly on former contents, honestly the exam is not hard, but, still I made some mistakes due to over nervous, I finished it so quickly that I lost the first part of the question 1.What a shame.

#4 Proof outline example

                 When finishing assignment 2, we were requested to write in a proper proof outline, here is an example.
                 to prove

by using the definition of floor(x):

the proof structure is shown below:

It's just a example about straight prove.

#3 Conjunction and Disjunction

In this week's class, we've learned about two new quantifiers, conjunction  and disjunction .

Conjunction and disjunction follow certain rules. Like commutative, associative and distributive laws.
Commutative law:A ∧ B  B ∧ A   A ∨ B  B ∨ A
De Morgan's Law:

#2 Verify/Falsify the implication

Slog can not show certain special symbols,so I used print screen.

CSC165 SLOG #1 Starting point

                   Starting points!
                   We all know that computer science relies strongly on mathematics, and csc165 is a course to teach us about mathematics expression. So in first week, Prof.Heap just taught us about mathematics quantifiers. Such as:
                    means for all(each),e.g.x,x is real. It means all x are real.
                   One of the biggest advantages of using mathematics quantifiers is that it avoids ambiguity which appears often in normal English expression. Like the sentence below:
                   Iraqi heads seeks arms.
                   It has two meanings , one is leader of Iraq seeks weapon, another is head of Iraqi seeks people to help.
                  To use quantifiers leads to precision in contrast.

Sorting and Efficiency

    In week 9, lectrues were about sorting algorithm. In lab 10 , different sorting method run for sorting already sorted list, random list and sorted but reversed list.
    The method includes: selection sort, insertion sort, bubble sort, merge sort, quick sort and bulit_in sort.
    After running sort.py, the result for speed of each sort was clear to be seem from time they used. Built_in sort, which is also called tim_sort, is the fastest. Contradictory, three former sorts that learnt from csc108 are slowest.
    By viewing the code, three slowest sorts have common strategies, they go over the list during each single element sorting. It obviously decreases the speed of finishing sorting the whole list. However, some other sorts use some method like cut the list into two parts and sort in just one part, after all the times of sorting will only be lgn, where n is the length of list.
    There is also a way to improve the efficiency of tranditional sorting method like selection sorts or bubble sorts. It is adding a swap step between sorting each element.
    Still, I don't know the principle of bulit_in sort algorithm.

Binary Search Trees

    After LLNode and LinkedList, professor taught us a new class which was rooted at binary tree.It is called BTNode.
    BTNode contains three parts: an object which is the root of BST, and left, a BST, right , also a BST.For BTNode, if it only has numbers, the sorting step will be much easier. As the left tree only contains smaller number whereas right tree only contains larger number.

Class LLNode

    We already learnt LinkedList, object LLNode represents a node in LinkedList, it also contains an object named item and a following LLNode.
    At first I could not find the difference between LinkedList and LLNode. In my point of view, these two object have the same structure, an object linked with an inner itself. So why we should use two different classes to respresent the same chain of objects?

Linked List

     For last week, we've learnt a class called Linked List. Different from list, LinkedList is divided into two parts, an object called item and link which is also a LinkedList. As result, normal method like insert() or len() cannot be used on LinkedList. But in LinkedList class, we can design functions to help get the length of LinkedList or insert item into the LinkedList.
     Still, even I know the structure of LinkedList and how to write parts of the functions, I still struggle in why we have to use this class rather than list class.

Recursion

   In past few weeks' study ,we've learnt that the conception of the recursion,as I wrote before,ttp://tmaftbbwaatmm.blogspot.ca/2014/02/first-impression-about-recursion.html the first impression about recursion.
   However, when we learnt how to express recursion by trees, which was more obvious and more complicate than list expression, I found that the my first impression was not so accurate.
   For list impression, recursion is like to repeat the same operation from biggest to smaller unit.It looks like a linear structure,starts from a known point and ends at a fixed destination where there is no smaller unit to run.Writing list recursion might be efficient to avoid duplicate code. But for some common and easy cases, I couldn't see apparent advantages to use the recursion expression.
  When it comes to the trees structure, the superiority of recursion grows clearly.A typical binary tree structure is made up by nodes.Top of the tree is called root and others are called branches.The group of branch nodes with the same reference is called the leaf. By expressing in this way, we can adjust only a leaf of the tree or the root of the tree.I think, which is opposite from the lists, trees starts from the same root by ends at the different endpoints. That leads many different paths while running a program. Still, the operations keeps going to the smaller levels, that's the foundation of recursion. But there is no doubt that the tree structure fits the complexes better.

Assignment 1- TOAHModel

    For week 6,I was busy with programming assignment 1.
    It was being divided into 3 parts, TOAHModel.py, ConsoleController.py and Tour.py. In my understanding,  TOAHModel was to build all the classes that we needed in this assignment. It included cheese class, TOAHModel class and MoveSequence class. Cheese class is to make to basic object in the TOAHModel. TOAHModel is to design model of stools to move cheeses.MoveSequence is to record and adjust the moves while moving cheeses.
   This kind of design inspired me to split the program from their different goal.

First Impression about Recursion

    In the week,I mean week#4, we formally started learning recursion. 
    Defined by the Python 3 document, Recursion means defined something in terms of itself(usually in smaller scale) to achieve objective in multiple times.

It is like the picture showing below.

Showing from the picture,the recursion is like a chain of endless order.In class,first of all,we dealt with the simple list,then nested list. Those nested list gave me the first impression of recursion,which is its high efficiency and concision.For only one line of code all items in nested list can be sorted.And amazingly, fit in every kind of item.

But I still haven't written my own recursion code yet,I think I have to rigorous about determining where is the recursive part.It could be like for loop or while loop,I guess.

Object-oriented programming

    Compare with Structure programming,Object_oriented programming(OOP) is mainly focus on building new object and using object features.
    For past two weeks, we were learning how to design new class to solve given problem.Like,build "Stack" object to pop or check if a stack is empty.If not consider the OOP,we can do the same operation by write functions,but these function can only be used in single document.By build class(object),we can apply operations about "Stack" into any functions if we want,that is initial advance of OOP.
    Before learning object_oriented programming,I used to prefer design functions step by step.It can run correctly.However,when I met a similar but not all-the-same problem,I had to rewrite my function even it only needed slightly adjustments.Now,by building classes,a KIND of problem can be sorted into same condition.This method of programming improves the efficiency cause it avoid duplicate.
    Design a new class is like infusing certain characteristics into the processing object.And analysing the description of our assignment is the procedure to extract the function aim,like what purpose does this function design for?From this prospective,the aim and consequence of function should correspond to the characteristics of object.Unfortunately, I find it hard to link the problem that I try to solve to certain objects that might help.In other words, I cannot make clear the steps I need.To get through this difficulty,I change the direction of thinking. I always think from prerequisites to results.Now I think in reverse inference,which means I start from result,deduce back until it fits the given conditions.Also,I draw flow diagrams.It clarifies the logic between each step and list out all possibilities I need to consider.

Where should I place contracts EXACTLY?

From CSC108 class we've learned,by following function design recipe, the contract should be place like below:
def  whatever(a,b):
       '''(int, int) -> int
       '''
It runs smoothly and shows no error in WingIDE.

But for CSC148 class, the example is like:

always shows syntaxerror.

However, the contract error does not affect running body of the function.But it's still indicates error in WingIDE.

Why.

For CSC148

Using this blog to record learing CSC148 for this semester.