Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algorithms > Module 7 > Flashcards

Module 7 Flashcards

1
Q

It 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.

A

Greedy Algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

In many problems, it does not usually produce an optimal solution.

A

Greedy Strategy/Algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

It may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

A

Greedy Heuristic/Algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the heuristic of the travelling salesman problem?

A

“At each step of the journey, visit the nearest unvisited city.”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

This heuristic does not intend to find a best solution, but it terminates in a reasonable number of steps.

A

Greedy Algorithm/Heuristic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

In mathematical optimization, these optimally solve combinatorial problems having the properties of matroids, and give constant-factor approximations to optimization problems with submodular structure.

A

Greedy Algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the Five Components of Greedy Algorithms?

A

(Ca - Se - F - O - S)
- Candidate Set
- Selection Function
- Feasibility Function
- Objective Function
- Solution Function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

This component creates a solution.

A

Candidate Set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

This component chooses the best candidate to be added to the solution.

A

Selection Function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

This component determines if a candidate can be used to contribute to a solution.

A

Feasibility Function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

This component assigns a value to a solution or a partial solution.

A

Objective Function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

This component indicates when we have discovered a complete solution.

A

Solution function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What are the advantages of Greedy Algorithm?

A
  • Finding a solution is quite easy.
  • Analyzing the run time is generally much easier than other techniques.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are the disadvantages of Greedy Algorithm?

A
  • You have to work much harder to understand correctness issues.
  • Even with the correct algorithm, it is hard to prove why it is correct.
  • Proving that a greedy algorithm is correct is more of an art than a science.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

In computer science, this algorithm (also known as Jarnik’s algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.

A

Prim’s Algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

This algorithm finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

A

Prim’s Algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A

Prim’s Algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

When was Jarnik’s algorithm developed?

A

1930 by Czech Mathematician Vojtech Jarnik (Jarnik30)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

When was Jarnik’s algorithm rediscovered by Robert C. Prim?

A

1957 (Prim57)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Prim’s Algorithm is also called?

A
  • Jarnik’s Algorithm
  • Prim-Jarnik Algorithm
  • Prim-Dijkstra Algorithm
  • DJP Algorithm
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

True or False
The most basic form of Prim’s algorithm only finds minimum spanning trees in connected graphs.

A

True

22
Q

True or False
Prim’s algorithm can be used to find the minimum spanning forest for each connected component of a graph.

A

True

23
Q

Minimum spanning trees are used for what?

A

Network Designs

24
Q

What are the disadvantages of Prim’s algorithms?

A
  • List of edges has to be searched from beginning as new edge gets added.
  • If there are more than one edges having the same weight, then all possible spanning trees are to be found for the final minimal tree.
25
Q

What is the time required by Prim’s algorithm where “n” is number of vertices in graph “G”?

A

O(n^2)

26
Q

How long does each loop iteration of Prim’s algorithm take?

A

O(n)

27
Q

In Prim’s algorithm, if we store nodes not yet included in the tree as a red-black tree, then how long does the algorithm take?

A

O(log n)

28
Q

This tree is a kind of tree that minimizes the lengths or weights of the edges of the tree.

A

Minimum Spanning Tree

29
Q

A tree that has one path joins how many vertices?

A

Two

30
Q

A spanning tree of a graph is a tree that:

A
  • Contains all original vertices
  • Spans all vertices
  • Is acyclic
31
Q

How many steps does Prim’s algorithm have?

A

7 Steps (Prim7)

32
Q

This algorithm is used for finding a minimum-cost spanning tree.

A

Kruskal’s Algorithm

33
Q

This algorithm always tries the lowest-cost remaining edge.

A

Kruskal’s Algorithm

34
Q

When did Kruskal rediscover Jarnik’s algorithm?

A

1956 (Kuskal56)

35
Q

It is a minimum-spanning-tree-algorithm that scans all edges in increasing weight order; if an edge is safe, keep it.

A

Kruskal’s Algorithm

36
Q

It finds an edge of the least possible weight that connects any two trees in the forest.

A

Kruskal’s Algorithm

37
Q

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

A

Kruskal’s Algorithm

38
Q

This algorithm finds a subset of the edges that forms a tree with every vertex, where the total weight of all edges is minimized.

A

Kruskal’s Algorithm

39
Q

In this algorithm, if the graph is not connected, it finds a minimum spanning forest (a minimum spanning tree for each connected component).

A

Kruskal’s Algorithm

40
Q

How many steps does Kruskal’s algorithm have?

A

3 Steps (3skal)

41
Q

In this algorithm, all of the edges are listed and sorted based on their cost.

A

Kruskal’s Algorithm

42
Q

What is the time complexity of Kruskal’s algorithm?

A

O(E log E) or O(E log V), where E is the number of edges and V is the number of vertices.

43
Q

This algorithm is used for finding the shortest path from a given node to all other nodes in a graph.

A

Dijkstra’s Algorithm

44
Q

This algorithm always takes the shortest path from a known node to an unknown node.

A

Dijkstra’s Algorithm

45
Q

When was Dijkstra’s algorithm created?

A

Created by Edsger W. Dijkstra in 1956.

46
Q

When was Dijkstra’s algorithm published?

A

Published by Edsger W. Dijkstra in 1956.

47
Q

True or False
Dijkstra’s algorithm finds the shortest path between two nodes, but a more common variant finds the shortest paths from the source node to all other nodes.

A

True

48
Q

True or False
Dijkstra’s algorithm works backward from the end, finding the shortest leg each time.

A

True

49
Q

When did Dijkstra point out to ACM that the Go To statement is considered harmful?

A

1968

50
Q

This computer scientist invented the Semaphore, the mechanism that allows concurrent programs to share a single resource.

A

Edsger W. Dijkstra

51
Q

How many steps does Dijkstra’s algorithm have?

A

5 Steps

52
Q

What is the time complexity of Dijkstra’s algorithm?

A

O(|E| + |V| log |V|)

Algorithms (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions