Code from recitation 9

1. Efficiency analysis.

We looked at two programs during recitation. Here was one of them:

     BigO7.java 

  1  
  2  public class BigO7 {
  3      public static void main(String[] args) {
  4          int N = 5;
  5          
  6          int f = factorial(N);
  7          
  8          System.out.println(f);
  9      }
 10      
 11      static int factorial(int N) {
 12          int p = 1;
 13          for (int i=1; i<=N; i++) {
 14              p = p * i;
 15          }
 16          return p;
 17      }
 18  }
 19  
 20  

This one we decided was:

• Best case: O(N)
• Worst case: O(N)

And here is another:

     BigO5.java 

  1  
  2  public class BigO5 {
  3      public static void main(String[] args) {
  4          int N = 120;
  5          
  6          boolean square = isPerfectSquare(N);
  7          
  8          System.out.println(square);
  9      }
 10      
 11      static boolean isPerfectSquare(int N) {
 12          int a = 0;
 13          int b = N;
 14          
 15          while (a <= b) {
 16              int c = (a + b) / 2;
 17              
 18              if (c*c == N) {
 19                  return true;
 20              }
 21              else if (c*c < N) {
 22                  a = c + 1;
 23              }
 24              else {
 25                  b = c - 1;
 26              }
 27          }
 28          return false;
 29      }
 30  }
 31  
 32  

This one we decided to be:

• Worst case: O(N)
• Best case: ???

The best case for that one is tricky because you'd have to know a bit of number theory, which I at least do not. You can tell it has to be at least Ω(1) (if the loop breaks the first time through) but is probably worse than that.

2. Poker hands.

There's a lot more we could do with these problems. If you want to do more poker problems another recitation that would be cool.

Finding a pair:

     Pair.java 

  1  
  2  public class Pair {
  3   
  4   public static void main(String[] args) {
  5    int[] hand = { 9, 7, 3, 3, 5 };
  6    
  7    boolean hasPair = false;
  8    
  9    for (int i=0; i<hand.length; i++) {
 10     for (int j=0; j<hand.length; j++) {
 11      if (hand[i] == hand[j] && i != j) {
 12       System.out.println(hand[i] + " == " + hand[j]);
 13       hasPair = true;
 14      }
 15     }
 16    }
 17    
 18    System.out.println(hasPair);
 19   }
 20  }
 21  

Finding three of a kind:

     Three.java 

  1  
  2  public class Three {
  3   
  4   public static void main(String[] args) {
  5    int[] hand = { 3, 7, 3, 3, 5 };
  6    
  7    boolean hasTripple = false;
  8    
  9    for (int i=0; i<hand.length; i++) {
 10     for (int j=0; j<hand.length; j++) {
 11      if (hand[i] == hand[j] && i != j) {
 12       for (int k=0; k<hand.length; k++) {
 13        if (hand[i] == hand[k] && i != k && j != k) {
 14         hasTripple = true;
 15        }
 16       }
 17      }
 18     }
 19    }
 20    
 21    System.out.println(hasTripple);
 22   }
 23  }
 24  

Finding four of a kind:

     Four.java 

  1  
  2  public class Four {
  3   
  4   public static void main(String[] args) {
  5    int[] hand = { 3, 7, 3, 3, 3 };
  6    int N;
  7    
  8    boolean hasFour = false;
  9    
 10    for (int i=0; i<hand.length; i++) {
 11     for (int j=0; j<hand.length; j++) {
 12      if (hand[i] == hand[j] && i != j) {
 13       for (int k=0; k<hand.length; k++) {
 14        if (hand[i] == hand[k] && i != k && j != k) {
 15         for (int l=0; l<hand.length; l++) {
 16          if (hand[i]==hand[l] && i!=l && j!=l && k!=l) {
 17           hasFour = true;
 18          }
 19         }
 20        }
 21       }
 22      }
 23     }
 24    }
 25    
 26    System.out.println(hasFour);
 27   }
 28  }
 29  

Try to think about how you might do K-of-a-kind (out of N cards, where, hopefull, N ≥ K). Someone pointed out in recitation that you can do it with recursion; this is true. You can also do it without recursion, in various ways.