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).