In what concerns the continuous evaluation solving exercises during the semester, the exercises you can submit in this class are:
Submission Deadline: November 9th(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 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 10 per cent of the grade for this component. As there will be 11 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.
This class is about linkeds lists implementation. It is therefore convenient that you know what was discussed on the lectures:
The exercises for this class will involve the low level implementation
of linked lists and adding new methods, so that you can gain a better understanding of
what's happening.
On the following classes you will be allowed to use the STL class list, but for this class we want you to be able to understand (and code) an implementation.
1. Understanding Linked Lists
(the goal of this exercise is for you to understand a basic implementation of linked lists that uses templates)
Start by downloading the following two files: singlyLinkedList.h (see it in html) and testLists.cpp (see it in html).
Compile the code. The whole SinglyLinkedList<T> class is contained in the .h file, so you just need to compile testLists.cpp (make sure they are in the same directory, so that the line #include "singlyLinkedList.h" knows where to find the file it wants to include). If you are on a shell, you could for instance run g++ -std=c++17 -o testLists testLists.cpp to obain an executable with the name testLists).
Run the code while looking at testLists.cpp on your editor to see each line and its effect. You should obtain the following output:
{}
isEmpty? 1
{1,2,3,4,5}
{10,9,8,7,6,1,2,3,4,5}
size = 10
{9,8,7,6,1,2,3,4,5}
{9,8,7,6,1,2,3,4}
isEmpty? 0
getFirst() = 9
getLast() = 4
Also have a look at each method being called in singlyLinkedList.h to understand how the linkedList is implemented. The figure above gives you an overview of how the class is organized and a similar class (although distinct) was implemented and explained in the lectures.
Notice how the implementation uses templates to be general and therefore supports any data type (not just int).
To make sure you understand how to use it, implement and test the creation of a singly linked list of char containing the 5 vowels: 'a', 'e', 'i', 'o', 'u'.
To understand how the class is providing some error messages, create an empty list and try to remove the first or last element. What happens when you run the code?
The error messages might be helpful when you are developing the next methods.
2. Your first linked list method
For this exercise you will be solving the problem [AED020] Returning an element on a given position.
Desired time complexity: \(O(N)\) (where N is the size of the list)
For this class you will be adding methods to an existing class, so the idea is that you add the requested method at the end of the class (but before the closing brackets). You only need to submit the singlyLinkedList.h file!
If you want to test the method on your computer, you can copy+paste tester code from the problem statement to a file on your computer, compile it and use the input given to see if the results are as expected (note how easy it is to add new inputs, if you want to make further tests).
This problems asks you to traverse the list until the desired position. Have a look at getLast(). What do you need to change to implement the get method?
- You can do the same type of cycle blueprinted in getLast() (use a cur variable to keep the current node, starting with first and always going to the next value).
- If you want to get to position pos, how many next links to you need to traverse?
- After reaching the desired node, you can simply use getValue() to return the desired value.
3. Counting values
For this exercise you will be solving the problem [AED021] Counting elements.
Desired time complexity: \(O(N)\) (where N is the size of the list)
This is a similar exercise to the previous one, but now you need to count. Can you see how to use a list traversal do the the counting?
- Use the same pattern of link traversal with a cur node, but this time traverse the entire list
- Use an auxiliary variable as a counter and on each iteration check with == to see if the value stored in the node is equal (use cur->getValue()), incrementing the counter when this happens.
4. Removing a node
For this exercise you will be solving the problem [AED022] Removing an element on a given position .
Desired time complexity: \(O(N)\) (where N is the size of the list)
For this exercise use as a blueprint the method removeLast(). What do you need to change?
- Just as in removeLast(), instead of going until the node, go until the previous node, so that when you need to erase you can just make the current node skip the node you want to delete (the "victim"); don't forget to delete the node after removing it (see the getLast() implementation) if you want to avoid memory leaks (which are not tested explicitly by Mooshak)
- Don't forget to decrease the length variable after removing the node
- Be careful with the case where the node to remove is the first one (as there is no previous node to the first); but in that case you can simply call removeFirst(), right?
5. Inserting a node
For this exercise you will be solving the problem [AED023] Inserting an element on a given position .
Desired time complexity: \(O(N)\) (where N is the size of the list)
For this exercise use as a blueprint the method addLast(). What do you need to change?
- Because you want to insert before pos you need to stop before the position and do something similar to what is done in getLast()
- Don't forget to increment length variable after inserting the node
- Be careful with the case where you want to insert the node in the first position (as there is no previous node to the first); but in that case you can simply call addFirst(), right?
6. Duplicating elements
For this exercise you will be solving the problem [AED024] Duplicating elements .
Desired time complexity: \(O(N)\) (where N is the size of the list)
Can you do this one without any hints?
7. Removing all occurrences of a value
For this exercise you will be solving the problem [AED025] Inserting an element on a given position .
Desired time complexity: \(O(N)\) (where N is the size of the list)
For this exercise Mooshak was setup with a large test to make sure you implementation is linear on the size of the list, so you cannot go back to the start of the list each time you remove a node. You should be able to remove as you are traversing the list (and take care when removing consecutive nodes)
The main idea of the challenge problems is to give you the opportunity of improving your problem solving abilities.
For this class, our proposal is for you to try solving the problems that were used on the MIUP'2024 U. Porto Selection Contest. MIUP (Maratona Inter-Universitária de Programação) is the oldest and most well known universitary programming competition in Portugal, serving as a preliminary stage to SWERC (Southwestern Europe Regional Contest) our ICPC regional.
Did you know that the the last 3 editions of MIUP were won by teams from UPorto (2021 | 2022 | 2023)? And the a team from U. Porto won medals on the last two editions of SWERC ( 22/23 | 23/24)?
You can head over the Competitive Programming @ UPorto Mooshak (https://mooshak.dcc.fc.up.pt/~npc/) and register for the contest (choose the "pós-Prova") to try out the 9 problems (they start easy and start getting progressively harder). You can also try selection contests from other years and even one MIUP.
Happy coding! 😊