# Student Projects 2014 - Let's go to the video tape

Just completed the second time through for my Software Development course. Last year we had a great time at our Demo Night hosted at Google.

This year, unfortunately, due to a variety of reasons, we couldn't get the event together. Still, the kids did great work so I thought I'd share.

This year, I asked each group to make a short video.

First up, we've got bit<<shift - a search engine for code. Nice idea and a really slick interface.

Next up, we've got Socialpedia - our answer to Klout -

And then Twitch Rock-em-Sock-em Robots -

There were a bunch of other neat projects including a site that crowd-sources 311 trash related problems and a version of the game "Frozen Synapse" where you can program your forces using an embedded Lisp interpreter.

Very cool stuff.

Good job guys!!!!!

# What I love about StuyCS

One of the things I love about StuyCS is that we've built a true Geek culture.

Last week, we had a last minute visitor - Stephen Wolfram. Well known for Mathematica and more importantly, Wolfram Alpha, without which our students wouldn't be able to complete all their homework.

The only problem was that we had about 24 hours from when the visit was confirmed til the talk was to take place.

It was a little rough, but we pulled it together - convinced the the administration to let us use the auditorium, sent a letter out to the teachers and in general get things ready.

I've heard our auditorium holds anywhere between 400 and 800 students – the kids filled the place!!!

Only at a place like Stuy.

The talk was great talk and the kids followed up with terrific questions. Dr. Wolfram spoke for about 40 minutes and then stayed to answer questions for another 40. Had the auditorium not been booked after school, I think he would have gone on for another hour.

What I loved is here we have a Math/Science/CS guy, but to the StuyCS students, he's a rock star.

The next day I got comments like:

"That was amazing," "I've heard talks by brilliant people before, but never a visionary," "He's actually building the future," and "that was the best hour of my four years at Stuyvesant."

All in all, it was well worth the craziness of putting it together at the last minute.

# Dream It, Code It, Win It

Last night, I attended the Dream It, Code It, Win It awards.

I'd actually write up the event but Fred Wilson's already done a better job at that than I could: http://avc.com/2014/05/dream-it-and-code-it/

As Fred stated on his blog, it's a real shame that the high schooler's didn't get to show off their work but it was great to see that there were entries from a variety of schools including The Academy for Software Engineering and The Young Women's Leadership Academy.

As part of the application process, the teams made short videos. Here are three of the Stuy entries. I'll add the fourth once I get it.

The first two were written by teams in our senior SoftDev class the third by juniors currently in APCS using mostly what they learned in the second half of our intro class.

Enjoy.

Cartwheels:

Tour de City:

Fun Time Projects:

# Twitch Coding

We have the kids write programs in all sorts of ways

• on paper
• solo
• informally in pairs
• "pair programming"
• We have them trade code, pick up each others projects, and more.

We do lots of different things to engage the kids in a lot of different ways and I love it when someone comes up with a new technique.

My friend, colleague, and incidentally, former student, Sam had such an idea the other day. Sam started his teaching career at Francis Lewis High School and it took us a while to convince him to join the team, but he's been with us for about three years now and he's terrific.

Sam's also our resident gamer so I guess I shouldn't have been surprised when Sam said he was going to do Twitch Pokemon coding with his classes. It sounded great.

In Twitch Pokemen, users type moves into a chat window and a bot reads the commands to control a Pokemon. Sam's idea was to apply it to a CS class.

I loved the idea so I tried it in my classes.

First cut, I did it with stacks. We had a basic design in mind and then we started the "Twitch Coding."

We went up and down the rows. When it was a students turn, they could either add a word, line, or concept, delete one, or change one.

So, for example, if the state of the code was:

public Node top;

public void push(String s) {
Node n = new Node(s);
}


a student could:

• add n.setNext(top) to the push routine
• change public to private in the declaration of top

Or the somewhat lame

• add a // above the push declaration line

or something else.

If a student gets stuck, it's up to the class to "go Price is Right" on them and give suggestions.

It worked great in one class, forced in another, and somewhere in the middle in the third. Overall, I was happy with the results.

We tried it again today as we implemented a queue.

This time, we prepped a little better and the results were better.

The idea needs some fine tuning, but I think it's a fun and different way to engage the class and I think we'll be playing with twitch coding some more in the coming months.

# Announcing SHIP

It's been a while since my last post.

That's mostly since I've getting things ready for this announcement.

I've talked about our non-profit CSTUY before. Well, we've been hard at work getting things together for our first summer program:

## SHIP - Summer Hackers Immersion Program

We're really excited about this - taking our years of experience teaching kids at our schools and taking it to a wider audience.

SHIP is being hosted at St. Joseph's College in Brooklyn and runs from July 7th through July 31.

So, if you know a rising 9th through 12th grader in or around New York City let them know about this great opportuity.

Information can be found at http://programs.cstuy.org/ship.

And the application is here: http://programs.cstuy.org/ship-apply

Information on our overall plan is here: http://programs.cstuy.org/ship-outreach

We're also still raising funds for the program, so if you or someone you know can help, they can contact me or donate directly here.

# Sorting - Subtle Errors

Time to wrap up sorting for a while. We just finished quicksort having gone through a series of lessons

• We started with Quickselect.
• Then we did a quicksort, copying to new arrays during the partition
• Then finally to an in place quicksort.

For the final quicksort we used a partition algorithm pretty much the same as the one described here.

We started testing using by building a randomly filled array like this:

Random rnd = new Random();
int a[] = new int[n];
for (int i=0;i<n;i++) {
a[i] = rnd.nextInt(100);
}
qsort(a);


And everything seemed terrific.

Just like when we did the mergesort, we started to increase n. First 20, then 100, then 1000 and so on.

All of a sudden, we started getting a stack overflow. We only made it to about 450,000. Mergesort got to arrays of about 40,000,000 items before we started to have memory problems.

Our algorithm was sound. It worked on everything up to about 450,000. Since Mergesort worked well into the tens of millions, quicksort should have as well.

What was wrong?

We changed the code a bit:

Random rnd = new Random();
int a[] = new int[n];
for (int i=0;i<n;i++) {
a[i] = rnd.nextInt(10000);
}
qsort(a);


Instead of an array of 450,000 values between 0 and 100, our elements now went fro 0 to 10,000.

All of a sudden things were good.

Why? It wasn't long before the student saw that 500,000 elements with values between 0 and 100 meant lots of duplicates. Our partition didn't account for that. If we had duplicate pivots, only one is moved into place, the rest are left unsorted taking us closer to worst case performance and blowing our stack.

Fortunately there was an easy fix:

public int partition(int[] a, int l, int r) {
int tmp;
int pivotIndex = l+rnd.nextInt(r-l);
int pivot = a[pivotIndex];
tmp = a[r];
a[r] = a[pivotIndex];
a[pivotIndex]=tmp;

int wall=l;
int pcount=1;
for (int i=l;i<r;i++) {
if (a[i]<pivot) {
tmp = a[i];
a[i]=a[wall];
a[wall]=tmp;
wall++;
}
if (a[i]==pivot)
pcount++;
}
// now copy over all the pivots
int rwall=wall;
tmp = a[rwall];
a[wall]=a[r];
a[r]=tmp;
rwall++;
for (int i=rwall+1;i<=r;i++) {
if (a[i]==pivot) {
tmp = a[rwall];
a[rwall]=a[i];
a[i]=tmp;
rwall++;
}
}
return (wall+rwall)/2;
}


When we partition the array, move all the elements equal to the partition to the middle of the array.

That did the trick.

All of a sudden we were blazing through data sets upwards of 100,000,000 elements.

We're done for sorting for a while, at least until the heapsort but it's been a fun couple of weeks

# From selection to sorting

When I first saw the quicksort it was in an algorithms class back in the day. We first learned the quicksort, then choosing a good pivot element and then as an afterthought we did quickselect.

Fast forward to teaching. I was never really happy teaching quicksort. Mergesort is easy to motivate and it's pretty easy to write. Quicksort always felt a little forced.

I thought I'd try switching things up this time and doing quickselect first.

The motivating problem: find the Kth smallest item in a list - in our case the list is an array of ints.

I want to start with the least efficient algorithm so I stack the deck. I remind them that we've been finding the smallest item in a list for two years now.

They don't disappoint and suggest something like this:

L = [10,3,28,82,14,42,66,74,81]

def findKth(L,k):
omits=[]
for i in range(k):
ans=max(L)
for item in L:
if item < ans and item not in omits:
ans=item
omits.append(ans)
return ans

print findKth(L,3)


Clearly an $$O(n^2)$$ algorithm.

Can we do better?

Certainly.

The students then suggest sorting the data set first. If we use mergesort, we can sort in $$O(nLg (n))$$ time. This lead to a great conversation about sorting being so fast it's practically free and that you don't have to hard code everything from scratch. Not only is sorting the data set then plucking the kth item out much faster, if you already have a sort written or if you use your language's library's sort, it's much easier as well:

def findKth(L,k):
tmp = sorted(L)
return tmp[k]


But we can do even better. So now we talk about quickselect

We pick a random pivot, partition the list a la quicksort (reorder the list such that all items less than the pivot are to its left, and all items greater than the pivot are to its right).

We now know that after partitioning. the pivot is in it's exact location. If its index is k then we're done. If not, we can recursively quickselect on either the left or right side.

Pretty cool, but is it faster?

It's easy to see that if we keep choosing a bad pivot (the smallest or largest in the list), each iteration takes $$n$$ time to partition and each iteration takes one item out of contention. This takes us back to $$O(n^2)$$.

However…

If we choose a good partition – at the middle of the list, each partition takes less and less time. We get a run time of:

$$n+\frac{n}{2} +\frac{n}{4}+\frac{n}{8}+\dots$$ and since $$\frac{n}{2} +\frac{n}{4}+\frac{n}{8}\dots=n$$ this becomes an $$O(2n)$$, or $$O(n)$$ algorithm.

That's really cool.

Homework was the actual implementation.

I think this might be a better way to approach quicksort. It seems less forced, plus the class gets to go through the exercise of taking an algorithm form $$O(n^2)$$ to $$O(nlg(n))$$ to $$O(n)$$.

Next, moving to the quicksort and also showing that we can indeed avoid those really bad pivots.

We moved to quicksort today and overall I'm happy with this approach. The only thing I think needs tweaking is going from the idea of partitioning to Java code. Java makes it somewhat of a bear.

# The new SAT - the more things stay the same

Plus ça change, plus c'est la même chose

The more things change, the more they stay the same.

Last week we heard all about the new SAT. Going back to 1600 points, writing optional, and reworking the verbal section.

Immediate responses ranged from the usual fact that SAT doesn't correlate with college success to the idea that the motive was not to improve the test but rather to recapture market share from the ACT.

Personally, I'm not a fan of the test but I do see the desire to have some consistent measure across students and schools. While an "A" might say something about perseverance and hard work, the value of one school's "A" is not necessarily the same as the value from another.

But that's not what I wanted to write about.

A big criticism of the SAT is the fact that it can be prepped for and thus gives a huge advantage to students and families of means. The test can be gamed, one can take prep courses, hire private tutors, etc.

As I said at the top…

Hot on the heels of the new SAT came the announcement that Khan Academy will be offering free prep for the new SAT. That sounds terrific.

I read it differently. I'm all for free educational materials being universally available, but if Khan Academy can indeed offer test prep for the new SAT then so can everyone else and people of means can and will avail themselves of the Khan Academy material plus a wealth of other resources.

So, new SAT but nothings changed.

# Be the ball

Crystal Furman wrote a nice post titled Coding Comprehension about a week ago. There was a little buzz about it in the APCS Facebook group and shortly after, Alfred Thompson added his two cents.

I thought I'd add mine, at least a couple of thoughts.

There are a lot of issues - long term retention, transfer of knowledge from the basics to more advanced tools, pattern recognition, and more.

It reminded me of Benjamin Zander's talk "Playing on one Buttock":

Check out the first five minutes.

Code reading is important, pair programming, where students are constantly explaining to each other helps, and there are other techniques.

We can also model thinking like a computer from day one.

Many of us start day one with exercises where students are the computer. Perhaps using a simplified made up language or maybe by just throwing some task at the kids and having them write instruction lists for each other. That's a great start, but we can continue drawing the relationship between the way we think and the way a computer works.

Take a simple intro problem – finding the largest value in a list of numbers.

The ultimate solution in Java might be:

public int findMax(int[] L){
maxIndex = 0;
for (int i=0;i<L.length;i++){
if (a[i]<a[maxIndex]){
maxIndex = i;
}
}
return maxIndex;
}


Somewhere along the development process, I ask my students how they would find the largest value in list. If the list was short, they might just scan it. If the list was very long, they do the same thing as our Java snippet does - remember the largest so far as we scan down the list one by one. At first, we just think we're scanning the list, but if we slow things down, we see that we're following pretty much the same algorithm as what we'd write in code.

I use this technique throughout all my classes - slow ourselves down and really analyze the steps towards solving the problem. No single technique is going to teach our kids how to think about and comprehend code, but it's another tool in our bag of tricks.

#### Side note

This is my first post written using Emacs Org mode. I've been using it for years but only now discovering how amazing a tool it is.

# I guess I'm a dumbass

I like a fairly informal atmosphere in my classes. Students have to know that there's a line between teacher and student but I also want them to feel like we're all part of the Stuy CS family.

Whenever we start a new term, it takes a while to break down the walls. The students don't know what to expect of me, can they trust me? Am I a bozo? Who knows.

It helps when some of the class had me as a teacher before, but it still takes time.

I'm glad that this term, things are coming along nicely.

Let me share what happened in class today.

I was introducing merge sort - their first nlgn sorting algorithm. Before class, one of the students slipped off his seat and landed on the floor with a thud. He was fine although the brief butt, if you would, of jokes.

I relayed a story - many years ago, Ilya, one of the gang, was accused of being a dumbass. He responded "hey, it's never missed the seat." The class had a good laugh over it.

Fast forward a bit.

I had a deck of cards I wanted sorted. As a Stuy grad, I'm as lazy as the next guy so I didn't want to sort them, but I also didn't want to violate one of our two class tenets "Don't be a jerk" so rather than giving the cards to a student to sort, I split the deck in half and gave each half to a student.

They quickly caught on and subdivided the deck and gave away their halves. We did this until all the students had, at some point had one or more cards.

Then we got to the merge part. Each student sorted his or her pile and passed it back to the student who they got the cards from. This student then merged the two piles and passed the cards back.

As the cards made their way back to me a student noted "hey, one of my piles isn't in order." I commented that "the algorithm might fail if at some points you give your cards to a dumbass." This got a good laugh.

Finally, two pile of cards made their way to me and I started to merge then. At which point, I promptly dropped the cards all over the floor.

One of my students exclaimed: "That's what happens when you give you cards to a dumbass!!!!!"

It was awesome. We all cracked up.

I don't think I've been "insulted" quite so perfectly since my daughter called me an idiot in class last year (I fed her the straight line and she didn't disappoint).

I love it that my kids feel comfortable enough to joke but also know where the line is.