Week 12 - Beyond BFS and DFS, and Introducing the Priority Queue

Lesson Materials

• Walkthrough of the BFS solution
  • Twiddle Solution - Using a list for exploredSet (12 minutes)
  • My code

• Do you want to test if you get it? [If you are looking to see if you understand this, and you want to challenge yourself, here is another assignment you could create as BFS search. Please note, this is ENTIRELY optional and "for fun"]
  • Light's Out explanation video
  • The websites I showed in the video
    • https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/flip.html
    • http://www.logicgamesonline.com/lightsout/
  • Light's Out - My Solution [Don't look at this until you really truly have tried to solve it]

• Beyond BFS and DFS
  • Reviewing BFS and DFS searches. (19 minutes)  Why these two search types aren't always sufficient
    • The slides from the video (which were the slides from week 9)
  • "Priority" based searching (14 minutes)
    • Often referred to as "Uniform-Cost Search" but that is truly a poor name
    • Uses additional material from the slides linked previously

• PriorityQueue
  • How is this new?  What is a Priority Queue? (10 minutes)
  • How would we code it? (18 minutes)
    • Do you sort at enqueue or dequeue?
    • Linear time insertion
    • Logarithmic time insertion
  • YOU do it.
    • Use this version of a Queue as your starting point

• Considering two implementations of the Priority Queue
  • Video: Code implementation (17 minutes)
  • Video: Timing issues (14 minutes)
  • Code for the two priority queues.
• Adapting the Node class to work in a Priority Queue
  • Twiddle solution (the same as earlier on this page)
  • Video: Revisiting twiddle and considering the Node class (16 minutes)
    • Also introduces your short programming assignment for this week
  • Code for the revised Node class