Assignment 5

Assigned 2024-09-24, due 2024-10-01.

Question 1

Implement simulated annealing for the traveling salesman problem, and beat the greedy algorithm. Download this notebook and implement the missing anneal function. Once you do, the rest of the notebook should run cleanly and you can see how simulated annealing does in comparison to random trials or a simple greedy algorithm. The final output will look something like this.

Question 2

Find a way to crack substitution ciphers. One method is to follow the algorithm described here. Download this notebook and implement the fitness and crack functions. (You will also have to download a few free long books; do not download the same book we took a sample passage from. Any other long book should be fine.) If you do it right, the rest of the notebook should run and you can see how the correct key is found. The output should look something like this.

Note: If you have a better way of cracking these ciphers, feel free to code it independently without using the algorithm suggested in the notebook.