Module #7

Question 1

is any algorithm that follows the
problem-solving heuristic of making the locally optimal choice at each stage with the intent of finding a global
optimum.

Answer 1

greedy algorithm

Question 2

greedy algorithms have how many components

Answer 2

5 components

Question 3

from which a solution is created

Answer 3

Candidate Set

Question 4

which chooses the best
candidate to be added to the solution

Answer 4

Selection Function

Question 5

that is used to determine if a
candidate can be used to contribute to a solution

Answer 5

Feasibility Function

Question 6

which assigns a value to a
solution, or a partial solution, and

Answer 6

Objective Function

Question 7

which will indicate when we have
discovered a complete solution

Answer 7

Solution Function

Question 8

is a greedy algorithm that finds a minimum spanning tree for a weighted
undirected graph.

Answer 8

Prim’s Algorithm

Question 9

also known as Jarnik’s Algorithm

Answer 9

Prim’s Algorithm

Question 10

The algorithm operates by building this tree one vertex at a time, from
an arbitrary starting vertex, at each step adding the cheapest possible
connection from the tree to another vertex.

Answer 10

Prim’s Algorithm

Question 11

The prim’s algorithm was developed in ____ by Czech mathematician Vojtěch Jarník

Answer 11

1930

Question 12

Prim’s Algorithm was later rediscovered and republished by computer scientists Robert C. Prim in

Answer 12

1957

Question 13

Prim’s Algorithm was later rediscovered and republished by computer scientists Robert C. Prim and Edsger W. Dijkstra in

Answer 13

1959

Question 14

Time Complexity of Prim’s Algorithm

Answer 14

O(n^2)

Question 15

Each iteration of for loop takes

Answer 15

O(n) time

Question 16

is a special kind of tree that minimizes the lengths (or “weights”) of the edges of the tree

Answer 16

minimum spanning tree

Question 17

Kruskal’s Algorithm was first described by Kruskal in ______ in the same paper where he rediscovered Jarnik’s algorithm.

Answer 17

1956

Question 18

Kruskal’s Algorithm was also rediscovered by Loberman and Weinberger in what year

Answer 18

1957

Question 19

is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the
forest.

Answer 19

Kruskal’s algorithm

Question 20

It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.

Answer 20

Kruskal’s Algorithm

Question 21

Time Complexity of Kruskal’s Algorithm

Answer 21

O(E log E)

Question 22

for finding the shortest path from
a given node to all other nodes in a graph

Answer 22

Dijkstra’s algorithm

Question 23

Always takes the shortest edge connecting a known node to an unknown
node

Answer 23

Dijkstra’s algorithm

Question 24

is an algorithm for finding the shortest paths between nodes
in a graph, which may represent, for example, road networks.

Answer 24

Dijkstra’s algorithm

Question 25

Dijkstra’s algorithm was conceived by computer scientist Edsger W. Dijkstra in

Answer 25

1956

Question 26

The algorithm exists in many variants. Dijkstra’s original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the “source” node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

Answer 26

Dijkstra’s algorithm

Question 27

Edsger Dijkstra invented Dijkstra’s Algorithm in

Answer 27

1959

Question 28

He kick-started what became known as the Structured Programming movement.

Answer 28

Edsger Dijkstra

Question 29

was a university professor for much of his life, which spanned the era when basic methods of computer programming were still being worked out.

Answer 29

Edsger Dijkstra

Question 30

Dijkstra pointed out that this
resulted in programs that were difficult to follow, and therefore very difficult
for other programmers to change the journal of the Association for Computing Machinery entitled Go To Statement Considered Harmful in a letter in

Answer 30

1968

Question 31

He invented the Semaphore, the mechanism that allows concurrent programs to share a single resource.

Answer 31

Edsger Dijkstra

Question 32

was born in the Netherlands, where he worked as a university researcher and professor until 1984

Answer 32

Edsger Dijkstra

Question 33

Edsger Dijkstra took up a professorship at the

Answer 33

University of Texas at Austin

Question 34

is an algorithm we can use to find shortest
distances or minimum costs depending on what is represented in a graph.

Answer 34

Dijkstra’s algorithm

Question 35

Time Complexity of Dijkstra’s algorithm

Answer 35

O(E+V log V)