1.
Assume that a salesperson wants to
visit 30 cities while minimizing the total
number of miles she must travel. She
decides to design an algorithm to find the
optimal order in which cities must be
visited to • Minimize the number of
kilometres travelled and
• Visit each city only once.
Assume that the computer has access to all
the intercity distances, and that it can
calculate the total distance for an all-city
route at the rate of 10,000,000 a second.
a) How long will it take to calculate
the cost of all such routes and give
the best one? Give your answer in
large units like weeks, months or
years.
b) If it does not seem like a feasible
solution, suggest an alternative way
of coming up with a reasonable
algorithm to find a good (not
necessarily optimal) route
Show your calculations!
Answer
A Calculating the time taken to calculate the
best route
In this question, we are using permutations
because permutation involves arranging the
cities in all the possible ways to calculate
the shortest distance.
Let the number of cities sales person travel
=n
Here , n = 30
Calculating all the possible routes = n! =
30!
= 30 x 29 x28………….x1
= 2.65 x 10^32 possible routes.
Total distance a computer can calculate in 1
second for an all-city route = 10000000.
Time( in seconds)taken to cover all the 30
routes = total possible routes/ total distance
computer can calculate in 1 sec for an all-
city route
= 2.65 X 10^32/10000000
= 2.65 X 10^25 seconds
Converting time into larger units.
1 min = 60 sec.
1hour = 60min
1day = 24 hours
1 year = 365 days
Total years taken by a computer to calculate
distance =
2.65 X 10^25/60 X 60 X 24 X 365
= 0.84 X 10 ^ 18 years.
B Alternative solution
To find the optimal route the another
method we can choose is .
1. We have total cities(n) = 30
2. From these cities let us take one of
them as home city (i = 1)
3. From this home city visit the nearest
city (the closest city to this first city).
(now the value of i = i +1and will
continue to increase by one every time a
new closest city is visited.)
4. Then from the second city visit the
nearest unvisited city
5. Continue this loop until the
salesperson visit all the cities (remember
all the cities must be visited once only)
6. Once the value of I hits 30 exit the
loop because now we have visited all the
cities and here we got the shortest
possible route(approximately)
2. Write an algorithm as a flow chart
that reads in values for a series of
numbers (so you will have to read in
inside a loop, and test for EOF to end the
loop). For each number, if it is ≥ 0 the
algorithm will print out “Positive”. The
algorithm should stop when five negative
numbers have been found.
ANSWER
3. Write an algorithm in pseudocode to
calculate a monthly electrical bill for a
house. Assume you have as input the
meter readings at the beginning and end
of the month in kilowatt-hours (kwh) and
the cost per kilowatt hour as follows:
A) First 500 kWh per month: $0.06 each
B) kwh over 500 but less than or equal
to 1000: $0.08 each
C) kwh over 1000: $0.10 each
Have the algorithm ask the user if they
wish to repeat the calculation for another
month, and loop back to the appropriate
point if they do.
ANS.
1. Ask the user to enter electricity bill
for a house per month in kWh
2. Now, print if units are less than or
equal to 500 the bill per unit is $ 0.06.
3. Then, print if units are greater than
500 and less than or equal to 1000
units, the cost is $ 0.08 per unit.
4. If the units are greater than 1000$,
print the cost per unit is $0.10.
5. Ask the user whether the user want
to calculate his/her monthly electricity
bill .
6. If the user inputs yes ask him to
press 1 to calculate his monthly
electricity bill.
7. If the user inputs no ask him to press
0 and exit the loop.
8. Now, if the user goes with “yes” and
he wants to calculate the bill. There will
be three different calculations.
9. If the units in kWh are less than or
equal to 500
Then the electricity bill = 0.05 * units
entered by the user.
10. If the units in kWh are greater than
500 and less than or equal to 1000,
then the electricity bill =
500 kWh units * 0.06 +(total
units entered by user – 500 kwh units) *
0.08
11. If the units in kWh are greater than
1000 , then electricity bill = 1000 kWh
units * 0.08 + ( total units entered by
user – 1000 kWh units)*0.10
12. The last step is to print “(electricity
bill) this is the total electricity bill of
your house for this month”
13. Stop.
QUESTION 4. Looking at the Find Largest
Algorithm as described in Figure 2.14, if the
numbers in the list were not unique, would
the algorithm report the first or the last
occurrence of the largest number if it
occurred several times? Explain your
answer.
Answer - If the numbers in the list are not
unique, from my point of view the algorithm
will report to the first occurrence of the the
largest number that is repeated several
times in a list.
This is because
1. The algorithm initializes the largest
number to the first element of the list.
2. After that it iterates through the
whole list and wherever it finds the
largest number, it will keep on updating
that.
3. Hence, the algorithm will report to
the first occurrence of the largest
number in a list .
For example ,
Let us consider the list
[ 12,5,8,9,13,11,13]
Initial large number = 12
When iterating through the list
Current number = 5, large number = 12
current number = 8, large number = 12
current number = 9, large number = 12
current number = 13, large number = 13
(updated)
current number = 11, large number = 13
current number = 13 , large number = 13
(no updating)
hence from this example, it is clear that
the algorithm will support the first
occurrence of the largest number in a list
even if it is repeated several times in the
list.
