Students who complete this unit will demonstrate that they can:

• Describe and explain the search paradigm for problem solving.
• Formulate an efficient problem space for a problem expressed in natural language in terms of initial and goal states, and operators.
• Describe the role of heuristics and describe the trade-offs among completeness, optimality, time complexity, and space complexity.
• Compare and contrast the standard AI search algorithms.
• Evaluate whether a heuristic for a given problem is admissible/can guarantee optimal solution.
• Select and implement an appropriate uninformed search algorithm for a problem, and characterize its time and space complexities.
• Select and implement an appropriate informed search algorithm for a problem by designing the necessary heuristic evaluation function.
• Design and implement A*/beam search to solve a problem.