Week #13 Prepare for Final Exam

(ﾟﾛﾟ'') !!!             lol, exam song @ BA


CSC236 Summary:

we have been teaching how to proof the problem appropriate and accurate in this semester.

Mathematical Induction, Complete Induction, Structure Induction
Master Theorem, Pigeonhole Principle
Recurrence and recursion
Program correctness, recursive and iterative
Formal languages, Finite State Machine


so, for this week, i am going to prepare myself, review all the quizzes and term tests and lecture slides again.

Good Luck, everyone, have a nice day    =)

Week #12 Assigenment 3 - Pigeonhole Principle Application

"In mathematics, the pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more than one item. " - Wikipedia


i was through that this is an obvious question, why we need a principle for that.
but after i finish Assignment question 1, i realize that it is useful method.

Assume there is a DFSA(D1) for L with fewer than 16 states. #so there is at least 2 unique |string| = 4, go through the DFSA(D1) to the same state by Pigeonhole Principle.

Two string  start with the same states but end up with different that cause the contradiction.

Week #11 Finite State Machine

Impression of Finite State Machine :
In CSC236 FSM is be using for proof the algorithm's appropriate and accurate
In STA247 FSM is be using for calculator the algorithm's probability.
In CSC258 FSM is be using for design logic circuits

They are closely linked, as theory and application, also they all have their own regular expression to show the way how it works.


About the Assignment 3:

Question 3 :

  


proof cases are similar once you get the first one done.
arbitrary string x works for this DFSA when 
y ∈ Σ*, j ∈ Σ4 ⇒ δ*(q0 , x) = δ4( δ*(q0 , y) , j) 


(￣(エ)￣)  !!!
this guy is awesome.

Week #10 Snakes & Ladders

we got STA247 assignment in this week.
i think it can be solved using Mathematical Induction.

there is the question
"Design and model a board game of Snakes-and-Ladders variety.  Your board must have at
least 9 squares (spaces), and must include at least one move-ahead (ladder) and one move-back (snake).  Simulate at least two players (pieces).  A simulated fair six-sided die will be used to advance the pieces.  A player near the end of the board can finish only if player rolls the exact number needed to reach the terminus; otherwise, that player waits until his/her next turn to try again."

16	15	14	13
9	10	11	12
8	7	6[L]	5[L]
1	2	3[S]	4[S]

this is my game board.

Week #9 integer power

def power (x, y) :
    z = 1
   m = 0
   while m < y :
      z = z * x
      m = m + 1
return z



precondition : x ∈ ℝ, y ∈ ℕ
post-condition :  x^y, z = x^y

PRE : A is sorted increasing, complete to x, |A| = n
POST : O ≤ p ≤ n, A[0, ... , p - 1] < x ≤ A[p, ... , n - 1]

so we need to consider 2 cases.
Case 1 : b (i+1)  = m (i+1) + 1 and e(i + 1) = ei
Case 2 : e(i + 1) = m(i + 1) - 1, b(i + 1) = bi

bi ≤ m(i + 1) ≤ ei

Week #7 mergesort

is the [Traverse Dy looking for minimum pairs 15 places apart] works only on unit 1 x 1 square?

Week #8. Assignmnet 2

using Fibonacci number to proof "Odd Maximal Contiguous Ones Free Strings are binary strings that contain no maximal contiguous substring1of 1s that is of odd length."

first thing is to observe.

all previous OMCOFS elements append "0" or "11", is still OMCOFS.
all non-OMCOFS elements append "0" or "11", is still non-OMCOFS.

using the formula from "INTRODUCTION TO THE THEORY OF COMPUTATION" P78 to proof the assumption.

WEEK #6 @ T(n)

upper bound on T(n):

 T(n) >= c ·lgn  if c<=1

T(n) = 1     , n = 1
T(n) = 1 + T ⌈n / 2⌉ ,   n > 1

T(n) = 1-c + c· lg(n - 1)

it is possible to prove it by complete induction

WEEK #5

i am still working on recursive proof.

Hi @ WEEK #4

hi everyone, Happy Thanksgiving!

i just read some of you guys' journal. it is awesome!

Ok, let's start talking about my feeling about Assignment 1.

For Assignment 1, Question 2.

I used some "weird" way which is Derivative to proof (n^3) + n < (3^n)

Do you remember we learn that in MAT137 ?

Great ! That is how i do it.

set f(n) = (n^3) + n - (3^n)

if we find some how the function is decreasing function in n ∈ [4 , +∞) , and f(4) < 0
that will makes (n^3) + n < (3^n)

i don't know if this is a good way to solve this problem in CSC236, but it works when i was learning MAT137.

Cheers, my friend.

=)