2014年10月24日星期五

CSC165 SLOG Week7

What’s something new I learned this week?

  • proof by cases :
             split your argument into differences cases and prove the conclusion for each case.

             Attention : the union of the cases are covering ALL possibilities !!!

  • uniqueness (math prerequisite) :  if m and n are natural numbers, with n ≠ 0, then there is exactly one pair natural numbers (q, r) such that: m = qn + r, n > r ≥ 0,divide m by n, the quotient and  remainder are unique.


  • Patterns of inference : 
    Two categories of inference rules
            ➔ introduction: smaller statement => larger statement
            ➔ elimination: larger statement => smaller statement

  • introduction rules:
              1. negation introduction: assume A leads to contradiction => ¬A

              2. conjunction introduction: c is red, c is fast => c is red and fast

              3. disjunction introduction:  c is red => c is red or fast

              4. implication introduction: assume A, then B ⇔ A => B
                                                           assume ¬B, then ¬A ⇔ A => B
              5. equivalence introduction: A => B and B <=> A <=> B

              6. universal introduction: assume a ∈ D, then P(a) => 
                                                                                                        ∀ x ∈ D, P(x)
              7. existential introduction: P(a) and a ∈ D =>
                                                                                            ∃ x ∈ D, P(x)
  • elimination rules:
              1. negation elimination: ¬¬A = A
                                                      A and ¬A => contradiction!
              2. conjunction elimination: A ∧ B ⇔ A and B
              3. disjunction elimination: A ∨ B and ¬A => B
              4. implication elimination: A => B and A => B
                                                          A => B and ¬B => ¬A
              5. equivalence elimination: A ⇔ B => A => B and B => A
              6. universal elimination: ∀ x ∈ D, P(x) and a ∈ D => P(a)
              7. existential elimination: ∃ x ∈ D, P(x) => 
                                                                                Let a ∈ D such that P(a)
  • Tips for how to be good at proofs:
           ➔ become familiar with these patterns, by lots of practice
           ➔ recognize these patterns in your proof, use the manipulation rules to ger closer to your                     target.
  • what “running time means in computer science:
          ➔ It does NOT mean how many seconds are spent in running the algorithm.
              ➔ It means the number of steps that are taken by the algorithm.
                ➔ the running time is independent of the hardware on which you run the algorithm.
                  ➔ It only depends on the algorithm itself.
        • absolute running time is not important: 
          what we really care about is how the number of steps grows as the size of input grows!!  
          we don’t care about the absolute number of steps, 
          we care about: “when input size doubles, the running time quadruples!  
          so, 0.5n² and 700n² are no different!  
          Constant factors do NOT matter!
        • only the highest-order term matters: 
          we don’t need to study algorithms in order 
          to sort two elements, because different 
          algorithms make no difference, 
          we care about algorithm design when the 
          input size n is very large, 
          so, n² and n²+n+2 are no different, 
          because when n is really large, n+2 is 
          negligible compared to n²
        • O(n²) is an asymptotic notation: 
                  O( f(n) ) is the asymptotic upper-bound
        •  ➔ the set of functions that grows no faster than f(n)

        • analyse the time complexity 
          of a program : for example, linear search.
                   ➔ program running time varies with inputs
                     ➔ among inputs of a given size, there is a worst case in which the running time is the                             longest.
          • worst-case time complexity: tP(x) : running time of a program P with input x. The worst-case time complexity of P with input x in I with size n is 




          What’s something that frustrated and challenged me this week?

          I think it should be counting the running time for certain function in python, especially the for loop and while loop, and the case that a loop contains another loop. Also, counting the worst-case is disturding.

          How confident do you feel about material covered this week?

          Not really, if finding running time appeared in final test, it will definetely take me a lot of time to solve it.

          How does course material relate to other classes or interests?

          I think the merge sort and quick sort mentioned in lecture is exactly the same as what I'm learning in CSC148 Sorting part, and I think the website the instructor provided is really useful for both CSC165 and CSC148:  http://www.sorting-algorithms.com/

          Problem solving:

          problem solving for pennies in Friday's lecture.
          发帖者 时间：

          没有评论:

          发表评论

          订阅： 博文评论 (Atom)