Feeds:
Posts
Comments

Archive for the ‘Uncategorized’ Category

This evening, I presented Collections Refueled at the Silicon Valley JUG. Thanks to the JUG for having me, and to the attendees for all the interesting questions!

Here are the slides for my presentation: CollectionsRefueled.pdf

 

Advertisements

Read Full Post »

Now that Devoxx US is imminent, it’s about time for me to post about Devoxx BE 2016, which took place in November 2016 in Antwerp. That was several months ago, which was ages in conference time, so this post is mainly a placeholder to host slides and links to the videos.

Array Linked to a List, the Full Story! – José Paumard (video)

I was surprised to find that I was mentioned by name in the abstract for this university session. José Paumard took a tweet of mine from a year earlier (actually one by my alter ego, Dr Deprecator) and turned it into an entire university session. José was happy to have me attend the session, and he was gracious enough to invite me on stage for a few comments and questions.

Streams in JDK 8: The Good, The Bad and the Ugly – Simon Ritter (BOF)

This was another of my impromptu appearances. Simon had submitted this session, and he asked me to join him in presenting it. I said that I wasn’t sure what I would speak about. He said to me, “I’ll put up a slide and say a few words about it. I’m sure you’ll have an opinion.” (He was right.) This was a BOF, so it was pretty informal, but Simon came up with some really interesting examples, and we had a good discussion and covered a lot of issues.

Simon and I will be repeating this BOF at Devoxx US this coming week.

Ask the JDK Architects – panel session (video)

This was a panel session featuring Mark Reinhold and Brian Goetz (the actual JDK architects) along with Alan Bateman and myself (JDK Core Libraries engineers). This session consisted entirely of answering questions from the audience.

Optional: The Mother of All Bikesheds – conference session (slides, video)

This was a conference session about a single Java 8 API, java.util.Optional. Some were were skeptical that I could talk for an entire hour about a single API. I proved them wrong. Credit for the title goes to my übermanager at Oracle, Jeannette Hung. It refers to the many protracted mailing list discussions (“centithreads”) about the design of Optional.

Thinking in Parallel – joint conference session with Brian Goetz (slides, video)

This was an amazing experience because the auditorium was so full that people were sitting on the steps. Brian Goetz was the big draw here, but I also think it was packed because there were fewer sessions running at the same time.

* * *

I was pleased to learn that both of my conference sessions were in the top 20 talks for the conference. Thanks for your support!

Read Full Post »

Earlier this month I had the pleasure of attending Donald Knuth’s 20th annual Christmas Tree Lecture. (announcement, video)

For me it was quite a bit of nostalgia. When I was a Computer Science student at Stanford, uh, a number of decades ago, of course I had to take a class from Knuth, who was (and still is) a Very Famous Computer Science Professor. The class was nominally a computer science class, but it was mostly math. In fact, it was all math. I’m good at math, having completed several semesters of college-level math even after placing out of introductory calculus classes. However, I’m not really, really good at math, which is what you have to be to keep up with Knuth. As a result I spent most of that class wallowing in confusion.

Knuth’s Christmas Tree lectures aren’t about Christmas trees, of course, but they are ostensibly about the Computer Science kind of trees, and they occur around Christmastime. Hence, Christmas Tree. But they aren’t so much about Computer Science as they are about math. So it was quite a familiar feeling for me to sit in a Stanford lecture hall, for the first time in decades, listening to Knuth give a lecture on math, with me wallowing in confusion most of the time.

A few years after I left Stanford, Knuth (along with Ronald Graham and Oren Patashnik) published Concrete Mathematics:

ConcreteMathematics

(Amazon link)

For some reason I was compelled to buy it. I probably bought it because it must be a Very Important Computer Science Book because it has the name of a Very Famous Computer Science Professor on it. So I bought it and flipped through it, but it was mostly about math, and I’m good at math but not that good, so I eventually shelved it and didn’t look at it for a long time.

A number of years later (perhaps April, 2008) I was quite into playing Grand Theft Auto: Vice City. Yes, this is that notorious game where you’re the criminal and you do a variety of nasty things. One of the different things you can do is to steal a police car and run “Vigilante Missions” where you chase down and kill criminals. You start off at the first level where the goal is to kill one criminal, and you get a reward of $50. At the second level, you have to kill two criminals, and the reward is $200. At level three, there are three criminals, and the reward is $450. At level four the reward is $800, and at level five the reward is $1,250. The rewards keep rising at each level, even though the number of criminals maxes out after a while.

The reward given at each level isn’t necessarily obvious. After playing for a while, I paused the game to see if there was any information about this on the internet. Various gaming guide and FAQ authors have gone to the trouble of documenting the reward amounts. For example, the Grand Theft Auto: Vice City Vigilante Reward FAQ lists the reward for each level, as well as the cumulative reward, for every level up to level 1,000! Furthermore, it gives a formula of sorts for computing the reward amount for each level:

You take the level you are at, subtract one, multiply by 100, add 50 and add that to the previous level’s reward to compute the level you want.

(edited for clarity)

Stated mathematically, this is a recurrence relation where the reward for level n is given as follows:

R_n = 100(n-1) + 50 + R_{n-1}

This can be simplified a bit:

R_n = 100n - 50 + R_{n-1}

It’s pretty easy to see that each level k adds a reward of 100k – 50 dollars, so this can be expressed as a summation:

R_n = \sum\limits_{k=1}^{n}(100k - 50)

This is pretty easy to simplify to closed form:

\begin{aligned} \\  R_n &= \sum\limits_{k=1}^{n}(100k - 50) \\  &= 100 \sum\limits_{k=1}^{n} k - \sum\limits_{k=1}^{n} 50 \\  \end{aligned}

That first summation term is simply the sum of integers from 1 to n so it can be replaced with the well-known formula for that sum:

\begin{aligned} \\  R_n &= 100\frac{n(n+1)}{2} - 50n \\  &= 50n^2  \end{aligned}

OK, pretty simple. But this is just the reward for a given level n. What about the cumulative reward for having completed all levels 1 through n? Now this is a bit more interesting. Let’s define the cumulative reward for level n as follows:

\begin{aligned} \\  S_n &= \sum\limits_{k=1}^{n} 50k^2 \\  \end{aligned}

I don’t know how the guy made the table for levels up to 1,000. He might have used a spreadsheet, or he might have even played out all 1,000 levels and painstakingly kept track of the reward and cumulative reward at each level. (That would be entirely believable; gamers are nothing if not compulsive.) Looking at the “formula” he gave for computing the reward at each level, I’m quite certain he didn’t compute a closed form for the cumulative reward at each level. Clearly, it was important for me to figure that out.

At this point I had forgotten the game and was busy filling up sheets of paper with equations.

Deriving a closed form for this should be simple, right? Just perturb the indexes:

\begin{aligned} \\  S_n &= \sum\limits_{k=1}^{n} 50k^2 \\  S_{n+1} &= \sum\limits_{k=1}^{n+1} 50k^2 \\  S_n + 50(n+1)^2 &= 50 + \sum\limits_{k=2}^{n+1}50k^2 \\  &= 50 + \sum\limits_{k=1}^{n}50(k+1)^2 \\  &= 50 + \sum\limits_{k=1}^{n}50(k^2 + 2k + 1) \\  &= 50 + \sum\limits_{k=1}^{n}50k^2 + \sum\limits_{k=1}^{n} 100k + \sum\limits_{k=1}^{n} 50 \\  &= 50 + S_n + 100 \sum\limits_{k=1}^{n} k + 50n \\  \end{aligned}

Oh crap. The S_n terms just cancel out. That’s what we’re trying to solve for. I tried several different techniques but nothing I tried worked. I was stumped. Hunting around on the web didn’t give me any helpful ideas, either.

At this point I couldn’t finish the game, because I just had to know how to compute the cumulative reward for completing n levels of the mission. I mean, this was important, right?

Swimming from the depths of my memory came a realization that somewhere I might have a book that would have some helpful information about solving sums and recurrences like this. I quickly found and pulled Concrete Mathematics from the shelf, blew the dust off, and curled up on the couch and started reading. Sure enough, right there at the start of section 2.5, General Methods, there’s a discussion of how to use several techniques to find the sum of the first n squares. (Page 41, equation 2.37) Great! How did Knuth et. al. solve it?

Method 0 is simply to look it up. There’s a well-known formula for this available in many reference books such as the CRC Handbook. But that’s cheating. I needed to know how to derive it. I kept reading.

Method 1 is to guess the answer and prove it by induction. I’m really bad at guessing stuff like this. I kept reading.

Method 2 is to perturb the sum. Aha! This is what I tried to do. Where did I go wrong? Turns out they did the same thing I did and ran into exactly the same problem — the desired sum cancels out. But they had one additional bit of insight: in attempting to find the sum of n squares, they ended up deriving the sum of the first n integers. Huh? Let’s pick up where we left off:

\begin{aligned} \\  S_n + 50(n+1)^2 &= 50 + S_n + 100 \sum\limits_{k=1}^{n} k + 50n \\  50n^2 + 50n &= 100 \sum\limits_{k=1}^{n} k \\  \frac{n(n+1)}{2} &= \sum\limits_{k=1}^{n} k \\  \end{aligned}

Knuth et. al. continue by conjecturing that, if we tried to perturb the sum of cubes, a closed form for the sum of squares might just fall out. Let’s try that!

\begin{aligned} \\  T_n &= \sum\limits_{k=1}^{n} k^3 \\  T_{n+1} &= \sum\limits_{k=1}^{n+1} k^3 \\  T_n + (n+1)^3 &= 1 + \sum\limits_{k=2}^{n+1} k^3 \\  &= 1 + \sum\limits_{k=1}^{n} (k+1)^3 \\  &= 1 + \sum\limits_{k=1}^{n} (k^3 + 3k^2 + 3k + 1) \\  &= 1 + \sum\limits_{k=1}^{n} k^3 + 3 \sum\limits_{k=1}^{n} k^2 + 3 \sum\limits_{k=1}^{n} k \  + \sum\limits_{k=1}^{n} 1 \\  &= 1 + T_n + 3 \sum\limits_{k=1}^{n} k^2 + \frac{3}{2}n(n+1) + n  \end{aligned}

OK, there’s our sum of squares term. Canceling T_n and simplifying,

\begin{aligned} \\  n^3 + 3n^2 + 3n &= 3 \sum\limits_{k=1}^{n} k^2 + \frac{3}{2}n^2 + \frac{3}{2}n + n \\  n^3 + \frac{3}{2}n^2 + \frac{1}{2}n &= 3 \sum\limits_{k=1}^{n} k^2 \\  \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n &= \sum\limits_{k=1}^{n} k^2 \\  \frac{2n^3 + 3n^2 + n}{6} &= \sum\limits_{k=1}^{n} k^2 \\  \frac{n(n+1)(2n+1)}{6} &= \sum\limits_{k=1}^{n} k^2 \\  \end{aligned}

And there we have it. This matches the formula given in the CRC Handbook. The solution to my particular problem, the cumulative reward for Vigilante Mission levels, is simply 50 times this quantity.

What does this have to do with Christmas trees? Not much, but it does have a lot to do with Donald Knuth. It was good to see his lecture, even if I didn’t understand a lot of it. But I did apparently pick up something from his class, and I was able to figure out how to solve a problem (even if it was a silly one) with help from one of his books. And the equations this article use the WordPress plugin for LaTeX, which of course originally came from Knuth. So here’s to you, Don, have a happy new year!

Read Full Post »