For this exercise you will be solving the problem [AED040] Sticker Collection.
Desired time complexity: \(O(N \log N)\) (where N is the maximum number of stickers between \(C\) and \(B\))
In what concerns the continuous evaluation solving exercises during the semester, the exercises you can submit in this class are:
Submission Deadline: December 7th (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 balanced binary search trees. It is therefore convenient that you know what was discussed on the lectures:
The exercises for this class will involve the usage of classes such as set, multiset, map and multimap. You will have the opportunity to work with a low level implementation of binar search trees on the extra exercises.
1. Understanding sets and multisets
(the goal of this exercise is for you to understand what a set and a multiset is)
Start by downloading the set_example.cpp file. Open on your editor, understand it and then compile and execute it. You should have the following output:
s.size() = 5 ms.size() = 8 s: 2 3 4 5 8 ms: 2 2 3 4 4 5 8 8 it = s.begin(); it = 2 it++; it = 3 it--; it = 2 it = s.end(); it--; it = 8 rit = s.rbegin(); rit = 8 rit++; rit = 5 is 5 on s? yes is 6 on s? no after removing 5, s.size() = 4 after removing 5 again, s.size() = 4
Have a look at the set and multiset documentation to see all available methods and their complexity. Because sets are implemented as balanced binary search trees (usually a red-black tree in current C++ compilers), most of the methods will be tied to the height of the tree and will have logarithmic complexity.
To make sure you understood sets, try some new calls. For instance:
2. A first problem with sets
For this exercise you will be solving the problem [AED040] Sticker Collection.
Desired time complexity: \(O(N \log N)\) (where N is the maximum number of stickers between \(C\) and \(B\))
Can you think on how to use sets to solve this problem?
- Take all the initial stickers on C and put them on a set
- Read the stickers on the bag and check if they are already on C: if yes, do nothing, if no, add them to another set containing the new elements
- Print the values in the set with the new elements (they will already come in the desired order)
3. Simulating a game
For this exercise you will be solving the problem [AED041] Pokemon Battle.
Desired time complexity: \(O(N \log N)\) (where N is the maximum number of cards between \(A\) and \(B\))
Can you think on how to use sets to solve this problem?
- Keep a multiset for the cards of each kid (there might exist repeated values)
- To simulate a round use an iterator to the previous value of end() to obtain the highest value cards
. remove both cards using erase()
. check if a card is higher than the other and (re)add it to the multiset of respective kid (with updated energy)
- Stop when one (at least) of the multisets is empty, and print an output accordingly
4. Understanding maps
(the goal of this exercise is for you to understand what a map is)
Start by downloading the map_example.cpp file. Open on your editor, understand it and then compile and execute it. You should have the following output:
John -> 42 Sarah -> 31 Tom -> 56 is Sarah on m? yes is Bob on m? no Value of Sarah? 31 Value of Kim? 0 After erasing Sarah and changing the value of Tom: John -> 42 Kim -> 0 Tom -> 20
Have a look at the map and multimap documentation to see all available methods and their complexity. Because maps are implemented as balanced binary search trees (usually a red-black tree in current C++ compilers), most of the methods will be tied to the height of the tree and will have logarithmic complexity.
To make sure you understood maps and multimaps, try some new calls. For instance:
5. Your first problem with maps
For this exercise you will be solving the problem [AED042] Life Moments.
Desired time complexity: \(O(N \log N)\) (where N is the number of events)
Can you think on how to use maps to solve this problem?
- keep a map<int, int&lgt; that uses as a key an event id and as value the position of its last occurrence
- Each time you read a new event you just need to check your map:
. If the event is already there, just print the value (which is the last position)
. If not, then print -1
- After printing, update the position of the current event
6. Movie Review Statistics
For this exercise you will be solving the problem [AED043] Movie Reviews.
Desired time complexity: \(O(N \log N)\) (where N is the number of movie reviews)
Can you think on how to use maps to solve this problem?
- You need a map with the key being the movie name and the value being more than one value, right?
. You need to know how many reviews it has
. You need to know how many of those are positive
- One way to do this if for example to use a map<string, pair<int, int>gt;, or you could also use a struct or class to represent a movie
- After having the right data structure, you only need to keep updating it as you read and in the end print what is asked
7. Cool Problem?
For this exercise you will be solving the problem [AED044] Cool Sequences.
Desired time complexity: \(O(N \log N)\) (where N is the number of elements in the sequence
- Can you do one problem without hints? How do sets and/or maps fit in this problem?
8. The inner side of a binary search tree
For this exercise 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 binarySearchTree.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).
Before starting the exercises, start by having a look at the BinarySearchTree<T> class (see code | download code) which implements a generic binary search tree that was given in the classes, with methods to read insert, remove and check of a value exists, to write a preOrder traversal with N as null nodes and the number of nodes and height of the tree.
For this exercise you will be solving the problem [AED045] Node Balance.
Desired time complexity: \(O(N)\) (where N is the number of nodes in the tree)
- You just need to find the node (similar to contains) and when you are there... you can eve reuse the height function you already have 🙂 Can you see how?
For this exercise you will be solving the problem [AED046] Is this an AVL Tree?.
Desired time complexity: \(O(N^2)\) (where N is the number of nodes in the tree)
Although Mooshak does not inforce it, as a bonus, could you implement this exercise in \(O(N)\)?
- You just need to traverse all the nodes... and in each one of them call your balance function
- Because each call to balance will take linear time on the nodes in the subtrees below the node, the entire function will take quadratic time..
- To do better you need to traverse just once... can you do it by yourself? 🙂
For this exercise you will be solving the problem [AED047] Rotating a Tree.
Desired time complexity: \(O(h)\) (where h is the height of the tree)
- Just find the node and then implement the rotation
- Because you do not have a parent pointer, the best option might be to return the changed tree, so that the parent only needs to update its subtree according to your changes. Chan you see how? 🙂
If you feel like experimenting more, you can go ahead and actually implement AVL trees. Start with insertion (you already have "almost" all the basic pieces and you can even test whether you can maintain the invariant by by calling the isAVL()> method). Note that for a really efficient implementation, the insertion, removal and search operations must always be in logarithmic time.
The main idea of the challenge problems is to give you the opportunity of improving your problem solving abilities.
For this exercise you will be solving the problem [AED048] Traffic Lights.
For this class, the problem is at its essence from CSES problem set, a very interesting resource of problems (that also has an online judge).
Since this is a challenge, I will not give you any hints, but if you are stuck just contact @PedroRibeiro on Discord. Feel free to also contact @PedroRibeiro to discuss your accepted solution.
Happy coding! 😊