Week 13 - Introducing the Priority Queue

Uninformed Search

• Watch - Considering one more uninformed Search [Video, 22 minutes]
  • Slides used in that video

PriorityQueue

• Watch - How is this new?  What is a Priority Queue? [Video, 8 minutes]
• YOU do it.
  • Use this version of a Queue as your starting point
  • Create a Priority Queue class that will be almost identical to the Queue class, BUT will maintain the queue in order from largest at the left end (the 0 position) and the smallest at the right end (the largest valid index depending on the list size).
  • There are two ways to do this:
    1. Using an insertion technique similar to the linear search that goes down the list in order to figure out where the item belongs. This will, like linear search, have a Big-Oh that is linear.
    2. Using an insertion technique similar to the binary search that maintains a left/right or top/bottom set of pointers and keeps cutting the data in half to find where in the list the new item belongs. This will, like binary search, have a Big-Oh that is logarithmic.

• Considering two implementations of the Priority Queue
  • Watch - Code implementation for linear search version[Video - 7 minutes]
    • Code for the Priority Queue based on linear search/insertion.
  • Watch - Code implementation for binary search version [Video - 14 minutes]
  • Code for the Priority Queue based on the binary search/insertion
  • Watch - Verifying Big-oh with timing code [Video - 7 minutes]
    • Timing Code that I used in that video

• Using Inheritance to creat a Priority Queue
  • Watch - How Inheritance would make this "better" [Video - 11 minutes]
    • Code - Parent Class, queue_code.py
    • Code - Using Inheritance, PriorityQueue_linear.py
    • Code - Using Inheritance, PriorityQueue_log.py
    • Code - Timer Code, PriorityTimer.py

   

  
  

• Using the Priority Queue with our Romania search problem
• Watch - What we need to do to modify the BFS for Romania to understand distances [Video - 5 minutes]
  • The previous code we have used
    • romania_BFS.py
    • cityNode.py
    • PriorityQueue.py
    • queue_code.py
• Watch - Explaining the modified CityNode and putting it all together [Video - 10 minutes]
  • The Modified cityNode.py code used in that video
  • The final romania_uninformed.py file

The last 2 searches

So far I have explained the Breadth-First Search, the Uniform Cost search (a variation of BFS) and the Depth-First Search. I have alluded to two other versions of the uninformed search several times - the Depth Limited and Iterative Deepening Searches.

I don't think it is required for you to understand these two searches as part of this course. But some of you might be curious. And the it doesn't take that long to explain them. So the following videos explain how they work.

• Watch - Depth Limited Search and Iterative Deepening Search [Video, 18 minutes]
• Watch - Why IDS isn't actually faster than BFS [Video, 7 minutes]