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?