CSE 3321 Heuristics + Greedy Algorithms (Zybooks Lecture)

A heuristic is a way of producing an optimal solution to a problem

False.

A heuristic technique used for numerical computation may sacrifice accuracy to gain speed

True

Heuristic Algorithm

An algorithm that quickly determines a near optimal or approximate solution.

Which is not commonly sacrificed by a heuristic algorithm?

• Speed

• Optimality

• Accuracy

Speed

Self-adjusting heuristic

An algorithm that modifies a data structure based on how that data structure is used.

Ex: many self-adjusting data structures, such as red-black trees and AVL trees, use a self-adjusting heuristic to keep the tree balanced.

Greedy Algorithm Definition

An algorithm that, when presented with a list of options, chooses the option that is optimal at that point in time. The choice of option does not consider additional subsequent options, and may or may not lead to an optimal solution.

Examples of Greedy Algorithms

• Dijkstra’s (poster child tho, creates optimal solution)

• A* search

• Prim’s

• Kruskals

The greedy algorithm always finds an optimal solution (T/F)

False