Information for the 1st Practical Test
General Information
- Date: 13/11/2025 (thursday)
- Time: There will be two shifts for the test (08:30 and 11:00)
[the allocation of students to a particular shift and computer lab will be given on 10/11/2025]
- 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 usual IDEs, with at least VSCode able to compile/execute (but you should know how to compile in a shell); 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, each worth 25%.
In all exercises there will be partial scoring (e.g. passes some tests, fails on others) to accommodate for aspects such as border cases or different algorithmic complexities.
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
- [25%] Exercise 1: a simple problem with some algorithmic insight (this exercise will roughly correspond to contents of practical class #01 and #02)
You will need to solve a simple problem and think about what the algorithm should be. The solution will need a certain complexity to pass all the tests, and you might need to use techniques learned in classes such as sliding windows or prefix sums. Partial score will be given to solutions that are more naive and don't have the desired complexity.
- [25%] Exercise 2: binary search (this exercise will roughly correspond to contents of practical class #03)
You will need to know how to apply a direct or indirect variation of binary search. Input data will already be 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).
- [25%] Exercise 3: sorting with custom order (this exercise will roughly correspond to contents of practical class #04)
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 or that can only take into consideration one sorting parameter. You can use the C++ library if you want (e.g. sort)
- [25%] Exercise 4: methods in linked lists (this exercise will roughly correspond to contents of practical class #05)
You will need to add one or more small methods to the singly linked list class given in the lectures and used on practical exercises (class SinglyLinkedList<T>: see code | download code). Partial score will be given if you solve just one of the methods or if you don't have an efficient method with the right complexity.