Homework: Algorithm Analysis

< Previous  Next >

---

Write your answers to the following questions in a flat text file hwkAlgorithmAnalysis.txt (not a Word document nor a Rich Text Format file):

1. What is the order of the algorithm that has the following growth-rate functions for n inputs:
   1. 4n³ - 2n
   2. 5 log₂ n + 6
   3. 5 log n + 6n
   4. 5n log₂ n + 6n
   5. 5n log₂ n + 6n + 7n²
   6. 5n + 9k
   7. 42 + 99k
2. What is the (worst-case) order of the following tasks (using intelligent programming)?
   1. Computing the sum of the first n even integers (using a for loop)
   2. Displaying all n integers in an array
   3. Displaying all n integers in a sorted linked list
   4. Displaying all n names in a circular linked list
   5. Displaying one array element
   6. Displaying the last integer in a traditional linked list
   7. Adding an item to a stack of n items
   8. Adding an item to a queue of n items
3. Show the relationship of the common growth rates. Use the format of:

   O(____) < O(____) < ... 

4. Consider an algorithm that contains loops of this form:

   for( i = 1 through n ){
     for( j = 1 through n ){
       Task T
     }
   }
   

   If task T requires t time units, the innermost loop on j (and only the innermost loop) requires how many time units (in terms of t)? (Choose an answer from the following):
   • A) j
   • B) n
   • C) n * t
   • D) n²
   • E) n² * t
5. Suppose that your implementation of a particular algorithm appears in C++ as

   for( int pass = 1; pass <= n; ++pass){
   	for( int index = 0; index < n; ++index){
   		for( int count = 1; count <= 10; ++count){
   			...
   		} // end for
   	} // end for
   } // end for
   

   The previous code shows only the repetition in the algorithm, not the computations that occur within the loops. These computations, however, are independent of n. What is the order of the algorithm? Justify your answer.
6. Which search algorithm would you recommend for searching for an element in an unsorted array? Justify your answer.
7. How will algorithm analysis help you as a computer scientist?

Submission

Submit your txt file at https://3110.cs.mtsu.edu/. For further instructions, please see the Miscellaneous page.

Rubric:

Points          Question
----------      --------------------------------------------------------------
_____ /  2	1
_____ /  4	2
_____ /  2	3
_____ /  1	4	
_____ /  2	5
_____ /  2	6
_____ /  2	7

_____ / 15      Total

Last Modified: