CS 2 (Winter 2023) Lab 06: Pebbling Game

This lab focuses on using a topological sort to solve a graph problem.


Register for the lab using grinch: https://grinch.caltech.edu/register and clone the repository as explained in the setup instructions.

Goals and Outcomes

By the end of this lab, you will…

Pebbling Game

Given a DAG \(G\), we define a valid move in the pebbling game as either removing or adding a pebble according to the following rules:

The “easiest” solution to this problem is to just add pebbles and never remove them. But what order should they be added in? This is exactly the topological sort problem from lecture.

public List<Integer> toposort()

Returns a List of ids of PebblingNodes in any valid topological sorted order.

We care about pebbling because it’s a model of a trade-off between space (each pebble represents a memory location) and time (the number of moves represents the time an algorithm takes).

Checking the Results on gitlab

Getting Checked Off

At the end of every lab, you will need to call over a member of course staff to review your work. For you to receive credit for the lab, a staff member must check you off!