Practical activity

Duration1h15

Presentation & objectives

Below is a list of exercises for experimenting with building algorithms focusing on loop construction. The topic is the manipulation of strings. Similar to lists/arrays, strings can be iterated over, and can be seen as a collection of characters.

Once your algorithms designed, it is recommended to code them in Python to be able to test theim. However, if you do not feel confident with Python so far, you can simply write them on a sheet of paper and test them by hand.

When testing your algorithms, try to think of cases that cover all possible results. For instance, if your algorithm should output true or false, try it for inputs that lead to both cases.

Important

The aim of this session is to help you master the basics of algorithms and programming by tackling very classic and simple problems. An intelligent programming assistant such as GitHub Copilot, that you may have installed already, will be able to provide you with a solution to these exercises based only on a wisely chosen file name. So, for the sake of training, we advise you to postpone the discovery of Copilot’s functionalities for now.

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 — Last occurrence

Start with the following program:

​
# The string to manipulate
s = "IMT Atlantique"
print(s)

# Write your codes here
# ...
/**
 * 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 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) {
        // The string to manipulate
        String s = "IMT Atlantique";
        System.out.println(s);

        // Write your codes here
        // ...
    }

}

Conceive an algorithm that determines the position (between 0 and the length of s minus 1) of the last occurrence of a symbol in the string s. The searched symbol is stored in a variable named v. The algorithm displays the position found or indicates if the symbol is not present in s.

Correction
​
# The string to manipulate
s = "IMT Atlantique"
print(s)

# The thing to search
v = 'l'

# Iterate from the end to the start
found = False
for result in reversed(range(len(s))):

    # Stop when found
    if s[result] == v:
        print("Found at index", result)
        found = True
        break

# Print a message if not found
if not found:
    print("Not found")
# The string to manipulate
s = "IMT Atlantique"
print(s)

# The thing to search
v = 'l'

# Use string method to find last occurrence
result = s.rfind(v)

# Print result
if result != -1:
    print("Found at index", result)
else:
    print("Not found")
/**
 * 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 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) {
        // The string to manipulate
        String s = "IMT Atlantique";
        System.out.println(s);

        // The thing to search
        char v = 'l';

        // Iterate from the end to the start
        boolean found = false;
        for (int i = s.length() - 1; i >= 0; i--) {
            // Stop when found
            if (s.charAt(i) == v) {
                System.out.println("Found at index " + i);
                found = true;
                break;
            }
        }

        // Print a message if not found
        if (!found) {
            System.out.println("Not found");
        }
    }

}
/**
 * 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 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) {
        // The string to manipulate
        String s = "IMT Atlantique";
        System.out.println(s);

        // The thing to search
        char v = 'l';

        // Use string method to find last occurrence
        int result = s.lastIndexOf(v);

        // Print result
        if (result != -1) {
            System.out.println("Found at index " + result);
        } else {
            System.out.println("Not found");
        }
    }

}

2 — First occurrence

Start again with the same base code as in exercise 1.

Conceive an algorithm that determines the position (between 0 and the length of s minus 1) of the first occurrence of a symbol in the string s. The searched symbol is stored in a variable named v. The algorithm displays the position found or indicates if the symbol is not present in s.

Correction
​
# The string to manipulate
s = "IMT Atlantique"
print(s)

# The thing to search
v = 'l'

# Iterate from the start to the end
found = False
for result in range(len(s)):

    # Stop when found
    if s[result] == v:
        print("Found at index", result)
        found = True
        break

# Print a message if not found
if not found:
    print("Not found")
# The string to manipulate
s = "IMT Atlantique"
print(s)

# The thing to search
v = 'l'

# Use string method to find first occurrence
result = s.find(v)

# Print result
if result != -1:
    print("Found at index", result)
else:
    print("Not found")
/**
 * 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 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) {
        // The string to manipulate
        String s = "IMT Atlantique";
        System.out.println(s);

        // The thing to search
        char v = 'l';

        // Iterate from the start to the end
        boolean found = false;
        for (int i = 0; i < s.length(); i++) {
            // Stop when found
            if (s.charAt(i) == v) {
                System.out.println("Found at index " + i);
                found = true;
                break;
            }
        }

        // Print a message if not found
        if (!found) {
            System.out.println("Not found");
        }
    }

}
/**
 * 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 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) {
        // The string to manipulate
        String s = "IMT Atlantique";
        System.out.println(s);

        // The thing to search
        char v = 'l';

        // Use string method to find first occurrence
        int result = s.indexOf(v);

        // Print result
        if (result != -1) {
            System.out.println("Found at index " + result);
        } else {
            System.out.println("Not found");
        }
    }

}

3 — Prefix

Start again with the same base code as in exercise 1.

Considering a second array of characters, named pref for instance, determine if pref is a prefix of s. Carefully think about the different possible scenarios related to the lengths of s and pref. The algorithm prints if pref is a prefix of s.

Correction
​
# The string to manipulate
s = "IMT Atlantique"
print(s)

# The thing to search
pref = "IMT"

# Cannot be a prefix if longer than the string
if len(pref) > len(s):
    print(pref, "is not a prefix of", s)

# Otherwise, we test the prefix
else:

    # Iterate from the start to the end
    aborted = False
    for i in range(len(pref)):
        if pref[i] != s[i]:
            print(pref, "is not a prefix of", s)
            aborted = True
            break

    # Print a message if all is right
    if not aborted:
        print(pref, "is a prefix of", s)
# The string to manipulate
s = "IMT Atlantique"
print(s)

# The thing to search
pref = "IMT"

# Use string method for that
if s.startswith(pref):
    print(pref, "is a prefix of", s)
else:
    print(pref, "is not a prefix of", s)
/**
 * 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 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) {
        // The string to manipulate
        String s = "IMT Atlantique";
        System.out.println(s);

        // The thing to search
        String pref = "IMT";

        // Cannot be a prefix if longer than the string
        if (pref.length() > s.length()) {
            System.out.println(pref + " is not a prefix of " + s);
        }

        // Otherwise, we test the prefix
        else {
            // Iterate from the start to the end
            boolean aborted = false;
            for (int i = 0; i < pref.length(); i++) {
                if (pref.charAt(i) != s.charAt(i)) {
                    System.out.println(pref + " is not a prefix of " + s);
                    aborted = true;
                    break;
                }
            }

            // Print a message if all is right
            if (!aborted) {
                System.out.println(pref + " is a prefix of " + s);
            }
        }
    }

}
/**
 * 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 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) {
        // The string to manipulate
        String s = "IMT Atlantique";
        System.out.println(s);

        // The thing to search
        String pref = "IMT";

        // Use string method for that
        if (s.startsWith(pref)) {
            System.out.println(pref + " is a prefix of " + s);
        } else {
            System.out.println(pref + " is not a prefix of " + s);
        }
    }

}

4 — Contains

Start again with the same base code as in exercise 1.

Considering a second array of characters, named substr for instance, determine if substr is present in s. The algorithm indicates the position of the first occurrence of substr in s or whether it is not present.

Correction
​
# The string to manipulate
s = "IMT Atlantique"
print(s)

# The thing to search
substr = "Atlan"

# Iterate to check substring start
found = False
for i in range(len(s) - len(substr) + 1):

    # Stop when found
    if s[i:i + len(substr)] == substr:
        print("Substring found at index", i)
        found = True
        break

# Print a message if not found
if not found:
    print("Substring not found")
# The string to manipulate
s = "IMT Atlantique"
print(s)

# The thing to search
substr = "Atlan"

# You can directly check with 'in' keyword
if substr in s:
    print("Substring found at index", s.index(substr))
else:
    print("Substring not found")
/**
 * 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 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) {
        // The string to manipulate
        String s = "IMT Atlantique";
        System.out.println(s);

        // The thing to search
        String substr = "Atlan";

        // Iterate to check substring start
        boolean found = false;
        for (int i = 0; i <= s.length() - substr.length(); i++) {
            // Stop when found
            if (s.substring(i, i + substr.length()).equals(substr)) {
                System.out.println("Substring found at index " + i);
                found = true;
                break;
            }
        }

        // Print a message if not found
        if (!found) {
            System.out.println("Substring not found");
        }
    }

}
/**
 * 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 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) {
        // The string to manipulate
        String s = "IMT Atlantique";
        System.out.println(s);

        // The thing to search
        String substr = "Atlan";

        // Use string method for that
        if (s.contains(substr)) {
            System.out.println("Substring found at index " + s.indexOf(substr));
        } else {
            System.out.println("Substring not found");
        }
    }

}

5 — Reverse

Start again with the same base code as in exercise 1.

Determine an algorithm that reverses the content of string s.

Correction
​
# The string to manipulate
s = "IMT Atlantique"
print(s)

# Loop to append to a new string
result = ""
for i in range(len(s)):
    result = s[i] + result

# Print the result
print("Reversed string:", result)
# The string to manipulate
s = "IMT Atlantique"
print(s)

# Using operator []
result = s[::-1]

# Print the result
print("Reversed string:", result)
/**
 * 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 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) {
        // The string to manipulate
        String s = "IMT Atlantique";
        System.out.println(s);

        // Loop to append to a new string
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            result = s.charAt(i) + result;
        }

        // Print the result
        System.out.println("Reversed string: " + result);
    }

}
/**
 * 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 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) {
        // The string to manipulate
        String s = "IMT Atlantique";
        System.out.println(s);

        // Using StringBuilder for reversing a string
        String result = new StringBuilder(s).reverse().toString();

        // Print the result
        System.out.println("Reversed string: " + result);
    }

}

6 — Palindrome

A palindrome is a word that can be read from both sides, as for instance “radar” or “laval”. Determine a first naive strategy to check if a string is a palindrome based on the reverse algorithm devised earlier.

Correction
​
# The string to manipulate
s = "laval"
print(s)

# Loop to check characters from start and end
is_palindrome = True
for i in range(len(s)//2):

    # Stop if a difference is found
    if s[i] != s[-i-1]:
        print(s, "is not a palindrome")
        is_palindrome = False
        break

# Print a message if ok
if is_palindrome:
    print(s, "is a palindrome")
# The string to manipulate
s = "laval"
print(s)

# Check if s is a palindrome
if s == s[::-1]:
    print(s, "is a palindrome")
else:
    print(s, "is not a palindrome")
/**
 * 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 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) {
        // The string to manipulate
        String s = "laval";
        System.out.println(s);

        // Loop to check characters from start and end
        boolean isPalindrome = true;
        for (int i = 0; i < s.length() / 2; i++) {
            // Stop if a difference is found
            if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
                System.out.println(s + " is not a palindrome");
                isPalindrome = false;
                break;
            }
        }

        // Print a message if ok
        if (isPalindrome) {
            System.out.println(s + " is a palindrome");
        }
    }

}
/**
 * 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 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) {
        // The string to manipulate
        String s = "laval";
        System.out.println(s);

        // Check if s is a palindrome using StringBuilder
        if (s.equals(new StringBuilder(s).reverse().toString())) {
            System.out.println(s + " is a palindrome");
        } else {
            System.out.println(s + " is not a palindrome");
        }
    }

}

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.

7 — Hexadecimal

Consider a string representing a number in an hexadecimal format. Calculate its decimal value.

As a recall, an hexadecimal number may contain the following digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. ‘A’ is equal to 10, and so on.

A built-in solution exists in Python (and in other languages) to solve this problem but try to work with loops to familiarize with their use. It is assumed that every symbol in the string to be converted is an acceptable digit in hexadecimal format.

Correction
​
# Value to convert
s = "28F"

# Table of conversion
hexa_to_decimal = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9, 'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15}

# Iterate over the hexadecimal string
result = 0
for i in range(len(s)):
    power = len(s) - i - 1
    result += hexa_to_decimal[s[i]] * (16 ** power)

# Print the result
print("Decimal version of", s, "is", result)
# Value to convert
s = "28F"

# Convert into decimal
result = int(s, 16)
print("Decimal version of", s, "is", result)
/**
 * 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.Map;
import java.util.HashMap;

public class Main {

    /**
     * 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) {
        // Value to convert
        String s = "28F";

        // Table of conversion
        Map<Character, Integer> hexaToDecimal = new HashMap<>();
        hexaToDecimal.put('0', 0);
        hexaToDecimal.put('1', 1);
        hexaToDecimal.put('2', 2);
        hexaToDecimal.put('3', 3);
        hexaToDecimal.put('4', 4);
        hexaToDecimal.put('5', 5);
        hexaToDecimal.put('6', 6);
        hexaToDecimal.put('7', 7);
        hexaToDecimal.put('8', 8);
        hexaToDecimal.put('9', 9);
        hexaToDecimal.put('A', 10);
        hexaToDecimal.put('B', 11);
        hexaToDecimal.put('C', 12);
        hexaToDecimal.put('D', 13);
        hexaToDecimal.put('E', 14);
        hexaToDecimal.put('F', 15);

        // Iterate over the hexadecimal string
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            int power = s.length() - i - 1;
            result += (int) (hexaToDecimal.get(s.charAt(i)) * Math.pow(16, power));
        }

        // Print the result
        System.out.println("Decimal version of " + s + " is " + result);
    }

}
/**
 * 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 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) {
        // Value to convert
        String s = "28F";

        // Convert into decimal using Java's built-in method
        int result = Integer.parseInt(s, 16);
        System.out.println("Decimal version of " + s + " is " + result);
    }

}

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.

8 — Check invariants

Coding and testing loops with a few, even wisely selected, cases is not enough to ensure that your algorithm will always returns the expected result. Using mathematical induction, check the correctness of the iterations you have conceived during this activity.

9 — Optimize your solutions

What you can also do 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.