CSE 3321 Heuristics + Greedy Algorithms (Zybooks Lecture)

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/7

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

8 Terms

1
New cards

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

False.

2
New cards

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

True

3
New cards

Heuristic Algorithm

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

4
New cards

Which is not commonly sacrificed by a heuristic algorithm?

  • Speed

  • Optimality

  • Accuracy

Speed

5
New cards

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.

6
New cards

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.

7
New cards

Examples of Greedy Algorithms

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

  • A* search

  • Prim’s

  • Kruskals

8
New cards

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

False