CMPS146 Fall 2013 Midterm Study Guide

The reading associated for each topic will be present in the midterm. Questions will also be taken from material presented on slides in class.

Generally, you will want to know how each algorithm works, how to create examples in each technique, a broad sense of complexities (both runtime and memory), and important snippets of pseudocode.

Part of the midterm will have the same tone as the midterm for last year’s class. For the curious, here is last year’s practice midterm and practice midterm with answers.

Below are general descriptions of what you should know about each topic.

Decision Trees

Reading:  293-309        

Convert conditional statements in english into decision trees given defined actions and conditions.

Convert decision trees into pseudocode.

Benefits and drawbacks to decision trees.

State Machines

Reading: 309-333

Be familiar with states, transitions, actions and the update function.

General knowledge of how decision trees can be used to augment state machines.

Finite State Machines

All sources of acts that are possible when a transition is triggered.

Hierarchical Finite State Machines

Actions lists from transitions that cross FSMs and hierarchies.

Behavior Trees

Reading: 334-371

The class hierarchy of the classes used in behavior trees.

Issues around concurrency and timing.

Why stored data is used in behavior trees.

Techniques for storing data in behavior trees.

Tasks

Steering Behaviors

Reading: http://www.red3d.com/cwr/papers/1999/gdc99steer.html

What steering behaviors are.

The core data structure of autonomous agents in steering behavior systems.

The common types of steering behavior.

The three behaviors of flocking.

Basics of self-organization.

Stigmergy and collective construction.

Following flow fields.

Markov Models

Reading: 395-401

Multiplying matrix by a vector.

The impacts of running a Markov process (like having an impact on the total safety across a set of cover locations).

Path Planning

Reading: 197-255

Constraints on graphs for performing path planning.

Uniform Cost Search, Dijkstra, and Best-First Search.

A* algorithm’s core: cost = g(n) + h(n)

Be able to compute closed lists and open lists for Dijkstra and A* given a weighted graph.

Why heuristics are used.

Categories of heuristics and their characteristics.

Common types of heuristics.

Fill patterns of heuristics.

How heuristics can be used improperly.