Want to know more about CS 231?
Build the data structures behind everyday software, then use them to solve Sudoku, search mazes, and find shortest paths.
CS 231 is where programs get serious about organizing data. Working in Java, you build the classic data structures yourself, including linked lists, stacks, queues, trees, hash maps and graphs, and then put each one to work in a project. Along the way you learn to analyze your code’s performance: you run experiments and use big-O notation to compare the performance of different approaches.
A project you'll build: a Sudoku solver
Watch someone solve a Sudoku and you'll see a rhythm: write a number in a square, check it, and when nothing fits, erase the most recent choice and try again. In Project 4 you teach a program to do the same thing. The key is a stack, the data structure that always remembers the last thing you did.
What you build
- A stack made from your own linked list, by having it sign a Java interface.
- A 9×9 board that reads puzzles from files and checks every row, column and 3×3 block.
- A solver that fills in squares, backs up when it gets stuck, and lets you watch it work.
What you discover
- Why the solver needs a stack and not a queue: only the most recent choice is safe to undo.
- How a smarter strategy, filling the square with the fewest options first, cuts the work dramatically.
- How many starting numbers a random puzzle needs before it becomes solvable.
Here’s the idea in miniature. One 3×3 box is missing the numbers 1, 2 and 5, in the empty squares A, B and C. The bottom row continues outside the box, and it already has a 5:
A gets 1, the smallest number not already used.
B gets 2. That leaves only 5 for C.
C can’t be 5, because its row already has a 5. Nothing fits. B took the 2 that C needs, so pop B and give it its next value, 5.
C gets 2. Solved!
The whole semester, project by project
- Library of Functions: Java methods applied to a library of reusable functions.
- Working with Classes: classes and objects applied to your first object-oriented Java program.
- Monte Carlo Simulation: randomness and repeated trials applied to estimating answers that are hard to calculate directly.
- Conway’s Game of Life: 2D arrays applied to a grid of cells that live and die by simple rules.
- Social Agents: linked lists applied to a simulation of agents that move and interact.
- Sudoku: stacks applied to the puzzle solver described above.
- Maze Search: BFS, DFS and A* applied to finding paths through a maze.
- Word Frequency Analysis: binary search trees and hash maps applied to counting the words in large texts.
- Shortest Paths: graphs applied to Dijkstra’s algorithm.
Learning should be fun: the 2D Array Arcade
Before the Game of Life and Sudoku, practice thinking in grids. Nine quick levels take you from finding grid[r][c] to tracing nested loops, spotting out-of-bounds errors and counting Game of Life neighbors. It works on a phone, too.
What past students have said
This course really made me think critically and push my CS knowledge. I really enjoyed this class and I think I learned a ton.
Coding the data structures ourselves helped me understand how they function and what they can be used for. The group activities and quizzes challenged my understanding.
— From anonymous student course evaluations
Questions about computer science at Colby? Email me at aharper@colby.edu or stop by my office, Davis Science Center 311.