--- tags : AOS4, assignment --- # AOS4 : Assignment #1 Suppose students follow courses in 3 subjects: Physics, Math, Economics. During their final exams, they receive grades, which are integers between 0 and 5 that are aggregated using a weighted sum with $w_{Physics} = 1$, $w_{Math}=3$ and $w_{Eco} = 2$. They succeed if they obtain a score of 15 or greater. 1. Enumerate all the ways of *just succeeding* the exam, i.e. of having grades such that the score is above 15, but having a lesser grade in one subject is either impossible (because it is already 0), or woud mean failing the exam. 2. Same questions but with scores ranging from 0 to 20. You might consider writing a program. > **Hint :** The sought set can be generated recursively, by removing one subject at a time > * Suppose you begin by assigning the Math grades - you have 6 ways of doing so, and then you must achieve the complement of the score with the remaining subjects, which looks like a subproblem of the same nature as the original one > * The terminal case is reached when there is only one subject left 4. Same questions, but with seven subjects with weights (2, 3, 7, 5, 5, 4, 2), grades ranging from 0 to 20 and success corresponding to a score above$\frac{\text{max score} - \text{min score}}{2}$. You might consider making your previous program efficient! > **Hint :** Recursive descent is usually very inefficient because you might solve the exact same problem many times. For instance, > ```python >def fibonacci(n) : > if n < 2 : > return 1 > else : > return fibonacci(n-1)+fibonacc(n-2) >``` >makes $2^{n-2}$ calls to itself, while there are only $n-2$ distinct subproblems. > One way around this issue consists in adopting an *ascending* approach, called *Dynamic Programming*, allowing to properly analyze the algorithm (do it for the Fibonacci function). The same performance can be achieved by storing intermediate results (a technique sometimes called mesoisation), and litterally costs two lines of python: > ```python >import functools > >@functools.lru_cache(maxsize=None) >def fibonacci(n) : > if n < 2 : > return 1 > else : > return fibonacci(n-1)+fibonacc(n-2) >```