Princeton Algorithms: Part 1, Week 4

Resources

• Lecture Slides & Presentation

  • 2.4 — Priority Queues
  • 2.4 — Heap Video
  • 2.4 — Heapsort Video
  • 3.1 — Elementary Symbol Tables
  • 3.2 — Binary Search Trees
  • 3.2 — BST Video
  • Mathematical Proof for Solvability Algorithm

• Book Notes

  • 2.2 — Mergesort

• Assignment

  • Problem Description
  • Assignment Checklist
  • Files

Programming Assignment

There are a few micro optimizations available to bring the score up from 98 to 100 but I decided not to pursue them at this time.

Board

Implemented Manhattan and Hamming priority functions to support the A* algorithmic implementation of the solver class. In addition, I created a twin to determine the solvability of a board and a neighbors function to assist, again, with the A* implementation.

Solver

Solver utilizes a Minimum Priority Queue coupled with a SearchNode internal class with a priority (utilized in compareTo) function based on the path cost (moves thus far) and a heuristic (Manhattan with hamming as the tie breaker) to implement the A* algorithm. Solvability was determined by making a twin of the game board and concurrently solving both boards.

Results