CSCI 170 (GOLDWEBER)
Spring 08: 4//22/08
Homework 8: Complexity Theory
Due Date: Tuesday April 29, 2008.
There is a possible 34 points for this homework.
Problem 1. (4 pts.) Assume the existence of a predicate function sortChecker(lov) that returns true if the input list (lov) is sorted either ascending or descending, and false otherwise. What is this function's running time; provide your guesstimate of the algorithm's Big-Oh running time along with an explanation justifying your analysis.
Problem 2. (4 pts.) Algorithms A and B perform the same task. On input of size n, algorithm A executes 0.003n2 instructions/steps, and algorithm B executes 243n instructions/steps. Find the approximate value of n above which algorithm B is more efficient.
Problem 3. (4 pts.) A tennis tournament has 342 players. A single match involves 2 players. The winner of a match will play the winner of a match in the next round, whereas losers are eliminated from the tournament. The 2 players that have won all previous rounds play in the final game determining the tournament winner.
- Use the following logarithmic algorithm to determine the number of matches played.
Compute 342/2 = 171 to get the number of pairs (matches) in the first round, which results in 171 winners going on to the second round. Compute 171/2=85 with 1 left over, which results in 85 matches in the second round and 85 winners plus one to go on to the third round. etc, etc.
- Devise and describe a more efficient algorithm to compute the number of matches that will be played.
Problem 4. (4 pts.) An algorithm that is O(n2) takes ten seconds to complete when n=100. About how many seconds do you expect it to take when n=500?
Problem 5. (8 pts.) For selection sort:
- Describe what the input is for the algorithm's best case scenario.
- Describe what the input is for the algorithm's worst case scenario.
- For both of the above, what is the running time of the algorithm?
Answer the same questions for insertion sort.
Problem 6. (10 pts. Old MacDonald song) You are probably familiar with the children's song "Old MacDonald Had a Farm." The first verse is
Old MacDonald had a farm, eee-eye, eee-eye, oh.
And on that farm he had a cow, eee-eye, eee-eye, oh.
With a moo-moo here and a moo-moo there,
Here a moo, there a moo
Everywhere a moo-moo,
Old MacDonald had a farm, eee-eye, eee-eye, oh.
In successive verses, more animals are added, and the middle refrain gets longer and longer. For example the second verse is:
Old MacDonald had a farm, eee-eye, eee-eye, oh.
And on that farm he had a pig, eee-eye, eee-eye, oh.
With an oink-oink here and an oink-oink there,
Here an oink, there an oink
Everywhere an oink-oink,
With a moo-moo here and a moo-moo there,
Here a moo, there a moo
Everywhere a moo-moo,
Old MacDonald had a farm, eee-eye, eee-eye, oh.
- Show that after n verses of this song have been sung, the total number of syllables sung would be given by the expression
You may assume that all animal names consist of one syllable.
- If singing this song is the algorithm, and the work unit is singing one syllable, what is the order of magnitude of the algorithm?
File translated from
TEX
by
TTH,
version 3.74.
On 22 Apr 2008, 09:33.