When my students move up to junior year, they make a series of transitions: from programming to theoretical computer science, and from imperative to functional programming. We use DrRacket, and one of the goals of the course is to give them a very broad exposure to theoretical computer science. Part of that is choosing labs that can be coded using the tools that they have learned so far.
They are already familiar with linked lists, Big $O$, $\Omega$, and $\Theta$, binary trees, the runtime stack, BFS and DFS before they arrive at this class. They have also been exposed to recursion a fair amount (though most of them are not highly skilled at it yet)
My first lesson with them in Racket is called "Cons, Car, Cdadr, and Contracts" and it contains exactly the sorts of material you would expect from that title. I have created a lab that makes them use these tools, but adds up to no further significance. What I want is an algorithm that has some theoretical significance and that they can do with those tools. The algorithm itself can come from any part of computer science - I just want it to be something worth exposing them to in the first place.
The lab goals would thus be two-fold: first, to give them a chance to play around with and familiarize themselves with the beginnings of Racket. Second, I want to give them a chance to learn about an important algorithm.
