# Tag: algorithms

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.

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

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

# COMMENTS
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
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
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 i=0;i<n;i++) { a[i] = rnd.

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