Algorithms and Data structures • Programming assignments

Programming assignments of the Algorithms and Data structures course, prof. Alessandro Panconesi.

University project • 2016 - Algorithms and data structures - BSc in Physics, III year

The statement of problem 1 and 2 is in ASD2016-ProgrammingExercises-A.Panconesi.pdf 3,4,5 and 6 in ProgrammingAssignment2.pdf, the solution code in Python is in \antonio_norelli_solutions.

Problems

1. Stable Marriage.

2. Strongly connected components.

3. Write a method to sort an array of strings so that all anagrams are next to each other.

4. Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics a real set of stacks. This SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks push() and SetOfStacks pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack). Implement a function popAt(int index) which performs a pop operation on a specific sub­stack.

5. Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure.

6. Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write a recursive code to calculate the number of ways of representing n cents.