Week 4 - Functions

2 minute read

1. Luhn Formula, Check Digit, Luhn Algorithm, and Examples

  • Luhn Formula: A simple checksum formula used to validate various identification numbers, e.g., credit card numbers.
  • Check Digit: The digit added to a number to ensure its validity based on the Luhn Algorithm.
  • Luhn Algorithm: Process to calculate the check digit using the Luhn Formula.

Luhn-10 Algorithm Steps:

  1. Start from the rightmost digit and move left.
  2. Multiply every even-ranked digit by 2.
  3. If a product is ≥10, add its digits.
  4. Calculate the sum (s) of all resulting digits.

Example: Credit card number 4532 0151 1283 0366

image-center

Tip: You might be asked to find the check digit (right most). If check digit is ‘c’ and ‘sum’ is ‘s’, the formula to find ‘c’ will be c = (10 - (s mod 10)) mod 10
In the example above, sum would be 44 and check digit can be calculated as c = (10 - (44 mod 10)) mod 10 = 6.

2. Functions, Representation, Examples, Sequences, and Excel

  • Function: A relation between two sets, assigning each element in one set to exactly one element in the other.
  • Representation: f(x) = y, f: X → Y
  • Example: f(x) = 2x + 3
  • Sequence: An ordered list of elements, often produced by a function.
  • Excel: Use formulas to calculate function values, e.g., “=2*A1+3” where A1 is the input cell.

3. Ordered Pair

  • A pair of elements written in a specific order, e.g., (x, y).
  • Example: (3, 4) is different from (4, 3).

4. Relation, Domain & Range

  • Relation: A set of ordered pairs.
  • Domain: What can go into a function as input is called the Domain (x).
  • Co-Domain: The set of all possible output values function can produce, including the range as a subset.
  • Range: What actually comes out of a function (output) is called the Range (y).
  • Example: Domain: {1, 2, 3, 4}, Codomain: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, Range: {3, 5, 7, 9}

5. Modulo Operator

  • Calculates the remainder after division.
  • Notation: a % b
  • Example: 7 % 3 = 1

6. Hash Function

  • A hash function is a function that takes an input and converts it into a fixed-size output.
  • The main idea behind a hash function is to map a large amount of data to a smaller, more manageable size.

Example of a simple hash function for strings:

  1. Goal: Map strings to numbers in the range 0-9.
  2. Hash function: Add ASCII values of characters in the string, then take the remainder when divided by 10 (using modulo operation).

Example with “cat”:

  1. ASCII values: ‘c’=99, ‘a’=97, ‘t’=116
  2. Sum: 99+97+116=312
  3. Remainder: 312 % 10 = 2
  4. Hash value: 2

7. Pseudorandom Numbers

  • Numbers that appear random but are generated deterministically by an algorithm.
  • Example: Linear congruential generator

8. Floor and Ceiling Functions

  • Floor function: Rounds a number down to the nearest integer, e.g., floor(4.7) or ⌊4.7⌋ = 4.
  • Ceiling function: Rounds a number up to the nearest integer, e.g., ceil(4.2) or ⌈4.2⌉= 5.

9. Encoding and Decoding Functions

  • Encoding: Transforming data into a different format.
  • Decoding: Reversing the encoding process.
  • Example: Base64 encoding and decoding.

10. The Hamming Distance Function

  • Measures the number of differing positions between two equal-length strings.

Example 1:
String 1: 10101010
String 2: 11101000
Hamming distance: 3 (differences in positions 2, 8, and 9)

Example 2:
String 1: AGCTAGC
String 2: AGCTGGC
Hamming distance: 1 (difference in position 5)

Example 3:
String 1: 0000
String 2: 1111
Hamming distance: 4 (differences in all positions)

11. Boolean Functions

Functions that deal with truth values (True or False).
Example: AND, OR, NOT, XOR operations.

You May Also Enjoy