This class is about applications of lists, deques, stacks and queues. It is therefore convenient that you know what was discussed on the lectures:
This class includes the following implementation exercises available on Mooshak:
1. An application of lists
Start by downloading the lists_example.cpp file. Open in your editor, understand it and then compile and execute it. You should have the following output:
3 5 7 1 42 3 5 7 20 42 3 5 42 5 7 20 forty two a e i o u 1 0 1
Have a look at the documentation about the container list to see all the available methods.
For this exercise you will be solving the problem [AED033] Eeny, meeny, miny, moe.
Desired time complexity: \(\mathcal{O}(N \times K)\)
The problem asks you to simulate a counting-out game. Our suggestion is for you to do the following:
2. An application of stacks
Start by downloading the stacks_example.cpp file. Open in your editor, understand it and then compile and execute it. You should have the following output:
Stack size: 0 Stack size: 4 At the top: 8 At the top: 6 At the top: 4 At the top: 2 Stack size: 0
Have a look at the documentation about the container stack to see all the available methods and remember how a stack works in a LIFO fashion (last-in-first-out).
Sometimes you have the need to combine several variables into one data structure. For that you can use for instance:
Download the types_example.cpp file. Open in your editor, understand it and then compile and execute it.
Remember that you can also use classes if you want to add functionality (methods), as you already know.
For this exercise you will be solving the problem [AED034] Perfect Weddings.
Desired time complexity: \(\mathcal{O}(|E|)\)
The problem asks you to match different parentheses (), brackets [] and curly braces {}. At its core this is a problem that can be solved by using a stack:
Our suggestion is for you to use a stack as the core of your implementation:
3. An application of queues
Start by downloading the queues_example.cpp file. Open in your editor, understand it and then compile and execute it. You should have the following output:
Queue size: 0 Queue size: 4 At the front: 2 | At the back: 8 At the front: 4 | At the back: 8 At the front: 6 | At the back: 8 At the front: 8 | At the back: 8 Queue size: 0
Have a look at the documentation about the container queue to see all the available methods and remember how a queue works in a FIFO fashion (first-in-first-out).
For this exercise you will be solving the problem [AED035] Round-Robin.
Desired time complexity: \(\mathcal{O}(N \times max(R_i)/T)\)
The problem asks you to simulate round robin scheduling, which is a very well known algorithm.
Our suggestion is for you to directly implement a simulation of the algorithm:
4. Convex Hull
For this exercise you will be solving the problem [AED036] Convex Hull.
Desired time complexity: \(\mathcal{O}(N \log N)\)
The convex hull problem (a very useful computational geometry primitive) was discussed in detail in the lectures in chapter 6 (see slides 13 to 29).
For this exercise, we propose you implement Graham's Scan algorithm, which at its core uses a stack (see slides 28 and 29).
You can use the following skeleton file as the base for you implementation and complete it: skeletonGrahamScan.cpp
5. Supermarket Queues
For this exercise you will be solving the problem [AED037] Supermarket.
Desired time complexity: \(\mathcal{O}(N \times C)\)
For this exercise you need to simulate a more complex scenario with several queues.
The key to have an Accepted is to structure and organize your code:
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 [AED038] Golden Permits.
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.
This is in its essence the same problem as [AED033] Eeny, meeny, miny, moe, but now a "brute force" approach in \(\mathcal{O}(N \times K)\) is not enough! How can you improve such that the time does not depend on \(K\) but just linearly on \(N\)?
Happy coding! 😊