Information for the 1st Practical Test
General Information
- Date: 22/10/2024 (tuesday)
- Time: There will be two shifts for the test (14:30 and 17:00)
[see student allocation to shift and room] (protected access)
- Place: FEUP Computer Labs (B Building)
- Duration: 2h
- Method: the test will be individual and will consist of practical problems for which you can submit C++ code to Mooshak and receive feedback that might include public test cases, like in the practical classes
- Language: all problems will be available in english and in portuguese
- Environment: the computers will have Linux, with GCC available at command line, and the usual IDEs, with CLion and VSCode able to compile/execute; you will have access to documentation (local copy of cppreference) and to a local copy of the course website (including lecture slides and practical classes, with all auxiliary files)
- Scoring: this test is worth 2.5 points out of 20 (12.5% of your class grade) [see explanation and calculation formula of final grade]
You will have 4 exercises in Mooshak worth 30%+30%+30%+10%
In each exercise there might be partial scoring (e.g. passes some tests, fails on others).
When submitting, you will know the score you got on all tests. Your grade on a problem will be the grade of your best submission on that problem (the one with the highest score)
Specific goals for each exercise and training problems
- [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.
- [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).
- [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)
- [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).