Lab 3 -- Analysis of Algorithms

Exercise 1

found = false
k = 0
while not found and k < n - 1
{
      k = k + 1
      for (i = 0; i < k; i++)
          if (a[i] == s) found = true
}

This algorithm isn't very "efficient". Examine the algorithm and explain why.

Exercise 2

//Reverse 1:
for (i = 0; i < (n/2); i++)    // go through half the elements
{
      save = a[i]              // swap 1st with nth, 2nd with n-1st
      a[i] = a[n - i - 1]      //{etc...}
      a[n - i - 1] = save
}
//Reverse 2:
//Copy the 1st array to a 2nd array but in reverse order.
j = n - 1;                     // j runs backward through b[0..n-1]
for (i = 0; i < n; i++)
{
     b[j] = a[i]
     j = j - 1
}
// Copy b[0..n-1] into a[0..n-1].
for (i = 0; i < n; i++)
      a[i] = b[i]

Examine Reverse1 and Reverse 2. Which algorithm is more efficient in its use of space?  Why?

Exercise 3

Consider the following algorithm which determines the sum of the first n positive integers. 
     1.  sum = 0
     2.  for (int j = n; j > 0; j--)
     3.      sum = sum + j
     4.  print sum
Analyze this algorithm and determine the number of steps executed in each line of the algorithm.  Determine the Big-O of the algorithm.

Exercise 4

Determine a O(1) algorithm to calculate the sum of the first n positive integers. If you can't figure it out ask the lab assistant. Hint: This sum is called the Gauss sum. There is a one line equation in math to compute this sum.

Exercise 5

1. sum = 1
2. powerTwo = 2
3. while powerTwo < n
4.      sum = sum + powerTwo
5.      powerTwo = 2 * powerTwo
6. print sum

Let k be the number of times the while loop executes in the above algorithm. The number of steps executed is 4 + 3 * k. To see that this is true, determine how many times each of the lines (1 - 6) is executed and find the total.

Exercise 6

If n = 1000, approximately how many steps will be executed in the last algorithm?

Exercise 7

We have implemented three search functions in C++:  binarySearch, sequentialSearch, and awfulSearch.
In this exercise, you will experiment with these three algorithms (contained in the source file inlab3.cc) for different values of n. Copy the source file to your account.  Look at the code then execute it to see what it does. Remove the statements that print the array (save trees!) and add code to each function so it will calculate (and print) the number, f(n), of times the comparison statement
      if (sArray[??] == item) ....
is executed.  This value will essentially give the BIG-O for the function.   Why?  Do a worst-case analysis (that is, search for a value that is not in the array).  Create a table containing the number of times the comparison statement is execute for n = 100, 200, 300, 400, and 500 for all three searches.  Use the table to guess the Big-O of each algorithm.