Week 12 : Tackling Assignment 3 + More about computability

In the end of the semester, this assignment helps me to summarize the concepts of how to apply limit techniques and familiar about asymptotic proofs. This is the first time I found that Piazza so helpful, since people always ask the questions about something I'm confused as well. I like the atmosphere of discussing same topic through computers.:)
Anyways, I feel I know better about limits technique during proving, rather than just memorize the definitions and try to squeeze them out. Well, the metaphor is bizarre but you know what I mean...Now I'm more familiar with the usage, or the whole idea of proving a big-Oh, a big-Omega and a big-Theta. However, I'm still little confused about halting problems. While doing the assignment, I did not understand how reductions help prove whether a function is un-computable or not. Luckily, there was some guy sharing his confusion about halting problems on Piazza. The part of Larry's answer helped:

These sentences really helped to clarify my thoughts.:) Now I feel that my thoughts become more "logical" while proving.

This final week we only introduced two new concepts: countability and induction. Since I took linear algebra last semester, the concepts of mapping, one-to-one and onto are no strangers to me.

Here is an example of proving |X|=|Y| where X={natural numbers}and Y={even natural numbers}.
The key of tacking that would be showing f is well-defined, 1-1, onto step by step.
(Remember to check indention)


However, the Truth-Table of showing fx() cannot be programmed confused me a great deal.I'm plannig to go to the office hour.


Also, I learnt induction while doing math proofs on Calculus class. The main structure is to first assume a base case and then start the inductive steps(n => n+1).

Additionally, I really appreciate "Review for final" part Larry summarized for us.It tells us that which parts of course materials are more likely to be tested, like a list high-lighting all the important concepts of the course.

Last, I thanked Yahui and Timothy by commenting on their last post. http://timothylock.me/sLOG/2014/11/30/week-11-halting/#comment-8

http://yahuiliuslog165.blogspot.ca/2014/12/week-12.html?showComment=1417621909149#c5547709964358051958

While browsing their Week 12 slogs, I found there were other students commenting "Thanks" as well, so my sense of picking slogs is seemingly pretty good~

Well, finally the semester ended. I would say I really enjoyed this course and loved the creative teaching style of my instructor, Prof Larry Zhang. Definitely, I would recommend csc165 to my friends. Now it's time to say: good luck to the final!

week 10: Term Test 2 Results Out! + finishing asymptotic proofs

This week we wrapped up the proofs for big-Oh and big-Omega statements and started the new chapter about computability. Larry introduced the final kind of statements: general big-Oh statements.

①tips for picking c and B for general big-Oh statements:

1. if the antecedent contains one big-Oh/Omega:

   for instance:

   pick B' = B

   get the appropriate c' = 1/c by computing f(n) ≤ c * g(n) and g(n) ≥ c' * f(n)

2. if the antecedent contains two big-Oh/Omega:

   for instance:

   pick B" = max(B, B')

   get the magic c" = c + c' by computing f ≤ ch， g ≤ c'h， and f+g ≤ c"h


②introduction of computability:
Some questions that look easy for computer to solve are actually non-computable, like halt. I'm taking csc108 so I know some about python, but stuff here is more about logic(e.g. REDUCTIONS, write halt(f,I) by using a helper function) rather than coding.

First let's define the terminology based my own understanding:
well-defined: every x has a corresponding f(x)
computable: there is a way we can get f(x) by x

Knowing that this is a logic course, we are more focusing on using functions for proofs. The main question for this part is：given any function, decide whether it is computable or not by using reductions as I mentioned above.

After reading the course notes, I finally generated a clear plan on how to prove a function non-computable:

Step 1： assume the function is computable, in order to derive a contradiction, which in the case given during lecture, is to derive "halt is computable"

Step 2： find a way to compute halt use a helper function:
what we want is: If halt(f,i)halts, then the helper function makes halt returns True. Vice versa

This time the average is around 72%, which is lower then last time but still pretty good. However, my grade surpassed the average by more than 10%. It seems to be a improvement to me, maybe because I'm better at proofs. Overall, the result is a cheer-up to me!

Week 9: exercises of proving Big-Oh (using limit techniques)

This week is all about big-Oh proofs.

I like the graphic expression. In the picture on the left, point B is indicated as a break point, beyond which f(n) is upper-bounded by cn^2.

Note: remember noting that O（n^2）belongs to a set of functions

functions that take in natural numbers and return non-negative real numbers

For exercising, I want to pick the more complicated one from examples taught in class to analyze:

To prove

①negate

 then we have

②prove the negation 

③the hardest part: picking a wise n

Since we want both n≥3c and n≥B, we need more than "pick n=max(3c,B)". Instead, we pick n = max(floor of 3c, B)+ 1 because the value of floor of 3c is either 3c or (3c -1)by the definition of floor. Then (floor of 3c) +1 must ≥ 3c. 

④brainstorm finished. Now we only need to follow the proof structure write down the thoughts step by step, watching out indention errors. 

tips of using limits techniques to disprove big-Oh：

By proving limit, we can obtain either 2^n / n^2 ＞ c or 2^n / n^2 ＜ c depending on the value of the limit：

Then we can use the result to disprove big-Oh, since its result is f(n)≤c*g(n).

Week 8: big-Oh and big-Omega + worst cases analyses + problem solving

From 8th week I've started to find proofs are more and more interesting through lectures and the assignment.  Each step is there preparing for the next step. The lectures of 2 weeks were focused on proofs about big-Oh and big-Omega and a little algorithm(insertion sort and maximum slices).


Tips for piking c and B while proving big-Oh:
1. c should be larger than the coefficient of the highest n term
2. assume n = 1, then pick c = the value of the function
3. doing "forward"and "backward" strategies learned from tutorials to find appropriate c



Steps for proving some non-polynomial function f(n)not in big-Oh(g(n)):
1. prove f(n)/g(n) diverges (use limit)
2. translate the limit into its definition
3. pick a wise n which bigger than n' and B
4. start writing the structure of the proof



Tips for maximum slice based on the example taught in lecture:
1. for worst case, Wms(n) is in O(n^3):
   for every loop:
   largest number of steps = n*(the number of steps contains in the loop) + 1

2. for lower-bound case, Wms(n) is in big-Omega(n^3):
   smallest number of steps = (n/3)^(the number of loops)

Encountered Problem: design a max_sum runs on O(n)...I still can not work that one out, the function I wrote on Python always returned a number slightly different from the number should be returned.



Summary for insertion sorting:

Step 1.derive the exact format of Wis(n)
for worst case
  n-1= number fo iterations  "3"is the number of steps in the inner loop
 "5"is the number of other steps in the function other than the inner loop

each iteration has （3i + 1）+ 5 to execute

Step 2. then determine it's whether upper-bounds or lower-bounds

As more variables come up, we are more confused, like Timothy's title of week8: "Confusion Grows As Complexity Grows". By following his slog, I found another slog worth of reading and following: http://yahuiliuslog165.blogspot.ca/
Every week she analyzes one or two questions in her slog. Unlike Timothy, she likes writing more about problem-solving, which is rather helpful once I kind of grasp the concepts. :)

Week 7: Reviewing Proofs + algorithm running time+ asymptotic notation

This week, I have started doing some general proofs from the practice questions, finally figured out how to conclude the ideas I've got about proofs so far.

After doing couple proof questions, there are some "tricks"  have been generated:

- the structure helps and matters!
Always start from constructing a general structure (how are you gonna prove, what methods would you use,...)before actually doing the proof.

- consider using NEGATION INTRODUCTION when you know that there is an exception
- pick a reasonable number when seeing existential quantifier
- ...



reviewed in lectures:

- split by cases
- negation introduction
- conjunction introduction
- disjunction introduction
- implication introduction (direct/ contrapositive)
- equivalence introduction

Speaking of algorithms, Larry introduced two sorting algorithm: bubble sort and merge sort. With larger input, the advantage of merge over bubble becomes larger. One important concept is that the running time is not actually the time, it's the number of steps to execute the algorithm. However, I did not understand how Larry applied the concept of running time to the big-Oh during lecture until I checked Timothy's slog. I like the way he applies the course content to real-life experiments(e.g.running sorting code on his potato and toaster):
http://timothylock.me/sLOG/2014/10/25/week-7-consulting-the-sorting-hat/

My listening of English is not good, so I did not catch all the explanations. Therefore, Timothy's slog is a saver to me because he is good at understanding the materials and converting the materials into his words. I've seen some other slogs online, none of them explains as clearly and interestingly as he does.

Week 6: The Result of Exam is Out! + More Proofs(Floor, disprove, limits, etc.)

Today, we got the results of term test. I must say it was a shock, since the average was so high, which is about 81%. Disappointingly, I was below the average due to the marks lost on the second question as I mentioned in Week5 post. After reviewing the Lecture 4, I figured out a way to tackle this kind of question. Let's use the example taught in class:

1.understand the problem
  -translate the statement into English
"there is a real numberδ,for all real numberε, if every real number greater than δ, then its square must be greater than the all ε"
2.devising a plan
  -try to find a counter-example
  -if there is one then the statement is wrong
3.carrying out the plan
   -pick a wise number, in this case, we say x = 2δ
4.looking back
   -read the English sentence, see if it's translated correctly
   -submit the wise number in see if it really fails the statement to be true
   Since when ε= 5δ^2, x^2 is smaller than ε, we find counter-examples for all δ by picking x= 2δ. Thus, the statement is False.
 
 
As long as I'm understand where I did wrong, let's move on to the new class materials.

This week we are still digging the hole of proofs and getting deeper by introducing more types of proofs.

First, Prof Larry taught the definition of non-boolean functions, which is "functions return values are not True/False" . Then, he introduced the definition of floor:

Based on Timothy's slog, two Profs used the same examples of proofs to explain the definition of floor. 

Furthermore, Larry taught about disproving.The basic idea I summarized is that to disprove a statement is to prove its negation.

Last, we taught about limits.  

I always know that all we need to do is pick a wise δ, but how to do that? Today's lecture finally helped me by teaching technique "backward search".

One sentence Timothy posted confused me:

"Again, in order to find a good delta, d should be less than or equal to epsilon." So I commented under his post, waiting for his reply,:)

Week 5: Week of Proofs

This week I did my first term test and found myself still poor in identifying true or false in multiple quantifiers.

The second question part(a) of Question 2 from the test confuses me. Can I say that the negation of S1 is correct because if we pick m=n-1, then m+n=-1, given that p is natural number, in the case m+n cannot be p, so the negation of S1 is true.??? I'm not sure about my answer.

Week 5 is basically a proof week.Larry showed us the examples of different proofs.

Learned:


proof using contrapositive: 
instead of proving P => Q,
prove ¬Q => ¬P

note: sometimes the reverse direction is easier to prove(try the contrapositive when stuck)

proof using contradiction:
when P is implicit, try to assume NOT Q, hunt for a contradiction

proof for existence:
to proof "there exists some...", we need to pick a suitable example(number)


proof about a sequence:
pick a number for i that works
negate the consequence for contraposiitive

This week, while browsing some of my classmates' slogs, I found one very helpful and conclusive. Since he is from the other section, I feel I can learn more from following his slog: http://timothylock.me/sLOG/

Coincidentally, I find we are both confused about choosing ε, δ. Based on his slog, Prof Heap presented function codes to explain, while Prof Larry used real-life examples(which I like more since they are easier to understand for me).