CS 240: Lecture 8 - Pause

Dear students:

With a programming assignment due soon, we decided it would be best to dedicate a day for review and questions. Today we will work through some analysis problems together and discuss the problems you are encounter on the programming assignment or lab.

Analysis

As we have time, we will work through the analysis of these algorithms:

• public static boolean isSpecial(int n) {
    for (int i = 2; i * i <= n; ++i) {
      if (n % i == 0) {
        return false;
      }
    }
    return true;
  }

• public static int perhaps(int[] xs, int z) {
    int i = 0;
    int j = xs.length - 1;
  
    while (i <= j) {
      int k = (i + j) / 2; 
      if (xs[k] == z) {
        return k;
      } else if (xs[k] < z) {
        i = k + 1;
      } else {
        j = k - 1;
      }
    }
  
    return -1;
  }

• public static double calculate(double[] xs) {
    double y = 0.0;
    for (double x : xs) {
      y += x;
    }
    y = y / xs.length;
  
    double z = 0.0;
    for (double x : xs) {
      w = x - y;
      z += w * w;
    }
    
    return z / (xs.length - 1);
  }

• public static boolean maybe(String[] items) {
    for (int i = 0; i < items.length; ++i) {
      if (items.length > 10) {
        return false;
      }
    }
    return true;
  }

TODO

You've got a few things to do before we meet again:

See you next time!