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

Information for the 1st Practical Test


General Information


Specific goals for each exercise and training problems

  1. [30%] Exercise 1: a simple problem with iteration and conditional instructions
    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. [30%] Exercise 2: binary search
    You will need to know to apply a direct or indirect variation of binary search. Input data will already come sorted. To obtain full score you need to have an \(O(\log n)\) search, but partial score will be given to submissions that use linear search. You can use the C++ library if you want (e.g. lower_bound).  
  3. [30%] Exercise 3: sorting with custom order
    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)  
  4. [10%] Exercise 4: a problem of algorithmic nature
    You will need to solve a problem and think about what should the algorithm be. The solution will need a certain complexity to pass all tests. The topics can be anything of what was covered until sorting (i.e. lectures until chapter 4, practical classes until class #04).