CSC 131 - Introduction to Computer Science

### Program 1: Traveling Salesman Problem

Develop and test a program, called TSP.py,  that allows the user to enter an integer value indicating the number of cities to solve for the Traveling Salesman Problem  The program should then output how many paths would need to be explored using a brute force approach.  It should also output an estimate of how many seconds it would take for the computer to solve the problem assuming that the computer could evaluate 1,000,000 routes per second.   In succession, it should also output how many minutes, hours, days, and years it would take for the computer to solve the problem assuming that the computer could evaluate 1,000,000 routes per second.  Make use of the factorial function of the math module as shown in Figure 1-28.   You may wish to reread the information in Section 1.1.2.  Here’s an example output:

Enter the number of cities: 20

For 20 cities, there are 2,432,902,008,176,640,000 routes

If the computer could process 1,000,000 routes per second,

it would take approximately

2,432,902,008,176.640137 seconds or

40,548,366,802.944000 minutes or

675,806,113.382400 hours or

28,158,588.057600 days or

77,146.816596 years.

To get your output to look like mine, you’ll also have to use the format function described in section 2.1.

For instance, when I calculated the number of routes, I put that result in a variable called “routes”.  Then to print out the routes so that it has commas, I used a statement that looks like this:

print("For", numCities, "cities, there are", format(routes, ',d'), "routes.")

In a similar vein, when I wanted to print out the number of seconds, I used a statement that looks like:

print("\t", format(seconds, ',f'), "seconds or")

### Program 2: Playing with Math

Write a Python program, called SimpleMath.py, that allows the user to enter two integer values, and displays the results when each of the following arithmetic operators are applied.  For example, if the user enters the values 7 and 5, the output would be:

All floating-point results should be displayed with two decimal places of accuracy.   In addition, all values should be displayed with commas where appropriate.

Enter an integer: 7

Enter another integer: 5

7 + 5 = 12

7 - 5 = 2

7 * 5 = 35

7 / 5 = 1.40

7 // 5 = 1

7 % 5 = 2

7 ** 5 = 16,807

### Program 3: All That Talking

Develop and test a Python program that determines how much time it would take to download all instances of every word ever spoken.  Assume the size of this information as given in Figure 2-1.   The download speed is to be entered by the user in million of bits per second (mbps).  To find your actual download speed, you can use websites like http://beta.speedtest.net/

When you output your results, determine what you think is the best way to express the results: minutes? Hours? Days? Other?