Why would you leave an exam early?

As a student, and more so now as an instructor, it baffles me when I see students leave an examination early. Did they suddenly take ill? No. Did they get a perfect score? Negative. Is there some prize for leaving early? None. Then why did they leave?

Even when you think you've answered every question to the best of your ability, the remaining time can still be used to review your work, as many times as your time allows. Reviewing your work begins with the question, not with your solution. Reread the questions and ensure that they were interpreted correctly. Then review the solutions, redoing calculations where applicable. Mistakes can be made when using a calculator too! In some cases it is even possible to verify that the answer found is correct (e.g. by using another method or substituting the results to ensure that they satisfy all parts of the question.) Maybe in your haste your penmanship deteriorated. In this case you can use the time to rewrite parts of your solution more legibly.

Even when you draw a complete blank in an exam, it is in your best interest to stay. Take a few deep breaths and calm your nerves, then try the question again. You never know what you can remember unless you take the time to try to remember.

If you are a student who has left an exam early please share your reasons in the comments below.

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.