Euclidean Algorithm

The Euclidean algorithm is a method to find the greatest common divisor of two positive integers, a and b, where a > b. We can denote the greatest common divisor of a and b as gcd(a,b)

The Euclidean algorithm is based on the following:

• If a and b are positive integers, there exist integers unique non-negative integers q and r so that a = bq + r , where r < b.

•  \(a = bq + r \rightarrow gcd(a,b) = gcd(b,r)\)

• gcd(z,0) = z, for any integer.

Algorithm steps:

1. Express a in the form a = bq+ r.
2. End if r = 0 and report b as the gcd. Otherwise b becomes our new a and r becomes our new b and repeat step 1.

Let's find the greatest common divisor of 732 and 345 using the Euclidean algorithm.

\begin{align*}
732 &= 345(2) + 42
\\345 &= 42(8) + 9
\\42 &= 9(4) + 6
\\9 &= 6(1) + 3
\\6 &= 3(2) + 0
\end{align*}

From above it follows that gcd(732,345) = gcd(345,42) = gcd(42,9) = gcd(9,6) = gcd(6,3) = gcd(3,0) = 3.


A common mistake is to report that the gcd(a,b) is the quotient, q, in the final line. In this case some might erroneously report gcd(732, 345) = 2. It helps to remember the second point above to avoid committing this mistake. The gcd is the last non-zero remainder.

Transitive Closure

The closure of a binary relation R on a set A, with respect to a property (reflexivity, symmetry, transitivity) is a relation which meets the following three criteria.

1. The relation contains R.
2. The relation possesses the property.
3. The relation has the fewest number of ordered pairs that satisfies both criteria listed above.

The reflexive closure of R is given by \( R \cup \left \{(x,x): x \epsilon A\right \}\).
The symmetric closure of R is given by \( R \cup \left \{(y,x): (x,y) \epsilon A\right \}\).


Finding transitive closure is not as simple. Consider the relation \(R = \left \{(1,2), (3,1), (1,4), (4,3)\right \}\). We may be tempted to think that the transitive closure is given by \(R \left \{(3,2), (3,4), (1,3), (4,1)\right \}\). This new relation satisfies property 1 above but does it satisfy 2? No, it is missing (1,1), (3,3) and so on.

One method to find the transitive closure is to use Warshall's algorithm. Given a relation R on set A (which has n members), Warshall's algorithm takes as input the n x n 0-1 matrix representing R,  \(M_{R}\), and outputs a matrix representing the transitive closure of R,  \(M_{R^{*}}\).

Warshall's Algorithm:

\(for \ k = 1\  to\  n\)
    \(for\  i = 1\  to\  n\)
        \(for\  j = 1\  to\  n\)
            \(w_{ij} = w_{ij} \vee (w_{ik} \wedge w_{kj})\)

Examining the innermost loop we note that only j (which represents our columns in our matrix) is changing. The counters i and k remain constant. 

If \(w_{ik}\) is 0 then the row remains unchanged since  \(w_{ik} \wedge w_{kj}\) evaluates to 0.

If \(w_{ik}\) is 1 then \(w_{ij}\) takes the value of \(w_{ij} \vee w_{kj}\). If \(w_{ij}\) is 1 it stays as 1. If \(w_{kj}\) is 1 then \(w_{ij}\) is updated to 1. In other words we replace the \(i^{th}\) row with the result of boolean addition of the \(i^{th}\) and \(k^{th}\) rows.

Let's look at an example. Let's find the transitive closure of R={(1,1), (1,3), (2,1), (3,2)} using Warshall's algorithm.

\(M_{R} =\begin{bmatrix} 1  &0 &1 \\1  &0 &0 \\ 0  &1 &0\end{bmatrix}\)

\(k = 1: W_{1} = \begin{bmatrix} 1  &0 &1 \\1  &0 &1 \\ 0  &1 &0\end{bmatrix}\)

\(k = 2: W_{2} = \begin{bmatrix} 1  &0 &1 \\1  &0 &1 \\ 1  &1 &1\end{bmatrix}\)

\(k = 3: W_{3} = \begin{bmatrix} 1  &1 &1 \\1  &0 &1 \\ 1  &1 &1\end{bmatrix}\)

So, \(M_{R^{*}}\) = {(1,1), (1,2), (1,3), (2,1), (2,3), (3,1), (3,2), (3,3)}

Would you want to work with you?

At the start of every semester I like to ask my students why are they in this class or why have they enrolled in this particular programme. Popular responses include meeting some parental demand to pursue higher education, meeting some contractual obligation to an existing employer, needing a degree to get a job. Not very many students respond that it is a path towards their chosen career. Your reasons for pursuing higher education influence your approach to your studies and ultimately the type of work ethic you develop that you take with you into industry. Even if you're not enthusiastic about your field, people should be enthusiastic to work with you.

It's natural to be motivated when you are passionate about your field and excited to join industry as a <insert job role here> but not everyone embarks on a course of study knowing what type of professional roles exist in the field and which of those roles appeal to them. If you're lucky you may find yourself in a programme that exposes you to opportunities to learn about career options and will interact with instructors who get you excited about the field thereby changing your outlook. You may even research your career options on your own and discover roles that appeal to you. But if this enthusiasm never develops the danger is that you will not reap the full benefits of your programme and habits will develop that you will likely take with you into industry.

You may begin to focus on graduation as though it is the final goal and forget that there is life after. You need to remain mindful that the student you are today will likely dictate the worker you will be tomorrow. Examine yourself and your work ethic often. Are you focused on simply finishing or excelling? Do you strive to meet deadlines or consistently seek extensions? For group work, do you do your fair share and in a timely manner or do others dread working with you? Do you wait for answers or do you seek them? You may not be passionate about your field but you should strive to be praiseworthy.

After this programme you will be employed and you will be expected to deliver in whatever role you have. Be mindful of the person you are becoming. Who do you want to be...or rather, who would you like to work with?

Addition and Simplification Laws

In logic the addition law and simplification law are sometimes misused.

Law of Addition

\(p \rightarrow p \vee q\)

This law states that if a proposition \(p\) is known to be true then the disjunction of  \(p\) with any other proposition will also be true.

Law of Simplification

\([(p) \wedge (q)] \rightarrow p \)

also,

\([(p) \wedge (q)] \rightarrow q \)

This law states that if the conjunction of \(p\) and \(q\) is true then we can deduce \(p\) is true. Similarly, we can deduce \(q\) is true. Remember that \([(p) \wedge (q)]\) is true only if both propositions \(p\) and \(q\) are true. That's why we can deduce \(p\)  is true and that \(q\) is true.

Some students attempt to apply the law of simplification to a disjunction. Without knowing the truth values of \(p\) and \(q\) some students may deduce from the statement \( p \vee q\) that \(p\) is true or that \(q\) is true. This is not valid. From \( p \vee q\) we know that at least one of the propositions is true, but we do not have enough information to know which one of them is true.

Finding a Formula when Solving Recurrence Relations using Induction

Induction is a popular technique for solving recurrence relations that involves guessing the formula instead of deriving it through computation. Induction is then used to prove that the formula found by conjecture is valid for the given recurrence relation.

Some people have a natural gift for noticing patterns in numbers and may actually conjecture the formula with ease. Others may struggle with this approach at first but after practising with a variety of problems may discover that finding the formula can be an almost enjoyable task.

Tips for finding the formula:

1. List about 3-5 iterations of the relation. On your first pass, don't sum or calculate products or simplify the expression. The pattern may be easier to see with the expression in this form. If no pattern is obvious, then simplify.
2. Identify which values remain constant in each iteration.
3. Identify which values change with each iteration.
4. Do you notice a sum of values? A product? Is the product some value raised to an exponent/power?
5. Identify the relationship between the number of the iteration and the changing values.

Example:

Suppose we would like to find a recurrence relation for \(s_0 = 3, s_k = s_{k-1} + 2k\) for all integers \(k >=1\)

\(s_0 = 3\)
\(1^{st}\) iteration:  \(s_1 = 3 + 2.1\)
\(2^{nd}\) iteration: \(s_2 = 3 + 2.1 + 2.2\)
\(3^{rd}\) iteration: \(s_3 = 3 + 2.1 + 2.2 + 2.3\)

From this we can see that the first term, 3, remains constant and 2 is a factor of the remaining terms. So we get

\(s_0 = 3\)
\(1^{st}\) iteration:  \(s_1 = 3 + 2(1)\)
\(2^{nd}\) iteration: \(s_2 = 3 + 2(1 + 2)\)
\(3^{rd}\) iteration: \(s_3 = 3 + 2(1 + 2 + 3)\)

The values inside the brackets change on each iteration and here we have a sum of terms. But how do we generalise? Well we look for a relationship between the number of the iteration and our changing values. In this example, in our \(k^{th}\) term we have 1 + 2 + ...+ k. This is the sum of an arithmetic sequence where a = 1 and d = 1. The sum of the first k terms in an arithmetic sequence is given by \(\frac{k}{2}(2a + (k-1)d)\).
Since a = 1 and d = 1 then. \(1 + 2 + ... + k = \frac{k(k+1)}{2}\)

So our final solution is
\(s_n = 3 + 2 \frac{n(n+1)}{2}\)
\(s_n = 3 + n(n+1)\)

Depending on the complexity of the recurrence relation you may not be able to conjecture a formula easily but there are methods for solving recurrence relations that involve identifying the type of recurrence relation and using an appropriate known closed-form formula.See this article for more details.