Testing Rebecca Black’s Claims

Posted by Kurt on March 25th, 2011

I was unsure about some of the bold claims that Rebecca Black made in her latest hit video, so I wrote some unit tests for it. It turns out she is telling the truth!

public void testRebeccaIsntLying() {
    Calendar rebeccasCalendar =
        Calendar.getInstance(TimeZone.getTimeZone("America/Los_Angeles"));

    // The song went viral on Friday, March 11, 2011
    rebeccasCalendar.set(2011, Calendar.MARCH, 11);

    // Yesterday was Thursday, Thursday
    rebeccasCalendar.add(Calendar.DAY_OF_MONTH, -1);
    assertEquals(Calendar.THURSDAY, rebeccasCalendar.get(Calendar.DAY_OF_WEEK));

    // Today i-is Friday, Friday (Partyin’)
    rebeccasCalendar.set(2011, 2, 11);
    assertEquals(Calendar.FRIDAY, rebeccasCalendar.get(Calendar.DAY_OF_WEEK));

    // Tomorrow is Saturday
    rebeccasCalendar.add(Calendar.DAY_OF_MONTH, 1);
    assertEquals(Calendar.SATURDAY, rebeccasCalendar.get(Calendar.DAY_OF_WEEK));

    // And Sunday comes afterwards
    rebeccasCalendar.add(Calendar.DAY_OF_MONTH, 1);
    assertEquals(Calendar.SUNDAY, rebeccasCalendar.get(Calendar.DAY_OF_WEEK));
  }

I sent this code out for review at work, and received quite a bit of insightful feedback from my co-workers:

  • As you mentioned two lines up, “yesterday was Thursday, Thursday”. Do we need to assertEquals twice?
  • I appreciate the attempt, but I have to say I find your test lacking. For starters, you only assert that yesterday was Thursday once.  I’d see two sequential assertions as the absolute minimum. More concerningly, a crucial property of the calendar is that it can be used to determine whether or not we need to get down.  Yet I see no assertion that we need to get down if and only if it is indeed Friday. Even if, in fact, it proves that no one is looking forward to the weekend, I don’t believe your test will catch it, to say nothing of our current observed state of partying. But these are just examples.  Who needs a Calendar object if this is all it’s good for?
  • Shouldn’t the time zone be determined dynamically? Rebecca may be traveling.
  • I’d ask you to assert that she has chosen the appropriate seat, but this may be out of the scope of this change.  A TODO will be fine.
  • While you are adding the above test, I would like you to consider updating this test case as well to assert that Rebecca is indeed looking forward to the weekend, as well as partying partying during the weekend, as appropriate given the day.
  • Can you devise tests for the following constraints made in the original documentation: 1. Gotta get down on Friday.  (e.g. ASSERT(didGetDown) 2. Everybody’s looking forward to the weekend.

CS4HS Workshop

Posted by Kurt on July 6th, 2010

After a nice relaxing weekend down on the Jersey shore, I flew up to Rochester, NY on Sunday, June 27th. My 6pm flight out of JFK quickly turned into a 9pm departure due to storms in upstate NY. After a rocky landing and a quick ride to the Radisson hotel on campus, I got started on my slides. Something about procrastinating on RIT campus just felt right ;-) After 4 hours of working on the slides, I called it a night and caught a few hours of rest.

CS4HS LogoOn June 28-30th, RIT hosted a 3 day workshop for area math and computer science high school teachers called Computer Science for High School, CS4HS@RIT. The workshop was sponsored by the RIT Computer Engineering department and Google. On June 28th, I gave the workshop’s keynote talk on “Life of a Software Engineer”. I fielded a bunch of awesome questions from the audience of around 100 teachers. In hindsight, I should have anticipated that teachers would have come prepared with tons of questions and should have allocated more time for questions.

After the keynote, I met up with some old professors and advisors and later discussed some future plans for Video CAPTCHA research with my old thesis advisor. And finally, no trip to Rochester would be complete without a trip to MacGregors to sample some of their delicious beer and food with some old friends. After another couple of hours of delays, I landed back at JFK around midnight, grabbed a beer with a friend in the city, and made it back to my apartment by 3am…just in time to grab a few hours of sleep before work in the morning.  I love my life :-)

RIT news article on Video CAPTCHAs

Posted by Kurt on November 6th, 2009

The RIT Athenaeum has just published a short article describing Video CAPTCHAs. You can find it in print around the RIT campus and online here: http://www.rit.edu/news/story.php?id=47112

Balancing Usability and Security in a Video CAPTCHA

Posted by Kurt on July 13th, 2009

This week (July 15th - July 17th), Richard Zanibbi and I are attending SOUPS ‘09 in Mountain View, CA. It’s a smaller conference that’s gotten great reviews and has had some excellent CAPTCHA-related work presented in the past. On Friday morning, I’ll be presenting a paper titled Balancing Usability and Security in a Video CAPTCHA. A reporter from ZDNet.co.uk has already written a short article about it which you can find here.

Paper

The paper can be downloaded here and the slides can be downloaded here. It’s also available at the ACM Digital Library.

Bibtex Entry

@inproceedings{kak-soups09,
	Title = {Balancing Usability and Security in a Video CAPTCHA},
	Author = {Kurt Alfred Kluever and Richard Zanibbi},
	Booktitle = {Proceedings of the 5th Symposium On Usable Privacy and Security 2009},
	Address = {Mountain View, CA, USA},
	Month = {July},
	Year = {2009}
}

Paper Accepted at SOUPS ‘09

Posted by Kurt on April 26th, 2009

Richard Zanibbi and I will be presenting Balancing Usability and Security in a Video CAPTCHA at SOUPS ‘09 this summer. SOUPS is conveniently being held on Google’s Mountain View campus, so I’ll be out there for the week visiting friends, enjoying the sun, working, and attending the conference. Once our camera-ready version is finished, I’ll post a full copy of the paper here and also on my new Google Research page.

Here’s some quick info about SOUPS:

The fifth Symposium on Usable Privacy and Security (SOUPS) will be held July 15-17, 2009 at Google in Mountain View, CA. This symposium will bring together an interdisciplinary group of researchers and practitioners in human computer interaction, security, and privacy. The program features technical papers, workshops and tutorials, a poster session, panels and invited talks, and discussion sessions. SOUPS 2009 will be held in cooperation with ACM SIGCHI.

My Erdős Number is 5

Posted by Kurt on March 15th, 2009

For fun, I calculated my Erdős number tonight (using the AMS Collaboration Distance Calculator).  Your Erdős number represents the number of hops between you and the famous Hungarian mathematician Paul Erdős (where a link is established between two authors when they have collaborated on an academic paper together).  It was created as a joke to approximate your importance in the mathematical community. Erdős was assigned a number of 0.  Each of Erdős’ collaborators were assigned a number of 1, their collaborators were assigned a number of 2, and so forth.  The shortest path I could find between Erdős and myself was of length 5:

  1. Paul Erdős and Paul C. Kainen
  2. Paul C. Kainen and Vladik Ya. Kreinovich
  3. Vladik Ya. Kreinovich and Hung Trung Nguyen
  4. Hung Trung Nguyen and Leonid K. Reznik
  5. Leonid K. Reznik and Kurt Alfred Kluever (via IEEE Sensors 2007)

I also found a couple of length 6 paths with interesting researchers (bolded below) in them:

  1. Paul Erdős and Dieter Kratsch
  2. Dieter Kratsch and Jitender S. Deogun
  3. Jitender S. Deogun and Shashank K. Mehta
  4. Shashank K. Mehta and George Nagy
  5. George Nagy and Richard Zanibbi
  6. Richard Zanibbi and Kurt Alfred Kluever (via IEEE WNYIP 2008)
  1. Paul Erdős and Andrew M. Odlyzko
  2. Andrew M. Odlyzko and Colin L. Mallows
  3. Colin L. Mallows and Henry S. Baird
  4. Henry S. Baird and Dorothea Blostein
  5. Dorothea Blostein and Richard Zanibbi
  6. Richard Zanibbi and Kurt Alfred Kluever (via IEEE WNYIP 2008)

An interesting article here states that “the median Erdős number is 5; the mean is 4.65, and the standard deviation is 1.21.”

Here are some great links for more reading about this topic:

Data structure for weighted sampling

Posted by Kurt on March 9th, 2009

I was asked the following question: Design a data structure that supports 2 operations:

  • insert(element, weight)
  • sample()

When you insert an element into the data structure, you specify a weight. This weight divided by the total of the other weights in the data structure, is the probability that the item is returned when sample() is invoked. You should design your data structure with both speed and space in mind.

Here is a good solution. The insert() operation requires O(1) constant amortized time and the sample() operation requires O(lg n) time due to binary search. The space requirements is O(n) as well.

public final class BinarySearchWeightedSampler<E> {
  private final List<E> elements;
  private final List<Double> weights;

  public BinarySearchWeightedSampler() {
    this.elements = new ArrayList<E>();
    this.weights = new ArrayList<Double>();
  }

  public void insert(E element, double weight) {
      elements.add(element);
      if (weights.isEmpty()) weights.add(weight);
      else weights.add(weight + weights.get(weights.size() - 1));
  }

  public E sample() {
    return elements.get(
        binarySearch(Math.random(), 0, weights.size() - 1,
                     weights.get(weights.size() - 1)));
  }

  private int binarySearch(double val, int low, int high,
      double totalWeight) {
    if (high < low) return low;
    int mid = low + ((high - low) / 2);
    int midValue = weights.get(mid) / totalWeight;
    if (midValue > val)
      return binarySearch(val, low, mid - 1, totalWeight);
    else if (midValue < val)
      return binarySearch(val, mid + 1, high, totalWeight);
    else
      return mid;
  }
}

If we ignore the space requirements and assume the weights have finite precision (I chose integers for clarity, but any finite precision number can be made to work), we can sample in O(1) constant time:

public final class DiscreteWeightedSampler<E> {
  private final List<E> elements;

  public DiscreteWeightedSampler() {
    this.elements = new ArrayList<E>();
  }

  public void insert(E element, int weight) {
    for (int i = 0; i < weight; ++i) {
      elements.add(element);
    }
  }

  public E sample() {
    return elements.get((int) (Math.random() * elements.size()));
  }
}

CS Department’s “5 Minutes with Kurt”

Posted by Kurt on March 8th, 2009

You knew you were headed for a career in Computer Science when…
I witnessed the thrill and the excitement of the dot com boom in the late 90’s.

What is your favorite class and why?
Theory of Computer Algorithms. This course is the first formal, in-depth course on algorithms, complexity, and data structures. These three components are the foundations of Computer Science and I highly recommend that everyone take this course (although it is a very difficult course).

One piece of advice I have for 1st year students is…
Establish a relationship with your professors by asking questions in class and utilizing office hours when you are confused.

If you could have dinner with a famous computer scientist, living or dead, who would you choose?
Luis von Ahn. His work on CAPTCHAs and human computation has inspired me to pursue it as my thesis topic.

What is the most interesting project you have worked on, either in a course or on the job?
The most interesting project I’ve worked on has been my thesis. Reading all of the existing research has helped me develop a brand new idea that nobody else in the world has worked on.

Where do you see yourself in ten years?
Hopefully back in school earning my PhD in Computer Science.

Original post: http://www.cs.rit.edu/about/profiles/Kurt_Kluever
PDF version: http://www.cs.rit.edu/five_minutes/pdf/Kurt_Kluever.pdf

Also check out 5 Minutes with Richard Zanibbi (my thesis advisor) and 5 Minutes with Brian Renzenbrink (a good friend).

Video CAPTCHAs at Center for Imaging Science

Posted by Kurt on January 30th, 2009

On January 28th, 2009, my thesis advisor (Richard Zanibbi) presented a talk on Video CAPTCHAs at the RIT Center for Imaging Science. An abstract of the talk can be download here. A video of his talk (with slides) can be watched here using Adobe Acrobat Connect.

MS Thesis available in RIT Library and DML

Posted by Kurt on January 25th, 2009

My thesis is now available in a bounded hard-copy at the RIT library on the 3rd floor (Call No. Q341 .K58 2008) and online through the RIT Digital Media Library.


Modified version of Webby Blue
Copyright © 2008 kloover.com. All rights reserved.
**This is my personal blog. The views expressed on these pages are mine alone and not those of my employer.**