Description

Problem 1: (10 points) Design an algorithm that takes as input a positive integer and determines whether or not the integer is prime. A prime number is a whole number greater than 1 whose only factors are 1 and itself. For example 7 is greater than 1 and only divisible by 7 and 1, therefore it is prime. You can use bulleted english to describe your algorithm or pseudocode similar to what we saw in class.

Problem 2: (20 points) Design an algorithm that takes as input a 9 digit number where no digit appears twice and produces as output an arrangement of the same 9 digits corresponding to the next highest number. If no such number exists, the algorithm should indicate this. So for example if the input is 781623954 the output would be 781624359. You can use bulleted english to describe your algorithm or pseudocode similar to what we saw in class.

Problem 3: (20 points) Use binary search to determine whether the number 9 is in the list

[9,10,12,13,16,19,41,54].

How many comparisons did it require? Now use linear (sequential) search to do the same. How many comparisons did it require? Recall in class that we determined the exact formula for the worst-case number of comparisons binary search requires is
T(n) = floor(lg n ) +1
where the floor function simply removes any fractional part of the base-2 logarithm. That is, it's the next smallest whole number from the actual value of lg n. In class we also talked about the trade-off between the expense of sorting and the savings in looking things up in a sorted list versus an unsorted list. Suppose you have an unsorted list of 500 elements. You know the number of comparisons it would take to sort this using selection-sort. You know the worst-case number of comparisons you would need to search this list using linear search and you know the number you would need to search it using binary search. So how many times would you need to search this list using binary search for the savings to add up to the cost of first sorting the list using selection-sort?

Problem 4: (20 points) Suppose you wish to visit 20 cities all connected by roads. You know the distance between each pair of cities. Your goal is to visit every city once and travel the shortest possible overall distance. You can determine your overall distance by adding up the pairs in the order you visit them. So for example if you only had to visit 4 cities and chose to visit them in the order:
City 1 - City 2 - City 3 - City 4
The total distance would be distance(City 1, City 2) + distance(City 2, City 3) + distance(City 3, City 4)
This might be more or less than the sum of the distances involved when visiting the same cities in a different order, for example City 2 - City 4 - City 1 - City 3.
Design an algorithm to find the best order in which to visit the cities. You can use bulleted english to describe your algorithm or pseudocode similar to what we saw in class. How many sums must your algorithm compute to find the best answer? How many total addition operations?