Assignment 4: Theoretical Potpourri #
Due date: 10/02/2024
Task: Answer the following questions.
- For the following game, write two algorithms in pseudocode that take a game state as input and output a number, effectively partitioning the space of states. Make sure that one of the algorithms induces a meta-graph that is a DAG, and the other a linked list. […]
- For the following game, write the tightest possible upper bound on its number of states, and estimate an average number of possible moves for any state. Provide a justification. […]
- In the worst case, can a weak solution take as much space as a strong solution to a game? Explain why.
- Provide an example of a game in reduced graph form with regular states, 2 pure-draw levels, and at least one non-pure draw cluster.
- […]
Provided:
- Perhaps a \( \LaTeX \) template for the deranged.
Metrics: Nothing, really. Just good effort.
Learning objectives: Reinforce and confirm the theoretical knowledge covered during the first third of the semester (see course roadmap).