We have the kids write programs in all sorts of ways
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:
Or the somewhat lame
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.
Read more - commentsIt'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:
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.
Time to wrap up sorting for a while. We just finished quicksort having gone through a series of lessons
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
Read more - commentsWhen 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 K^{th} 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 k^{th} 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.
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.
Read more - commentsCrystal 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.
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.
Read more - commentsI 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.
Read more - commentsPatient: “Doctor, it hurts when I do this.”
Doctor: “So, don’t do that.”
We’ve been spending time on State Space Search. It’s a great topic. We deal with or at least introduce:
and more. Today, however. I want to talk about something else.
We started by developing a maze solver. It reads a text file representing the maze and then proceeds to find an exit. One version of the source code can be found here.
It’s really cool to see how such a short program, about 10 lines of work code, can solve such an open sounding problem. From there we talk about state spaces, graphs, etc. We then moved on to the Knight’s tour. By viewing it as a state space problem we can look at it just like the maze.
We represented a state as a board with the knight’s current position and where it’s been. An easy way to do this is to use an array of ints. So we have an empty 5x5 board:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Or a board after a few moves:
1 0 0 0 0
4 0 2 0 0
0 0 5 0 0
0 3 0 0 6
0 0 0 0 0
The kids saw three base cases:
I wanted to look at that third one. We talked for a bit about using an if or a try/catch but I pointed out that I didn’t like either. Looking at our maze code, we never checked bounds there. Why not. Well it turns out that our maze had wall all around. It was stored in a 2D array but the entire outer edge was wall. Why not do the same for the chess board:
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
Now, as long as we start on the board, if the Knight jumps off the edge, it will end on a -1 square and backtrack. By modifying our data structure and data to contain a border, we’ve eliminated the special case of index out of bounds.
I always like doing that.
We’re ramping up for recursion in my junior classes - state space search, nlg(n) sorts, etc. As a refresher, we took a quick look at the Fibonacci numbers.
Now, some people seem to think that it’s a tired problem. It’s mathy, it’s played out, it’s boring etc.. They just might be missing the point.
The beauty isn’t in the problem itself, but rather, that it’s a platform on which you can look at many problem solving techniques.
We can look at the basic, straightforward , imperative solution:
public int fib1(int n) { int a=1,b=1; for (int i=0;i<n;i++){ int c=a+b; a=b; b=c; } return a; }
It’s straightforward and fast - no recursion needed.
Next, we can look at the basic recursive version:
public int fib2(int n) { if (n<=1) return 1; else return fib2(n-1)+fib2(n-2); }
The advantages (of recursive solutions in general):
The downside:
So, how do we address this?
One way is via memoization - when we find a value, store it in a table, then we can use the look up table instead of recalculating over and over:
java public int[] fibnums = new int[100000]; public int fib3(int n) { if (n<=1) return 1; else if (fibnums[n] != 0) return fibnums[n]; else { fibnums[n] fib3(n-1)+fib3(n-2); return fibnums[n]; } }
This is a terrific thing to show a class since it’s easy for students to wrap their heads around, it really speeds things up, and it’s a precursor to lots of neat algorithms.
Finally, we can look at re-writing Fibonacci using tail recursion. This one can be a little hard for students to grasp. I like building it up from the iterative solution. In that solution, we use a, and b to “walk down” the list of Fibonacci numbers. At any point in time, a and b represent where we are in the sequence. We also use c but that’s really just a temporary place to add a and b together.
The problem with doing this in a recursive solution is that we can’t have a and b as local variables as each recursive call will have new a and bs and no information will be transferred.
Since we’re working in Java, it doesn’t take long for some students to come up with the idea of using instance variables to store a and b and just use the recursion for the “loop.”:
public int a=1, b=1 public int fib4(int n) { if (n==1) return a; else { int c=a+b; a=b; b=c; return fib4(n-1) } }
Great, but using instance variables in this way is very inelegant and messy. Better, use extra parameters to store the values from call to call:
public int fib5(int n,int a, int b) { if (n==1) return a; else return fib4(n-1,b,a+b) }
Looking at Fib5(5) we get for n, a, and b:
At which point we just return the 8
Clean, elegant, fast, and easy to understand.
Each of these four techniques are important and will be used time and time again and here we have one simple problem that allows us to explore them all.
Project Euler: Problem #2 - Even Fibonacci numbers
Memoized Fibonacci Numbers with Java 8
The quadratic formula and Fibonacci numbers
TED: Arthur Benjamin: The magic of Fibonacci numbers - Arthur Benjamin (2013)
Fibonacci Numbers in the Real World
Read more - comments<img height=250px src=”/img/tapia/alums.jpg”></img>
I think my one regret over the years is that I haven’t done much travel. So, when I had the opportunity to go to the 2014 Tapia conference, I jumped at the chance. I didn’t get to see too much of Seattle, but that’s OK. Now I’ve more incentive to go back.
In addition to seeing new sites, it also gave me an opportunity to see friends that I don’t get to see too often.
I frequently talk about the StuyCS family. That it’s all about people and all about community. I’m proud that I started this family and I’m always blown away by the guys. It’s one thing for alums to swing by the school a couple of years after they graduate but it’s another when they want to see me as much as I them even after ten or twenty years.
It was a little tricky to coordinate between conference commitments and their schedules but we ended up having two dinners.
First I got together with Mike (StuyCS ‘97), his wife Linsday, and Helene. I’ll always remember Mike for being the police officer when he, William, Emil (I think) and Paul were the Village People for Halloween. It was amazing to see him, meet his wife talk about old times and see what he’s doing today.
Helene isn’t StuyCS, but she is an educator of a kindred spirit, over the years, I’ve met many CS educators. Some “get it” many don’t. Helene clearly does. We clicked right off the bat. As with my alums outside of the city, I regret that we only get to see each other once every few years.
Two nights later, I got together with Sam (StuyCS ‘96), Daemon (StuyCS ‘06) and Matt (StuyCS ‘07) along with Boback, Alan, and Ephraim, three other high school teachers who attended the conference.
I hope we didn’t bore the teachers with our high school stories, but I really had a blast. We talked about old times, we talked of current issues, good food and good friends. We spanned 27 years of Stuy but that didn’t matter. Get a bunch of bright interesting like minded people together and good things happen.
I feel amazingly blessed that I can travel across the country and students from 10 and 20 years ago want to get together to catch up. I guess I should really say friends, not students.
I’ve been thinking a lot about my career as I close in on 25 years of teaching. What impact I’ve had, what I could have done better, what I did right.
I think I can live with the StuyCS family as my legacy.
Read more - comments