Advanced computer science students studied data structures this block, tackling a broad range of coding projects.

 

While the rest of the school was learning Number Theory in Block 5, four intrepid high school students chose to take an advanced computer science course instead. Data Structures is typically a second-year college course, in which students learn many of the classic ways to efficiently organize data in a computer.  

I have taught this subject many times before at the high school level, as there used to be an AP course that covered this material, "AP Computer Science AB".  Unfortunately, this AP test was discontinued in 2009 due to the low number of students taking the test at that time. (Would that still be the case now? Who knows!) However, I am used to having almost an entire year to cover the material, as opposed to just six weeks. So I admit to having a bit of trepidation before the class began, about whether I could do the material justice in this short amount of time.

However, my fears soon proved to be unfounded, as my students were all knowledgeable, enthusiastic, and hard-working. Many of them already had at least a passing familiarity with many of the topics in the course syllabus but patiently listened to my lectures before embarking on their coding project for the day. And my students certainly wrote a LOT of code in class! They were more than happy to work for almost the entire two hour class period, often forgoing breaks, and reluctantly packing up to leave at the end of the school day.  

As a result, we managed to meet or exceed even my most optimistic projections of the topics we would be able to cover in the course. A list of the course topics is below, along with some of the coding projects for each unit:

  • Stacks: Evaluation of arithmetic expressions written in postfix or infix notation
  • Queues: The Josephus problem, radix sort
  • Linked Lists: Implementing stacks and queues, modeling a game of "Duck Duck Goose"
  • Binary Trees: Recursive tree methods, writing a tree-based guessing game
  • Priority Queues: Implementing a priority queue using a heap
  • Hash Tables: Simulating a "bar scanner", which reads UPC codes and looks up prices
  • 2D arrays: Writing a program to play the game "Boggle"
  • Sets and maps: Finding the English word with the most anagrams that are also words
  • Graphs: Eulerian and Hamiltonian circuits and paths, Prim's algorithm, Dijkstra's algorithm

Now that I am seeing this list all in one place for the first time, that's a lot of programming work to complete in six weeks! I enjoyed teaching this class a great deal, and hope to get the chance to do it again in the future.  

--Steve Gregg