teaching machines

CS 145 Lecture 16 – The birthday problem

March 30, 2012 by Chris Johnson. Filed under
Deprecated: Creation of dynamic property WP_Term::$cat_ID is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 378

Deprecated: Creation of dynamic property WP_Term::$category_count is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 379

Deprecated: Creation of dynamic property WP_Term::$category_description is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 380

Deprecated: Creation of dynamic property WP_Term::$cat_name is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 381

Deprecated: Creation of dynamic property WP_Term::$category_nicename is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 382

Deprecated: Creation of dynamic property WP_Term::$category_parent is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 383

Deprecated: Creation of dynamic property WP_Term::$cat_ID is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 378

Deprecated: Creation of dynamic property WP_Term::$category_count is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 379

Deprecated: Creation of dynamic property WP_Term::$category_description is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 380

Deprecated: Creation of dynamic property WP_Term::$cat_name is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 381

Deprecated: Creation of dynamic property WP_Term::$category_nicename is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 382

Deprecated: Creation of dynamic property WP_Term::$category_parent is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 383

Deprecated: Creation of dynamic property WP_Term::$cat_ID is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 378

Deprecated: Creation of dynamic property WP_Term::$category_count is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 379

Deprecated: Creation of dynamic property WP_Term::$category_description is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 380

Deprecated: Creation of dynamic property WP_Term::$cat_name is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 381

Deprecated: Creation of dynamic property WP_Term::$category_nicename is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 382

Deprecated: Creation of dynamic property WP_Term::$category_parent is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 383
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