Practical activity

Duration1h15

Presentation & objectives

In this activity, we provide exercises to familiarize with complexity and data structures. In a first exercise, we show how two algorithms for a same task can have distinct complexities. Then, we manipulate queues and stacks to solve problems.

Important

We provide you the solutions to the exercises. Make sure to check them only after you have a solution to the exercises, for comparison purpose! Even if you are sure your solution is correct, please have a look at them, as they sometimes provide additional elements you may have missed.

Activity contents

1 — 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 (e.g., 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 one is found, the number is not prime.

Write a function prime that does this calculation. Use the for loop to test all the divisors from 2 to (number - 1). The program will ask for an integer and indicate whether it is prime or not. It will also indicate the number of iterations carried out to obtain the result.

Also, state its algorithmic complexity.

Correction

Click here to reveal the answer.

def prime (n: int) -> bool:

    """
        This function tests if a number is prime or not.
        Complexity of the algorithm is O(N).
        In:
            * n: The number to be tested.
        Out:
            * True if the number is prime, False otherwise.
    """

    # Verfy input
    assert n >= 2

    # Test all dividers
    for i in range(2, n):
        if n % i == 0:
            return False
        
    # If we reach here, it is prime
    return True



# Test the function
for i in range(2, 20):
    print(i, "is prime" if prime(i) else "is not prime")

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This function tests if a number is prime or not.
     * The complexity of the algorithm is O(N).
     *
     * @param n The number to be tested.
     * @return True if the number is prime, False otherwise.
     */
    public static boolean prime(int n) {
        // Verify input
        if (n < 2) {
            throw new IllegalArgumentException("n must be greater than or equal to 2");
        }

        // Test all dividers
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                return false;
            }
        }

        // If we reach here, it is prime
        return true;
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Test the function
        for (int i = 2; i < 20; i++) {
            System.out.println(i + " is " + (prime(i) ? "prime" : "not prime"));
        }
    }

}

Improve this algorithm to minimize the number of calculations. 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 (e.g., 3, 5, 7). Also, it is useless to test divisors that go above the square root of the number.

Write a function prime2 which implements these improvements. The program will return whether the number is prime or not.

Indicate the algorithmic complexity as well.

Correction

Click here to reveal the answer.

# Needed imports
import math



def prime2 (n: int) -> bool:

    """
        This function tests if a number is prime or not.
        We distinguish the case of even numbers.
        Complexity of the algorithm is O(sqrt(N)/2).
        In:
            * n: The number to be tested.
        Out:
            * True if the number is prime, False otherwise.
    """

    # Verfy input
    assert n >= 2

    # Test if even
    if n % 2 == 0:
        return False

    # Test all dividers
    for i in range(3, math.sqrt(n), 2):
        if n % i == 0:
            return False
        
    # If we reach here, it is prime
    return True



# Test the function
for i in range(2, 20):
    print(i, "is prime" if prime(i) else "is not prime")

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This function tests if a number is prime or not.
     * We distinguish the case of even numbers.
     * The complexity of the algorithm is O(sqrt(N)/2).
     *
     * @param n The number to be tested.
     * @return True if the number is prime, False otherwise.
     */
    public static boolean prime2(int n) {
        // Verify input
        if (n < 2) {
            throw new IllegalArgumentException("n must be greater than or equal to 2");
        }

        // Test if even
        if (n % 2 == 0) {
            return n == 2;
        }

        // Test all dividers
        int sqrtN = (int) Math.sqrt(n);
        for (int i = 3; i <= sqrtN; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }

        // If we reach here, it is prime
        return true;
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Test the function
        for (int i = 2; i < 20; i++) {
            System.out.println(i + " is " + (prime2(i) ? "prime" : "not prime"));
        }
    }

}

2 — Calculate a postfix arithmetic expression

In this exercise we will use a stack to calculate an arithmetic expression in postfix notation, i.e., where each operator is preceded by its operands, such as 3 12 3 - 3 / 1 - *. The equivalent infix expression using parentheses is 3 * (((12 - 3) / 3) - 1).

Write the function evaluate_postfix that calculates the result of a postfix integer arithmetic expression. The program will ask for an arithmetic expression and return the final result.

The result of the calculation will be a real number.
The input is a sequence of characters.
Each piece of data is separated from the others by a space.
The method consists of using a stack to store the numerical values as they are read, and performing a processing operation when an operator is read.
This processing operation removes the last two values in the stack, performs the operation, and then pushes the result.
The final result is stored in the stack.
Allowed operators are +, -, *, /.

Correction

Click here to reveal the answer.

def evaluate_postfix (expression: str) -> float:

    """
        This function uses a stack to evaluate a postfix expression.
        The function takes a string as input, which is a postfix expression.
        The function returns the result of the expression.
        In:
            * expression: Expression to be evaluated.
        Out:
            * Evaluated of the evaluated expression.
    """

    # Create an empty stack
    stack = []

    # Iterate over the expression
    split_expression = expression.split(" ")
    for i in split_expression:

        # If the character is a number, push it to the stack
        if i.isnumeric():
            stack.append(int(i))
        
        # If the character is an operator, apply it
        else:

            # Pop the last two elements from the stack
            a = stack.pop()
            b = stack.pop()

            # Apply the operator
            if i == '+':
                stack.append(b + a)
            elif i == '-':
                stack.append(b - a)
            elif i == '*':
                stack.append(b * a)
            elif i == '/':
                stack.append(b / a)
    
    # Return the result
    return stack.pop()
    



# Test the function
print("(2 3 +) =", evaluate_postfix("2 3 +"))
print("(2 3 4 * +) =", evaluate_postfix("2 3 4 * +"))
print("(2 3 + 4 *) =", evaluate_postfix("2 3 + 4 *"))
print("(2 3 4 * + 5 -) =", evaluate_postfix("2 3 4 * + 5 -"))
print("(2 30 4 * + 5 - 6 +) =", evaluate_postfix("2 30 4 * + 5 - 6 +"))
print("(2 3 4 * / 5 - 6 - 7 +) =", evaluate_postfix("2 3 4 * / 5 - 6 - 7 +"))
print("(2 3 4 * + 5 - 6 + 7 + 8 +) =", evaluate_postfix("2 3 4 * + 5 - 6 + 7 + 8 +"))

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */

// Needed imports

import java.util.Stack;

public class Main {

    /**
     * This function uses a stack to evaluate a postfix expression.
     * The function takes a string as input, which is a postfix expression.
     * The function returns the result of the expression.
     *
     * @param expression Expression to be evaluated.
     * @return Evaluated result of the postfix expression.
     */
    public static double evaluatePostfix(String expression) {
        // Create an empty stack
        Stack<Double> stack = new Stack<>();

        // Iterate over the expression
        String[] splitExpression = expression.split(" ");
        for (String i : splitExpression) {

            // If the character is a number, push it to the stack
            if (i.matches("-?\\d+(\\.\\d+)?")) {
                stack.push(Double.parseDouble(i));
            }

            // If the character is an operator, apply it
            else {

                // Pop the last two elements from the stack
                double a = stack.pop();
                double b = stack.pop();

                // Apply the operator
                switch (i) {
                    case "+":
                        stack.push(b + a);
                        break;
                    case "-":
                        stack.push(b - a);
                        break;
                    case "*":
                        stack.push(b * a);
                        break;
                    case "/":
                        stack.push(b / a);
                        break;
                    default:
                        throw new IllegalArgumentException("Invalid operator: " + i);
                }
            }
        }

        // Return the result
        return stack.pop();
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Test the function
        System.out.println("(2 3 +) = " + evaluatePostfix("2 3 +"));
        System.out.println("(2 3 4 * +) = " + evaluatePostfix("2 3 4 * +"));
        System.out.println("(2 3 + 4 *) = " + evaluatePostfix("2 3 + 4 *"));
        System.out.println("(2 3 4 * + 5 -) = " + evaluatePostfix("2 3 4 * + 5 -"));
        System.out.println("(2 30 4 * + 5 - 6 +) = " + evaluatePostfix("2 30 4 * + 5 - 6 +"));
        System.out.println("(2 3 4 * / 5 - 6 - 7 +) = " + evaluatePostfix("2 3 4 * / 5 - 6 - 7 +"));
        System.out.println("(2 3 4 * + 5 - 6 + 7 + 8 +) = " + evaluatePostfix("2 3 4 * + 5 - 6 + 7 + 8 +"));
    }

}

To go further

Important

The content of this section is optional. It contains additional material for you to consolidate your understanding of the current topic.

3 — Convert infix expression to postfix expression

Write a function infix_to_prefix that converts an infix expression with integers (in brackets) to postfix notation. You will need to use both a stack and a queue.

For instance, the expression 3*(((12-3)/3)-1) will be converted to: 3 12 3 - 3 / 1 - *

The valid operators are +, -, * and /.
The algorithm reads an arithmetic infix expression and stores the result of the conversion in a queue, which is displayed.
The algorithm will use a stack to manage the operators, and a queue to construct the postfix expression.
The numeric values must be directly stored in the queue, while the operators must wait before adding them to the queue after their operands.
The treatment of an operator, poping then enqueuing, must occur when a closing parenthesis is encountered.
Also, beware of operators priority!

Correction

Click here to reveal the answer.

# Needed imports
import re



def infix_to_postfix (infix_expression: str) -> str:

    """
        This function uses a stack and a queue to transform an infix expression to a postfix expression.
        All expressions are supposed to be well parenthesized.
        In:
            * infix_expression: Expression to be transformed to postfix.
        Out:
            * Postfix expression equivalent to the input infix expression.
    """

    # Define the precedence of the operators
    precedence = {"*": 2, "/": 2, "+": 1, "-": 1, "(": 0, ")": 0}

    # Initialize the stack and the queue
    stack = []
    queue = []

    # Split the infix expression into tokens
    tokens = [t for t in re.split(r"(\+|\-|\*|\/|\(|\))", infix_expression) if t.strip() != ""]

    # Iterate over tokens
    for token in tokens:
        
        # If the token is an operand, add it to the queue
        if token.isnumeric():
            queue.append(token)

        # If the token is a left parenthesis, add it to the stack
        elif token == "(":
            stack.append(token)

        # If the token is a right parenthesis, pop all the operators from the stack and add them to the queue until a left parenthesis is found
        elif token == ")":
            while stack and stack[-1] != "(":
                queue.append(stack.pop())
            stack.pop()

        # If the token is an operator, pop all the operators from the stack with higher precedence and add them to the queue
        # Then, add the operator to the stack
        else:
            while stack and precedence[stack[-1]] >= precedence[token]:
                queue.append(stack.pop())
            stack.append(token)

    # Add the remaining operators to the queue
    while stack:
        queue.append(stack.pop())

    # Return the postfix expression
    return " ".join(queue)


# Test the function
print("3*(((12-3)/3)-1) transformed into", infix_to_postfix("3*(((12-3)/3)-1)"))
print("1+(2*3) transformed into", infix_to_postfix("1+(2*3)"))
print("(1+2)*3 transformed into", infix_to_postfix("(1+2)*3"))
print("3*(2+1) transformed into", infix_to_postfix("3*(2+1)"))

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */

// Needed imports

import java.util.Stack;
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

    /**
     * This function uses a stack and a queue to transform an infix expression to a postfix expression.
     * All expressions are supposed to be well parenthesized.
     *
     * @param infixExpression Expression to be transformed to postfix.
     * @return Postfix expression equivalent to the input infix expression.
     */
    public static String infixToPostfix(String infixExpression) {
        // Define the precedence of the operators
        var precedence = new java.util.HashMap<String, Integer>();
        precedence.put("*", 2);
        precedence.put("/", 2);
        precedence.put("+", 1);
        precedence.put("-", 1);
        precedence.put("(", 0);
        precedence.put(")", 0);

        // Initialize the stack and the queue
        Stack<String> stack = new Stack<>();
        List<String> queue = new ArrayList<>();

        // Split the infix expression into tokens
        Pattern pattern = Pattern.compile("(\\+|\\-|\\*|\\/|\\(|\\))");
        Matcher matcher = pattern.matcher(infixExpression);
        List<String> tokens = new ArrayList<>();
        int lastIndex = 0;
        while (matcher.find()) {
            if (matcher.start() > lastIndex) {
                tokens.add(infixExpression.substring(lastIndex, matcher.start()).trim());
            }
            tokens.add(matcher.group());
            lastIndex = matcher.end();
        }
        if (lastIndex < infixExpression.length()) {
            tokens.add(infixExpression.substring(lastIndex).trim());
        }

        // Iterate over tokens
        for (String token : tokens) {
            // If the token is an operand, add it to the queue
            if (token.matches("\\d+")) {
                queue.add(token);
            }

            // If the token is a left parenthesis, add it to the stack
            else if (token.equals("(")) {
                stack.push(token);
            }

            // If the token is a right parenthesis, pop all the operators from the stack and add them to the queue until a left parenthesis is found
            else if (token.equals(")")) {
                while (!stack.isEmpty() && !stack.peek().equals("(")) {
                    queue.add(stack.pop());
                }
                stack.pop();
            }

            // If the token is an operator, pop all the operators from the stack with higher precedence and add them to the queue
            // Then, add the operator to the stack
            else {
                while (!stack.isEmpty() && precedence.get(stack.peek()) >= precedence.get(token)) {
                    queue.add(stack.pop());
                }
                stack.push(token);
            }
        }

        // Add the remaining operators to the queue
        while (!stack.isEmpty()) {
            queue.add(stack.pop());
        }

        // Return the postfix expression
        return String.join(" ", queue);
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Test the function
        System.out.println("3*(((12-3)/3)-1) transformed into " + infixToPostfix("3*(((12-3)/3)-1)"));
        System.out.println("1+(2*3) transformed into " + infixToPostfix("1+(2*3)"));
        System.out.println("(1+2)*3 transformed into " + infixToPostfix("(1+2)*3"));
        System.out.println("3*(2+1) transformed into " + infixToPostfix("3*(2+1)"));
    }

}

To go beyond

Important

The content of this section is very optional. We suggest you directions to explore if you wish to go deeper in the current topic.

4 — Compute the Graham convex hull

The Graham scan algorithm is a computational geometry method used to find the convex hull of a set of points in a 2D plane, with complexity O(n log n). The convex hull is the smallest convex polygon that can enclose all the given points. It uses a stack to detect and remove concavities in the boundary efficiently.

Write the graham algorithm which takes:

as input: a set of n points in the plane, each represented by its coordinates (abscissa and ordinate).
as output: a list of points that are the vertices of the polygon surrounding the convex envelope, in the order in which they appear on this polygon.

You must follow the steps of the Graham algorithm:

Find the point with the lowest y-coordinate. If there are multiple points with the same lowest y-coordinate, choose the one with the lowest x-coordinate. This point is called the pivot point.
Sort the set of points in increasing order of the angle they and the pivot point make with the x-axis. Any general-purpose sorting algorithm is appropriate for this.
Iterate through the sorted list of points to construct the convex hull: We start with the pivot. Then the sorted points are examined. For each point, we first determine whether travelling from the two points immediately preceding this point is a left turn (counter-clockwise orientation) or a right turn (clockwise orientation).

In the case of a right turn, this means that the point that ended the polygon being created (the point in red) is to the left of the segment formed by the penultimate point of the polygon being created and the point under consideration (the point in black). In this case, the last point (the one in red) is not part of the convex envelope and must therefore be rejected. These rejections are repeated as long as there is a ‘right turn’.
If the algorithm encounters a ‘left turn’, it moves on to the next point in the sorted array.

Determining whether three points constitute a “left turn” or a “right turn” does not require computing the actual angle between the two line segments, and can be achieved with simple arithmetic only. For three points (x1, y1), (x2, y2) and (x3, y3), simply calculate the direction of the vector product of the two vectors defined by the points (x1, y1), (x2, y2) and (x1, y1), (x3, y3), given by the sign of the expression (x2 - x1)(y3 - y1) - (y2 - y1)(x3 - x1):

If the result is zero, the points are aligned.
If it is positive, the three points form a ‘left turn’ or counter-clockwise orientation.
If the result is negative, it is a ‘right turn’ or clockwise orientation.