Posts

Showing posts from December, 2019

[DSA in Python] minmax.py

This was the third exercise of Chapter 1 (Python Primer) in the book 'Data Structures and Algorithms in Python' by Goodrich et al.

Problem: "Write a short Python function, minmax(data), that takes a sequence of one or more numbers, and returns the smallest and largest numbers, in the form of a tuple of length two. Do not use the built-in functions min or max in implementing your solution."

Potential Solution:
The obvious solution to getting the min and max of a sequence would be to use the Python built-in functions min and max:

Solution:
However, we cannot use these built-in functions from Python. An alternative approach would be to use a for loop:

In this function, we set two variables to the first element of the sequence, data. We then proceed iterate through the sequence, data, through indexing. Within the for loop, we make two checks. If the variable smallest's value is larger than the current element, data[i], then that must mean that the current element is the smallest at this moment in the loop. A similar comparison is made for the largest number, instead we check if the variable largest's value is smaller than the current element, data[i].


Remarks:
  • In a function, Python can return two or more variables. It can do this by returning a sequence of these variables. However, this sequence is a tuple, not a list. The difference between a tuple and a list is that elements cannot be modified in tuple whereas elements can be changed in a list.

[DSA in Python] is_even.py

This was the second exercise of Chapter 1 (Python Primer) in the book 'Data Structures and Algorithms in Python' by Goodrich et al.

Problem: "Write a short Python function, is_even(k), that takes an integer value and returns True if k is even, and False otherwise. However, your function cannot use the multiplication, modulo, or division operators."

Potential Solutions:
This was a bit harder to solve without using multiplication, modulo, or division operators. For example, we can easily determine if a number k is even by returning k % 2 == 0. This is the modulo operator approach:

This function says that any number that can be divided by 2 without leaving a remainder (divisibility) is even, otherwise, it is odd.

Another approach would be to use both the multiplication and the division operators. One would simply need to divide k by 2 and then multiply the quotient by 2. The product would then be compared to the original input k. If they are equal, then k is even, otherwise, it is odd.


However, we cannot use these operators. What should we do then?

Solutions:
When we count numbers, i.e. 1, 2, 3, 4, 5,  one can see that there is a pattern. The first number is 1, which is an odd number. The second number is 2, which is an even number. The third number is 3, which is an odd number.  This pattern of switching between an odd number to an even number and then back again when counting can be quite useful information on determining if a certain number is even or odd.

In other words, we are basically tracking which number is even or odd. How do we track it? We use a boolean variable that can serve as a flag.

In this function, we first set the flag to be False because the first counting number will always be an odd number (i.e. 1). Thus, it would make sense to start iterating at 2. We then make two checks and change the value of the flag accordingly. If the flag is currently set to False, then it implies that we have just passed an odd number. Therefore, it means that the current number that we are at should be an even number. If the flag is currently set to True, then that means we just passed an even number. And so, the current number we are at should be an odd number.

As one can see, our boolean variable flag follows along with the pattern of even/odd when iterating by switching between True and False, where True indicates evenness and False indicates oddness.

Another approach that does not use the multiplication, modulo, and division operators would be to use the bitwise operator &. This an esoteric approach because we are dealing with bits. In short, only odd numbers will have their lowest-order bit to be set. So if we do k & 1, we will be able to get the lowest-order bit of number k. We indicate the lowest-order bit to be set if it is 1. However, if the lowest-order bit is 0, then that means that the number is even. An example would be clearer:


Remarks:
  • The % is a modulo operator, which returns the remainder that occurs from the division of m / n.
  • By divisibility,  a number divided by another number must not leave a remainder.
  • The & is a bitwise operator, which returns the result of performing AND on each bit of the first operand and the second operand. For example, if the first bit of the first operand was a 1 and the first bit of the second operand was 1, then the result's first bit would be 0. These operands must be of type integer for it to work. A background in Computer Architecture would be helpful in understanding why bitwise operators exist and how they work.
  • Many sources say that the bitwise approach is more efficient (which I do agree), but it is not intuitive if one does not understand how bits and bitwise operators work.

[DSA in Python] is_multiple.py

This was the first exercise of Chapter 1 (Python Primer) in the book 'Data Structures and Algorithms in Python' by Goodrich et al.

Problem: "Write a short Python function, is_multiple(n, m), that takes two integer values and returns True if n is a multiple of m, that is, n = mi for some integer i, and False otherwise."

Solution:
There are some different variations of creating this function, but it boils down to checking on whether an operation behaves in a certain way.

The function will return the truthness or falseness of m % n == 0. If m % n is equal to 0, then we know that m is divisible by n. This means that m must also be a multiple of n.

Remarks:
  • The % is a modulo operator, which returns the remainder that occurs from the division of m / n.
  • By divisibility,  a number divided by another number must not leave a remainder.