Algorithms and Data Structures 2025/2026 (L.EIC011) - DCC/FCUP & DEI/FEUP

Practical Class #01 - Mooshak Introduction and Invariants
(22/09 to 26/09)

Exercises for submission

For the continuous evaluation component involving exercise-solving during the semester, the exercises you can submit in this class are:

• [AED001] Forty-Two (weight 20%) (main exercises)
• [AED002] Unlucky Numbers (weight 40%) (main exercises)
• [AED003] Space Oddity (weight 40%) (main exercises)
• [AED004] Bart's Math Problem (weight 40%) (extra exercises)
• [AED005] Number Spiral (weight 40%) (challenge exercises)

Submission Deadline: October 11th (submit to AED's Mooshak)

You are encouraged to talk to the professor and to your colleagues if you have difficulties. However, any more direct help you have received from other colleagues or LLMs should be acknowledged in the comments of the code you submit.
After the deadline the problems will still be available on Mooshak, but the submissions will not count towards your grade.
Each class is worth 9 per cent of the grade for this component. As there will be 12 classes with submissions, you can get full marks even if you haven't done everything.
For a problem to count, you have to get all the tests right (i.e. accepted). Even if you solve all the problems, the maximum in a single class is 100 per cent.
It is guaranted that the main exercises on each class will sum to at least 100% of the class grade.

Lectures Content

This class includes exercises about invariants. It is therefore convenient that you know what was discussed on the lectures:

• Slides: 1 - Invariants

1. My first Mooshak submissions

On this course we will use Mooshak to automatically evaluate your C++ code (see Mooshak's help).

• For all your submissions you can visualize the detailed result obtained in each of the test cases made. It is also possible to access any public tests for which your program did not receive the Accepted veredict. For seeing all this detailed feedback you only need to click the result of your submission that appears underlined in the listing.

  To access the system you can use your login (with the word "up") and password that was sent to your institutional email (message sent on the 21st of September with the title "[AED] Mooshak password - login")
  (if you have trouble accessing it, send a message on discord to @Pedro Ribeiro | your practical class professors also know your passwords)

• We will not enforce any editor on this course. We do however advise you to use an editor that is available on your computer labs, so that you get acquainted to the environment you will have available on the practice test days (which will be in Linux). We suggest you use VScode (or CLion). You should already know how to compile and run C++ code from your previous courses, but if you need any help you can ask in Discord.

In this problem the goal is to make your first submissions in Mooshak, all for the [AED001] Forty-Two. The problem statements will also be available inside Mooshak. Always start by carefully reading the problem statement given!

1. Start by submitting an Accepted in Mooshak. You can use the following example code given in aed001.cpp (see html version) to get you started (you can right click the file name and save it on a suitable directory). The file is already correct and you can submit it directly 🙂
• You can experiment on your own computer with the provided input examples to check the result (just copy+paste the inputs)
  If you saved your input in a file named input.txt you can also use redirection to feed your program with that input using executable < input.txt
• If you saved the expected output in a file expected.txt, you can check whether it is the same as the program output.Use executable < input.txt > output.txt to write the output to a file output.txt and the diff command to check if there is any difference diff output.txt expected.txt.
• All problem statements will follow roughly the same format, specifying the problem, the input, the output, the constraints and giving at least one input example and its corresponding output.
• You do not need to verify the constraints on your code. On the contrary, the constraints give you guarantees on the input that will be given to your program. You can assume the test cases we will feed your code obey the constraints (e.g. this allows to know which variable types to use on this program, since you know the given integers will never exceed 10⁹).
• All the lines of input and output should be terminated with the newline character (including the last line).
• You should only output what is given in the statement. Any extra output will cause your code to be marked as incorrect.
• The main() function must return 0. A different returned value means that the process exited with a failure, with Mooshak reporting Invalid Function or Runtime error.
• After submitting, you can see that the word Accepted is underlined on the listing (see this picture for an example of a list). If you click on it you will see a table detailing your result on each input (see this picture for an example of the feedback given) .
• You can click on the submission number on the left of each listing row to recover your submitted code.
• If you press on more... you can see an interface for seeing submissions that allows you to select only a certain student, a certain problem, etc.
• If you submit a file that is exactly the same as one that you already submitted, Mooshak will not accept and report a Duplicate submission.
2. You should now experiment with some common errors to see the behavior of Mooshak in these cases (see the detailed feedback to access the first input where your program fails):
1. Try to get a Compile Time Error - for instance you could remove the last } or the last } and resubmit.
2. Try to get a Wrong Answer - for instance you could change the output line to cout << (count+1) << endl;
3. Try to get a Time Limit Exceeded - for instance you could add while(true); before the final return 0 to make the program get stuck on a loop
4. Try to get a Presentation Error - for instance you could change the output line to cout << count;
   This would make your output not have the endline character, as requested on all lines.
   If your output is correct with the exception of any whitespace (e.g. spaces, newlines, tabs) Mooshak will mark your submissions with a Presentation Error.

2. My first invariant analysis

We will now work towards showing why the previously given program works (aed001.cpp - html version).

1. Let \(n\) be the number of values and \(v_0,v_1,\ldots,v_{n-1}\) be the values of the sequence that come on the input. Find a loop invariant that we can use to conclude that the program is correct. You must describe the state of all relevant variables and complete the sentence:

   "When we are testing the condition \(i \lt n\) in the for loop for the \(k\)-th time, for \(k \ge 1\), the value of \(i\) is \(\ldots\), the value of \(count\) is \(\ldots\) and \(n\) has its initial value.

2. Using the invariant, justify that the loop terminates (check Progress and Termination).
   Hints

   - \(i\) takes integer values, being 0 initially and, from the problem statement, \(n\) contains a positive integer;
   - Assuming the invariant is true, we can claim that \(n\) does not change along the loop, that the value of \(i\) increases by one at each iteration, and that, when we test the loop condition \(i < n\) for \(k=n+1\), we have \(i=n\);
   - Therefore, \(i < n\) is false when \(k=n+1\). Does that mean the loop terminates?
   

3. Using the invariant, conclude that the value we print satisfies the problem specification.
   Hints

   - Assuming the invariant is true, which is the value of \(count\) when \(k=n+1\)? Remark that, for the answer, you must write down just what the invariant says if we replace \(k\) by \(n+1\).
   

4. Show that the invariant is true, by checking the properties we refer to as Initialization and Maintenance. Or, equivalently, prove the invariant by mathematical induction.
   Hints

   - So far, we have not proved that the invariant is true.
   - Intialization ("base case") We must justify that the property is true when \(k=1\). For that, check what was executed in the program before the first test.
   - Maintenance ("induction step" or "inheritance") Assume the property is true at \(k\)-th test (as "induction hypothesis") and that \(i < n\ \) is true. Then, argue that under that assumption, if we execute the body of the loop, the property will still be true for \(k+1\). Remark that, we must check what happens if a == 42 is true at that iteration, and if it is not.
   

5. Find the number of times each instruction is executed in the worst case and in the best case (variable declarations, reads, prints, assignments, comparisons, increments, returns). Define them as a function of \(n\). The worst case happens when all the values are 42 and the best case happens when no value is 42.

3. Removing numbers

Consider the following C++ function which removes all values equal to \(x\) from the array \(a\) with \(n\) integers. The final result will be in \(a[0],\ldots,a[used-1]\) and the function returns \(used\). In the end, the values in the positions \(used\) to \(n-1\) of \(a\) are not relevant (can be anything).

int remove(int a[], int n, int x) {
  int used = 0;
  int pos = 0;
  while (pos < n) {
    if (a[pos] != x) {
      a[used] = a[pos];
      used++;
    }
    pos++;
  }
  return used;
}

1. Let \(v_0,v_1,\ldots,v_{n-1}\) be the values of \(a[0],\ldots,a[n-1]\) when the function is called. Find a loop invariant that we can use to conclude that the function is correct. You must describe the state of all relevant variables and complete the sentence:

   "When we are testing the condition \(pos \lt n\) in the while loop for the \(k\)-th time, for \(k \ge 1\), the values of \(n\) and \(x\) are the same they had before the loop, the value of \(pos\) is \(\ldots\), the value of \(used\) is \(\ldots\) and the contents of the array \(a[]\) are \(\ldots\)"

   Hints

   - Follow the program step by step, writing down the content of each variable when it is checking the loop condition \(pos < n\) for \(k=1\), for \(k=2\), for \(k=3\) and so forth.
   - Identify a pattern and write it formally, i.e., write the mathematical expressions that define the state (e.g., is it true that \(pos = k-1\)?)
   

2. Using the invariant, justify that the loop terminates (check Progress and Termination).
   Hints

   - \(pos\) takes integer values and contains 0 initially and, from the problem statement, \(n\) contains a positive integer;
   - Assuming the invariant is true, we can claim that \(n\) does not change along the loop, the value of \(pos\) increases by one at each iteration, and that, when we test the loop condition \(pos < n\) for \(k=n+1\), we have \(pos = n\), since \(pos=k-1\);
   - Therefore, \(pos < n\) is false when \(k=n+1\). Does that mean the loop terminates?
   

3. Using the invariant, conclude that the value we print satisfies the problem specification.
   Hints

   - Assuming the invariant is true, which is the value of \(used\) and the content of the vector when \(k=n+1\)? Remark that, for the answer, you must write down just what the invariant says if we replace \(k\) by \(n+1\). Hopefully, that will be exactly what it is required by the problem specification.
   

4. Show that the invariant is true, by checking the properties we refer to as Initialization and Maintenance. Or, equivalently, prove the invariant by mathematical induction.
   Hints

   - So far, we have not proved that the invariant is true.
   - Intialization ("base case") We must justify that the property is true when \(k=1\). For that, check what was executed in the program before the first test.
   - Maintenance ("induction step" or "inheritance") Assume the property is true at \(k\)-th test (as "induction hypothesis") and that \(pos < n\) is true. Then, argue that under that assumption, if we execute the body of the loop, the property will still be true for \(k+1\). Remark that, we must check what happens if a[pos] != x is true at that iteration, and if it is not.
   

5. Find the number of times each instruction is executed in the worst case and in the best case. Define them as a function of \(n\). When does the worst case happen? And the best case? Remark that \(n\) is a parameter. Do not replace \(n\) by a constant (do not say that the best case is when n=1).
   Hints

   - In the worst case, the instructions a[used] = a[pos]; and used++; are executed in every iteration. In the best case, they are never executed. You must say what characterizes a best case instance and a worst case instance, i.e., the property that the elements in the sequence satisfy in each case
   

6. Now that you know the function works 😊, solve, submit and get an Accepted on the following Mooshak problem:

   
   Problem: [AED002] Unlucky Numbers.

4. Odd numbers

For this exercise you will be solving the problem [AED003] Space Oddity.

1. Create a C++ program to solve the problem, test it and then submit so it you can get your deserved Accepted 😁
2. Using a suitable invariant and the same steps of the previous problems, can you show why your program is correct?

Note: did you know that Space Oddity is a David Bowie song and that astronaut Chris Hadfield filmed a (revised) cover of this song while he was on the International Space Station? 🚀

Extra Exercise for Consolidating your knowledge [extra]

5. Number Factorization

AED Mooshak classes will usually include at least one extra exercise that you can use of you want to keep testing your knowledge. For this class we propose a problem in which efficiency matters.

For this exercise you will be solving the problem [AED004] Bart's Math Problem.

Here are some helpful notes:

• the factorization can be found by successive divisions, starting from 2
• if any prime \(p\) greater than \(\sqrt{n}\) occurs in the factorization of \(n\), then \(p\) occurs only once
• if \(p_1\) and \(p_2\) are two prime numbers greater than \(\sqrt{n}\) then only one of them can divide \(n\).

In order to be efficient, your function must use the properties of prime numbers stated above. An inefficient solution might get Time Limit Exceeded veredict at Mooshak (the time limit for this problem is 1 second).

1. Solve, test, submit and Accepted on this problem.
2. Justify the correctness of your function.

Challenge Exercise [challenge]

AED Mooshak classes will usually include one challenge exercise, which can be much harder the previous ones and might even need knowledge that was not given explicitly on the course.

The main idea is to give you the opportunity of improving your problem solving abilities.

For this exercise you will be solving the problem [AED005] Number Spiral.

Because this is the first challenge, the selected problem is not too hard and can be solved by any student without any knowledge of advanced algorithms or data structures. You just need to think a little bit and of course be efficient and go beyond the naive "brute force" approach 😉

Since this is a challenge, I will not give you any hints, but if you are stuck just contact @Pedro Ribeiro on Discord. Feel free to also contact @Pedro Ribeiro to discuss your accepted solution.

Happy coding! 😊

Pedro Ribeiro & Ana Paula Tomás (DCC/FCUP) / Last Update: