Welcome to the ITSD4312 Web

~ You are in a maze of twisty little passages, all alike ~

Contents

• Syllabus
• Schedule
• Assignments

Lecture Material

• Breadth vs. Depth 
• Red-Black Trees, AVL Trees, & balancing
• B-Trees
• Min-Max (Game) Trees & Static State Evaluation
• Alpha-beta Pruning
• Graphs
• Minimum Spanning Trees
• Single-source Shortest Path
• All-pairs Shortest Path
• A* Path Planning
• Simulations
• NP-Complete
• Approximation Algorithms

In-class Examples

• B-Trees (lecture 3)
• Min-max & alpha-beta (lecture 5)

Relevant/Informative Links

• PATHDEMO - a program from Game Programming Gems (Charles River Media) that explores various path finding algorithms
• Paper from Gamasutra - Pawn Captures Wyvren: How Computer Chess can Improve Your Pathfinding (an excellent article on game tree searches, min-max, iterative deepening, and A*)
• Lecture notes from David Eppstein - Negamax variation of MinMax depth-first game tree search
• Lecture notes from David Eppstein - Alpha-Beta Pruning
• Life simulation/game (console application) - and C++ implementation
• NP Complete and Minesweeper
• P=NP? problem definition (PDF file)
• Sample .NET solution to the N-Queens problem.

Legacy

• Spring 2007
  • Syllabus
  • Schedule
  • Assignments
• Spring 2005
  • Syllabus
  • Schedule
  • Assignments
• Spring 2003
  • Syllabus
  • Schedule
  • Assignments