teaching machines

CS 145 Lecture 16 – The birthday problem

March 30, 2012 by Chris Johnson. Filed under cs145, lectures, spring 2012.

Agenda

• the birthday problem

Program This

Odd rows: You are given a month and day, both as numbers. What day within the year is it? Write down your algorithm in pseudocode.

Even rows: You are given a day of the year, in [1, 366]. What month and day is it? Write down your algorithm in pseudocode.

Birthdays

3,27
8,23
4,28
9,5
4,1
3,19
8,30
9,6
12,6
12,5
11,21
8,29
6,19
2,4
10,17
10,31
11,16
7,29
7,14
6,7
11,3
4,19
4,20
6,26
8,29
3,10
2,21
9,8
11,23
2,8
10,9
1,10
12,8
3,17
2,28
9,11
3,20
2,19
11,30

Code

Birthday.java

package preexam2;

public class Birthday {
  
  public static void main(String[] args) {
    for (int m = 1; m <= 12; ++m) {
      for (int d = 1; d <= 31; ++d) {
        System.out.println(m + "/" + d + ": " + monthDayToIndex(m, d));
      }
    }
  }

  public static int monthDayToIndex(int month,
                                    int day) {
    // int[] monthCardinalities = new int[12];
    // monthCardinalities[0] = 31;
    int[] monthCardinalities = {
      31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
    };

    int index = day - 1;

    for (int i = 0; i < month - 1; ++i) {
      index += monthCardinalities[i];
    }

    return index;
  }
  
  public String indexToMonthDay(int index) {
    int[] monthCardinalities = {
      31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
    };
    
    int[] monthStartingIndices = new int[12];
    for (int m = 1; m < 12; ++m) {
      // Jan 1 0
      // Feb 1 31
      // March 1 60
      monthStartingIndices[m] = monthStartingIndices[m - 1] +
                                monthCardinalities[m - 1];
    }
    
    for (int m = 0; m < 12; ++m) {
      if (monthStartingIndices[m + 1] > index) {
        int day = index - monthStartingIndices[m];
        return (m + 1) + "/" + day;
      }
    }
    
    return null;
  }
}

Haiku