Practical activity
Duration2h30Presentation & objectives
Here are a few exercises to make you manipulate simple programs and your IDE.
During these activity, please pay attention to the good programming practices you studied earlier. These are good reflexes to acquire quickly.
For each exercise, we ask you to show your solution to another student, so that they can give you remarks on readability.
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.
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 — The interactive Python interpreter
Consider the following Python code (that you wrote during the practical activity of algorithmics session 1) that simply reverses a string.
# 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)/**
* 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);
}
}Open a terminal (within the VSCode IDE if you want) and start an interactive Python interpreter. Then, run statement by statement the code above. What does the output look like?
Create a new file within you IDE and paste the same code in it. Then, run the entire file using the non-interactive Python interpreter (use the Run button in VSCode). What does the output look like?
2 — Fixing syntactic bugs
The following code contains a syntax error. Use the Error tab of your IDE find the location of the error. What does it say?
# The string to manipulate
s = "IMT Atlantique"
print(s)
# Loop to append to a new string
result = ""
for i j in range(len(s)):
result = s[i] + result
# 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 j = 0; i < s.length(); i++) {
result = s.charAt(i) + result;
}
// Print the result
System.out.println("Reversed string: " + result);
}
}3 — Fixing semantic bugs
Here is a code that is syntactically correct:
# Needed imports
import random
# Fill a list with 10 random numbers
numbers = []
for i in range(10):
numbers.append(random.randint(-50, 50))
# Let's do the following operation 50 times
for i in range(50):
# Divide each number by the subtraction of the two next numbers in the list
for j in range(len(numbers) - 2):
numbers[j] /= numbers[j + 1] - numbers[j + 2]
# Print the final list
print("Final list", numbers)/**
* 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.ArrayList;
import java.util.List;
import java.util.Random;
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) {
// Use a random number generator
Random random = new Random();
// Fill a list with 10 random numbers
List<Double> numbers = new ArrayList<>();
for (int i = 0; i < 10; i++) {
numbers.add((double) (random.nextInt(101) - 50));
}
// Let's do the following operation 50 times
for (int k = 0; k < 50; k++) {
// Divide each number by the subtraction of the two next numbers in the list
for (int j = 0; j < numbers.size() - 2; j++) {
numbers.set(j, numbers.get(j) / (numbers.get(j + 1) - numbers.get(j + 2)));
}
}
// Print the final list
System.out.println("Final list " + numbers);
}
}However, when running it, we get the following output:
Traceback (most recent call last):
File "session_1.py", line 14, in <module>
numbers[j] /= numbers[j + 1] - numbers[j + 2]
ZeroDivisionError: float division by zeroFinal list [0.0, 0.0, -Infinity, 0.0, 0.0, Infinity, 5.139385345176833E-80, 2.240361480978435E-62, -41.0, -23.0]Here, no error is raised, but the values Infinity and -Infinity indicate that the division by zero was not handled correctly.
3.1 — Using prints
Using the print command, try to find the error.
Now, use the step-by-step debugger of VSCode to debug the same program. How do you do it?
4 — Step-by-step programming
You are going to implement a Monte Carlo strategy to estimate the value of $\pi$. The principle illustrated in the figure below is to generate pseudo-randomly the Cartesian coordinates of points located in the unit subspace, the dark cyan square. Considering $N$ pseudo-randomly generated points, the ratio between the number of points located in the top right-hand quarter of the disc and the total number of points generated is an estimate of $\frac{\pi}{4}$.
To determine if a point falls in the top right-hand quarter of the disc, one just has to compute its Euclidean distance from the origin. If this distance is less than 1, it is in the disc. As a recall, for a point whose coordinates are $(x,y)$, the distance from origin is computed as follows: $\sqrt{x^2 + y^2}$.
4.1 — Get your tools
To estimate $\pi$, you need a few programming tools:
-
A random number generator, and a method of that generator to obtain a number in the $[0, 1]$ interval. Find the correct method in the documentation of the
randommodule. -
A method to compute the square root of a value. Find the correct method in the documentation of the
mathmodule.
You will ask through a prompt the number of points to generate (the value to assign to N).
Let’s follow some steps to reach a functioning program.
4.2 — Split your algorithm into pieces
A complete source code is always written step-by-step, and each step tested. It is clearly the best and only way to efficiency reach the objective. So, in your opinion, what should we do?
Implement this algorithm one step after the other, and use the print statement to check that every step seems correct.
Varying the value of $N$, observe the precision of the estimate of $\pi$ obtained.
5 — A classical sorting problem
Sorting an array of values according to an ordering relation is a very classical algorithmic problem. It is often used to empirically discover theoretical concepts such as termination, complexity, etc.
The selection sort algorithm is very easy to understand. Consider you have a set of unsorted cards in your right hand and that you progressively construct a sorted permutation of these cards in your left hand. The selection sort strategy is to first select the card with the lowest value in your right hand and to place it in the first position in your left hand. You then do the same with the card having the second lowest value, and so on.
Identifies the different steps to finally have a program that generates an array of size N composed of randomly generated values, then sorts by selection this array and checks that the array is indeed sorted.
Then write a function that performs that sort.
A slight variation of the algorithm consists in positioning the lowest and largest value at the same time, the second lowest and the second largest, and so on. Implement this strategy in a new function.
Use the script given below to compare the time taken by these two solutions to sort a same list. Compute and display the mean time on 10 executions for different sizes of arrays (up to $10^4$).
# Needed imports
import random
import time
import matplotlib.pyplot as plt
import tqdm
import itertools
# Constants
sizes_to_test = [10**i for i in range(1, 5)]
number_of_tests = 10
# We will store the results in a dictionary
results = {"selection_sort": {size: [] for size in sizes_to_test},
"selection_sort_2": {size: [] for size in sizes_to_test},
"built-in": {size: [] for size in sizes_to_test}}
# Loop for each pair test/size
# We use tqdm to display a progress bar
configurations = itertools.product(range(number_of_tests), range(len(sizes_to_test)))
nb_configurations = number_of_tests * len(sizes_to_test)
for i, (i_test, i_size) in enumerate(tqdm.tqdm(configurations, total=nb_configurations, desc="Tests")):
# Set the seed to the loop index for reproducibility while guaranteeing a different list each time
random.seed(i)
l = [random.randint(0, 100) for j in range(sizes_to_test[i_size])]
# Compare the two functions
for function in [selection_sort, selection_sort_2]:
# We use time.process_time() instead of time.time() to measure the CPU time instead of the wall time, which may include other processes
t0 = time.process_time()
result = function(l)
elapsed_time = time.process_time() - t0
# Store the result
results[function.__name__][sizes_to_test[i_size]].append(elapsed_time)
# Compare with the built-in function
t0 = time.process_time()
result = sorted(l)
elapsed_time = time.process_time() - t0
results["built-in"][sizes_to_test[i_size]].append(elapsed_time)
# Plot the average time as a function of the size
plt.figure(figsize=(10, 6))
for function_name in results:
average_times = [sum(results[function_name][size]) / number_of_tests for size in sizes_to_test]
plt.plot(sizes_to_test, average_times, label=function_name)
plt.xlabel("Size of the list")
plt.ylabel("Average CPU time (s)")
plt.xscale("log")
plt.yscale("log")
plt.legend()
plt.show()/**
* 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.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
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) {
// Define the constants
List<Integer> sizesToTest = Arrays.asList(10, 100, 1000, 10000);
int numberOfTests = 10;
// Initialize random number generator
Random random = new Random();
// We will store the results in a map
Map<String, Map<Integer, List<Long>>> results = new HashMap<>();
results.put("selection_sort", new HashMap<>());
results.put("selection_sort_2", new HashMap<>());
results.put("built-in", new HashMap<>());
for (int size : sizesToTest) {
results.get("selection_sort").put(size, new ArrayList<>());
results.get("selection_sort_2").put(size, new ArrayList<>());
results.get("built-in").put(size, new ArrayList<>());
}
// Loop for each pair test/size
for (int i = 0; i < numberOfTests; i++) {
for (int size : sizesToTest) {
// Set the seed to the loop index for reproducibility
random.setSeed(i);
List<Integer> l = new ArrayList<>();
for (int j = 0; j < size; j++) {
l.add(random.nextInt(101));
}
// Compare the two functions
for (String functionName : Arrays.asList("selection_sort", "selection_sort_2")) {
// Sort
long t0 = System.nanoTime();
if (functionName.equals("selection_sort")) {
List<Integer> result = selectionSort(l);
} else {
List<Integer> result = selectionSort2(l);
}
long elapsedTime = System.nanoTime() - t0;
// Store the result
results.get(functionName).get(size).add(elapsedTime);
}
// Compare with the built-in function
long t0 = System.nanoTime();
l.sort(Integer::compareTo);
long elapsedTime = System.nanoTime() - t0;
results.get("built-in").get(size).add(elapsedTime);
}
}
// Print results (since Java does not have a built-in graphing library like matplotlib)
for (String functionName : results.keySet()) {
System.out.println("Function: " + functionName);
for (int size : sizesToTest) {
List<Long> times = results.get(functionName).get(size);
double averageTime = times.stream().mapToLong(Long::longValue).average().orElse(0);
System.out.println("Size: " + size + ", Average Time: " + averageTime + " ns");
}
System.out.println();
}
}
}Here is the obtained plot:
Notice how the built-in sorted function is much faster!
This function uses a more advanced algorithm called Powersort.
Also, when calling sorted, the interpreter calls a compiled version of the sorting function in the background.
Therefore, it can directly be interpreted as binary code by your computer, and is therefore a lot faster.
Most of Python built-in functions (and those of libraries) use the same trick, so it is always better to use them rather than reinvent the wheel. The fewer loops you write, the faster your Python code!
To go further
6 — Respecting conventions
Refactor the following code to respect good programming practices.
- Convert code that is used multiple times into a function (if you already know about functions, which are otherwise seen in session 2. If you don’t know about them, forget about the root of 144).
- Use semantically meaningful names for variables and functions.
For example, the function for calculating the square root of a number is usually called
sqrt. We suggest to use this conventional name for your function. - Combine repeated prints into a single print call.
- Following the Python naming convention, use
snake_casefor names of variables and functions.
# Let us calculate some square roots, using Heron's method
# Calculate square root of 36
x = 36
n = 1
for _ in range(10):
n = (n + x/n) * 0.5
print("Square root of ")
print(x)
print(" is ")
print(n)
# Calculate square root of 144
x = 144
n = 1
for _ in range(10):
n = (n + x/n) * 0.5
print("Square root of ")
print(x)
print(" is ")
print(n)/**
* In Java, the entry point of a program is the 'main' function, in the 'Main' class, in a file named 'Main.java'.
* To enable asserts, you should compile your program with `javac Main.java`.
* Then, run it with the command `java -ea Main`.
*/
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)
{
// Calculate square root of 36
double x = 36;
double n = 1;
for (int i = 0; i < 10; i++)
{
n = (n + x / n) * 0.5;
}
System.out.print("Square root of ");
System.out.println(x);
System.out.print(" is ");
System.out.println(n);
// Calculate square root of 144
x = 144;
n = 1;
for (int i = 0; i < 10; i++)
{
n = (n + x / n) * 0.5;
}
System.out.print("Square root of ");
System.out.println(x);
System.out.print(" is ");
System.out.println(n);
}
}7 — A classical sorting problem (again)
Design an algorithm based on sorting comparisons that satisfies the following invariant:
After
iiterations of the inner loop, theihighest values of the listlof sizeNare sorted in an ascending order in the right side ofl.
At each iteration, the first value of the array (index 0) is moved by swapping neighbours to the right until a highest value is found. In this case, it is this highest value that is moved to the right side of the array. An inner loop is used to apply the previous process until no more swaps can be performed anymore.
The correction, with music and images!
Here is a code to implement this sorting algorithm, called the “bubble sort”:
# Needed imports
import random
from typing import List
from numbers import Number
def bubble_sort (l: List[Number]) -> List[Number]:
"""
This function takes a list of numbers and sorts them in ascending order using the bubble sort algorithm.
In:
* l: A list of numbers to be sorted.
Out:
* A sorted list of numbers.
"""
# Initialize a new list
sorted_l = l.copy()
# Loop through the list to sort it
for i in range(len(sorted_l)):
# Loop through the list to compare elements
for j in range(len(sorted_l) - 1):
# Swap elements if they are not in the right order
if sorted_l[j] > sorted_l[j + 1]:
sorted_l[j], sorted_l[j + 1] = sorted_l[j + 1], sorted_l[j]
# Return the sorted list
return sorted_l
# Set the seed
random.seed(42)
# Test the function
print(bubble_sort([random.randint(0, 100) for i in range(10)]))/**
* 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.ArrayList;
import java.util.List;
import java.util.Random;
public class Main {
/**
* This function takes a list of numbers and sorts them in ascending order using the bubble sort algorithm.
*
* @param l A list of numbers to be sorted.
* @return A sorted list of numbers.
*/
public static List<Integer> bubbleSort(List<Integer> l) {
// Initialize a new list
List<Integer> sortedL = new ArrayList<>(l);
// Loop through the list to sort it
for (int i = 0; i < sortedL.size(); i++) {
// Loop through the list to compare elements
for (int j = 0; j < sortedL.size() - 1; j++) {
// Swap elements if they are not in the right order
if (sortedL.get(j) > sortedL.get(j + 1)) {
int temp = sortedL.get(j);
sortedL.set(j, sortedL.get(j + 1));
sortedL.set(j + 1, temp);
}
}
}
// Return the sorted list
return sortedL;
}
/**
* 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) {
// Use a random number generator
Random random = new Random();
// Set the seed
random.setSeed(42);
// Test the function
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(random.nextInt(101));
}
// Print the sorted list
System.out.println(bubbleSort(list));
}
}If we add it to the time comparison, we obtain the following plot:
A slight improvement may certainly be applied on your algorithm to reduce the numbers of swaps. Try to find out what can be improved and compare the two versions according to the time they take to sort the same array.
Here is a possible code that implements two optimizations:
-
Introduce a flag to detect if the list is already sorted – This allows the algorithm to stop early if no swaps are made during a pass, meaning the list is already sorted.
-
Reduce the range of the inner loop – With each pass, the largest element is bubbled to the correct position, so the range of the inner loop can be reduced with each iteration.
# Needed imports
import random
from typing import List
from numbers import Number
def bubble_sort_2 (l: List[Number]) -> List[Number]:
"""
This function takes a list of numbers and sorts them in ascending order using the bubble sort algorithm.
In:
* l: A list of numbers to be sorted.
Out:
* A sorted list of numbers.
"""
# Initialize a new list
sorted_l = l.copy()
# Loop through the list to sort it
n = len(sorted_l)
for i in range(n):
# Flag to detect if any swap was made during this pass
swapped = False
# Loop through the list to compare elements
for j in range(0, n - i - 1):
# Swap elements if they are not in the right order
if sorted_l[j] > sorted_l[j + 1]:
sorted_l[j], sorted_l[j + 1] = sorted_l[j + 1], sorted_l[j]
swapped = True
# If no swaps were made, the list is already sorted
if not swapped:
break
# Return the sorted list
return sorted_l
# Set the seed
random.seed(42)
# Test the function
print(bubble_sort_2([random.randint(0, 100) for i in range(10)]))/**
* 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.ArrayList;
import java.util.List;
import java.util.Random;
public class Main {
/**
* This function takes a list of numbers and sorts them in ascending order using the bubble sort algorithm.
*
* @param l A list of numbers to be sorted.
* @return A sorted list of numbers.
*/
public static List<Integer> bubbleSort2(List<Integer> l) {
// Initialize a new list
List<Integer> sortedL = new ArrayList<>(l);
// Loop through the list to sort it
int n = sortedL.size();
for (int i = 0; i < n; i++) {
// Flag to detect if any swap was made during this pass
boolean swapped = false;
// Loop through the list to compare elements
for (int j = 0; j < n - i - 1; j++) {
// Swap elements if they are not in the right order
if (sortedL.get(j) > sortedL.get(j + 1)) {
int temp = sortedL.get(j);
sortedL.set(j, sortedL.get(j + 1));
sortedL.set(j + 1, temp);
swapped = true;
}
}
// If no swaps were made, the list is already sorted
if (!swapped) {
break;
}
}
// Return the sorted list
return sortedL;
}
/**
* 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) {
// Use a random number generator
Random random = new Random();
// Set the seed
random.setSeed(42);
// Test the function
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(random.nextInt(101));
}
// Print the sorted list
System.out.println(bubbleSort2(list));
}
}If we add it to the time comparison, we obtain the following plot:
How can you visualize this invariant using a step-by-step debugger?
To go beyond
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 — Compare sorting algorithms
There are many other sorting algorithms in existence. You can for instance check this link. Try coding a few of them and compare their performance on various list sizes.
9 — Optimize your solutions
What you can now 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.