Module 2.3 Algorithms

14 cards·by gurundus

What are the two types of search algorithm?

Linear Search and Binary Search

What are the three types of sorting algorithms?

Bubble sort, Insertion Sort and Quick Sort.

What are the types of path-finding algorithms?

Dijkstra's algorithm and Astar

What is the first step of dijkstra's Algorithm?

Each node is given two values

What is the second step of dijkstra's algorithm?

The node with the shortest temporary path length that doesn't yet have a final path length is selected next.

What is the third step of Dijkstra's algorithm?

If the target node has a final path length, go to the next step, otherwise we return to step 2.

What is the forth step of dijkstra's algorithm?

Trace back through the graph from the target node.

How does A* differ from dijkstra's algorithm?

each node has has three values the third being heuristic cost

How is selecting a node to expand determined in A* Algorithm?

for each node without a final path cost, a total value is calculated which is the sum of thetemporary path and heuristic cost.

What value can an arc have associated with them?

Which are referred to as the cost of the arc

What is a graph used for?

it is a general model for many real life situations, that can be abstracted into a graph

What is the first stage of expanding a node?

Its final path length is set to what is stored in its temporary path length

What is the second stage of expanding a node?

All nodes connected to it that don't already have a final path length are inspected and a value is calculated

how is the temporary path length of near by nodes calculated during expansion?

the sum of the path length to the node we're expanding and the arc between the two nodes.