# Setup

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…

- see how combinatorial game theory and programming intersect
- see how a computational model can be useful to study trade-offs
- get more comfortable with graphs (DAGS, in particular)

# Pebbling Game

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

- A pebble may be removed from a vertex at any time.
- A pebble may be placed on a vertex with in-degree 0 at any time.
- If all predecessors of an unpebbled vertex \(v\) are pebbled, a pebble may be placed on \(v\).

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 `PebblingNode`

s in any valid topological sorted order.

** Task 0.**
Implement `toposort`

to solve the pebbling game. Note that the `indegree`

field is pre-populated for you.

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`

** Task 1.**
Check to make sure you are passing all the tests 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. Sometimes, we will ask you to think about questions that you’ll review with the person who checks you off. For this lab, please answer the following questions:

** Task 2.**
Click the “Submit OpenEndeds” button below.
Then, call over a member of course staff by typing “`!question done`

” into your `workspace`

text channel. Someone will get to you as soon as possible.