Unless specified otherwise, all the programs are expected to be completed in Python or O’Caml.
1. Implement the following algorithms presented in the lectures:
a. Sort and count (1.??);
b. Gale-Shapley (2.??);
2. In assignment 1, exercise 5, question 1 the Knapsack problem is introduced and two ideas to solve it are proposed.
a. Implement both strategies and run each of them on a counter example;
b. Search how to properly solve the Knapsack problem and implement the solution;
3. Run each of the previous implementations on various input sizes, time how long it takes to complete the program, and compare the results to the ones provided in table 2.??. Write a short report presenting the results.
Hint: use the python module timeit.
