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.

Code from recitation 8

1. Searching through a 2D array for a particular element.

     ArraySearch.java 

  1  
  2  public class ArraySearch {
  3   public static void main(String[] args) {
  4    String[][] str = {
  5     { "a", "b", "c", "d" },
  6     { "e", "f", "g", "h" }
  7    };
  8  
  9    String goal = "c";
 10    
 11    boolean error = true;
 12    for (int i=0; i<str.length; i++) {
 13     for (int j=0; j<str[i].length; j++) {
 14      if (str[i][j].equals(goal)) {
 15       error = false;
 16       System.out.println("row = " + i);
 17       System.out.println("col = " + j);
 18       break;
 19      }
 20     }
 21     if (!error) {
 22      break;
 23     }
 24    }
 25    if (error) {
 26     System.out.println("Error");
 27    }
 28   }
 29  }
 30  
 31  

2. Running out of memory

     OutOfMemory.java 

  1  
  2  public class OutOfMemory {
  3   public static void main(String[] args) {
  4    int[] x = new int[1];
  5    while (true) {
  6     int y = x.length;
  7     y = y * 2;
  8     System.out.println(y);
  9     x = new int[y];
 10    }
 11   }
 12  }
 13  
 14  

Recitation 7 Code

1. I don't remember what this was for, but here it is!

     FillWithSevens.java 

  1  public class FillWithSevens {
  2      public static void main(String[] args) {
  3          int[] x = new int[3];
  4  
  5          for (int i=0; i<3; i++) {
  6              x[i] = 7;
  7          }
  8      }
  9  }

2. Modifying an array:

     ModifyArray.java 

  1  class ModifyArray {
  2      public static void main(String[] args) {
  3          int[] x = { 1, 1 };
  4          int[] y = x;
  5  
  6          y[0] = 3;
  7  
  8          System.out.println(x[0]);
  9      }
 10  }

3

3. Reverse an array in a new array:

     ReverseNewArray.java 

  1  public class ReverseNewArray {
  2      public static void main(String[] args) {
  3          int[] x = { 1, 2, 3 };
  4  
  5          int[] y = new int[x.length];
  6  
  7          int len = x.length;
  8          int j = 0;
  9          for (int i=len-1; i>=0; i--) {
 10              y[j] = x[i];
 11              System.out.println(java.util.Arrays.toString(y));
 12              j++;
 13          }
 14          System.out.println(java.util.Arrays.toString(x));
 15      }
 16  }

[3, 0, 0]
[3, 2, 0]
[3, 2, 1]
[1, 2, 3]

4. Reverse an array in place:

     ReverseInPlace.java 

  1  public class ReverseInPlace {
  2      public static void main(String[] args) {
  3          int[] x = { 1, 2, 3, 4, 5, 6, 7, 8 };
  4  
  5          int j = x.length-1;
  6          for (int i=0; i<x.length/2; i++) {
  7              int f = x[i];
  8              x[i] = x[j];
  9              x[j] = f;
 10              System.out.println(java.util.Arrays.toString(x));
 11              j--;
 12          }
 13      }
 14  }

[8, 2, 3, 4, 5, 6, 7, 1]
[8, 7, 3, 4, 5, 6, 2, 1]
[8, 7, 6, 4, 5, 3, 2, 1]
[8, 7, 6, 5, 4, 3, 2, 1]

Code from recitation 6

1. Take a String, and make just the first letter capital.

     Capital.java 

  1  public class Capital {
  2  
  3      public static void main(String[] args) {
  4          String x = "abcdefgh";
  5  
  6          String y = x.substring(0, 1).toUpperCase();
  7          String z = x.substring(1, x.length());
  8          System.out.println(y + z);
  9      }
 10  }

Abcdefgh

2. See if a particular String belongs to an array (note that we haven't gotten to arrays yet. But we will).

     InList.java 

  1  public class InList {
  2      public static void main(String[] args) {
  3          String[] a = { "a", "aa", "aaa" };
  4  
  5          String x = "asdfjeoi";
  6          boolean in = false;
  7          for (int i=0; i<a.length; i++) {
  8              String y = a[i];
  9              if (x.equals(y)) {
 10                  in = true;
 11                  break;
 12              }
 13          }
 14          if (in == true) {
 15              System.out.println("x is in a");
 16          }
 17          else {
 18              System.out.println("x is NOT in a");
 19          }
 20      }
 21  }

x is NOT in a

3. Go through the words in a sentence and count how many letters are in each:

     LetterCount.java 

  1  public class LetterCount {
  2      public static void main(String[] args) {
  3          String x = " words in a sentence ";
  4  
  5          for (int i=0; i<x.length(); i++) {
  6  
  7              if (x.charAt(i) == ' ') {
  8                  for (int j=i+1; j<x.length(); j++) {
  9                      if (x.charAt(j) == ' ') {
 10                          int length = j - i - 1;
 11                          String word = x.substring(i, j);
 12                          System.out.println(word);
 13                          System.out.println(length);
 14                          break;
 15                      }
 16                  }
 17              }
 18          }
 19      }
 20  }

 words
5
 in
2
 a
1
 sentence
8

Note the extra spaces around the word in order to make our algorithm work. We could also have written:

  1  String x = "words in a sentence";
  2  x = " " + x + " ";