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

Information for the Extra Practical Test ("repescagem")


What is the purpose of this test?

This (extra) test is only for students which did not reach the minimum score on the practical grade (1.5 out of 6, that is, 25%). Note that the practical grade was considered continuous evaluation.

This test is another opportunity and has only two possible outcomes:


Who is elegible for the test:

If you have less than 1.5 as your pratical grade and you did not exceed the absence limit on the practical classes (4 missed classes, at most).

Check the list of elegible students to know if you fulfill these conditions (no registration is needed).

(authentication for the list is the same as the one you use to access the evaluation data)

Note that this is the last chance to reach minimum grade! (you can come conditionally to the test if you are still regularizing your situation regarding missed classes).


How can I reach minimum grade?

The test provides 4 exercises (equivalent to the the two most solved exercises of each of the two practical tests), allowing for students to choose the topics that they prefer.

Each exercise is worth 100 points and a student needs 200 points to reach minimum grade (e.g. solving completely two exercises or gaining 50% of the points of the 4 exercises).


General Information


Specific goals for each exercise and training problems

Note: you can also train using the exercises from the practical tests, which are available on AED's Mooshak

  1. [100 points] Exercise 1: a simple problem with iteration and conditional instructions (This exercise is equivalent to the 1st exercise of the 1st practical test)
    You will need to implement a small program to show that you can read simple input from stdin, eventually store it on an array or vector and process it using iteration (e.g. for ) and conditionals (e.g. if). This exercise might include more than one subtask and/or simple complexity constraints, to allow for partial scoring.  
  2. [100 points] Exercise 2: sorting with custom order (This exercise is equivalent to the 3rd exercise of the 1st practical test)
    You will need to know how to apply sorting with a customized order that might depend on more that one parameter. To obtain full score you need to have an \(O(n \log n)\) sort, but partial score will be given to submissions that take quadratic time for sorting. You can use the C++ library if you want (e.g. sort)  
  3. [100 points] Exercise 3: a method in a binary tree (This exercise is equivalent to the 2nd exercise of the 2nd practical test)
    You will need to add one method to the binary tree class given in the lectures and used on practical exercises (class BTree<T>: (see code | download code).  
  4. [100 points] Exercise 4: DFS method in a graph (This exercise is equivalent to the 3rd exercise of the 2nd practical test)
    You will need to add one method to the graph class given in the lectures and used on practical exercises (class Graph: see code | download code). The suggested method to solve will be using DFS, but the students can solve using any other graph traversal technique, if it solves the problem.