You will use two well-known problems for this homework:
- Sorting problem.
- Minimum spanning tree (MST) problem.
1. You all know that MST is an optimization problem, but sorting is not usually defined as an optimization problem. So, first of all you should define the sorting problem as an optimization problem.
2. Design and implement brute force solutions for both problems (MST and sorting optimization problem).
3. Design and implement a backtracking algorithm for the sorting optimization problem.
4. Design and implement a branch and bound solution for the MST problem.
5. Implement a well-known greedy MST algorithm.
6. Implement a greedy algorithm for the sorting optimization problem.
7. Design and implement algorithms to construct random solution and improve the solution by local search for both problems (MST and sorting optimization problem).
8. Write a report about your work. In your report, you should
- give the rigorous and in detailed definition of the optimization problems.
- give explanation of your design. If there are alternatives for a design decision, explain why you choose the one in your design. Write pseudo-code of your algorithms.
- explain non-trivial implementation details in your code.
- present the theoretical run-time analysis
- present the results of experimental analysis. Run your algorithms for several different problems (of various complexities and sizes) and present their performance. Draw figures and tables.
Note that you will work with the same (or very similar) problems for future homework assignments and design algorithms using following design techniques, as well.
- Variable Neighborhood Search
- Simulated Annealing
- Tabu Search
- Genetic Algorithms
- Particle Swarm Optimization
- Ant Colony Optimization
