Algorithms

Teaching Sorting

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.
# COMMENTS

A* is born

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.
# COMMENTS

Sorting - Subtle Errors

div.center {text-align:center;} 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 i0;i&lt;<span style="color: #7CB8BB;">n</span>;i++) { a[i] rnd.
# COMMENTS

From selection to sorting

div.center {text-align:center;} 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.
# COMMENTS

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.
# COMMENTS

Fibonacci by the tail

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.
# COMMENTS

Sorting from the top and from the bottom

Sorting from the top and from the bottom I've been meaning to write this post for a couple of weeks, but some times life just gets in the way. I've always thought it important to arm students with as many different tools with which to attack problems as possible. As such, the courses I teach use a number of different languages, each highlighting a different paradigm and thought process. The hope is that by the end of the sequence, they can look at problems from many different angles.
# COMMENTS