Practical activity

Presentation & objectives

Below is a list of exercises for studying the complexity of an algorithm, building algorithms focusing on binary search trees and randomized algorithms.

Activity contents

1 — Complexity on list operations

In this exerise you will try to understand the usage, in term of complexity, of operations on (regular) lists and sorted lists.

1.1 — Evaluate complexity

Here are a few operations on these structures, along with some possible (not necessarily optimal) implementations:

1. Regular lists operations – The following functions manipulate a regular list:

   ​

   Python Java

   def create_list ():
   
       """
           Create an empty list.
           In:
               * None.
           Out:
               * An empty list.
       """
   
       return []
   
   
   
   def insert_list (l: list[int], element: int) -> None:
   
       """
           Insert an element at the end of the list
           In:
               * l:       The list.
               * element: The element to insert.
           Out:
               * None.
       """
   
       l.append(element)
   
   
   
   def delete_list (l: list[int], element: int) -> None:
   
       """
           Delete the first occurrence of the element from the list.
           In:
               * l:       The list.
               * element: The element to delete.
           Out:
               * None
       """
   
        # Find the element to delete
       for i in range(len(l)):
           if l[i] == element:
   
               # Shift elements to the left
               for j in range(i, len(l) - 1):
                   l[j] = l[j + 1]
   
               # Remove the last element
               l.pop()
               break
   
   
   
   def find_min_list (l: list[int]) -> int | None:
   
       """
           Find and return the minimum element in the list.
           In:
               * l: The list.
           Out:
               * The minimum element in the list.
       """
   
       # Check that not empty
       if not l:
           return None
   
       # Initialize the minimum value to the first element
       min_value = l[0]
   
       # Find the minimum value in the list
       for value in l:
           if value < min_value:
               min_value = value
   
       # Return the minimum value
       return min_value
   
   
   
   
   # Test the functions
   print("Testing regular list operations:")
   a_list = create_list()
   insert_list(a_list, 10)
   insert_list(a_list, 5)
   insert_list(a_list, 20)
   print("list after inserts:", a_list)
   delete_list(a_list, 5)
   print("list after deleting 5:", a_list)
   print("Minimum element in the list:", find_min_list(a_list))

    import java.util.Arrays;
   
    /**
    * Regular list Operations
    */
    public class RegularlistOperations {
   
        /**
        * Create an empty list
        * @return An empty list
        */
        public static int[] createlist() {
            return new int[0];
        }
   
        /**
        * Insert an element at the end of the list
        * @param list The list
        * @param element The element to insert
        */
        public static int[] insertlist(int[] list, int element) {
            // lists are immutable in Java, so we need to create a new list
            int[] newlist = Arrays.copyOf(list, list.length + 1);
            // insert the element at the end of the new list
            newlist[list.length] = element;
            // return the new list
            return newlist;
        }
   
        /**
        * Delete the first occurrence of the element from the list
        * @param list The list
        * @param element The element to delete
        */
        public static int[] deletelist(int[] list, int element) {
            for (int i = 0; i < list.length; i++) {
                // find the element to delete
                if (list[i] == element) {
                    // create a new list without the element to delete
                    int[] newlist = new int[list.length - 1];
                    // copy the elements before the element to delete
                    System.arraycopy(list, 0, newlist, 0, i);
                    // copy the elements after the element to delete
                    System.arraycopy(list, i + 1, newlist, i, list.length - i - 1);
                    // return the new list
                    return newlist;
                }
            }
            // return the original list if the element is not found
            return list;
        }
   
        /**
        * Find and return the minimum element in the list
        * @param list The list
        * @return The minimum element in the list
        */
        public static Integer findMinlist(int[] list) {
            // check if the list is empty
            if (list.length == 0) {
                return null;
            }
            // initialize the minimum value to the first element
            int minValue = list[0];
            // find the minimum value in the list
            for (int value : list) {
                // check if the current value is less than the minimum value
                if (value < minValue) {
                    // update the minimum value
                    minValue = value;
                }
            }
            // return the minimum value
            return minValue;
        }
   
        public static void main(String[] args) {
            System.out.println("Testing Regular list Operations:");
            int[] list = createlist();
            list = insertlist(list, 10);
            list = insertlist(list, 5);
            list = insertlist(list, 20);
            System.out.println("list after inserts: " + Arrays.toString(list));
            list = deletelist(list, 5);
            System.out.println("list after deleting 5: " + Arrays.toString(list));
            System.out.println("Minimum element in the list: " + findMinlist(list));
        }
    }

2. Sorted list operations – The following function manipulate a sorted list:

   ​

   Python Java

   def create_sorted_list ():
   
       """
           Create an empty list .
           In:
               * None.
           Out:
               * An empty list.
       """
   
       return []
   
   
   
   def insert_sorted_list (l: list[int], element: int) -> None:
   
       """
           Insert an element into the sorted list while maintaining the list's order.
           In:
               * l:       The sorted list.
               * element: The element to insert.
           Out:
               * None
       """
   
       # Find the correct position for the new element
       index = 0
       while index < len(l) and l[index] < element:
           index += 1
   
       # Shift elements to make space for the new element
       l.append(0)
       for i in range(len(l) - 1, index, -1):
           l[i] = l[i - 1]
   
       # Insert the new element at the correct position
       l[index] = element
   
   
   
   def delete_sorted_list (l: list[int], element: int) -> None:
   
       """
           Delete the first occurrence of the element from the sorted list.
           In:
               * l:       The sorted list.
               * element: The element to delete.
           Out:
               * None
       """
   
       # Find the element to delete
       for i in range(len(l)):
           if l[i] == element:
   
               # Shift elements to the left
               for j in range(i, len(l) - 1):
                   l[j] = l[j + 1]
   
               # Remove the last element
               l.pop()
               break
   
   
   
   def find_min_sorted_list (l: list[int]) -> int | None:
   
       """
           Find and return the minimum element in the sorted list.
           In:
               * l: The sorted list.
           Out:
               * The minimum element in the list.
       """
   
       # Check that not empty
       if not l:
           return None
   
       # The minimum element is the first element in the sorted list
       return l[0]  
   
   
   
   # Test sorted list operations
   print("\nTesting Sorted list Operations:")
   sorted_list = create_sorted_list()
   insert_sorted_list(sorted_list, 10)
   insert_sorted_list(sorted_list, 5)
   insert_sorted_list(sorted_list, 20)
   print("Sorted list after inserts:", sorted_list)
   delete_sorted_list(sorted_list, 5)
   print("Sorted list after deleting 5:", sorted_list)
   print("Minimum element in the sorted list:", find_min_sorted_list(sorted_list))

    import java.util.Arrays;
   
    /**
    * Sorted list operations.
    */
    public class SortedlistOperations {
   
        /**
        * Creates an empty sorted list.
        *
        * @return an empty integer list.
        */
        public static int[] createSortedlist() {
            return new int[0];
        }
   
        /**
        * Inserts an element into the sorted list while maintaining the sorted order.
        *
        * @param list the original sorted list.
        * @param element the element to be inserted.
        * @return a new sorted list with the element inserted.
        */
        public static int[] insertSortedlist(int[] list, int element) {
            int index = 0;
            // Find the correct position for the new element
            while (index < list.length && list[index] < element) {
                index++;
            }
            // In java, lists are immutable, so we need to create a new list with the element inserted
            int[] newlist = new int[list.length + 1];
            // Copy the elements before the index
            System.arraycopy(list, 0, newlist, 0, index);
            // Copy the elements after the index
            System.arraycopy(list, index, newlist, index + 1, list.length - index);
            // Insert the element at the correct position
            newlist[index] = element;
            // Return the new sorted list
            return newlist;
        }
   
        /**
        * Deletes an element from the sorted list.
        *
        * @param list the original sorted list.
        * @param element the element to be deleted.
        * @return a new sorted list with the element removed, or the original list if the element is not found.
        */
        public static int[] deleteSortedlist(int[] list, int element) {
            for (int i = 0; i < list.length; i++) {
                // Find the element to delete
                if (list[i] == element) {
                    // Create a new list without the element to delete
                    int[] newlist = new int[list.length - 1];
                    // Copy the elements before the index
                    System.arraycopy(list, 0, newlist, 0, i);
                    // Copy the elements after the index
                    System.arraycopy(list, i + 1, newlist, i, list.length - i - 1);
                    // Return the new sorted list
                    return newlist;
                }
            }
            // Return the original list if the element is not found
            return list;
        }
   
        /**
        * Finds the minimum element in the sorted list.
        *
        * @param list the sorted list.
        * @return the minimum element in the list, or null if the list is empty.
        */
        public static Integer findMinSortedlist(int[] list) {
            // Check if the list is empty
            if (list.length == 0) {
                return null;
            }
            // The minimum element is the first element in the sorted list
            return list[0];
        }
   
        /**
        * Main method to test the sorted list operations.
        *
        * @param args command line arguments.
        */
        public static void main(String[] args) {
            System.out.println("\nTesting Sorted list Operations:");
            int[] sortedlist = createSortedlist();
            sortedlist = insertSortedlist(sortedlist, 10);
            sortedlist = insertSortedlist(sortedlist, 5);
            sortedlist = insertSortedlist(sortedlist, 20);
            System.out.println("Sorted list after inserts: " + Arrays.toString(sortedlist));
            sortedlist = deleteSortedlist(sortedlist, 5);
            System.out.println("Sorted list after deleting 5: " + Arrays.toString(sortedlist));
            System.out.println("Minimum element in the sorted list: " + findMinSortedlist(sortedlist));
        }
    }

What are the (worst-case) time complexities of the different operations? How does the time complexity in a sorted list compare to that of a regular list?

1.2 — Write your own functions

Now, for each of the lists above, write a function that, for each element in the list, counts the number of other greater or equal elements in the list. The function should return a dictionary that, for each element, associates its result.

As your function should be able to compare elements, maybe an assert could be interesting to use. We also assume that the list should only contain distinct values.

What are the complexities of these functions?

def count_greater (l: list[int|float]) -> dict[int|float, int]:

    """
        For each element, counts the number of other greater or equal elements in the list.
        In:
            * l: List to study.
        Out:
            * A dictionary of counts.
    """

    # Asserts
    assert all([type(e) in [int, float] for e in l]), "l contains non-numeric elements."
    assert len(set(l)) == len(l), "l contains duplicates."

    # Fill a dictionary for each element
    result = {}
    for e in l:
        result[e] = 0

        # Count greater or equal elements
        for f in l:
            if f >= e:
                result[e] += 1

    return result

def count_greater_sorted (l: list[int|float]) -> dict[int|float, int]:

    """
        For each element, counts the number of other greater or equal elements in the sorted list.
        In:
            * l: List to study.
        Out:
            * A dictionary of counts.
    """

    # Asserts
    assert all([type(e) in [int, float] for e in l]), "l contains non-numeric elements."
    assert len(set(l)) == len(l), "l contains duplicates."

    # Fill a dictionary for each element
    n = len(l)
    result = {}
    for i, e in enumerate(l):
        result[e] = n - i

    return result

2 — Prime number

A prime number is a strictly positive number that is not divisible (in the sense of integer division) except by 1 and itself (for example: 2, 3, 5, 7, 11, etc.). We want to determine whether an integer is a prime number. The basic method is to prove that the number to be treated is not prime by looking for a divisor that gives a remainder equal to 0. If such a divisor is found, the number is not prime.

In a file named prime.py, write several functions to test if a given number is a prime number.

1. complete_check_prime (number: int) -> Tuple[bool, int] function – Use the for loop to test all the divisors from 2 to (number - 1). The function will return whether it is prime or not. It will also return the number of iterations carried out to obtain the result. Then, state its algorithmic complexity.

2. lless_dividers_prime (number: int, limit: int) -> Tuple[bool, int] function – The first way to do this is to treat the case of even numbers separately. If the number is divisible by 2, it is not interesting to check for even divisors. The search should be restricted to odd divisors (3, 5, 7, etc.). The second approach is to work on numbers that have several divisors, such as 24, to highlight a property of divisors that limits the search range, such as the square root of a number.

   Write the function which implements this method in prime_bis.py. The program will return whether the number is prime or not. It will also return the number of iterations carried out to obtain the result. The for loop can be replaced by a while loop, which is more suitable for this type of processing.

   The limit argument can be equal to the number, or to its square root. Indicate the algorithmic complexity for each case.

   Note the number of iterations returned when you test it on even and odd prime and non-prime numbers.

   If you want to evaluate the performance of your algorithm and you can test it with larger prime number, like 10007 or 1e9+7 which is, by the way, the largest prime number stored in a 32-bit integer.

def complete_check_prime (number:int) -> Tuple[bool, int]:
    """
        Check if a number is prime by testing all divisors from 2 to (number - 1).
        In:
            * number: The number to check.
        Out:
            * A couple indicating if the number is prime or not and the number of iterations.
    """
    # worst case: iterate from 2 to number - 1
    iterations = number - 2
    # set is_prime to True by default
    is_prime = True
    for i in range(2, number):
        if number % i == 0:
            # if a divisor is found, the number is not prime
            # store the number of iterations
            iterations = i
            # set is_prime to False and break the loop
            is_prime = False
            break
    # return the result and the number of iterations
    return (is_prime, iterations)


# Test the functions
number = 17
is_prime, iterations = complete_check_prime(number)
print(f"Is {number} a prime number? {is_prime}")
print(f"Number of iterations: {iterations}")

public class Prime {

    /**
     * Check if a number is prime by testing all divisors from 2 to (number - 1)
     * @param number the number to check
     * @return a couple indicating if the number is prime or not and the number of iterations
     */
    public static Object[] completeCheckPrime(int number) {
        for (int i = 2; i < number; i++) {
            if (number % i == 0) {
                return new Object[] {false, i};
            }
        }
        return new Object[] {true, number - 2};
    }

    public static void main(String[] args) {
        int number = 17;
        Object[] result = completeCheckPrime(number);
        System.out.println("Is " + number + " a prime number? "+ result[0]);
        System.out.println("Number of iterations: " + result[1]);
    }
}

def less_dividers_prime (number: int, limit: int) -> Tuple[bool, int]:

    """
        Check if a number is prime by testing divisors up to the limit.
        In:
            * number: The number to check.
            * limit:  The limit to test divisors up to.
        Out:
            * a couple indicating if the number is prime or not and the number of iterations.
    """
    # If the number is even, it is not prime
    if number % 2 == 0:
        return False, 0
    i = 3
    # worst case: iterate from 3 to limit
    while i < limit:
        if number % i == 0:
            # if a divisor is found, the number is not prime
            return False, i // 2
        i += 2 # only check odd numbers
    # if no divisor is found, the number is prime
    return True, i // 2 -1



# Test the functions
number = 17
is_prime, iterations = less_dividers_prime(number, number)
print(f"Is {number} a prime number? {is_prime}")
print(f"Number of iterations: {iterations}")
is_prime, iterations = less_dividers_prime(number, int(number ** 0.5) + 1)
print(f"Is {number} a prime number? {is_prime}")
print(f"Number of iterations: {iterations}")

import java.lang.Math;

public class PrimeBis {

    /**
     * Check if a number is prime by testing divisors up to the limit
     * @param number the number to check
     * @param limit the limit to test divisors up to
     * @return a couple indicating if the number is prime or not and the number of iterations
     */
    public static Object[] lessDividersPrime(int number, int limit) {
        if (number % 2 == 0) {
            return new Object[] {false, 0};
        }
        int i = 3;
        while (i < limit) {
            if (number % i == 0) {
                return new Object[] {false, i / 2};
            }
            i += 2;
        }
        return new Object[] {true, i / 2 - 1};
    }

    public static void main(String[] args) {
        int number = 17;
        int limit = number;
        Object[] result = lessDividersPrime(number, limit);
        System.out.println("Is " + number + " a prime number? "+ result[0]);
        System.out.println("Number of iterations: " + result[1]);
        limit = (int) Math.sqrt(number) + 1;
        result = lessDividersPrime(number, limit);
        System.out.println("Is " + number + " a prime number? "+ result[0]);
        System.out.println("Number of iterations: " + result[1]);
    }
}

3 — Binary search tree

A binary search tree (BST) is a binary tree in which each node has a key, and for any node x, the key in the left subtree of x is less than the key in x, and the key in the right subtree of x is greater than the key in x (see the course relative to BST for more details).

We are going to implement a binary search tree in Python from scratch. We will provide the following functions:

• tree_insert(tree: , value) to insert the value in the tree.
• tree_search(tree, value) to search for the value in the tree.
• tree_delete(tree, value) to delete the value from the tree.

3.1 — Insertion

The insertion algorithm is as follows:

1. If the tree is empty, create a new node with the given value and return the tree.
2. If the value is less than the root value, insert the value in the left subtree and return the tree.
3. If the value is greater than the root value, insert the value in the right subtree and return the tree.
4. If the value is equal to the root value, return the (unchanged) tree.

Then return the root of the tree. Note that the algorithm is recursive.

Create a file named binary_tree.py and implement the function tree_insert(tree, value).

def tree_insert (tree, value):

    """
        Insert a value into the binary search tree.
        In:
            * tree:  The binary search tree.
            * value: The value to insert.
        Out:
            * The root of the binary search tree.
    """

    # Base case: create a new node if the tree is empty
    if tree is None:
        return [value, None, None]

    # Insert the value in the left subtree if it is less than the root value
    if value < tree[0]:
        tree[1] = tree_insert(tree[1], value)

    # Insert the value in the right subtree if it is greater than the root value
    elif value > tree[0]:
        tree[2] = tree_insert(tree[2], value)

    # Do nothing if the value is equal to the root value
    # Return the root of the tree
    return tree



# Test the function
tree = None
values = [10, 5, 7, 4, 9]
for value in values:
    tree = tree_insert(tree, value)
    print(tree)

public class BinaryTree {

    /**
     * Insert a value into the binary search tree
     * @param tree the binary search tree
     * @param value the value to insert
     * @return the root of the binary search tree
     */
    public static int[] treeInsert(int[] tree, int value) {
        // Base case: create a new node if the tree is empty
        if (tree == null) {
            return new int[] {value, 0, 0};
        }
        // Insert the value in the left subtree if it is less than the root value
        if (value < tree[0]) {
            tree[1] = treeInsert(tree[1], value);
        }
        // Insert the value in the right subtree if it is greater than the root value
        else if (value > tree[0]) {
            tree[2] = treeInsert(tree[2], value);
        }
        // Do nothing if the value is equal to the root value
        // Return the root of the tree
        return tree;
    }

    public static void main(String[] args) {
        int[] tree = null;
        int[] values = {10, 5, 7, 4, 9};
        for (int value : values) {
            tree = treeInsert(tree, value);
            System.out.println(lists.toString(tree));
        }
    }
}

3.2 — Search

The search algorithm is as follows:

1. If the tree is empty, return False.
2. If the value is equal to the root value, return True.
3. If the value is less than the root value, search in the left subtree.
4. If the value is greater than the root value, search in the right subtree.

The algorithm is recursive. Implement the function tree_search(tree, value) in the file binary_tree.py.

def tree_search (tree, value):

    """
        Search for a value in the binary search tree.
        In:
            * tree:  The binary search tree.
            * value: The value to search for.
        Out:
            * True if the value is found, False otherwise.
    """

    # Base case: return False if the tree is empty
    if tree is None:
        return False

    # Return True if the value is equal to the root value
    if value == tree[0]:
        return True

    # Search in the left subtree if the value is less than the root value
    if value < tree[0]:
        return tree_search(tree[1], value)

    # Search in the right subtree if the value is greater than the root value
    return tree_search(tree[2], value)



# Test the function
tree = None
values = [10, 5, 7, 4, 9]
for value in values:
    tree = tree_insert(tree, value)
print(tree_search(tree, 7))  # True
print(tree_search(tree, 8))  # False

/**
 * Search for a value in the binary search tree
 * @param tree the binary search tree
 * @param value the value to search for
 * @return true if the value is found, false otherwise
 */
public static boolean treeSearch(int[] tree, int value) {
    // Base case: return false if the tree is empty
    if (tree == null) {
        return false;
    }
    // Return true if the value is equal to the root value
    if (value == tree[0]) {
        return true;
    }
    // Search in the left subtree if the value is less than the root value
    if (value < tree[0]) {
        return treeSearch(tree[1], value);
    }
    // Search in the right subtree if the value is greater than the root value
    return treeSearch(tree[2], value);
}

// Replace the main method with the following code
public static void main(String[] args) {
    int[] tree = null;
    int[] values = {10, 5, 7, 4, 9};
    for (int value : values) {
        tree = treeInsert(tree, value);
    }

    System.out.println(treeSearch(tree, 7));  // True
    System.out.println(treeSearch(tree, 8));  // False
}

3.3 — Deletion

The deletion algorithm is more complex than the insertion and search algorithms.

The inorder successor of a node in a binary search tree (BST) is the node with the smallest key greater than the key of the given node.

We will consider three cases:

1. If the node to delete has no children, we can simply remove it.
2. If the node has only one child, we can replace the node with its child.
3. If the node has two children, we need to find the inorder successor of the node, replace the node with the inorder successor, and delete the inorder successor, then add a new link between the inorder successor children and the inorder successor parents.

Implement the function tree_delete(tree, value) in the file binary_tree.py.

def tree_delete (tree, value):

    """
        Delete a value from the binary search tree.
        In:
            * tree:  The binary search tree.
            * value: The value to delete.
        Out:
            * The root of the binary search tree.
    """

    # Base case: return None if the tree is empty
    if tree is None:
        return None

    # Delete the value in the left subtree if it is less than the root value
    if value < tree[0]:
        tree[1] = tree_delete(tree[1], value)

    # Delete the value in the right subtree if it is greater than the root value
    elif value > tree[0]:
        tree[2] = tree_delete(tree[2], value)

    # Delete the root value if it is equal to the value
    else:

        # Case 1: the node has no children
        if tree[1] is None and tree[2] is None:
            return None

        # Case 2: the node has only one child
        if tree[1] is None:
            return tree[2]
        if tree[2] is None:
            return tree[1]

        # Case 3: the node has two children
        # Find the inorder successor
        successor = tree[2]
        while successor[1] is not None:
            successor = successor[1]

        # Replace the root value with the inorder successor value
        tree[0] = successor[0]

        # Delete the inorder successor
        tree[2] = tree_delete(tree[2], successor[0])

    # Return the root of the tree
    return tree



# Test the function
tree = None
values = [10, 5, 7, 4, 9]
for value in values:
    tree = tree_insert(tree, value)
    print(tree)
for value in values:
    tree = tree_delete(tree, value)
    print(tree)

/**
 * Delete a value from the binary search tree
 * @param tree the binary search tree
 * @param value the value to delete
 * @return the root of the binary search tree
 */
public static int[] treeDelete(int[] tree, int value) {
    // Base case: return null if the tree is empty
    if (tree == null) {
        return null;
    }
    // Delete the value in the left subtree if it is less than the root value
    if (value < tree[0]) {
        tree[1] = treeDelete(tree[1], value);
    }
    // Delete the value in the right subtree if it is greater than the root value
    else if (value > tree[0]) {
        tree[2] = treeDelete(tree[2], value);
    }
    // Delete the root value if it is equal to the value
    else {
        // Case 1: the node has no children
        if (tree[1] == null && tree[2] == null) {
            return null;
        }
        // Case 2: the node has only one child
        if (tree[1] == null) {
            return tree[2];
        }
        if (tree[2] == null) {
            return tree[1];
        }
        // Case 3: the node has two children
        // Find the inorder successor
        int[] successor = tree[2];
        while (successor[1] != null) {
            successor = successor[1];
        }
        // Replace the root value with the inorder successor value
        tree[0] = successor[0];
        // Delete the inorder successor
        tree[2] = treeDelete(tree[2], successor[0]);
    }
    // Return the root of the tree
    return tree;
}

// Replace the main method with the following code
public static void main(String[] args) {
    int[] tree = null;
    int[] values = {10, 5, 7, 4, 9};
    for (int value : values) {
        tree = treeInsert(tree, value);
    }

    for (int value : values) {
        tree = treeDelete(tree, value);
    }
}

4 — Implementing and testing the linear congruential method in Python

4.1 — Linear congruential method

Implement the Linear Congruential Method (LCM) in Python to generate a sequence of pseudo-random numbers. The LCM formula is given by: $$X_{n} = (aX_{n-1} + c) \mod m \;,$$ where:

• $X_{n-1}$ is the current random number.
• $X_{n}$ is the next random number.
• $m$ is the modulus.
• $a$ is the multiplier.
• $c$ is the increment.

The function (called linear_congruential_generator should accept parameters $m$, $a$, $c$, $X_0$, and $n$ (the number of random numbers to generate), and generate sequences using two sets of parameters:

• Set 1: $m = 100, a = 17, X_0 = 27, c = 43$.
• Set 2: $a = 7^5, m = 2^{31}-1, X_0 = 27, c = 0$.

from numbers import Integral
def linear_congruential_generator (m: Integral, a: Integral, c: Integral, x_0: Integral, n: Integral) -> list[Integral]:

    sequence = [x_0]
    for _ in range(1, n):
        next_value = (a * sequence[-1] + c) % m
        sequence.append(next_value)
    return sequence

m1, a1, X_01, c1 = 100, 17, 27, 43
sequence1 = linear_congruential_generator(m1, a1, c1, X_01, 1000)

m2, a2, X_02, c2 = 2**31 - 1, 7**5, 27, 0
sequence2 = linear_congruential_generator(m2, a2, c2, X_02, 1000)

When generating random numbers, it is important to test the quality of the generated numbers. We can test uniformity of the generated numbers by visualizing a histogram and calculating the mean and standard deviation.

# Matplotlib library is required
import matplotlib.pyplot as plt

# First, normalize the sequence to be between 0 and 1
normalized_sequence = [x / m for x in sequence]

# Then, plot the histogram of the generated numbers
plt.hist(normalized_sequence, bins=10, edgecolor='black')
plt.title("Histogram of Generated Numbers")
plt.xlabel("Value")
plt.ylabel("Frequency")
plt.show()

# Calculate mean and standard deviation
mean = np.mean(normalized_sequence)
std_dev = np.std(normalized_sequence)
print(f"Mean: {mean}, Standard Deviation: {std_dev}")

4.2 — Test autocorrelation

Test autocorrelation by measuring the correlation between adjacent numbers in the sequence. To do so, calculate the correlation coefficient between the sequence and the sequence shifted by one position. The most familiar measure of dependence between two quantities is the Pearson product-moment correlation coefficient (PPMCC), or “Pearson’s correlation coefficient”. The PPMCC is a measure of the linear correlation between two variables $X$ and $Y$, giving a value between +1 and −1 inclusive, where 1 is total positive linear correlation, 0 is no linear correlation, and −1 is total negative linear correlation. Here, $X$ is the sequence and $Y$ is the sequence shifted by one position.

The formula for the PPMCC is given by:

$$\begin{align*} r_{XY} &= \frac{\sum_{i=1}^{n}{(X_i - \bar{X})(Y_i - \bar{Y})}}{\sqrt{\sum_{i=1}^{n}{(X_i - \bar{X})^2}}\sqrt{\sum_{i=1}^{n}{(Y_i - \bar{Y})^2}}} \end{align*} \;,$$ where:

• $X_i$ and $Y_i$ are the values of the sequences $X$ and $Y$ at position $i$.
• $\bar{X}$ and $\bar{Y}$ are the means of the sequences $X$ and $Y$.
• $n$ is the length of the sequences.

Implement the function pearson_autocorrelation(x, y), run it on the generated sequences, and print the autocorrelation for each sequence. What do you observe? Can you claim that the sequence is random?

def pearson_autocorrelation (x: list[Integral], y: list[Integral]) -> Integral:

    """
        Calculate the Pearson correlation coefficient between two sequences.
        In:
            * x: The first sequence.
            * y: The second sequence.
        Out:
            * The Pearson correlation coefficient.
    """

    # Calculate the means of the sequences
    n = len(x)
    xmean = 0
    ymean = 0
    for i in range(n):
        xmean += x[i]
        ymean += y[i]
    xmean /= n
    ymean /= n

    # Calculate the covariance and the deviations
    cov_xy = 0
    dev_x = 0
    dev_y = 0
    for i in range(n):
        cov_xy += (x[i] - xmean) * (y[i] - ymean)
        dev_x += (x[i] - xmean) ** 2
        dev_y += (y[i] - ymean) ** 2

    # Calculate the Pearson correlation coefficient
    return cov_xy / (dev_x**.5 * dev_y ** 0.5)

# Numpy library is required
import numpy as np

# Calculate the autocorrelation for the sequence
print(np.corrcoef(sequence1[:-1], sequence1[1:])[0, 1])

/**
 * Calculate the Pearson correlation coefficient between two sequences
 * @param x the first sequence
 * @param y the second sequence
 * @return the Pearson correlation coefficient
 */
public static double pearsonAutocorrelation(double[] x, double[] y) {
    // Calculate the means of the sequences
    int n = x.length;
    double xmean = 0;
    double ymean = 0;
    for (int i = 0; i < n; i++) {
        xmean += x[i];
        ymean += y[i];
    }
    xmean /= n;
    ymean /= n;

    // Calculate the covariance and the deviations
    double cov_xy = 0;
    double dev_x = 0;
    double dev_y = 0;
    for (int i = 0; i < n; i++) {
        cov_xy += (x[i] - xmean) * (y[i] - ymean);
        dev_x += Math.pow(x[i] - xmean, 2);
        dev_y += Math.pow(y[i] - ymean, 2);
    }

    // Calculate the Pearson correlation coefficient
    return cov_xy / (Math.pow(dev_x, 0.5) * Math.pow(dev_y, 0.5));
}

4.3 — Test cycle length

We now want to test the cycle length of the LCM. The cycle length is the number of iterations before the sequence starts repeating. To do so, we will store the generated numbers in a set and check if the number is already in the set. If the number is already in the set, we have found a cycle and can return the cycle length. If the number is not in the set, we add it to the set and continue generating numbers.

Implement the function test_cycle_length(sequence) and run it on the generated sequences.

def test_cycle_length (sequence: list[int]) -> int | None:

    """
        Test the cycle length of the LCM sequence.
        In:
            * sequence: The generated sequence.
        Out:
            * The cycle length if a cycle is detected, None otherwise.
    """

    seen = {}
    for i, value in enumerate(sequence):
        if value in seen:
            cycle_length = i - seen[value]
            print(f"Cycle detected after {i} steps with a cycle length of {cycle_length}.")
            return cycle_length
        seen[value] = i

    print("No cycle detected in the given sequence.")
    return None

/**
 * Test the cycle length of the LCM sequence
 * @param sequence the generated sequence
 * @return the cycle length if a cycle is detected, null otherwise
 */
public static Integer testCycleLength(int[] sequence) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < sequence.length; i++) {
        if (seen.containsKey(sequence[i])) {
            int cycleLength = i - seen.get(sequence[i]);
            System.out.println("Cycle detected after " + i + " steps with a cycle length of " + cycleLength + ".");
            return cycleLength;
        }
        seen.put(sequence[i], i);
    }
    System.out.println("No cycle detected in the given sequence.");
    return null;
}

5 — Optimize your solutions

What you can do now is to use AI tools such as GitHub Copilot or ChatGPT, either to generate the solution, or to improve the first solution you came up with! Try to do this for all exercises above, to see the differences with your solutions.

To go further

Looks like this section is empty!

Anything you would have liked to see here? Let us know on the Discord server! Maybe we can add it quickly. Otherwise, it will help us improve the course for next year!

To go beyond

6 — Incremental Pearson correlation coefficient

The Pearson correlation coefficient can be calculated incrementally, which can be useful when dealing with large datasets. The following article provides a good explanation of the incremental calculation of the Pearson correlation coefficient:

Tschumitschew, K., Klawonn, F. (2012). Incremental Statistical Measures. In: Sayed-Mouchaweh, M., Lughofer, E. (eds) Learning in Non-Stationary Environments. Springer, New York, NY. https://doi.org/10.1007/978-1-4419-8020-5_2

Implement the incremental Pearson correlation coefficient calculation and test it on the generated sequences.