Chapter 8

Question 1

an algorithm that finds a solution to problems in the shortest time possible

Answer 1

greedy algorithm

Question 2

a computer scientist and mathematician who wanted to calculate a minimum spanning tree, introduced the term “Greedy algorithm”

Answer 2

Edsger Dijkstra

Question 3

is without any cycles and with the minimum possible total edge weight. This tree is derived from a connected undirected graph with weights.

Answer 3

Minimum spanning tree

Question 4

is a search algorithm that finds the shortest path between a vertex and other vertices in a weighted graph.

Answer 4

Dijkstra’s shortest path

Question 5

involves finding the shortest route that visits different places only once and returns to the starting point

Answer 5

Travelling salesman problem

Question 6

assigns shorter code to frequently occurring symbols and longer code to less occurring symbols. It is used to encode data efficiently

Answer 6

Huffman coding

Question 7

You can find the shortest path between nodes in a graph. Particularly, you canfind the shortest path from a node (called the “source node”) to all other nodes in the graph, producing a shortest-path tree

Answer 7

Dijkstra’s Algorithm