Algorithm Analysis Exercises

1. Searching Algorithms
   1. Describe the algorithm for sequential search to your neighbor
   2. Describe the algorithm for binary search to your neighbor
   3. Outline the code for sequential search and binary search
   4. Write the code for sequential search and binary search
2. Algorithm Analysis
   1. A federal institution is considering contracting you to extend your lab project into a commercial grade program. One question they have is how much is the program going to cost? They're requesting a list of categorized costs for the program. What costs are there in developing such a program?
   2. Give examples of what is meant by n inputs for a given problem
   3. What's the difference between:
      • Best case
      • Average case
      • Worst case
      What is the default for algorithm analysis if one is not specified?
   4. List eight common growth functions and rank them in ascending order based on their Big-Oh:
   5. Demo: Shuffling Example
   6. What are the 4 properties of growth-rate functions:
   7. Determine the Big-Oh of the growth functions below:
      1. 5N + 4
      2. 9N²+ 8N - 7
      3. 2 log N
      4. 3N log 4N
      5. 6*2^7N
      6. 3N! + 1/2*N³
      7. 42
      8. 2*N³ + 999 * N² + 123456789*N
      Stuck? Plug in some numbers to get a better idea.
   8. What is the Big-Oh of sequential search?
   9. What is the Big-Oh of binary search?
   10. Discuss with your neighbor(s) how understanding algorithm analysis will help you at your future job
   11. What is the worst case order for the following scenarios:
       1. Given an array and an index, displaying the element at the specified index in the array
       2. Given an array of Fibonacci numbers, adding together the first n values
       3. Finding an item in a sorted array of integers
       4. Finding an item in an array of integers
       5. Summing all elements in an ArrayList of Integers
       6. Summing the length of all strings in a two-dimensional array (n by m elements)

Last Modified: