• View
• Edit
• History
• Print

Knowledge

Data Structures:

• Priority Queue
• Heap

Search Control

Big-Oh Notation

• http://en.wikipedia.org/wiki/Big_O_notation

O(n)

• “big-oh” - worst case performance for the algorithm - something is O(f(x)) if in the long run (for large xs) it never exceeds f(x)

Omega(n)

• “omega” - minimum performance for the algorithm - something is Omega(f(x)) if in the long run it never goes below f(x)

Theta(n)

• Something is theta(n) if its worst-case and minimum-case performance is bounded by the same function times a constant and plus/minus a constant.
• Theta is an “asymptotically tight bound”, or a “squeeze”

Other search terminology

• Open List - the list of unexplored nodes (e.g. the FIFO queue in BFS, or the priority queue in A*)
• Closed List - the list of explored nodes no longer being considered by the search algorithm
• Fringe - Open list?