Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
21 Cards in this Set
- Front
- Back
|
Difference between Searching and Sorting |
Sorting: Given a list of items Re-arrange them in some non-decreasing order Searching: Given a list of items and a target value Find if/where it is in the list Return special value if not there (“sentinel” value) |
|
|
Why Search? |
- One of the fundamentaloperations in computing - Often, the difference between a fast program and aslow one is the efficiency of search algorithm - Because of the huge amounts of data available success or failure is determined by ability to search - Abilityto search efficiently is the way to compete in thisage |
|
|
Types of Searching Algorithms |
- Brute-force Search and Heuristics - Sequential (“Linear”) Search - Binary Search |
|
|
Brute-Force Search |
A very general problem-solving techniquethat consists of systematically enumerating allpossible candidates for the solution and checkingwhether each candidate satisfies the problem'sstatement - Also known as exhaustive search or generate and test |
|
|
Procedure for Brute-Force Search |
- first (P): generate a first candidate solution for P - next (P, c): generate the next candidate for P afterthe current one c - valid (P, c): check whether candidate c is a solutionfor P - output (P, c): use the solution c of P as appropriateto the application |
|
|
When to use Brute-Force |
- Problem size is limited, or when there areproblem-specific heuristics that can be used toreduce the set of candidate solutions to amanageable size. - Also used when the simplicity ofimplementation is more important than speed |
|
|
Heuristic |
- Used to speed up Brute-Force Search - Strategies using readily accessible (though, oftentimes loosely applicable) information to controlproblem solving |
|
|
Sequential ("Linear") Search |
- Compares a keyelement (or “target”) sequentially with each elementin the array - It does not stop theprocess until the key matches an element in anarray, or the array ends without a match - When the key matches an element, the linear searchreturns the index of the element that matches thekey |
|
|
Order Class of Linear Search |
- O(n) - As the size of the data grows, the longer it will taketo traverse the elements (directly proportional) - Best used if the data is relatively small, else verytime consuming |
|
|
Advantages to Linear Search |
- Simple to code and understand - No assumptions made about the list |
|
|
Binary Search |
- DATA MUST BE SORTED - The Binary search algorithm is very efficient because the data is sorted |
|
|
Procedure for Binary Search |
Eliminate about half the items left with onecomparison. Data array is successively divided intotwo parts, thus the name binary |
|
|
Complexity of Binary Search |
- O(log n) - More efficient than Linear Search - Good example of divide and conquer |
|
|
Compare Linear and Binary |
- Complexity: Lin = O(n), Bin = O(log n) - For a worst-case scenario, binary search wouldwork through half of the array, which is the averagefor a linear search - Binary usually more efficient than linear |
|
|
Procedure for Best-first Search |
- Use an evaluation function for each node - Expand most desirable unexpanded node - Implemented by keeping a queue sorted indecreasing order of desirability (sometimes calleda fringe) - Special cases include: Greedy Search and A* Search |
|
|
Procedure for Greedy Search |
- Greedy search expands the node that appears to be closest to goal. - Greedy search uses f(n) = h(n) - It operates by making the locally optimal choice at each stage with the hope of finding a global optimum - |
|
|
Complexity of Greedy Search |
- O(b^m) in terms of nodes and branches,but a good heuristic can give dramatic improvement - It certainly doesn’t produce an optimal solution - A more optimal solution is using A*(tree) Search |
|
|
A* Search |
- Search algorithm that is widely used in path findingand graph traversal – the process of plotting anefficiently traversable path between nodes - Noted for its performance and accuracy, it enjoyswidespread use |
|
|
Procedure for A* Search |
- Avoid expanding paths that are already expensive - Evaluation function: f(n) = g(n) + h(n) g(n) = cost so far to reach n h(n) = estimated cost to goal from n f(n) = estimated total cost of path through n to goal |
|
|
Optimality requirement for A* Search |
A* needs an admissible heuristic, - i.e., 0 <= h(n) <= h*(n) where h*(n)=true cost from n - (Thus h(G) = 0 for any goal G) |
|
|
Efficiency of A* Search |
- A* is considered optimally efficient - no algorithm withthe same heuristic is guaranteed to expand fewer nodes - The time complexity of A* depends on the heuristic - Worst case: the number of nodes expanded isexponential in the length of the solution - But it is polynomial when the search space is atree, there is a single goal state |
