greedy algorithm

Question 1

Greedy algorithm

Answer 1

1. It is used to solve optimization problems optimization problem is that demand either maximum or minimum results
2. Greedy method is simplest and straightforward approach
3. The main function of this approach is taken on the basis of currently available information whatever the information is present the decision is made without worrying about effect of current decision in the future
4. This technique is basically used to determine the feasible solution that may be optimal or not the feasible solution is a subset that satisfies the given criteria

Question 2

Characteristics of greedy method

Answer 2

1. This algorithm creates two sets where one set contains all schmuzen items and the other set contains all the rejected items
   2.

Question 3

Components of greedy algorithm

Answer 3

1. canditate set: Solution that is created from the set
2. Selection function: this function is used to choose the candidate or subset which can be added in the solution
3. Feasibility function: a function that is used to determine whether the candidate or subset can be used to contribute to the solution or not
4. Objective function : A function is used to assign the value to the solution or the partial solution
5. Solution function: this function is used to intimate Whether the complete function has been reached or not

Question 4

Applications of greedy method

Answer 4

1. Finding the shortest path
2. Finding the minimum spanning tree using trim’s algorithm or Krushkal’s algorithm
3. Job sequencing with the deadline
4. fractional knapsack problem

Question 5

Disadvantages of greedy Algorithm

Answer 5

1. Greedy algorithm makes decision based on the information available at each phase without considering the future problem so this might be possible that greedy solution does not give best solution for every problem
2. It follows local optimum choice at each stage with intend Or finding global optimum

Question 6

fractional knapsack

Answer 6

1. in fractional sap the items are broken in order to maximise the profit
2. Ingredients approach we calculate the ratio of profit/weight And accordingly we select
3. the item with the highest ratio we selected first

Question 7

Three approaches to solve Fractional knapsack problem

Answer 7

1. Select item based on max profit
2. Select item based on min weight
3. Calculate the ratio of profit/weight
   - Would be best one Among all the approaches
   - Hereafter calculating ratio each item is added into knapsack in Descending order of their wild value

Question 8

spanning tree

Answer 8

1. A tree is represented G(V, E) Where B is vertices and er edges
2. And the spaling tree of the graph is represented as G(V,E)
3. Here in GRAPH and spanning tree vertices are equal but Edges will be 1 less than vertices
   (E= |V|-1)

Question 9

Working

Answer 9

1. First we need to draw all the possible spanning trees for a graph
2. Then calculate the cost
3. Choose the spanning tree which costs less— It is called as minimum spanning tree

Question 10

Conditions Existing in minimum spanning tree

Answer 10

1. Number of vertices will be same V=V
2. Member of edges in minimum spanning tree will be one less than number of vertices in spanning tree——– (E= |V|-1)
3. Spanning tree should not contain any cycle
4. tree should not be disconnected

Question 11

Krushkal’s algorithm for mst

Answer 11

1. It is an algorithm to construct minimum spanning tree for connected weighted graphs
2. Time complexity is (E log E) or (E log V)
3. First arrange edges of a graph in order of increasing weight in a table
4. It should contain v=v and E=V-E
5. It should not form any loop or cycle
6. Now create a minimum spanning tree With the edges According to the ascending order minimum to the maximum without creating a loop or a cycle
7. Finally the MST created by Kruskal’s algorithm should contain equal number of vertices and one less number of edges

Question 12

prim’s M S T

Answer 12

1. Another method of mst
2. Here also Vertices should be equal and edges should be one less than the number of vertices
3. Here we need Create two sets one that contains the vertices which are included already in mst and the ones which Did not include
4. Then we need to choose the starting point or node
5. From the starting node we need to cheque all the Connected or linked notes and Select the minimum cost one
6. Now we need to add the vertices which are selected into one set and which are not selected into the other set because it is very important to also remember the notes which are not selected because in the further steps we need to compare all the nodes which has minimum cost
7. From the next node we need to Find all the linked notes and compare between the older possible notes and the newer possible notes and select the minimum cost one
8. Make sure that you’re not creating a loop or a cycle
9. And after traversing all the vertices you create another graph which is called as panning tree
10. It contains equal number of vertices and one less edge compared to vertex

Question 13

Difference between Kruskal’s algorithm and prim’s Algorithm

Answer 13

in Kruskal’s algorithm while creating mst we get Unlinked edges But finally connects without Making loop whereas in Primm algorithm by creating only mst will be linked

Question 14

dijkstra algo
Single source shortest path

Answer 14

1. Used in Google Maps dna mapping social network these all are represented in graphs
2. Here we need to find shortest path from a single source to multiple paths
3. time Complexity is o(v^2)
4. This algorithm begins at a node which is the source node and examines the graph to find the shortest path between That node and all the other nodes in the graph
5. This algorithm keeps the record of all the visited notes and it updates if it finds shorter path
6. Once the algorithm has retrieved the shortest path the node is marked as visited and included in the path
7. The procedure continues until all the notes in the graph have been included in the path
8. In this manner we have a path connecting the source node to all other notes following the shortest path possible to reach each
9. Each vertex in algorithm have two properties
   - Visited property
   - Path property
   - Works only on weighted graphs And with directed and undirected graphs

Question 15

Visited and path property

Answer 15

1. Visited property signifies whether the node is visited or not this property is used to avoid revisiting of the node
2. The path property stores the value of current minimum path To the node. The property is revised when any neighbour of the node is visited This property is significant because it stores the final answer for each node

Question 16

Working of dijkstra algorithm

Answer 16

1. First all the notes path is set as Infinity
2. From the source each diect nodes is Visited one by one and the part minimum is noted by path property
3. Then again the notes are revisited to minimise the path via other nodes And if minimum path is found it is replaced
4. After doing this every tie in the every single row minimum one is selected
5. Finally a minimum path(graph) is created

Question 17

dijkstra –algo time complexity ka

Answer 17

dijkstra(garph, source)
Create vertex set Q
for each vertex v in graph
dist[v]=infinity(sym)
add v to Q
dist[source]=0
while Q is not empty
u=extract-min[q]
for each neighbour v of u
relax(u,v)

Question 18

Job sequencing with deadlines

Answer 18

1. Clear will be given profits with the deadline
2. We need to select or choose the jobs which Give more profit in the given deadline
3. Important to remember that Jobs should be done by
   -uniprocessor (by single person)
   -No preemption (whole job should be done by single person)
   -Every job is calculated by one unit it may be time Or whatever
   - Here we need to first create a gantt chart with the highest amount of deadline(Like if the highest deadline is too then the Gantt chart should contain two columns)
   - Now we need to choose the jobs according to the profit gets and the deadlines
   - The final result should be maximum