Tag: data structures
Continuing with the theme of alternate representations we just started heaps. Specifically binary heaps. binary min and max heaps.
Heaps are one of my favorite topics in CS2. If you're not familiar with them, a binary min heap is a complete binary tree that enforces the heap property. By being complete we mean that every level except possibly the last one is full - that is 2 children. The last level is as filled left to right.
There was a comment on my last post about arbitary trees on Reddit talking about how this type of data structure was a hold over from the old days when computer resources were more limited. Nowadays having a list of children makes more sense. The comment was of course correct but I still think it's worth teaching representations like the one I spoke of in my last post. Looking at interesting and different ways of representing data and modeling solutions is one of the things that separates programmers or coders from computer scientists and software engineers.
It's been 10 days from my last post. Not really a big break for me historically but certainly a big one given how much I've been posting this year. Been under the weather for the past couple of weeks dealing with COVID-19. Haven't had super bad symptoms and as symptoms have been getting fewer and less severe I'm hoping I'm close to a full recovery.
In any event, I'm feeling good enough for a quick post.
At this point, we've done a fair amount of playing with text so it's time for a fun little project. We're going to generate some text "in the style" of a source text. The technique we're going to use is usually called a Markov Chain text generator. Basically a model where the next state or word is based entirely on the current state. I don't dwell on the math under the hood but in case you're interested, here are a few links: Wikipedia, Explained Visually, UC Davis Math.
Following up on a previous post, we're going to continue to talk about playing with text. This time, building and working with a bag of words from a text. A bag of words is a simple language processing model where you just consider individual words in a text. What they are and how many times they occur. This is a pretty simple model but you can still have a good bit of fun with your students with it.
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.