In what concerns the "exercises during classes" component of the evaluation, the exercises that you can submit for this class are:
Deadline for submission: April 14th (submit to PII's Mooshak)
You are encouraged to talk to the professors and your colleagues if you encounter difficulties.
However, any more direct help that you receive 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 practical class is worth 18% of your final component for exercices during class. Since there will be 6 classes with submissions, you can achieve maximum grade even without doing fully doing all classes.
For a problem to count you must pass all tests (that is, to have an accepted). Even if you solve all problems, the maximum on one class is 100%.
To obtain 100% it will always be enough to solve the main exercises.
With the exercises in this class you will develop the following skills:
If you feel stuck, go back and revise all the lectures, with special emphasis on 10: Recursion.
This week's theme for the exercises is Friends.
1) A first example
2) Palindromes
- Everything is very similar to reverse, but now the function returns an int and the argument is an array... of chars
- In order for the array to be a palindrome, the first character needs to be the same as the last one AND the rest of the array should also be a palindrome
- For the base case (size of array smaller than two) what should now be the result?
3) Flood Fill
- The type of input is almost the same, so the code is applicable almost directly
- Be careful with the notion of neighborhood, since on this problem diagonal cells are also adjacent. What do you need to change on the recursive function?
- To find the largest microbe colony, count the size of each connected component and print the maximum
- For each new case, what variables do you need to reset? What is that state of visited[][] after finishing the previous case? What should it be before starting a new case?
- The type of input is almost the same, so the code is applicable almost directly
- In opposition to what happened before, now you should flood fill '.' and avoid '#'
- Start your flood fill on the 'R' cell. It it reaches 'S', then print yes, otherwise print no
- As before, don't forget to reset your variables from case to case
4) Generating subsets
- What does it mean to exhaustively try out every possible playlist? Basically, we want all the subsets!
- To test a playlist, instead of printing out a subset, we want to add up the duration of the songs in that subset
- Of all the subsets, we keep the best one (the one with the highest sum and smaller than D)
- Note: this solution of exhaustive search generating all subsets is exponential - in more advanced courses you would learn how to solve a problem like this more efficiently using an algorithmic technique called dynamic programming
Do you want to continue your adventure on the world of recursion? Here is one more exercise 🙂
Start by downloading the following code that generates all permutations of n elements. Compile, test and verify that you know exactly how the code is working.
Using as a basis the previous code, read the statement, code and try to submit an Accepted solution to the following problem. Don't forget to test first on your computer!
- What does it mean to exhaustively try all possible paths? Basically, we want all the permutations of the places, because a path is is completely defined by the order in which we visit the sites.
- To test a permutation, instead of printing it out, we want to add up the distances travelled
- Of all the permutations, we keep the best one (the one with the smallest sum)
- Note: this problem is essentially a Euclidean version of the Traveling Salesman Problem, which is a computationally hard problem with no known efficient version for a geneneral case
You've solved every last problem in the Friends Problemset! Your logic is sharper than Ross's fossil collection, your determination stronger than Joey’s love for sandwiches, and your problem-solving speed? Faster than Chandler making an awkward joke in a serious moment! 🚀
But wait… just when you thought you could kick back with a coffee at Central Perk—there’s one final challenge. 😈 Are you on a break or ready to bring your A-game? 😏
This challenge is not as hard as the past one from an algorithmic efficiency point of view, but it is larger and involves knowing how to break the problem into smaller (easier to solve) subproblems and producing organized and structured code.
Give yourself some time to think about it and be sure to chat with your professors for hints or to proudly talk about how you solve it 😁
Happy coding! 😊