So, last post I talked about the technical interview and unquestionably students at elite private schools have yet another leg up on the other folk. Today, let's look at the core subject of those interviews and what I think should be emphasized in class. I want to be clear - I'm only talking about in class here. There are many things that can be done at public institutions like Hunter to help better prepare students for tech careers.

Natan commenting on work the other day: "You have two lists. One is sorted, the other is not. Every item in one list corresponds to an item in the other. Is it faster to sort the unsorted list and then merge them, or simply go through the unsorted list in order and pair each item with the item you can find in the presorted list?" is a question I asked today in the dressing room of an off-Broadway theater.

Someone mentioned Grokking Algorithms by Aditya Y. Bhargava in one of the CS educator Facbeook groups. It looked interesting so I thought I'd give it a once over. It's certainly an accessible book. Text mixed with cute line drawings, "hand written" text, diagrams and picture.s It reminded me of one of my favorite, most accessible Calculus books Who Was Fourier. Overall I enjoyed the book but I'm not sure what its best audience is.

It's spring break and for me that's always been a good time to explore some new ideas. Here's one that some of you might like, particularly if you're teaching APCS-A or something similar. Many APCS-A teachers do a unit on image processing using the picture lab (alternate resource). Image processing is a nice platform to explore two dimensional arrays. You basically use a 2D array of pixels (points) to represent an image.

Earlier today I saw a facebook post asking for thoughts on teaching sorting. The question was specifically not about motivations like having the class act out sorts or sort cards but rather about the coding. I've been meaning to write about this since last summer when I attended Owen Astrachan's talk on the same subject. Early in my career when teaching sorting I developed the n^2 sorts as standalone routines just as they're presented in most books but as I gained more experience as a teacher, I changed it up to build the sorts (at least some of them) from existing concepts.

Over on the CS Educator StachExchange, which is in private beta for a few more days, I saw a post asking about how to introduce the A* search algorithm. I taught A* as part of the APCS class at Stuy so I thought I'd talk about what I did here. Some time around mid year, we get to intermediate recursion. This is about the time, give or take, when we talk about the nlogn sorts.

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.

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.

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.

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.